存储桶实例的散列键

Question

当涉及到映射hash key --> bucket instance时，什么算法会产生最佳分布？换句话说，假设我有散列函数（可能是SHA-1），并且我有n存储桶;我使用什么算法将密钥映射到存储桶？例如。低位，高位，别的东西？

Answer 1

通常，你只需要mod你的散列值与桶的数量。在不太可能的情况下，存储桶的数量是2的幂，您可以使用按位进行转换。

维基百科上hash function的摘录：

一个常见的解决方案是计算一个固定的散列函数具有非常 大范围（比如，0〜2 - 1），除以结果n，并使用 分部的余数。如果n本身是2的幂，则可以通过位掩码和位移进行 。使用此方法时，必须选择散列函数 ，以便结果在0和n-1之间具有相当一致的 分布，对于可能发生在 应用程序中的任何n。根据功能的不同，其余部分可能只是对于某些n是统一的，例如 。奇数或素数。

Answer 2

SHA-1和其他cryptographic hash functions应该已经给你一个漂亮的均匀分布，倾向于表现得像一个随机函数（以相同的概率生成所有输出）。

所以，只需从函数的输出中选择合适的位数，即可给出您想要的范围内的数字。

您应该研究关于散列函数和散列表的文献以更好地理解空间，以便根据您的要求做出明智的选择。您可以从Wikipedia或算法教科书（如CLR）开始。最终你会想要移动到Knuth。