algorithm - 哈希函数使用乘法的缺点是什么

Question

几乎每本教科书和 CS 类(class)都引用了两种实现哈希函数的基本方法:

1. 除法，我们简单地执行 k mod m 本质上是选择 m 作为素数，不要太接近 2 的幂。
2. 乘法，我们将 k 与一些精心选择的 0 到 1 之间的无理数(Knuth 建议使用基于黄金比例的数字)相乘，取乘积的小数部分并使用所需的数它的最高有效位。

大多数教科书和类(class)都列举了方法 1 的几个缺点，包括它很昂贵，而且一切都取决于 m。然而，我从未见过任何教科书或类(class)提到方法 2 的单一缺点。

这使得方法 2 更可取。另外，方法 2 在现代计算机上可以非常有效地消除浮点运算。所以看起来方法 2 无疑是赢家，没有人应该谈论方法 1。但事实显然不是这样。事实上，我从未见过方法 2 在任何实际实现中得到使用。所以它确实有一些缺点。

问题是它们是什么以及为什么方法 1 尽管有缺点但仍被更频繁地使用？

Answer 1

除法与需要素表大小的哈希表算法结合使用 - 例如，使用双哈希的开放寻址或 QHash ，当您无论如何都需要将键或它的散列除以表大小以获得索引时。

乘法适用于表大小为2的幂的情况，从哈希中获取索引可以实现为按位与运算，因此整个通过key计算表索引，乘法哈希的路径为非常快。您可以通过 searching for magic constant 2654435769 on Github 探索一些实际的实现.

最近有一种使用 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

因为它只是有点慢，但被认为对错误的 key 分发更健壮。这就是为什么您可能会产生错误(或正确？)的印象，认为乘法方法很少被不公平地使用。