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

Question

9

这并不是一个具体问题和具体解决方案，而是针对我无法在Stack Overflow上找到有关如何为哈希表和类似任务选择好哈希函数的好问题的回应。

所以！让我们谈谈哈希函数，以及如何选择一个。一个需要为他们特定任务选择好哈希函数的编程新手应该如何选择？简单快速的Fowler-Noll-Vo什么时候适用？什么时候应该使用MurmurHash3?您有没有任何链接可以比较各种选择的良好资源呢？

- ELLIOTTCABLE

2个回答

1

如果你的哈希键是字符串（或其他变长数据），你可能会对Ramakrishna和Zobel的this paper感兴趣。他们对几种哈希函数进行了基准测试（以获得速度和低冲突），并展示了一类比通常的Bernstein哈希更好的哈希函数。

- phs

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Andreas Bakurov · Accepted Answer

哈希表的哈希函数应具备以下两个特性：

均匀性：尽可能平均地分布H()的所有输出。换句话说，对于32位哈希函数，每个输出的概率应该等于1/2^32（对于n位哈希函数，应该是1/2^n）。使用均匀的哈希函数可以最大程度地减少任何可能输入的冲突机会。
低计算成本：与加密哈希函数相比，哈希表的哈希函数应该快速，因为速度被用来交换预像抗性（例如，从给定哈希值中找到消息很难）和碰撞抗性。

对于哈希表，所有加密函数都是不好的选择，因为计算成本非常高。因为这里的哈希不是用于安全，而是用于快速访问。MurmurHash被认为是适用于大型哈希表或哈希索引的最快和均匀的函数之一。对于小表，简单的哈希函数应该是可以的。一个简单的哈希是我们通过乘法、加法和减法与一些质数混合对象的值。