Memcached 使用分布式一致性哈希来选择将密钥放在哪个服务器上，但它使用哪个哈希算法将字符串密钥映射到应用 Ketama 算法用于服务器选择的最终哈希。该算法在将相似的密钥传播到不同的服务器方面有多好。
问问题
8142 次
1 回答
7
根据hash.c中的源代码，memcached 使用以下算法：
这里使用的散列函数是 Bob Jenkins，1996 年的：
http://burtleburtle.net/bob/hash/doobs.html
“作者 Bob Jenkins，1996 年。bob_jenkins@burtleburtle.net。您可以以任何您希望的方式使用此代码，私人的、教育的或商业的。它是免费的。”
来自鲍勃詹金斯的网站：
我为您提供了一种用于哈希表查找的新哈希函数，它比您现在使用的更快、更彻底。我还给你一种方法来验证它是否更彻底。
此外，他的要求是：
- 键是未对齐的可变长度字节数组。
- 有时键是几个这样的数组。
- 有时需要一组独立的散列函数。
- 平均密钥长度从 8 字节到 200 字节不等。
- 键可能是字符串、数字、位数组或更奇怪的东西。
- 表大小可以是任何值，包括 2 的幂。
- 哈希必须比旧的更快。
- 哈希必须做得很好。
...
那么真正的要求是一个好的散列函数应该为用户实际使用的键均匀地分配散列值。
回到你的另一个问题，他测量了算法均匀分布散列值的能力，所以我认为散列在将相似的密钥传播到不同的服务器方面做得很好。如果您有顾虑，代码是隔离的，因此您应该能够运行自己的测试。
于 2012-05-03T15:29:56.093 回答