A short introduction to the problem: I'm working with a small database where I have a table of strings (web URLs, to be precise) as pairs: hash|string
. Another table references these strings by hash so I'm saving a lot of space and some CPU cycles by using hashes (a compact identifier of a string). I knew collisions were going to be a problem with large data sets, but I didn't expect to start hitting collisions as soon as I had mere 281 000 unique strings for a 64-bit hash.
So, I need a hash-like function that doesn't have to be cryptographic, and it doesn't even need to be evenly distributed. It might be variable length, but I would like to squeeze as much as possible out of 64 bits of entropy first.
Idea #1: use the positional number of a string in the table as its unique ID. That would work, but I don't like how it relies on a single global counter for assigning an incremented number. If nothing else, it's a point of congestion for a distributed system with multiple writers and readers.
Idea #2: compress the strings. But how? Apparently, it would have to be a compression algorithm with a pre-computed dictionary. Even then, how many characters, on average, would it be possible to squish into 64 bits?
Idea #2.5: Compress if compressible to the target number of bits, otherwise hash.
Note that by "hash-like" I mean that the function need not be reversible.