0

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.

Improve this question
  • 1
    What kind of a hash are you using that's already hitting collisions after so few inputs? – Becuzz Oct 12 '18 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. – Violet Giraffe Oct 12 '18 at 17:49
  • en.wikipedia.org/wiki/Birthday_problem. – Robert Harvey Oct 12 '18 at 18:15
  • 1
    The moment the words "collision-free hash-like function" are put into the same sentence, you should know you're solving the wrong problem – whatsisname Oct 12 '18 at 18:57
  • 1
    @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. – Becuzz Oct 12 '18 at 19:54
4

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.

Improve this answer
  • Not bad! Definitely a solution, but still, I would very much like to find another approach that doesn't depend on the global god object (the sequence generator). – Violet Giraffe Oct 12 '18 at 17:07
  • 3
    OK, but I'm not sure why. You are already dependent on any number of global gods in the database anyway. I'll add another tweak to this approach – JimmyJames Oct 12 '18 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.