Sololearn: Learn to Code
New course! Every coder should learn Generative AI!
Try a free lesson
+ 1
Quadratic probing should perform up to a given number of "probes" (checks) = TS (the table size) checks. The hash keys will repeat sooner (most probably), but it doesn't bring much value to reduce the max number of probes done. It's true that once you find the same position twice, it will keep on reusing positions, so you can precompute this for a given table size by checking the values in order: inc = (i*i) % table_size, for i = 0 to table_size. We only need the increments (inc), as it doesn't matter if we add the initial hash key value to all of them, the sequence will still repeat. The reason why I don't find it relevant to precompute this max number of probes is: -in practice, you shouldn't reach the case where there are that many collisions -smart implementations of hash tables use *resizing* (e.g.: from 8 -> 16 buckets, or 64 -> 32) when needed You can check this reference for a quadratic probing implementation: https://www.google.com/amp/s/www.geeksforgeeks.org/quadratic-probing-in-hashing/amp/
30th Sep 2020, 1:48 AM
Mihai Iacov
Mihai Iacov - avatar