A collision-free hash-like function for use in hash tables and other data structures?

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.

• What kind of a hash are you using that's already hitting collisions after so few inputs? Oct 12, 2018 at 17:44
• @Becuzz: tried MurmurHash3, FNV-1a and SHA-3 256-bits XOR-folded to 64 bits. FNV-1 was the best, but it fell eventually. I'm in the process of exporting my strings to a file and writing a tool for evaluating different hash functions. It does seem odd to me, too. Oct 12, 2018 at 17:49
• Oct 12, 2018 at 18:15
• The moment the words "collision-free hash-like function" are put into the same sentence, you should know you're solving the wrong problem Oct 12, 2018 at 18:57
• @VioletGiraffe The right problem is finding a hash function that either just creates a 64 bit hash or can be configured as such. What you have going (by XOR folding) is probably causing the likelihood of collision to go way way up (I'd have to see code to be sure, but given your data, it certainly looks that way). Barring the ability to do that, you may want to consider using more than 64 bits of space for a hash. Why so short? Buying some storage space is probably far cheaper than paying for programmer time to figure out a problem like this. Oct 12, 2018 at 19:54

You write "Idea #1: use the positional number of a string in the table as its unique ID." but this is not how sequences work. If you want to avoid contention around the sequences, you use sequence batches. That is each writer grabs, say, a range of 1000 sequences to use. I thought this was built into at least some database/drivers but you can implement it using the basic features of sequences. Just set the increment value to `N` (`N` being whatever your batch size is) and have your writer retrieve the first one. It then can increment the value internally until you've created `N` entries. Then request another. You are guaranteed to have no collisions and it will be faster and use less space than a hash.