# Generate a unique 64 bit numeric database key 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

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.