memcached使用哪种散列算法来散列密钥？

Question

Memcached使用分布式一致性散列来选择放置密钥的服务器,但是使用散列算法将字符串密钥映射到应用Ketama算法进行服务器选择的最终散列.这个算法在向不同服务器传播类似密钥方面有多好.

Answer 1

根据hash.c中的源代码,memcached使用以下算法:

这里使用的哈希函数是Bob Jenkins,1996:

http://burtleburtle.net/bob/hash/doobs.html

"Bob Jenkins,1996.bob_jenkins@burtleburtle.net.您可以按照您希望的方式使用此代码,私人,教育或商业.它是免费的."

来自Bob Jenkins的网站:

我为哈希表查找提供了一个新的哈希函数,它比你现在使用的更快更彻底.我还给你一个验证它更彻底的方法.

此外,他的要求是:

• 键是未对齐的可变长度字节数组.
• 有时键是几个这样的数组.
• 有时需要一组独立的哈希函数.
• 平均密钥长度范围为8个字节到200个字节.
• 键可能是字符串,数字,位数组或更奇怪的东西.
• 表大小可以是任何值,包括2的幂.
• 哈希必须比旧哈希更快.
• 哈希必须做得很好.

...

那么真正的要求是良好的散列函数应该为用户实际使用的密钥统一分配散列值.

为了回到你的另一个问题,他测量了算法统一分配哈希值的能力,所以我认为哈希在将相似的密钥传播到不同的服务器方面做得很好.如果您有疑虑,代码将被隔离,因此您应该能够运行自己的测试.