What’s a reliable way to hash up to 10,000 strings with a very low collision risk?
Asked by
MellowPine42
I need to hash around 10,000 keywords and would prefer to avoid collisions entirely, or at least make their probability extremely small. I wrote a quick Python-related implementation and tested it with a handful of short inputs such as "a", "aa", "aaa", "b", "bb", "bbb", and "ab". Those produced different results, but I realize that is not much testing. Is there a more efficient or reliable approach than combining operations such as XOR or multiplication? I would also appreciate advice on how to properly test the implementation.
Answers
For only 10,000 values, the simplest and safest option may be a lookup table rather than a custom hash. If you need compact numeric IDs, use a well-tested standard hash implementation with a sufficiently large output and still handle the possibility of collisions. A hash function can reduce the risk dramatically, but it cannot guarantee unique results unless you compare and resolve duplicates.
Reply to this answer
Testing seven small strings does not tell you much about a several-hundred-line implementation. Use a standard, well-distributed hash function unless you have a very specific reason not to. Then test it against a large word list or a few hundred thousand generated strings, checking that outputs are distinct for your actual input set. Also verify behavior for empty strings, long strings, similar prefixes, non-ASCII text, and adversarial inputs. If uniqueness is a hard requirement, maintain a map from hash to the original string and resolve any collision rather than assuming one cannot happen.
MellowPine42: I’ll expand the tests substantially and include edge cases instead of judging the algorithm from a few short examples.
Reply to this answer
Add your answer
Answers are reviewed before publication.
MellowPine42: That makes sense. I’ll look into using a lookup table or an established implementation instead of relying on my quick custom version.