1
$\begingroup$

I'm taking a data-structure class, and the lecturer made the following assertion:

the number of attempts needed to insert n keys in a hash table with linear probing is independent of their order.

No proof was given, so I tried to get one myself. However, I'm stuck.

My approach at the moment: I try to show that if I swap two adjacent keys the number of attempts doesn't change. I get the idea behind it, and I think it's going in the right direction, but I can't manage to make it into a rigorous proof.

Aside, does this fact also hold for other probing techniques such as quadratic or double hashing?

$\endgroup$
1
$\begingroup$

You can get from any order to any other order by making a series of swaps (see e.g., https://en.wikipedia.org/wiki/Cyclic_permutation#Transpositions). So, if you can prove that making a single swap never changes the number of attempts, then it follows that the number of attempts does not depend on the order.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.