0
$\begingroup$

A hash function indexes all items in hash tables and searches for near items via hash table lookup. The hash

table is a data structure that is composed of buckets, each of which is indexed by a hash code.

The hash table is defined the function family $G = \{g:S \rightarrow U^k\}$ such that $g(p) = (h_1(p),\ldots,h_k(p))$ , where $h_i ∈ H$ to obtain a $k$ bit hash code. The query point $q$ is hashed into all the hash table $\{g_1(p),\ldots,g_l(p)\}$. The candidate set, $\{p_1,p_2,\ldots,p_m\}$, is composed of the points in all the hash tables which are hashed into the same bucket with the query point $q$. Two hash codes for two different messages can collide if they have the same hash code. This is often called the Birthday paradox.

The properties of a good hash function is that there should be no hash collision.

How can I calculate the probability of hash collision?

$\endgroup$
2
$\begingroup$

I'll start with the answer: the number of keys falling into a given bucket quite accurately follows a Poisson distribution:

$$P(n) = e^{-\lambda}\frac{\lambda^n}{n!}$$

Here, $\lambda$ is the average number of keys per bucket, which is equal to the number of keys $K$ divided by the number of buckets $B$. The total number of keys and buckets is approximately irrelevant, so long as they are larger than about $10$; only the ratio of those two numbers matters.

An easy way to derive this formula is to start from the formula for the number of heads in $K$ throws of a biased coin:

$$P(n\text{ heads}) = \frac{K!}{n!(K-n)!}h^n(1-h)^{K-n}$$

In this formula, $h$ is the probability that a given throw will come out heads.

The hash collision problem for a single bucket can be viewed as a coin where "heads" means the hash landed in the bucket and "tails" means it landed somewhere else. Therefore, we take $h=\lambda/K$:

$$P(n\text{ heads}) = \frac{K!}{n!(K-n)!}\left(\frac{\lambda}{K}\right)^n\left(1-\frac{\lambda}{K}\right)^{K-n}$$

Now let's suppose $K$ is very large. We make three approximations:

  • $K!/(K-n)!$ is roughly $K^n$.
  • $(1-\lambda/K)^{-n}$ is roughly $1$.
  • $(1-\lambda/K)^K$ is roughly $e^{-\lambda}$. This is a good formula to know; I use it again lower down.

Cancel the two factors of $K^n$ and rearrange a bit and you get the Poisson distribution.

But I think you are asking for the probability of two or more keys landing in any bucket, whereas I have so far given a formula for the number landing in a single bucket. The interesting case is when $\lambda$ is very small, because otherwise we're almost guaranteed to have a collision somewhere in the table. Let's look at the first few values of $P(n)$:

  • $P(0)$ is $e^{-\lambda}$, which is close to (a bit smaller than) $1$.
  • $P(1)$ is $e^{-\lambda}\lambda$, which is close to $\lambda$.
  • $P(2)$ is $e^{-\lambda}(\lambda^2/2)$, which is close to $\lambda^2/2$.
  • $P(3)$ is smaller by a further factor of $\lambda/3$, which is very small, and subsequent terms are even smaller. These cases basically don't happen, so let's ignore them.

$n=0$ and $n=1$ are not collisions, so the probability of a collision in a single bucket is about $P(2)$, which is about $\lambda^2/2$. Therefore, the probability of no collision in any bucket is about $P(\text{good}) = (1-\lambda^2/2)^B$. Here I have also made the approximation that the buckets are independent, which is good for large $B$.

We would prefer a formula involving $K$ and $B$, so let's substitute $\lambda=K/B$. This gives $P(\text{good}) = (1-K^2/2B^2)^B = (1-((K^2/2B)/B))^B$. For large $B$, this approaches $e^{-K^2/2B}$.

This gives you the birthday result: the chance of a collision somewhere in the table becomes significant when $K^2$ approaches $2B$.

$\endgroup$
  • $\begingroup$ Thank you for your reply. Can you please tell how the expression would change if the probability that two bit strings of length $L$ are equal is $P(a=b)$ = $1\2^L$ where (for example ) assuming $a = [1,0,1,1]$, $b=[1,1,0,1]$. $a$ is the hash code for a data point $x$ and $b$ is the hash code for another data point $y$. I want to work out step by step what the value would be for these 2 strings to get a clear picture based on your answer but it is hard to follow. I want to check what happens when $x \neq y$ and $x =y$ $\endgroup$ – SKM Mar 31 '17 at 17:30
  • $\begingroup$ It took me a while to understand what the expression mean but without an example, it is very hard to follow. $\endgroup$ – SKM Mar 31 '17 at 17:35
  • $\begingroup$ Sure. In your example you are using 4-bit hashes. There are 16 combinations ($2^L$ as you said). The pattern of bits determines which bucket a key lands in. The keys in your example are $x$ and $y$, and they land in the buckets labelled $[1, 0, 1, 1]$ and $[1, 1, 0, 1]$ respectively. The number of buckets $B$ is 16. The number of keys $K$ is 2. The average number of keys per bucket $\lambda$ is $1/8$. Now let us choose a bucket (it doesn't matter which) and ask how many keys land in it. The answer is random, as it depends on the keys and the hash function. The probabilities can be computed. $\endgroup$ – apt1002 Apr 4 '17 at 14:06
  • $\begingroup$ [...] We can get an exact answer using the binomial distribution. For example, the probability that the bucket is empty is $P(0)$ which is $(15/16)^2$, or about 0.879. We can get an approximate answer using the Poisson distribution, which gives $e^{-1/8}$, or about 0.882. For larger $K$ and $B$ the answer would be even closer. $\endgroup$ – apt1002 Apr 4 '17 at 14:12
  • 1
    $\begingroup$ I should explain where the $1/2^L$ formula comes from. For $K=2$ and $B=2^L$ the binomial distribution gives $P(2) = 1/B^2$ for a particular bucket. In this case, we know we cannot have two keys land in more than one bucket, so we can just multiply the probability for a collision in a particular bucket by the number of buckets, and get $1/B$. This doesn't work for $K > 2$. $\endgroup$ – apt1002 Apr 5 '17 at 14:19

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.