Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
For an open-addressing hash table, what is the average time complexity to find an item with a given key:
From my understanding my answer to the first question would be $O(n)$ but I'm not sure about the double probing question.
What are the odds of a collision given a fixed hash table size?
Size of hashtable
When hashing $k$ items into a hash table with $n$ slots, the expected number of collisions is
$n - k + k(1-{\frac{1}{k}})^n$
The main statistic for a hash table is the load factor: $\alpha = \frac{n}{k}$
For a perfect hash the load factor also happens to be the probability that a collision will occur.
Open addressing
Back to the question:
average time complexity to find an item with a given key if the hash table uses linear probing for collision resolution?
The length of probe sequence is proportional to $\frac{\alpha}{(1 - \alpha)}$. As the load factor $\alpha$ approaches 1, probe times goes to infinite.
The following graph shows the benefits and drawbacks of open addressing quite clearly.
Because of locality of reference open addressing is fast up to 70% load factor, after that running time deteriorates quickly.
Note that the graph only shows cache locality issues. Its for this reason that the chaining times do not go up much. In reality the chaining time goes up exponentially as well when the hash table fills up, albeit slower than the linear probing time.
Let $\alpha$ be the load factor
Double hashing has a time complexity of $O(2 * \frac{1}{2}(\dfrac{\alpha}{(1-\alpha)}))$
Linear probing has a time complexity of $O(1 * (\dfrac{\alpha}{(1-\alpha)}))$
So the time complexities are the same, but the constants are different.
Double hashing takes more time, but linear probing goes into pathological running time sooner as the fill factor goes up.
