Averege time complexity of open addressing

Question

I get that it depends from the number of probes, so by how many times the hash code has to be recalculeted, and that in the best case there will only be one computation of the hash code and the complexity will be O(1) and that in the worst case the hash code will be calculated a number of times equal to the size of the hash table and the complexity will be O(n).

But what about the averege case, what would be the asymptotic notation of insert and search operations in open addressing? when solving the collisions with double hashing for example.

Answer 1

Define the load factor of a hash table with open addressing to be $n/m$, where $n$ is the number of elements in the hash table and $m$ is the number of slots. It can be shown that the expected time for doing an insert operation is $\frac{1}{1-\alpha}$, where $\alpha$ is the load factor. If $\alpha$ is bounded to some constant less than $1$, then the expected time for an insert operation is $O(1)$.

The gist of the intuition for this result can be obtained by looking at geometric random variables. If $p$ is the probability of success in a Bernoulli trial, then the expected number of trials for the first success is $1/p$. In a hash table with open addressing, a slot that is being probed can be empty or occupied, where "empty" denotes success and "occupied" denotes failure. The success probability is the probability a slot is empty, which is $p=1-\alpha$, and so we have the desired result that the expected number of slots probed before reaching an empty slot is $\frac{1}{1-\alpha}$.

More specifically, in open addressing, if the probe sequence is completely random (i.e. all $m!$ probe sequences are equally likely) then the probability that the first slot is occupied is the failure probability $\alpha$. The probability that the first two slots being probed are both occupied is at most $\alpha^2$ (I say “at most”, not “exactly”, because if the first slot is occupied, then the probability the second slot is also occupied is smaller than $\alpha$ when the second slot is different from the first slot). You can work out these details, and we essentially get the result above, assuming completely random probe sequences.

Answer 2

Implementations will typically store the hash value inside the table - this will save lots of hash value calculations.

For the hash value of the key being looked up, it depends on the caller how often that value is calculated. Hash values can be cached. I might have an object with a name, address, and age. And name objects and address objects that cache their hash value, and the hash value of my complete object is calculated from the three hash values of name, address and age. In that case the second call to calculate the hash value of the same object will be quite fast. So the cost of calculating hash codes is very highly variable.

Consider this: Your implementation calculates one hashcode, then determines one or more slots where an item with this hashcode could be stored. Then every time a slot is filled you need to check first if the hash code matches, then if the item matches. The check for matching hash codes is trivial if the hashcode is stored in the table. The cost for comparing items can be high. You will have one successful comparison during a lookup or delete of an existing item, independent of load factor. You may have 0 or more unsuccessful comparisons during any operation, depending on the load factor, but with a good hash function this should happen almost never.

So assuming that calculating hash codes and comparing items are expensive, the other cost is likely quite trivial. (Why would they be expensive? For example strings are most likely Unicode strings, and Unicode strings with different representations can be equal, so comparison and calculating the hash code are not trivial. )