Short term Redis plans
antirez.com
Short term Redis plans
1–4 of 4 posts
Re: Short term Redis plans
#2Just curious about the key distribution algorithm -- why use CRC-16(key) % 4096 instead of a fast hash function like djb2, which almost certainly has better key equidistribution?
Re: Short term Redis plans
#3Just curious about the key distribution algorithm -- why use CRC-16(key) % 4096 instead of a fast hash function like djb2, which almost certainly has better key equidistribution? http://www.cse.yorku.ca/~oz/hash.html
Actually CRC-16 has a much better distribution than djb2 and other algorithms for this use case.
CRC-16 is a remarkably good algorithm for certain kind of hashing, and has a few very interesting qualities being the reminder of a polynominal division. For instance if you hash two bytes data you are guaranteed to have different hashes for every different pair of bytes without collisions.
CRC-16 performed very well in tests also with the very common case of keys with the same prefix, like object:0, object:1, and so forth.
So CRC-16 is very good for our use case and has the advantage of being simple and fast.
Re: Short term Redis plans
#4Just curious about the key distribution algorithm -- why use CRC-16(key) % 4096 instead of a fast hash function like djb2, which almost certainly has better key equidistribution? http://www.cse.yorku.ca/~oz/hash.html
Actually CRC-16 has a much better distribution than djb2 and other algorithms for this use case. CRC-16 is a remarkably good algorithm for certain kind of hashing, and has a few very interesting qualities being the reminder of a polynominal division. For instance if you hash two bytes data you are guaranteed to have different hashes for every different pair of bytes without collisions. CRC-16 performed very well in t…
Thank you! Perhaps this warrants a blog post by itself?