I have an input of 128 bits (binary, 0s and 1s) and want to hash this input with 32 bit CRC. But I am not sure if collision rate is moderate or too high ?
Is it 2^128/2^32 = 2^98.
And does that means 1 collision after 2^98 hashes OR something else ?
I am a little bit confused with the math involved.
Is there any other 32 bit hash better (collision resistant) than CRC 32. I can not use any other hash greater than 32 bits as I have to store these values somewhere.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
We don't know anything at all about the distribution of your keys, so we will assume they're random.
You are guaranteed to have one collision after $2^{32}+1$ hashes, by the pigeonhole principle.
You can expect $\frac{1}{2}$ a collision after $2^{16}$ hashes. The reason for this is not entirely obvious, but it follows from the fact that given $m$ keys and $n$ possible hash values, the distribution of "collisions" follows a Poisson distribution with parameter $\lambda = \frac{m}{n}$.
Think of a hash table with $n$ entries, and you try to insert $m$ keys. Then the probability that a given entry has $k$ keys inserted in it is:
$$\mathrm{Poiss}(k;\lambda) = \frac{\lambda^k e^{-\lambda}}{k!}$$
If you do the sum, you will find that the expected number of collisions is $\frac{1}{2}$ when $m = \sqrt{n}$. This is, of course, the famous birthday problem.
This also means, for example, that if $m=n$, you can expect $\frac{n}{e}$ hash values (i.e. about a third of them) to be unused, $\frac{n}{e}$ (again, about a third) to be used once, and $n(1 - \frac{2}{e})$ (about a quarter) to be used twice or more.
As for using CRC as a hash function, it's hard to say without testing it on your specific keys. CRC is designed for message integrity, and is especially good at detecting burst errors in a noisy channel. But it's probably not a terrible choice.
Just as a final note, "CRC32" usually refers to the polynomial used in HLDC, Ethernet, SATA, MPEG, PNG, and most compression algorithms. The other one that is in common use is Castiglioni's "CRC32C", used in iSCSI, ext4, and several other standards. (There are others, such as CRC32Q used in AXIM, but we'll ignore them.)
Both Intel/AMD (SSE4.2 and above) and ARM (NEON) CPUs have built-in instructions to compute CRC32C. So if you're free to pick the polynomial, that would seem like the best choice on performance grounds.
