哈希表的大小为何最好是素数

深碍√TFBOYSˉ_ 2023-02-16 00:59 23阅读 0赞

# 引言 #

为什么散列函数采用取模运算？又为什么取模运算的被取模数最好是素数？素数是如何在取模运算中很好的规避冲突的？

这些问题可能困扰诸多程序员很久了。我们总是说素数可以更好的避免冲突，但总是对各种长篇大论的分析望而却步。

这篇文章是我在学习散列时针对素数在哈希函数中的如何成功避免大量冲突的原因总结。

尽可能言简意赅地描述为什么素数那么香。

# 一、结论 #

素数能够在取模运算中避免冲突并不是一个数学定律，而且能够避免冲突也不是绝对的。

从规律上来看，如果待存储的数列**间隔**恰好是是**被取模数**的**因子大小**，那么合数要比素数**更容易**呈现**周期性**的**取模重复**。

这仅仅是一个规律，目前数学家也无法对这一规律进行严格定义，毕竟这个规律也并不是绝对的。

# 二、演示 #

我们通过一个简单的例子来印证一下上面的这个规律：

> 从规律上来看，如果待存储的数列**间隔**恰好是是**被取模数**的**因子大小**，那么合数要比素数**更容易**呈现**周期性**的**取模重复**。

这个规律不是绝对的。下面选取了一个合数和一个素数，待存储的数列间隔为 2 或 3，请仔细观察规律：

