分析目标并选择一个好的哈希函数

Question

这不是具体解决方案的具体问题; 但它反而是对我无法找到关于如何为哈希表和类似任务选择好的哈希函数的任何好的Stack Overflow问题的回应.

所以!让我们来谈谈哈希函数,以及如何选择哈希函数.如果编程菜鸟需要为他们的特定任务选择一个好的哈希函数,那么选择一个呢？简单快速的Fowler-Noll-Vo什么时候适合？他们什么时候应该在MurmurHash3中供应？在比较各种选项时,您是否有良好的资源链接？

Answer 1

哈希表的哈希函数应该具有这两个属性

• 均匀性H()的所有输出应尽可能均匀分布。换句话说，对于 32 位哈希函数，每个输出的概率应等于 1/2^32。（对于 n 位，它应该是 1/2^n）。使用统一散列函数，可以将任何可能的输入发生冲突的机会降至最低。
• 计算成本低与加密哈希函数相比，表的哈希函数预计将是快速的，加密哈希函数以速度换取原像抵抗力（例如，很难从给定的哈希值中找到消息）和碰撞抵抗力。

对于哈希表来说，所有加密函数都是糟糕的选择，因为计算成本巨大。因为这里使用散列不是为了安全而是为了快速访问。MurmurHash 被认为是适用于大型哈希表或哈希索引的最快且统一的函数之一。对于小表，一个简单的哈希函数应该就可以了。简单的哈希是我们混合对象值的地方（通过乘法、加法和减法与一些素数）。