# Calculating probability of exceeding fixed Hash table bucket chain depth

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.

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 , 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$$