<table> 
 <tbody> 
  <tr> 
   <td style="border-color:#000000;text-align:center;vertical-align:middle;width:16.8pt;"><span style="color:#000000;">1</span></td> 
   <td style="border-color:#000000;text-align:center;vertical-align:middle;width:106px;"> <p><span style="color:#000000;">数列间隔 3</span></p> <p><span style="color:#000000;">(3是12的因子)</span></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:94px;"><span style="color:#000000;">数列</span></td> 
   <td style="border-color:#000000;vertical-align:middle;width:54pt;"><span style="color:#000000;">34</span></td> 
   <td style="border-color:#000000;vertical-align:middle;width:54pt;"><span style="color:#000000;">37</span></td> 
   <td style="border-color:#000000;vertical-align:middle;width:54pt;"><span style="color:#000000;">40</span></td> 
   <td style="border-color:#000000;vertical-align:middle;width:54pt;"><span style="color:#000000;">43</span></td> 
   <td style="border-color:#000000;vertical-align:middle;width:54pt;"><span style="color:#000000;">46</span></td> 
   <td style="border-color:#000000;vertical-align:middle;width:54pt;"><span style="color:#000000;">49</span></td> 
   <td style="border-color:#000000;vertical-align:middle;width:54pt;"><span style="color:#000000;">52</span></td> 
   <td style="border-color:#000000;vertical-align:middle;width:54pt;"><span style="color:#000000;">55</span></td> 
   <td style="border-color:#000000;vertical-align:middle;width:54pt;"><span style="color:#000000;">58</span></td> 
  </tr> 
  <tr> 
   <td style="border-color:#000000;text-align:center;vertical-align:middle;"><span style="color:#000000;">2</span></td> 
   <td style="border-color:#000000;vertical-align:middle;width:94px;"><span style="color:#000000;">mod 11 =</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">1</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">4</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">7</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">10</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">2</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">5</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">8</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">0</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">3</span></td> 
  </tr> 
  <tr> 
   <td style="border-color:#000000;text-align:center;vertical-align:middle;"><span style="color:#000000;">3</span></td> 
   <td style="border-color:#000000;vertical-align:middle;width:94px;"><span style="color:#000000;">mod 12 =</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">10</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">1</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">4</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">7</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><strong><span style="color:#f33b45;">10</span></strong></td> 
   <td style="border-color:#000000;vertical-align:middle;"><strong><span style="color:#f33b45;">1</span></strong></td> 
   <td style="border-color:#000000;vertical-align:middle;"><strong><span style="color:#f33b45;">4</span></strong></td> 
   <td style="border-color:#000000;vertical-align:middle;"><strong><span style="color:#f33b45;">7</span></strong></td> 
   <td style="border-color:#000000;vertical-align:middle;"><strong><span style="color:#f33b45;">10</span></strong></td> 
  </tr> 
  <tr> 
   <td style="border-color:#000000;text-align:center;vertical-align:middle;"><span style="color:#000000;">4</span></td> 
   <td style="border-color:#000000;vertical-align:middle;width:94px;"><span style="color:#000000;">mod 13 =</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">8</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">11</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">1</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">4</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">7</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">10</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">0</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">3</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">6</span></td> 
  </tr> 
  <tr> 
   <td style="border-color:#000000;text-align:center;vertical-align:middle;"><span style="color:#000000;">5</span></td> 
   <td style="border-color:#000000;vertical-align:middle;width:94px;"><span style="color:#000000;">mod 14 =</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">6</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">9</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">12</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">1</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">4</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">7</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">10</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">13</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">2</span></td> 
  </tr> 
  <tr> 
   <td style="border-color:#000000;text-align:center;vertical-align:middle;"><span style="color:#000000;">6</span></td> 
   <td style="border-color:#000000;text-align:center;vertical-align:middle;width:106px;"> <p><span style="color:#000000;">数列间隔 2</span></p> <p><span style="color:#000000;">(2是12、14的因子)</span></p> </td> 
   <td style="border-color:#000000;vertical-align:middle;width:94px;"><span style="color:#000000;">数列</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">67</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">69</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">71</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">73</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">75</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">77</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">79</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">81</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">83</span></td> 
  </tr> 
  <tr> 
   <td style="border-color:#000000;text-align:center;vertical-align:middle;"><span style="color:#000000;">7</span></td> 
   <td style="border-color:#000000;vertical-align:middle;width:94px;"><span style="color:#000000;">mod 11 =</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">1</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">3</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">5</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">7</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">9</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">0</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">2</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">4</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">6</span></td> 
  </tr> 
  <tr> 
   <td style="border-color:#000000;text-align:center;vertical-align:middle;"><span style="color:#000000;">8</span></td> 
   <td style="border-color:#000000;vertical-align:middle;width:94px;"><span style="color:#000000;">mod 12 =</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">7</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">9</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">11</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">1</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">3</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">5</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><strong><span style="color:#f33b45;">7</span></strong></td> 
   <td style="border-color:#000000;vertical-align:middle;"><strong><span style="color:#f33b45;">9</span></strong></td> 
   <td style="border-color:#000000;vertical-align:middle;"><strong><span style="color:#f33b45;">11</span></strong></td> 
  </tr> 
  <tr> 
   <td style="border-color:#000000;text-align:center;vertical-align:middle;"><span style="color:#000000;">9</span></td> 
   <td style="border-color:#000000;vertical-align:middle;width:94px;"><span style="color:#000000;">mod 13 =</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">2</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">4</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">6</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">8</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">10</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">12</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">1</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">3</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">5</span></td> 
  </tr> 
  <tr> 
   <td style="border-color:#000000;text-align:center;vertical-align:middle;"><span style="color:#000000;">10</span></td> 
   <td style="border-color:#000000;vertical-align:middle;width:94px;"><span style="color:#000000;">mod 14 =</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">11</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">13</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">1</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">3</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">5</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">7</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><span style="color:#000000;">9</span></td> 
   <td style="border-color:#000000;vertical-align:middle;"><strong><span style="color:#f33b45;">11</span></strong></td> 
   <td style="border-color:#000000;vertical-align:middle;"><strong><span style="color:#f33b45;">13</span></strong></td> 
  </tr> 
 </tbody> 
</table>

上图中，数列代表待存储的整型数据，一般在很多散列表（如HashMap）中，都是通过对关键字进行某种变换得到一个整型数字，比如，如果key是字符串，那么可以通过计算字符编码得到一个整数值。

