3
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – mikeazo
    Jun 10, 2014 at 12:56
  • 1
    $\begingroup$ 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. $\endgroup$
    – AHalvar
    Jun 10, 2014 at 13:51
  • $\begingroup$ @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. $\endgroup$
    – espeed
    Jun 10, 2014 at 14:12
  • $\begingroup$ @mikeazo Confusion and Diffusion / Avalanche effect. $\endgroup$
    – espeed
    Jun 10, 2014 at 14:12
  • 1
    $\begingroup$ 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. $\endgroup$
    – otus
    Jun 10, 2014 at 14:45

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.