cipriancraciun commented :
(The statements bellow take into account that you use only a single 64bit hash function.)
Granted that by using an AES based hashing algorithm, the chance of a collision given exactly two entries is 2^63 (not 64 due to the “birthday effect”).
However quoting from Birthday problem on Wikipedia article (the probability table section), it would take only 200 million different keys to get a 0.1% chance for a collision (these keys don’t necessarily have to be all stored at the same time).
However by adding a second 64 bits hash function, you’re basically using now a “compound” 128 bits hash, which means that from a practical point of view you can just do the following:
- instead of using AES to generate the hash, use SHA (one of the SHA functions in the family that are hardware accelerated and provides at least 192 bits);
- use the first 64 bits of the hash as you are doing now to establish a “slot”;
- use the remaining 128 bits to store besides the the actual data;
I think will provide a much better collision “margin”, and will increase the current storage requirements by only 16 bytes.