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

Question

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.

Answer 1

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.

If you really want to avoid a sequence generator in the DB, you can have a identity generator that is based on the identity of the writer and have each writer manage it's own sequence. UUID version 1 & 2 use this basic idea. You could give each writer an integer 'name' or use any other approach where they have unique identifiers. Prepend this to the id and you know they will not collide with values created by other writers.