Why exactly does quadratic probing lead to a shorter avg. search time than linear probing?
I fully get that linear probing leads to a higher concentration of used slots in the hash table (i.e. higher “clustering” of used consecutive indices). However, it’s not immediately trivial (to me at least) why that translates to higher search times in expectation than in quadratic probing, since in both linear and quadratic probing the first value of the probing sequence determines the rest of the sequence.
I suppose this has to do more with the probability of collisions between different probing sequences. Perhaps different auxiliary hash values are less likely to lead to collisions early in the probing sequence in quadratic than in linear hashing, but I haven’t seen this result derived or formalized.