hashtable - 分析目标并选择良好的哈希函数

Question

这不是针对特定解决方案的特定问题；但这是对以下事实的回应:我找不到有关如何为哈希表和类似任务选择良好的哈希函数的良好堆栈溢出问题。

所以!让我们谈谈散列函数，以及如何选择一种。需要为自己的特定任务选择良好哈希函数的编程新手应该如何选择一个呢？简单快速的Fowler-Noll-Vo什么时候合适？他们什么时候应该在MurmurHash3中销售？在比较各种选项时，您是否有指向良好资源的链接？

Answer 1

哈希表的哈希函数应具有以下两个属性

均匀性 H()的所有输出应尽可能均匀地分布。换句话说，对于32位哈希函数，每个输出的概率应等于1/2 ^ 32。 (对于n位，应为1/2 ^ n)。使用统一的哈希函数，将冲突的可能性降到最低，对于任何可能的输入，冲突的可能性都最小。

较低的计算成本与以哈希方式交换速度(例如，很难从给定哈希值中找到消息)和抗冲突性的加密哈希函数相比，表的哈希函数预计为FAST。

出于哈希表的目的，所有加密功能都是 BAD 选择，因为计算量很大。因为这里的哈希不是用于安全性，而是用于快速访问。 MurmurHash被认为是适用于大型哈希表或哈希索引的最快且统一的函数之一。对于小表，一个简单的哈希函数应该可以。一个简单的哈希是我们混合对象值的地方(通过乘，加，减一些质数)。