0
$\begingroup$

I need a 128-bit hash function which is extremely fast since it will be used for generating unique IDs for billions of objects. It doesn't need to be a cryptographic hash function nor does it have to act as a PRF (though I would imagine any decent one would).

The only requirements are amazing collision resistance and speed (along with 128-bit output).

IDs are generated in two ways. Either by hashing another (128-bit) ID or by hashing 2 IDs (which would be concatenated together). This means the hash function would only have to be fast for 128 and 256-bit inputs.
The IDs for the initial objects which are not derived from other objects are just generated randomly (perhaps by hashing numbers 0 to N, where N is at most in the order of hundreds).

I came across XXH128, but I wonder if anyone knows if there are any potentially better alternatives for my usecase.

$\endgroup$
5
  • $\begingroup$ If you only need to hash 128/256-bit values, and you think these values are already "generated randomly" then hash 128-bit values by doing nothing and hash 256-bit values by throwing away half the data (or xor'ing the two halves). If inputs are truly random then you'll avoid collisions up to $\sim 2^{64}$ inputs which is the best you could hope for from a 128-bit hash. $\endgroup$
    – Mikero
    Feb 23 at 0:10
  • $\begingroup$ @Mikero Yes, but which hash function should I use? Also, I don't think I can XOR the two 128-bit IDs because I would get the same output if IDs switch places. For that scenario, I need to get a different ID (If I had 2 objects with IDs 123 and 456 and another 2 with IDs 456 and 123 - they would have to produce different distinct new objects and XORing them would produce the same ID for both cases). $\endgroup$
    – TypicalHog
    Feb 23 at 0:18
  • $\begingroup$ Thanks for the clarification. I think I understand the problem better. $\endgroup$
    – Mikero
    Feb 23 at 0:25
  • $\begingroup$ SipHash with a nul key? $\endgroup$
    – DannyNiu
    Feb 23 at 0:46
  • 1
    $\begingroup$ Or $\text{Hash}(A, B) = \text{ROL}(A, 1) + B$; that avoids the issue of $\text{Hash}(A, B) = \text{Hash}(B, A)$ (which is only a problem if $(A, B)$ is a probable identifier when $(B, A)$ is an identifier). $\endgroup$
    – poncho
    Feb 23 at 2:44

0

Your Answer

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