使用乘法的哈希函数有什么缺点

小编典典

使用乘法的哈希函数有什么缺点

algorithm

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

除法，我们只需要简单地k mod m选择m作为素数就不太接近2的幂。
乘法方法 是将k与0到1之间的某些非理性选择数（Knuth建议使用基于黄金比率的数）相乘，取乘积的小数部分，并从中使用所需数目的最高有效位。

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

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

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

阅读 644

2020-07-28

共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

因为它速度稍慢，但被认为对不良的密钥分发更可靠。这就是为什么您可能会错误（或正确？）的印象，即很少使用不公平的乘法方法。

2020-07-28