# Generate a unique 64 bit numeric database key from a string without collisions at $2^{32}$ birthday threshold?

What is the best way to generate a unique 64 bit numeric database key from a string?

For example: if the string is a URL, you could generate a 64 bit key using SipHash or by truncating a SHA256 hash to 64 bits, but collisions are likely at $2^{32}$ (~ 4 billion) entries.

However, if instead you truncated the hash to (64 bits - X bits), and concatenated the resulting hash with the first X bits of the input string, you would reduce the chance of collisions since two similar strings are unlikely to produce the same hash code:

key_bits = 64
x_bits = 8
hash_code = sha256(url_string)
key = truncate(hash_code, key_bits - x_bits) + truncate(url_string, x_bits)


Is this correct? Is there a better way?

-
Why do you think that "two similar strings are unlikely to produce the same hash code"? If you look at MD5 collisions that are out there, it is the opposite. Many of the (MD5) colliding strings are very similar. –  mikeazo Jun 10 '14 at 12:56
What do you REALLY want to solve? If by database key you mean data useful as a primary key in a RDBMS, never, ever create primary keys that are somehow related to the data (here URL) since the data may change and you do not want to update the primary key that by then may be used elsewhere as a foreign key. Best regards from a DBA. –  AHalvar Jun 10 '14 at 13:51
@AHalvar Using Hadoop to bulk load a massive dataset into a graph DB built on HBase that requires 64bit keys, the data is immutable so no chance of it changing. Need key generation to be deterministic to avoid reads to find out if key exists. –  espeed Jun 10 '14 at 14:12
@mikeazo Confusion and Diffusion / Avalanche effect. –  espeed Jun 10 '14 at 14:12
Related: Best way to reduce chance of hash collisions: Multiple hashes, or larger hash? – Your truncation setup can be considered as two hash functions (one of which is quite poor on its own), so it is in general worse than a single longer hash. –  otus Jun 10 '14 at 14:45

Unfortunately, without some additional assumptions about the strings (e.g. that the first 8 bytes are unique), there is no way to reduce the chance of collision below the usual chance levels. If you need unique 64-bit ids, the options are:

1. Do a database lookup when generating keys and pick another key if it is already in use (you state that you want to avoid this).

2. Ignore duplicate keys, e.g. set things up so that only one of the two entries is kept. As long as you don't go much above $2^{32}$ entries, the expected number of collisions will be very low, and depending on your task, it may be acceptable to ignore a small fraction of the entries.

-

However, if instead you truncated the hash to (64 bits - X bits), and concatenated the resulting hash with the first X bits of the input string, you'd reduce the chance of collision since two similar strings are unlikely to produce the same hash code:

For a good cryptographic hash a given similar string is just as likely to have a hash collision as a very different string.

If you are limited to 64-bit keys, the best you can do is take a strong hash – or a key-derivation function if the string is guessable and that's an attack – and hope there are no collisions/have a backup solution in case there is.

-