4
$\begingroup$

For an open-addressing hash table, what is the average time complexity to find an item with a given key:

  1. if the hash table uses linear probing for collision resolution?
  2. if the hash table uses double probing for collision resolution?

From my understanding my answer to the first question would be $O(n)$ but I'm not sure about the double probing question.

$\endgroup$
  • $\begingroup$ the question is just asking what is the average time complexity without doing any calculation or anything. from what i saw online the linear probing is O(n), but im not sure how double probing effects the time complexity. is it O(n) also ? $\endgroup$ – imGreg Mar 5 '13 at 0:34
  • 1
    $\begingroup$ AFAIR, there is a nice analysis made by Knuth that should answer this. (that is, "it's in the `BOOK'"). $\endgroup$ – Ran G. Mar 5 '13 at 6:33
  • $\begingroup$ @RanG, I believe CLRS also covers the math (in a somewhat more approachable way). $\endgroup$ – vonbrand Mar 5 '13 at 14:29
4
$\begingroup$

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.

enter image description here

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.

$\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.