除留余数法

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 1.7k 阅读时长 ≈ 2 分钟

除留余数法是哈希表中常用的哈希函数，假设哈希表的大小为\(m\)，则除留余数法的哈希函数的一般形式为：

\[ hash(key) = key \% p \]

其中\(p\)是不大于\(m\)且最接近\(m\)的素数。

参考文献：《数据结构——用面向对象方法与C++语言描述》第2版

现在问题来了：\(p\)的选取为什么非得是素数呢？

哈希函数的构造要点

  1. 哈希函数的定义域要包括所有关键码key
  2. 如果哈希表的大小为\(m\)，则哈希函数的值域必须是\(0\)到\(m-1\)
  3. 哈希函数的取值应当尽量分布均匀以减少冲突
  4. 哈希函数的计算应当足够简单

从需求来看，1和2是对哈希函数定义域和值域的要求，3是要求冲突尽可能低，4是要求计算量低。

  • 很显然1是容易满足的，因为取模函数的定义域是全体整数
  • 为了满足2，\(p\)只需取一个小于等于\(m\)的数即可
  • 4也是容易满足的，因为取模运算足够简单

下面详细讨论3：

3的需求用数学语言可以表述为：设\(key\)是一个整数随机变量，则\(hash(key)\)是一个取值为\(0\)到\(m-1\)的整数随机变量，希望取适当的\(p\)使得\(hash(key)\)的每个取值都为\(\frac{1}{p}\)。很显然\(key\)服从何种概率分布是至关重要的，实际上已知\(key\)分布列情况下求出\(p\)的最优取值还是有办法的。

求解最优的\(p\)

假设\(key\)的分布列为\(P\{key = i\} = p_i\)。只需要用到一点离散概率知识，求出\(hash(key)\)的分布列，为了记号简单我就直接写成\(P\{hash(key) = i\} = q_i(p)\)好了。参数\(p\)的最优性可以定义为使\(hash(key)\)取每个值的概率与\(\frac{1}{p}\)的平方误差最小，即 \[ p = \arg\min \sum_i (q_i(p) - \frac{1}{p})^2\] 然后求解这个优化问题即可。这里\(q_i(p)\)表示\(q_i\)依赖于\(p\)。忽略求解过程。

稍微偏题了一下给出了一种数学建模的解法，上面这个方法说复杂也不复杂，但是求解那个优化问题可能还是没那么简单的。如果先承认\(p\)取素数比取合数好的话，那么用脚趾头想也知道选最接近\(m\)又不超过\(m\)的素数作为\(p\)是非常好的选择，而且也绕开了上面求解优化问题的繁琐。下面回归正题，解释为什么\(p\)要选素数。

哈希函数中\(p\)取素数的原因

如前所述，需求3与\(key\)所服从的分布有密切关系。如果\(key\)服从均匀分布的话，那么取\(p=m\)这个问题就解决了。

对于不服从均匀分布的时候，先看这样一种情况：

例：\(key\)的取值范围\(A=\{0,6,12,18,24,30,36,...\}\)，如果\(m=10\)，直接取\(p=10\)，很容易发现\(hash(key)\in \{0,6,2,8,4\}\)。出现的问题有两个，哈希表的空间浪费了，冲突现象变多了。

网上有很多靠谱的解释，这里感谢由知乎用户Porzy给出的一个比较简洁的解释(原文链接)

因为\(hash(key)=key\%p\)，不妨设\(key = a*p+hash(key)\)，则\(hash(key)=key-a*p\)。

于是有

\[hash(key)=gcd(key,p)*(\frac{key}{gcd(key,p)}-\frac{a*p}{gcd(key,p)})\]

这个等式表明\(hash(key)\)的取值只能是\(gcd(key,p)\)的倍数，对于上面的例子，A中的元素都是6的倍数，6和10的最大公约数为2，因此A中的元素只能被映射成0,2,4,6,8。

将\(p\)取成素数的好处就在于\(gcd(key,p)=1\)，保证了上述这种极端情况下哈希值不会只取到部分值导致冲突现象变多。

其他

其实将\(p\)取成素数并不是最优的选择，仅仅是杜绝了上述的极端现象，在查阅资料的时候也有看到说\(p\)的选取准则并不是只有取素数。