使用乘法方法的哈希函数有哪些缺点？

Question

使用乘法方法的哈希函数有哪些缺点？

algorithmhashhashtable

6

在几乎所有的教科书和计算机课程中，实现哈希函数有两种基本方法：

除留余数法，我们简单地执行 k mod m，选择 m 为质数且不太接近2的幂。
乘法取整法，我们将 k 与某个精心选择的无理数相乘（Knuth 建议使用基于黄金比例的数字），介于0到1之间，取乘积的小数部分，并使用所需数量的最高有效位。

大多数教科书和课程都列出了方法1的几个缺点，包括它很昂贵，而且结果取决于m。然而，我从未见过任何教科书或课程提到方法2的任何缺点。

这使得方法2更受欢迎。此外，方法2可以在现代计算机上变得非常高效，完全消除浮点运算。因此，看起来方法2是毋庸置疑的胜者，没有人应该谈论方法1。但显然并非如此。事实上，我从未见过方法2在任何实际实现中被使用。所以它确实有一些缺点。

问题是它们是什么，为什么方法1尽管有缺点却更常被使用？

- Shital Shah

1个回答

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

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

- leventov · Accepted Answer

除法法是与哈希表算法一起使用的，需要素数表大小。例如，使用双重散列或QHash 的开放地址法在任何情况下都需要将键或其哈希值除以表大小以获取索引。

乘法法适用于表大小为2的幂次方的情况，因此从哈希中获取索引可以实现为按位与运算，因此使用乘法哈希计算键的表索引的整个过程非常快速。您可以通过在Github上搜索魔术常数2654435769来探索一些实际的实现方法。

最近有一种趋势，即使用MurmurHash3雪崩程序替代乘法法:

int hash = key;
hash ^= (hash >> 16);
hash *= 0x85ebca6b;
hash ^= (hash >> 13);
hash *= 0xc2b2ae35;
hash ^= (hash >> 16);
// see this code and the version for 64 bits here:
// https://smhasher.googlecode.com/svn/trunk/MurmurHash3.cpp

因为它稍微慢一些，但被认为在处理糟糕的密钥分布时更加强大。这就是为什么你可能会得到错误（或正确？）的印象，即乘法方法使用得不太频繁。