1
$\begingroup$

I'm attempting to create a Hash table in hardware and I would like to calculate the optimal table size and chain length (for collisions). Unlike in software, I can't easily (and don't want to) grow my table, and I'd like to set a fixed chain length per bucket. So having some probability equations would be excellent--I'm particularly interested in calculating the probability of exceeding the chain length for any bucket.

For example, say I have 4000 random values I'm inserting, my table size is 64K buckets, and each bucket has a chain length of 4 for collisions. What is the probability that I will exceed the chain length of any bucket? The number of values I will be inserting is fixed, but their contents is unknown, so I can't necessarily simulate the exact behavior.

I've done a bunch of google searching, but can't seem to find this even though it seems like an interesting problem. I've found equations to calculate the probability of a single collision, but I need to go further.

$\endgroup$
2
$\begingroup$

Your problem can be cast as a variation of the Birthday Problem where the year has 64K days, there are 4000 people in the room, and we are asking if 5 or more people have the same birthday. According to [1], if $B$ is the number of people in the room when the first $b$-way collision occurs and there are $r$ days in the year, then $$P(B > t r^{1-1/b}) \sim \exp(-t^b / b!)$$ For your example, we have $r = 64,000$, $b = 5$, and solving $t r^{1-1/b} = 4,000$ for $t$, we find $t \approx 0.5716$, so $$P(B > 4,000) \approx 0.999492$$

  1. Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Note II.8.
$\endgroup$
  • $\begingroup$ +1. For anyone else trying to find the reference, the Note II.8 is on page 116. $\endgroup$ – ShreevatsaR Dec 24 '13 at 4:27
  • $\begingroup$ Very, very helpful. Thank you. $\endgroup$ – Greg Taylor Dec 31 '13 at 16:05
  • $\begingroup$ This is useful but not exactly what the question asks for: "What is the probability that I will exceed the chain length of any bucket?" This answers "What is the probability that I will need B number of items to exceed the chain length of any bucket?" $\endgroup$ – sudo Aug 19 '15 at 22:52

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.