Independence of order of insertion hashtable with open addressing

Question

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?

Answer 1

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.