2
$\begingroup$

I want to compute the average number of collisions before sucessfully adding an item into a hash table. Let $m$ be the size of a hash table $H$.

I was thinking that since it is a linear probing and we do not know where the free slots in the hash table are, the probability that first slot is free is $(m-n)/m$ where $n$ denotes the amount of 'bad' slots, i.e. there are $n$ items stored in our hash table. If the second slot is free then $(m-n)/(m-1) > (m-n)/n$ and so on.

So the expected number of collisions is $1/p = 1/ (1-\alpha)$ where $\alpha := n/m$ is our load factor.

But my friends got totally different numbers. Am I going into the right direction?

$\endgroup$
2

1 Answer 1

3
$\begingroup$

1 / (1 - alpha) is about right, if you ignore that for the second slot the chance is (m - 1 - n) / (m - 1) and so on. But when that difference becomes relevant, you should have increased the size of your hash table :-)

What also will happen if you visit consecutive slots on collisions is that once your table is reasonably full then you might have large ranges of occupied slots, which could very much change the situation. Say you have 1,000,000 slots and 999,500 used entries: It's quite likely that the 500,000 slots from 0 to 499,999 are all used.

But all this depends on having a good hash function. Your hash function needs to rarely map different items to the same hash code. And if your hash table visits consecutive slots for collisions, then your hash function mustn't map similar items to consecutive hash codes. Otherwise the average number of slots might be a lot larger.

On the other hand, the cost of visiting a few or a dozen used slots is usually very low to the cost of computing a hash code, if the hash table stores hash codes. It gets really expensive when you have a collision not in slot numbers, but in hash codes. That's when you actually have to compare values. So the most important thing would be a good hash function.

Added: Assume that you have a hash table with 1,000,000 slots, and that 999,500 slots are used. Which is obviously a much higher load factor than a hash table should ever be allowed to have. If the used slots were perfectly random, then inserting a new element would require visiting 2,000 slots on average.

But if you had a range of 500,000 consecutive used slots (which would be quite likely if inserting always visited the next available slot), and you inserted the next item: There would be a 50% chance that the next item gets inserted into that range, visiting from 500,000 to 0 slots, or 250,000 on average. And a 50% chance that the next item gets inserted into the other range which has 0.1% empty slots, or 1,000 on average. So the total average is 125,500 slots visited.

$\endgroup$
1
  • $\begingroup$ how the average number would change if n keys are stored in consecutive locations? $\endgroup$ Commented Oct 22, 2016 at 18:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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