使用乘法的散列函数的缺点是什么

Question

几乎每本教科书和 CS 课程中都引用了两种实现哈希函数的基本方法：

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

大多数教科书和课程都引用了方法 1 的几个缺点，包括它很昂贵并且事情取决于 m。但是，我从未见过任何教科书或课程提到方法 2 的单一缺点。

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

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

Answer 1

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

乘法方法适用于表大小为2的幂时，然后从哈希中获取索引可以实现为按位AND运算，因此通过乘法哈希通过键计算表索引的整个路径非常快。您可以通过在 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

因为它只是慢一点，但被认为对错误的密钥分配更稳健。这就是为什么您可能会产生错误（或正确？）的印象，即乘法方法很少被不公平地使用。