mod 11 代表对11取模，mod 12 代表对 12 取模，依此类推。

我们分别选取了比较普通的两组数列，分别对合数（12、14）和素数（11、13）进行取模运算，可以看到，取模结果重复的已经使用**红色**标记。

当数列间隔为 3 时，由于 3 是 12 的因子，因此，可以看到表中 mod 12 的结果呈现了周期性的模冲突。而其他的 11、13、14，并没有发现明显的冲突问题，而是很好地分散了取模结果。

当数列间隔为 2 时，由于 2 是 12、14 的因子，因此，可以看到表中 mod 12 和 mod 14 的结果都呈现了周期性的模冲突，而 11、13 两个素数并没有发现明显的冲突问题，而是很好地分散了取模结果。

# 总结 #

从实验结果可以清晰的看到，素数要比合数更适合取模运算。在不知道数列间隔的情况下，拥有较少因子的素数可以有效的避免规律性的取模冲突。

大家如果对我的结论感兴趣，可以通过对比试验来尝试寻找数列间隔与因子之间的关系。

发表评论取消回复

表情：

评论列表（有 0 条评论，23人围观）

还没有评论，来说两句吧...

相关阅读

相关哈希表是什么

哈希表(Hash table)是一种数据结构，它通过计算一个哈希函数，将键映射到表中的一个位置，然后使用该位置来存储值。哈希表可以用来快速查找、插入和删除数据。哈希表的查找和插

我会带着你远行/ 2024年03月25日 09:08/ 0 赞/ 122 阅读

相关哈希值哈希表_哈希杰森

哈希值哈希表我最近写了一个[简单的库，可预测地对json进行哈希处理][json] 。该实用程序基于出色的[Jackson Json解析库][Jackson Json

阳光穿透心脏的1/2处/ 2023年02月25日 04:56/ 0 赞/ 54 阅读

相关哈希表的大小为何最好是素数

引言为什么散列函数采用取模运算？又为什么取模运算的被取模数最好是素数？素数是如何在取模运算中很好的规避冲突的？这些问题可能困扰诸多程序员很久了。我们总是说素数可以更

深碍√TFBOYSˉ_/ 2023年02月16日 00:59/ 0 赞/ 24 阅读

相关哈希表

哈希表概念哈希函数设计冲突调节负载因子冲突解决闭散列开散列/哈希桶实现自己的哈希表：

谁践踏了优雅/ 2023年01月13日 04:14/ 0 赞/ 49 阅读

相关哈希表

![Center][] [Center]: /images/20220731/1379dbdc6efb4a42a0b011f0b3aa4455.png

「爱情、让人受尽委屈。」/ 2022年08月14日 04:56/ 0 赞/ 229 阅读

相关哈希表

什么是哈希表哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的[数据结构][Link 1]。也就是说，它通过把关键码

悠悠/ 2022年07月15日 12:14/ 0 赞/ 247 阅读

相关哈希表

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速

系统管理员/ 2022年06月10日 01:26/ 0 赞/ 305 阅读

相关哈希表

我们知道，通过对数组进行直接寻址（Direct Addressing），可以在 O(1) 时间内访问数组中的任意元素。所以，如果存储空间允许，可以提供一个数组，为每个可能的关键

快来打我*/ 2022年06月05日 02:20/ 0 赞/ 417 阅读

相关哈希表

一、简介如果所有的键都是小整数，那么我们可以用一个数组来实现无序的符号表，将键作为数组的索引i而数组中i（键）处储存的就是对应的值。这样就可以快速地访问任意键的值，

旧城等待，/ 2021年12月22日 01:21/ 0 赞/ 456 阅读

相关哈希表

【一】哈希表 > 他通过把关键码值映射到表中的一个位置来访问记录，以加快查找的速度。这个映射函数就是散列函数。 ![watermark_type_ZmFuZ3poZW5na

傷城~/ 2021年08月11日 17:13/ 0 赞/ 611 阅读