哈希表长度为素数的试证明

已知原始列表中的元素为均匀分布（步长任意的等差数列），对列表中的每个元素进行取余运算后，余数需要均匀分布，才能减少冲突。那么取余运算中的除数为何要选为素数？

试证明如下：

设原始数列为{c + kb}，其中c任意常数，k=0，1，2...，b为等差数列的步长，取值为任意正整数。设除数为m，余数为均匀分布，即 {c + kb} % m 的结果{c + kb} - Lm，在[0, m - 1] 间能等概率取到任何值，其中L为正整数，使Lm<={c + kb}<(L+1)m 。

一、假设m为非素数，那么至少存在一个约数g，使得1

        1) 若g也是b的约数，那么b 与 m 存在公约数 g，令b=vg, m=wg，有

                 {c + kb} % m

                = {c + kb} - Lm

                = {c + kvg} - Lwg

                = c + (kv-Lw) g

                由于公约数g>=2, 因此上式结果在区间[0, m-1] 上 最多能取到 (m // g) + 1个数，而

                (m // g) + 1 <= m/g + 1 <= m/2 + 1 < m （最后一个小于号成立条件为m>2，一般来说

                除数m都是大于2的），故 (m // g) + 1 < m，因此该数列除m后，余数中至少有1个数

                取不到，故不是均匀分布。

        2) 若所有的g都不是b的约数，那么b 与 m 公约数 仅有g=1，

                {c + kb} - Lm，由于kb - Lm线性无关，因此结果可取到[0,m-1]区间上的任意数。

二、m为素数，那么b与m的公约数g=1，极小概率恰好存在公约数m（此时，b=km）,不考虑

                此时情况同上 一、2），结果可以取到 [0, m-1]区间上的任意数

综上所述，需要哈希表长度为素数，使余数呈均匀分布。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！