哈希表扩容简述

哈希表什么时候扩容？

影响哈希表扩容的因素有两个，本身的容量$Capacity$和负载因子$LoadFactor$，当前的哈希表大小大于$Size>Threshold=Capacity\ast LoadFactor$的时候，哈希表就需要扩容。
负载因子好比我们电脑C盘比如100G，实际上在没装满100G的情况下，比如到了80-90G的时候电脑就开始卡顿，这时候就需要扩容。负载因子的值一般为0.75，如果太小，那么哈希表需要不断的扩容，扩容是个耗时的过程；如果太大，那么哈希表放满了也不不会扩容，导致冲突越来越多，解决冲突而起的链表越来越长，效率越来越低，而 0.75 这是一个折中的值，是一个比较理想的值。

哈希表的容量一定是2^n

比如table 是一个数组，那么如何最快的将元素 e 放入数组 ？ 当然是找到元素 e 在 table 中对应的位置 index ，然后 table[index] = e; 就好了；如何找到 e 在 table 中的位置了 ？ 我们知道只能通过数组下标（索引）操作数组，而数组的下标类型又是 int ，如果 e 是 int 类型，那好说，就直接用 e 来做数组下标（若 e > table.length，则可以 e % table.length 来获取下标），可 key - value 中的 key 类型不一定，所以我们需要一种统一的方式将 key 转换成 int ，最好是一个 key 对应一个唯一的 int (目前还不可能, int有范围限制，对转换方法要求也极高)，所以引入了 hash 方法。拿到了 key 对应的 哈希值h 之后，我们最容易想到的对 value 的 put 和 get 操作如下：

# put
table[h % table.length] = value
# get
e = table[h % table.length]

直接取模是我们最容易想到的获取下标的方法，但是最高效的方法吗 ？我们知道计算机中的四则运算最终都会转换成二进制的位运算，如下，只有 & 数是1时，& 运算的结果与被 & 数一致:

1&1=1
0&1=0
1&0=0
0&0=0

对于多位也是一样：

1010&1111=1010;      => 10&15=10;
1011&1111=1011;      => 11&15=11;
01010&10000=00000;   => 10&16=0;
01011&10000=00000;   => 11&16=0;

10 & 16 与 11 & 16 得到的结果一样，也就是冲突（碰撞）了，那么 10 和 11 对应的 value 会在同一个链表中，而 table 的有些位置则永远不会有元素，这就导致 table 的空间未得到充分利用，同时还降低了 put 和 get 的效率（对比数组和链表）；由于是 2 个数进行 & 运算，所以结果由这两个数决定，如果我们把这两个数都做下限制，那得到的结果是不是可控制在我们想要的范围内了 ？ 我们需要利用好 & 运算的特点，当右边的数的低位二进制是连续的 1 ，且左边是一个均匀的数（需要 hash 方法实现，尽量保证 key 的 h 唯一），那么得到的结果就比较完美了。低位二进制连续的 1，我们很容易想到 $2^n-1$; 而关于左边均匀的数，则通过 hash 方法来实现。到此就清楚了为什么大小是$2^n$。

我们一般扩容为原来的两倍，基本步骤如下：

1. 创建一个新的数组，创建一个新的数组，长度newCap是原来的2倍。
2. 遍历oldTab 取出元素的键后，重新进行hash,算出index=i = (newCap - 1) & hash
3. 重新插入元素。

本文地址：https://blog.csdn.net/JohnJim0/article/details/109248472