Two hash keys landing close on a ring

Question

A consistent-hashing scheme places 30 keys uniformly at random on a ring of 1000 positions. Two keys "crowd" each other if they land within 2 positions (a window of \pm 2). What is the probability that at least one pair of keys crowds another?

Accepted Answer

Find the chance a single pair crowds, then apply the birthday-problem approximation. Fix one key's position. The other key crowds it if it lands on that position or within 2 on either side, that is 5 of the 1000 positions (on a ring there are no edge effects): p = \frac{5}{1000} = 0.005. There are \binom{30}{2} = 435 pairs. The chance of no crowding anywhere is approximately P(	ext{no crowding}) \approx e^{-435\,p} = e^{-435 	imes 0.005} = e^{-2.175} \approx 0.114. Therefore P(	ext{at least one crowding pair}) \approx 1 - 0.114 \approx 0.886, about 89\%. The expected number of crowding pai…

Two hash keys landing close on a ring

Your answer

Discussion

Learn the concepts

Related questions