开发者

Mapping from sparse key space to dense key space

开发者 https://www.devze.com 2023-02-04 01:07 出处：网络

I have a list of events which has a UUID identifying the browsers. Given this sparse key space, I\'d like to map to a dense key space.

相关专题：algorithm

I have a list of events which has a UUID identifying the browsers. Given this sparse key space, I'd like to map to a dense key space.

Besides Bloom Filters, what other options do I have?

If I开发者_StackOverflow could have something which mapped to a 64 bit value, it would be perfect, especially if it were algorithmic rather than a lookup table.

If the list of events is constant and not dynamic, you could use a Minimal Perfect Hashing function.

To guarantee zero collisions, use any standard dictionary/symbol table algorithm. That's what they do.

For minimal collisions, there are all sorts of hash functions available. Bob Jenkins' lookup3.c is fairly popular. A question you then have to ask yourself is if you will be subject to maliciously chosen UUIDs. If so, you need a better hash function and a secure random salt. (If you can tolerate the speed, a keyed HMAC is the perfect way to go for this.)