1
$\begingroup$

I have a need to generate a unique hash for millions of Strings of same length. Would prefer a non cryptographic hashing algorithms for performance reasons. The hash can be of length upto 24 bytes, but hash collisions are a strict no.

A dumb implementation I can think of is to use the String.hashCode() method in java as 4 bytes [of the allowed 24 bytes]

  • First 4 bytes = String.hashCode(string)
  • Second 4 bytes = String.hashCode(reverse of string)
  • Third 4 bytes = String.hashCode(first half of string)
  • Fourth 4 bytes = String.hashCode(last half of string)

Thats just 16 bytes of hashes... and as the size of the string is fixed, would this give a unique 16byte hash for every different string? This is similar to using a bloom filter, but I need to ensure there are absolutely NO hash collisions.

Keeping this hash is memory if more efficient than keeping the entire string in memory.

Improve this question
$\endgroup$
5
  • $\begingroup$ Well, how long are your strings? $\endgroup$
    – Maeher
    Jul 31, 2020 at 15:24
  • 3
    $\begingroup$ "I need to ensure there are absolutely NO hash collisions"; unless you know all the strings before hand (and there are no more than $2^{192}$ of them), this is impossible to ensure. Would "there are NO hash collisions with extremely high probability" suffice? Also, would the strings possibly be generated by an adversary (who is trying to trick you into producing a collision)? $\endgroup$
    – poncho
    Jul 31, 2020 at 15:32
  • 1
    $\begingroup$ If no collision and non cryptographic See Perfect hash function $\endgroup$
    – kelalaka
    Jul 31, 2020 at 15:53
  • $\begingroup$ Size of string = 10K characters. I do NOT know all the strings before hand.. I was thinking if I can use more than 2 or 3 hash functions to make the possibility of a hash collision as 0. The strings will NOT be generated by any adversary. $\endgroup$
    – ESri
    Jul 31, 2020 at 17:27
  • 1
    $\begingroup$ If the number of possible strings is large ($\ggg 2^{192}$), then if you select two random strings from the list of possible strings, then those two strings will hash the same with probability at least $2^{-192}$, no matter how you design your hash function. This is not zero. $\endgroup$
    – poncho
    Jul 31, 2020 at 19:15

1 Answer 1

Reset to default
2
$\begingroup$

It's mathematically not possible for a hash function to guarantee an exact probability of zero collision if it shrinks space, just by virtue of the pigeon hole principle.

This means that if, for example, targeted input is on average ~20 bytes, and content can be anything within these 20 bytes, but then you want to map that "space of all possibles" into a fixed-size space of 16-byte, thanks to a 128-bit hash function, it "shrink" the space, and therefore it is mathematically necessary for many entries to share the same hash value.

That being said, it's possible to make the probability of such collision to occur so small that it does not make sense to worry about it. For example, using a 128-bit hash, the probability of collisions between millions of elements is so ridiculously small that one would have more chances to get biten by a shark and striken by a comet and win the lottery ticket all together at the exact same time. If you start to worry about that, then you have to worry about a hidden bit-flip happening inside the cpu due to a rare X-ray interaction from solar flare, which is much more probable. And of course, there are myriads of other problems, starting with software bugs, which are way way more probable than that. So focusing on the infinitesimal risk while being blind to much more common sources of issues is an incorrect stance.

Side note : not sure if it matters in your case, but note that in the case of expanding space, or even identical space, it's possible to guarantee no collision with some hash functions. For example, XXH64 and XXH3_64bits guarantee no collision for 8-bytes->8-bytes hashes. Similarly, XXH3_128bits guarantees no collision for 16->16 hashes. It's even easier when expanding space, for example for mapping 6-bytes input into 64-bit hashes results in no collision. Not all hash functions guarantee this outcome though. Select the ones advertising bijective transformations.

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.