前篇，我们引入了哈希表，散列函数，以及什么是散列冲突等概念，而本篇我们还需要介绍一个重要的概念就是重散列(Rehashing),它伴随着哈希表的负载系数(Load Factor)一起对哈希表的结构产生实质性的作用
- 表的内容空间扩容
- 对表中的所有元素的索引无序重算(即表中所有元素的位置获得新的散列值)
我们知道负载系数的公式是
其中N是哈希表的尺寸,n是哈希表中已存在元素个数
- α<1即表中有常有可用的空间，允许我们想当前哈希表插入其他元素
- α=1即表中空间已经被填满,此时需要扩容
- α>1即n>N已经溢出，这种情况在具体的代码实现中是要避免的
后面两种情况，就要求我们对现在的哈希表的向操作系统申请更多的内容空间(更多存储桶)，哈希表的这种操作就叫重散列(Rehashing), 下面一个简单的示例来了解重散列的原理以及对哈希表的意义。这里有一个长度为3的哈希表，现在需要插入的键值对是(6,"Mosa"),(7,"Kally"),(8"Berry"),且哈系表的散列函数是 hash(k)=k mod N,当前N=3
这三个键值对插入表后的状态，如下图，当前N=3，n=3,那么α=1，此时，就需要执行重散列的操作,以满足后续插入元素有可用的存储桶可用。
那问题来了，究竟需要扩容至多大的尺寸才适合呢？首先实现哈希表的底层基本数据结构就是顺序表，更贴切地说是数组,按照惯例就是新的内存空间是原来内存空间的2倍，我以前写这两篇都有详细解析了内存分配double方案的由来
回归正题，那正如你所说的，扩容后的尺寸不就是N=2x3=6吗？稍等,那又不正确哦，为什么，如果你对散列函数了解的话，由于散列函数设计中取模运算是会经常用到的，如果你稍微留心的话，我们mod运算中的除数是我们哈希表的尺寸N，因为使用取模运算的散列函数实现中，若N是非素数的话，那么多个不同的键值对出现散列冲突的概率会使用素数高出许多。也就是说新哈希表的尺寸N不可能是2的倍数。
上面所说的,好奇者没必要跟我抬杠，若你要浪费表情去深入证明的,请找相关的数论知识来证明。
因此更准确地说，重散列的最终效果就是为哈希列表扩容提供更多的可用的存储桶，我们扩容后的哈希表尺寸N'可以靠近2N附近的素数。在本例来说,因为2N=2x3=6，那么6附近的素数可以是5和7,或者远点11,13都可以，当然按照我们这里的约定，当然7是完美的选择。扩容后的状态如下图
ss8.png
但这里的事情还没完，重散列的第二个步骤就是将旧表的元素迁移到新表中，迁移过程中就需要对就旧表的每个元素的键传入hash(k)重新散列一遍，此时散列函数中的N是新表的尺寸即N=7，这也是重散列的关键操作,下图已经展示的很清楚。
这里，本篇介绍了重散列的含义以及工作原理，但这里引发一个重要的问题点是，如何找到最接近给定整数的素数(质数)？这个留给读者自己去思考。
题外话
素数有一些如下基本事实
- 0和1不是素数
- 2即是偶素，也是素数,其他大于2且能被2整除的都不是素数
- 如果一个数字各位上的数字总和是3的倍数，一定不是素数
- 5是素数大于5且末尾的数字是0或5的一定不是素数
网上能找到的答案基本上就是用循环去穷举做整除测试!!
要证明数字是否为质数，请先尝试将其除以2，然后查看是否得到整数。 如果是整数则不是素数。 如果没有得到整数，请尝试将其除以质数：3、5、7、11（9被3整除），依此类推，请始终除以质数（请参见下表）。
网友评论