数据结构与算法-哈希表

哈希表是一种非常重要的数据结构，几乎所有的编程语言都有直接或者间接的应用这种数据结构。

认识哈希表

首先我们再来回顾下数组的一些缺点：

1. 数组进行插入操作时，效率比较低。
2. 数组进行查找操作的效率，如果基于索引进行查找效率非常高；但基于内容去查找效率比较低。
3. 数组进行删除操作，效率也不高。

哈希表通常是基于数组进行实现的，但是相对于数组，它也很多的优势：

• 哈希表可以提供非常快速的 插入-删除-查找 操作。
• 无论多少数据，插入和删除值都只需接近常量的时间，即 O(1) 的时间复杂度。实际上，只需要几个机器指令即可完成。
• 哈希表的速度比树还要快，基本可以瞬间查找到想要的元素。

哈希表同样存在不足之处：

• 哈希表中的数据是没有顺序的，所以不能以一种固定的方式（比如从小到大 ）来遍历其中的元素。
• 通常情况下，哈希表中的 key 是不允许重复的，不能放置相同的 key，用于保存不同的元素。

哈希表并不好理解，不像数组、链表和树等可通过图形的形式表示其结构和原理。哈希表的结构就是数组，但它神奇之处在于对下标值的一种变换，这种变换我们可以称之为哈希函数，通过哈希函数可以获取 HashCode。

通过以下案例了解哈希表：

• 案例一：公司想要存储 1000 个人的信息，每一个工号对应一个员工的信息。现在需要将数据存储起来
  • 方案一：使用数组，将所有的员工依次存入一个长度为1000的数组中，通过下标值去获取信息是数组的一大优势，那么将工号当作下表值，可以快速通过工号获取某个员工。但是如果只知道员工的名字去查找员工，就不得不一个个找，比较麻烦。此外，新增和删除员工可能需要大量位移员工，性能不好。
  • 方案二：使用链表，链表对应插入和删除数据有一定的优势。但是获取员工信息，每次都必须从头遍历到尾。
  • 方案三：使用哈希表，把某一员工的姓名转换为它对应的工号，再根据工号查找该员工的完整信息。即使用哈希函数，让某个key的信息和索引值对应起来。
• 案例二：存储联系人和对应的电话号码
  • 方案一：使用数组，如果需要查询某个联系人，就需要从数组中一个个取出数据和查询的联系人比较，效率很低。
  • 方案二：使用链表，和数组一样，效率很低。
  • 方案三：使用哈希表，将名字转成下标值来获取联系人对应的电话。
• 案例三: 高级语言的编译器
  • 事实上哈希表还有另外一个非常重要的应用场景，就是高级语言的编译器。
  • 它通常用哈希表来保留符号表。
  • 符号表记录了程序员声明的所有变量和函数名，以及它们在内存中的地址。
  • 程序需要快速的访问这些名字，所以哈希表是理想的实现方式。

字母转数字

使用一种数据结构存储单词信息，比如有50000个单词。找到单词后每个单词有自己的翻译、读音、应用等等。

将单词转成数组的下标，那么以后我们要查找某个单词的信息，直接按照下标值一步即可访问到想要的元素。

但是怎样将单词即字母转成数组的下标值呢？其实计算机中有很多的编码方案就是用数字代替单词的字符。比如ASCII编码：a是97，b是98，依次类推122是z。

我们创建这样一套编码系统：比如 a 为 1，b 为 2，c 为 3，以此类推 z 为 26，空格为 27（不考虑大写情况）。有了编码系统后，一个单词如何转成数字呢？

方案一：数字相加

• 一个转换单词的简单方案就是把单词每个字符的编码求和。例如单词cats转成数字: 3+1+20+19=43，那么43就作为cats单词的下标存在数组中。
• 但是这种方式会存在这样的问题：很多的单词按照该方式转化为数字后都是 43，比如 was。而在数组中一个下标值只能储存一个数据，所以该方式不合理。

方案二：幂的连乘

• 我们平时使用的大于 10 的数字，就是用幂的连乘来表示它的唯一性的。比如： 6543 = 6 * 10^3 + 5 * 10^2 + 4 * 10 + 3

• 这样单词也可以用该种方式来表示：cats = 3 * 27^3 + 1 * 27^2 + 20 * 27 + 17 = 60337。这样得到的数字可以几乎保证它的唯一性，不会和别的单词重复。

• 如果一个单词是zzzzzzzzzz(一般英文单词不会超过10个字符)。那么得到的数字超过7000000000000。数组可以表示这么大的下标值吗

• 而且就算能创建这么大的数组，事实上有很多是无效的单词。创建这么大的数组是没有意义的。比如不存在asdreerte 这样的单词，造成了数组空间的浪费

两种方案总结：

• 第一种方案（让数字相加求和）产生的数组下标太少。

• 第二种方案（与 27 的幂相乘求和）产生的数组下标又太多。

认识哈希化

现在需要一种压缩方法，把幂的连乘方案系统中得到的巨大整数范围压缩到可接受的数组范围中。可以通过取余操作来实现。虽然取余操作得到的结构也有可能重复，但是可以通过其他方式解决。

如果只有50000个单词，可能会定义一个长度为50000的数组。但是实际情况中，往往需要更大的空间来存储这些单词。因为我们不能保存单词会映射到每一个位置。比如两倍的大小: 100000

现在，就找一种方法，把0到超过7000000000000的范围，压缩为从0到100000。

有一种简单的方法就是使用取余操作符，它的作用是得到一个数被另外一个数整除后的余数。

取余操作的实现，假设把从0~199的数字，比如使用largeNumber代表，压缩为从0到9的数字，比如使用smallRange代表。那么，下标值的结果为index = largeNumber % smallRange。

当一个数被10整除时，余数一定在0~9之间；比如13%10=3，157%10=7。

当然, 这中间还是会有重复，不过重复的数量明显变小了。因为我们的数组是100000，而只有50000个单词。

就好比，你在0~199中间选取5个数字，放在这个长度为10的数组中，也会重复，但是重复的概率非常小。重复的话，也会有处理方法。

通过上面的理解，我们来看下哈希表的概念：

• 哈希化：将大数字转化成数组范围内下标的过程，称之为哈希化。
• 哈希函数：我们通常会将单词转化成大数字，把大数字进行哈希化的代码实现放在一个函数中，该函数就称为哈希函数。
• 哈希表：对最终数据插入的数组进行整个结构的封装，得到的就是哈希表。

地址冲突

0~199的数字选取5个放在长度为10的单元格中，如果我们随机选出来的是33, 82, 11, 45, 90, 那么最终它们的位置会是3-2-1-5-0，没有发生冲突。但是如果还有一个73呢，会和33发生冲突。

在实际中，经过哈希函数哈希化过后得到的下标值可能有重复，这种情况称为冲突，冲突是不可避免的，我们只能解决冲突。

解决冲突常见的两种方案：链地址法（拉链法）和开放地址法。

链地址法

我们将每一个数字都对 10 进行取余操作，则余数的范围 0~9 作为数组的下标值。并且，数组每一个下标值对应的位置存储的不再是一个数字了，而是存储由经过取余操作后得到相同余数的数字组成的数组或链表。

一旦发现重复，将重复的元素插入到链表的首端或者末端即可。当查询时，先根据哈希化后的下标值找到对应的位置，再取出链表，依次查询找寻找的数据。

使用链表还是数组都可以，效率上也差不多。因为根据哈希化的index找出这个数组或者链表时，通常就会使用线性查找，这个时候数组和链表的效率是差不多的。

当然在某些实现中，会将新插入的数据放在数组或者链表的最前面, 因为觉得心插入的数据用于取出的可能性更大。这种情况最好采用链表，因为数组在首位插入数据是需要所有其他项后移的，链表就没有这样的问题。

所以看需求进行选择数组或链表即可。

链地址法解决冲突的办法是每个数组单元中存储的不再是单个数据，而是一条链条，这条链条常使用的数据结构为数组或链表，两种数据结构查找的效率相当（因为链条的元素一般不会太多）。

开放地址法

开放地址法的主要工作方式是寻找空白的单元格来放置冲突的数据项。

根据探测空白单元格位置方式的不同，可分为三种方法：线性探测、二次探测、再哈希法

线性探测

线性探测就是线性的查找空白的单元。

• 当插入 13 时：
  • 经过哈希化（对 10 取余）之后得到的下标值 index=3，但是该位置已经放置了数据 33。而线性探测就是从 index 位置+1 开始向后一个一个来查找合适的位置来放置 13，所谓合适的位置指的是空的位置，如上图中 index=4 的位置就是合适的位置。
• 当查询 13 时：
  • 首先 13 经过哈希化得到 index=3，如果 index=3 的位置存放的数据与需要查询的数据 13 相同，就直接返回；
  • 不相同时，则线性查找，从 index+1 位置开始一个一个位置地查找数据 13。
  • 查询过程有一个约定，就是查询到空位置, 就停止。所以查询过程中不会遍历整个哈希表，只要查询到空位置，就停止，插入 13 时不会跳过空位置去插入其他位置。
• 当删除 13 时：
  • 删除操作和上述两种情况类似，但需要注意的是，删除一个数据项时，不能将该位置下标的内容设置为 null，否则会影响到之后其他的查询操作，因为一遇到为 null 的位置就会停止查找。
  • 通常删除一个位置的数据项时，我们可以将它进行特殊处理（比如设置为-1），这样在查找时遇到-1 就知道要继续查找。

线性探测存在的问题：

• 线性探测存在一个比较严重的问题，就是聚集。
• 如哈希表中还没插入任何元素时，插入 23、24、25、26、27，这就意味着下标值为 3、4、5、6、7 的位置都放置了数据，这种一连串填充单元就称为聚集。
• 聚集会影响哈希表的性能，无论是插入/查询/删除都会影响。
• 比如插入 13 时就会发现，连续的单元 3~7 都不允许插入数据，并且在插入的过程中需要经历多次这种情况。二次探测法可以解决该问题。

二次探测

线性探测存在的问题：就是如果之前的数据时连续插入的，那么新插入的一个数据可能需要探测很长的距离。

二次探测在线性探测的基础上进行了优化：

• 线性探测：我们可以看成是步长为 1 的探测，比如从下表值 x 开始，那么线性探测就是按照下标值：x+1、x+2、x+3 等依次探测；
• 二次探测：对步长进行了优化，比如从下标值 x 开始探测：$x+1^2、$x+2^2$、$x+3^3$$ 。这样一次性探测比较长的距离，避免了数据聚集带来的影响。

二次探测存在的问题：

• 比如我们连续插入的是13-163-63-3-213，那么它们依次累加的时候步长的相同的。
• 也就是这种情况下会造成步长不一的一种聚集。还是会影响效率。

让每个人的步长不一样，可以解决这个问题。

再哈希法

为了消除线性探测和二次探测中无论步长+1，还是步长+平方中存在的问题，还有一种最常用的解决方案：再哈希法。

在开放地址法中寻找空白单元格的最好的解决方式为再哈希化。

• 二次探测的步长是固定的：1，4，9，16 依次类推。
• 现在需要一种方法：产生一种依赖关键字(数据)的探测序列，而不是每个关键字探测步长都一样。
• 这样，不同的关键字即使映射到相同的数组下标，也可以使用不同的探测序列。
• 再哈希法的做法为：把关键字用另一个哈希函数，再做一次哈希化，用这次哈希化的结果作为该关键字的步长。

第二次哈希化需要满足以下两点：

• 和第一个哈希函数不同，不然哈希化后的结果仍是原来位置；
• 不能输出为 0，否则每次探测都是原地踏步的死循环；

工作很好的哈希函数：stepSize = constant - （key % constant），其中 constant 是质数，且小于数组的容量；例如：stepSize = 5 - （key % 5），满足需求，并且结果不可能为 0。

哈希化的效率

哈希表中执行插入和搜索操作可以达到O(1)的时间级，如果没有发生冲突，只需要使用一次哈希函数和数组的引用，就可以插入一个新数据项或找到一个已经存在的数据项。

如果发生冲突，存取时间就依赖后来的探测长度。一个单独的查找或插入时间与探测的长度成正比，这里还要加上哈希函数的常量时间。

平均探测长度以及平均存取时间，取决于填装因子，随着填装因子变大，探测长度也越来越长。

随着填装因子变大，效率下降的情况，在不同开放地址法方案中比链地址法更严重。

装填因子：

• 装填因子表示当前哈希表中已经包含的数据项和整个哈希表长度的比值；
• 装填因子 = 总数据项 / 哈希表长度；
• 开放地址法的装填因子最大为 1，因为只有空白的单元才能放入元素；
• 链地址法的装填因子可以大于 1，因为只要愿意，拉链法可以无限延伸下去；当然，后面的效率会越来越低

开放地址法

线性探测

• 下面的等式显示了线性探测时，探测序列(P)和填装因子(L)的关系
  • 对成功的查找: P = (1+1/(1-L))/2
  • 对不成功的查找: P=(1+1/(1-L)^2)/2

当填装因子是1/2时，成功的搜索需要1.5次比较，不成功的搜索需要2.5次

当填装因子为2/3时，分别需要2.0次和5.0次比较

如果填装因子更大，比较次数会非常大。

应该使填装因子保持在2/3以下，最好在1/2以下，另一方面，填装因子越低，对于给定数量的数据项，就需要越多的空间。

实际情况中，最好的填装因子取决于存储效率和速度之间的平衡，随着填装因子变小，存储效率下降，而速度上升。

二次探测和再哈希

二次探测和再哈希法的性能相当。它们的性能比线性探测略好。

• 对成功的查找： -log2(1 - loadFactor) / loadFactor
• 对于不成功的查找： 1 / (1-loadFactor)

当填装因子是0.5时，成功和不成的查找平均需要2次比较

当填装因子为2/3时，分别需要2.37和3.0次比较

当填装因子为0.8时，分别需要2.9和5.0次

因此对于较高的填装因子，对比线性探测，二次探测和再哈希法还是可以忍受的。

链地址法

链地址法的效率一般来说比开放地址法简单。

假如哈希表包含arraySize个数据项，每个数据项有一个链表，在表中一共包含N个数据项。

那么，平均起来每个链表有多少个数据项呢？非常简单， N / arraySize。其实就是装填因子。

• 成功可能只需要查找链表的一半即可: 1 + loadFactor/2
• 不成功可能需要将整个链表查询完才知道不成功: 1 + loadFactor

可以看到随着装填因子的增加，平均探测长度呈线性增长，较为平缓。在开发中使用链地址法较多，比如 Java 中的 HashMap 中使用的就是链地址法。

哈希函数

好的哈希函数应该具备：快速计算、分布均匀。

快速计算

好的哈希函数应该尽可能让计算的过程变得简单，应该可以快速计算出结果。

提高速度的一个办法就是让哈希函数中尽量少的有乘法和除法。因为它们的性能是比较低的。

在前面，我们计算哈希值的时候使用的方式是

• $cats = 3*27^3+1*27^2+20*27+17= 60337$
• 这种方式是直观的计算结果，这种计算方式会进行8次乘法3次加法呢？当然, 我们可能不止4项，可能有更多项。
• 当有n项时，多项式表达式为$a_{n}x^n + a_{n-1}x^{n-1} + a_{n-2}x^{n-2} + ... + a_1x + a_0$
  • 乘法的次数：$n + (n-1) + (n-2) + ... + 1 = \frac{n(n+1)}{2}$
  • 加法的次数：n
• 多项式可以根据霍纳法则进行优化，上面的多项表达式可以表示为$((…(((a_nx +a_{n-1})x+a_{n－2})x+ a_{n－3})…)x+a_1)x+a_0$
  • 乘法和加法的次数都是n
• 时间复杂度$O(n^2)$降到了$O(n)$

均匀分布

在设计哈希表时，我们已经有办法处理映射到相同下标值的情况：链地址法或者开放地址法。但是，为了提供效率，最好的情况还是让数据在哈希表中均匀分布。因此，我们需要在使用常量的地方，尽量使用质数，比如在哈希表的长度、N 次幂的底数等。

常量为什么要使用质数呢？下面来看哈希表的长度质数的使用：

• 这个在链地址法中事实上重要性不是特别明显，明显的是在开放地址法中的再哈希法中。
• 再哈希法中质数的重要性：
  • 假设表的容量不是质数，例如: 表长为15(下标值0~14)，有一个特定关键字映射到0，步长为5。探测序列会在0 - 5 - 10 - 0 - 5 - 10，依次类推，循环下去。算法只尝试着三个单元，如果这三个单元已经有了数据，那么会一直循环下去，直到程序崩溃。
  • 如果容量是一个质数，比如13。探测序列是0 - 5 - 10 - 2 - 7 - 12 - 4 - 9 - 1 - 6 - 11 - 3 - 8 一直这样下去。不会产生循环(除非填满)，且可以让数据在哈希表中更加均匀的分布。

链地址法中质数没有那么重要，甚至在Java中故意是2的N次幂：

• Java中的哈希表采用的是链地址法
• HashMap的初始长度是16，每次自动扩展，长度必须是2的次幂，这是为了服务于从key映射到index的算法
• HashMap中为了提高效率，采用了位运算的方式：index = HashCode（Key） & （Length - 1）
• 比如计算book的hashcode，结果为十进制的3029737，二进制的101110001110101110 1001
• 假定HashMap长度是默认的16，计算Length-1的结果为十进制的15，二进制的1111
• 把以上两个结果做与运算，101110001110101110 1001 & 1111 = 1001，十进制是9，所以 index=9
• 这样的方式相对于取模来说性能是高的，因为计算机更擅长计算二进制的数据。

N次幂的底数，使用质数:

• 采用质数的原因是为了产生的数据不按照某种规律递增。
• 比如我们这里有一组数据是按照4进行递增的：0 4 8 12 16，将其映射到长度为8的哈希表中，它们的位置是0 - 4 - 0 - 4，依次类推。
• 如果我们哈希表本身不是质数，即还是长度为8，而我们递增的数量可以使用质数，比如5，那么 0 5 10 15 20 对应的的位置分别是 0 - 5 - 2 - 7 - 4，依次类推，也可以尽量让数据均匀的分布。
• 之前使用的是27，这次可以使用一个接近的数，比如31/37/41等等。一个比较常用的数是37。

/**
 * 哈希函数
 * @param {*} str 
 * @param {*} size 
 * @returns hashCode
 */
function hashFun (str, size) {
  const prime = 37 // 质数
  // 初始化hashCode的值
  let hashCode = 0

  // 霍纳法则
  for (let i = 0; i < str.length; i++) {
    hashCode = prime * hashCode + str.charCodeAt(i)
  }

  // 求模运算
  return hashCode % size
}

哈希表

实现的哈希表(基于storage的数组)每个index对应的是一个数组(bucket)。

bucket中存放最好将key和value都放进去，继续使用一个数组。

结构如下图：

常见操作

• put(key, value) 插入或修改操作。

• get(key) 获取哈希表中特定位置的元素。

• remove(key) 删除哈希表中特定位置的元素。

• isEmpty() 如果哈希表中不包含任何元素，返回 trun，如果哈希表长度大于 0 则返回 false。

• size() 返回哈希表包含的元素个数。

• resize(value) 对哈希表进行扩容操作。

实现

首先创建哈希表类 HashTable，并添加必要的属性和上面实现的哈希函数，再进行其他方法的实现。

class HashTable {
  constructor () {
    this.storage = [] // 存放相关元素
    this.count = 0 // 已存储的数据个数
    this.limit = 7 // 数组的长度

  }
}

put

哈希表的插入和修改操作是同一个函数：因为，当使用者传入一个 [key, value] 时，如果原来不存在该 key，那么就是插入操作，如果原来已经存在该 key，那么就是修改操作。

实现思路：

• 首先，根据 key 获取索引值 index，目的为将数据插入到 storage 的对应位置；
• 然后，根据索引值取出 bucket，如果 bucket 不存在，先创建 bucket，随后放置在该索引值的位置；
• 接着，判断新增还是修改原来的值。如果已经有值了，就修改该值；如果没有，就执行后续操作。
• 最后，进行新增数据操作。

// 插入和修改元素
put (key, value) {
  // 获取key对应的index
  const index = this.hash(key, this.limit)

  // 获取数组bucket （也可用链表）
  let bucket = this.storage[index]
  if (bucket === undefined) {
    // 数组不存在则初始化数组
    bucket = []
    this.storage[index] = bucket
  }

  // 修改已存在的元素
  for (const tuple of bucket) {
    if (tuple[0] === key) {
      tuple[1] = value
      return
    }
  }

  // 执行到次数则说明元素不存在 新增元素
  bucket.push([key, value])
  // 已存储个数加1
  this.count++
}

get

实现思路：

• 首先，根据 key 通过哈希函数获取它在 storage 中对应的索引值 index。
• 然后，根据索引值获取对应的 bucket。
• 接着，判断获取到的 bucket 是否为 null，如果为 null，直接返回 null。
• 随后，线性遍历 bucket 中每一个 key 是否等于传入的 key。如果等于，直接返回对应的 value。
• 最后，遍历完 bucket 后，仍然没有找到对应的 key，直接 return null 即可。

// 根据key获取value
get (key) {
  const index = this.hash(key, this.limit)

  const bucket = this.storage[index]

  if (bucket === undefined) {
    return null
  }

  // 循环判断bucket中是否有key对应的value
  for (const tuple of bucket) {
    if (tuple[0] === key) {
      return tuple[1]
    }
  }

  // 未找到，返回null
  return null
}

remove

实现思路：

• 首先，根据 key 通过哈希函数获取它在 storage 中对应的索引值 index。
• 然后，根据索引值获取对应的 bucket。
• 接着，判断获取到的 bucket 是否为 null，如果为 null，直接返回 null。
• 随后，线性查找 bucket，寻找对应的数据，并且删除。
• 最后，依然没有找到，返回 null。

// 根据key移除元素
remove(key) {
  const index = this.hash(key, this.limit)

  const bucket = this.storage[index]
  if (bucket === undefined) {
    return null
  }

  // 遍历bucket，寻找对应的数据并做移除
  for (let i = 0, len = bucket.length; i < len; i++) {
    const tuple = bucket[i]
    if (tuple[0] === key) {
      // 移除元素
      bucket.splice(i, 1)
      this.count--

      return tuple
    }
  }

  // 来到该位置，说明没有对应的数据，返回null
  return null
}

其他

isEmpty () {
  return this.count === 0
}

size () {
  return this.count
}

哈希表的扩容与压缩

为什么需要扩容？

• 前面我们是将所有的数据项放在长度为7的数组中，因为使用的是链地址法，装填因子loadFactor可以大于 1，所以这个哈希表可以无限制的插入新数据。
• 但是, 随着数据量的增多, 每一个index对应的bucket会越来越长，这就会造成效率的降低。所以，在合适的情况对数组进行扩容，比如扩容两倍。

什么情况下需要扩容？

• 比较常见的情况是loadFactor > 0.75的时候进行扩容。比如Java的哈希表就是在装填因子大于0.75的时候，对哈希表进行扩容。

如何进行扩容？

• 简单的扩容可以直接扩大两倍（关于质数，之后讨论）。
• 但是这种情况下，所有的数据项一定要同时进行修改，重新哈希化，来获取到不同的位置
• 比如hashCode=12的数据项，在length=8的时，index=4；在长度为16的时，index=12。
• 这是一个耗时的过程，但是如果数组需要扩容，那么这个过程是必要的。

哈希表扩容实现

实现思路：

• 首先，定义一个变量，比如 oldStorage 指向原来的 storage。
• 然后，创建一个新的容量更大的数组，让 this.storage 指向它。
• 最后，将 oldStorage 中的每一个 bucket 中的每一个数据取出来依次添加到 this.storage 指向的新数组中。

resize

装填因子 = 哈希表中数据 / 哈希表长度，即 loadFactor = count / HashTable.length。

resize 方法，既可以实现哈希表的扩容，也可以实现哈希表容量的压缩。

// 重新调整哈希表大小，扩容或压缩
resize (newLimit) {
  // 保存旧的数组内容
  const oldStorage = this.storage

  // 重置所有属性
  this.storage = []
  this.count = 0
  this.limit = newLimit

  for (const bucket of oldStorage) {
    if (bucket) {
      for (const tuple of bucket) {
        this.put(...tuple)
      }
    }
  }
}

• 通常情况下当装填因子 laodFactor > 0.75 时，对哈希表进行扩容。添加扩容代码到put方法中

  // 插入和修改元素
  put (key, value) {
    // 获取key对应的index
    const index = this.hash(key, this.limit)
  
    // 获取数组bucket （也可用链表）
    let bucket = this.storage[index]
    if (bucket === undefined) {
      // 数组不存在则初始化数组
      bucket = []
      this.storage[index] = bucket
    }
  
    // 修改已存在的元素
    for (const tuple of bucket) {
      if (tuple[0] === key) {
        tuple[1] = value
        return
      }
    }
  
    // 执行到次数则说明元素不存在 新增元素
    bucket.push([key, value])
    // 已存储个数加1
    this.count++
  
    // 是否需要扩容判断 如果装填因子大于0.75，则扩容
    if (this.count / this.limit > 0.75) {
      this.resize(this.limit * 2)
    }
  }
  

• 当装填因子 laodFactor < 0.25 时，对哈希表容量进行压缩。添加压缩代码到remove中

  // 根据key移除元素
  remove(key) {
    const index = this.hash(key, this.limit)
  
    const bucket = this.storage[index]
    if (bucket === undefined) {
      return null
    }
  
    // 遍历bucket，寻找对应的数据并做移除
    for (let i = 0, len = bucket.length; i < len; i++) {
      const tuple = bucket[i]
      if (tuple[0] === key) {
        // 移除元素
        bucket.splice(i, 1)
        this.count--
        // 压缩
        if (this.limit > 7 && this.limit / this.count < 0.25) {
          this.resize(this.limit / 2)
        }
        return tuple
      }
    }
  
    // 来到该位置，说明没有对应的数据，返回null
    return null
  }
  

容量质数

我们前面提到过，容量最好是质数。

虽然在链地址法中将容量设置为质数，没有在开放地址法中重要，但是其实链地址法中质数作为容量也更利于数据的均匀分布。

判断质数

质数也称为素数；质数表示大于1的自然数中，只能被1和自己整除的数。

实现1：

针对质数的特点：只能被 1 和 number 整除，不能被 2 ~ (number-1)整除。遍历 2 ~ (num-1) 。

// 方法1 是否是质数
isPrime (num) {
  if (num <= 1) return false
  for (let i = 2; i < num; i++) {
    if (num % i === 0) {
      return false
    }
  }
  return true
}

实现2：

一个数若可以进行因数分解，那么分解时得到的两个数一定是一个小于等于sqrt(n)，一个大于等于sqrt(n)。

比如16可以被引述分解为$2*8$, 2小于16的平方根4，8大于4。而$4*4$都是等于sqrt(n)

只需要遍历 2 ~ num 的平方根即可。该方法性能较好。

// 方法2 是否是质数
isPrime (num) {
  if (num <= 1) return false
  const sqrtNum = Math.ceil(Math.sqrt(num))
  for (let i = 2; i < sqrtNum; i++) {
    if (num % i === 0) {
      return false
    }
  }
  return true
}

扩容的质数

前面，我们有对容量进行扩展，方式是：原来的容量 * 2

• 比如之前的容量是7, 那么扩容后就是14，而14显然不是质数，所以我们还需要一个方法， 来实现一个新的容量为质数的算法。

实现思路：

2 倍扩容或压缩之后，通过循环调用 isPrime 判断得到的容量是否为质数，不是则+1，直到是为止。比如原长度：7，2 倍扩容后长度为 14，14 不是质数，14 + 1 = 15 不是质数，15 + 1 = 16 不是质数，16 + 1 = 17 是质数，停止循环，由此得到质数 17。

// 获取质数
getPrime (num) {
  while(!this.isPrime(num)) {
    num++
  }
  return num
}

那么，修改put和remove方法：

// 插入和修改元素
put (key, value) {
  // 获取key对应的index
  const index = this.hash(key, this.limit)

  // 获取数组bucket （也可用链表）
  let bucket = this.storage[index]
  if (bucket === undefined) {
    // 数组不存在则初始化数组
    bucket = []
    this.storage[index] = bucket
  }

  // 修改已存在的元素
  for (const tuple of bucket) {
    if (tuple[0] === key) {
      tuple[1] = value
      return
    }
  }

  // 执行到次数则说明元素不存在 新增元素
  bucket.push([key, value])
  // 已存储个数加1
  this.count++

  // 是否需要扩容判断 如果装填因子大于0.75，则扩容
  if (this.count / this.limit > 0.75) {
    this.resize(this.getPrime(this.limit * 2))
  }
}

// 根据key移除元素
remove(key) {
  const index = this.hash(key, this.limit)

  const bucket = this.storage[index]
  if (bucket === undefined) {
    return null
  }

  // 遍历bucket，寻找对应的数据并做移除
  for (let i = 0, len = bucket.length; i < len; i++) {
    const tuple = bucket[i]
    if (tuple[0] === key) {
      // 移除元素
      bucket.splice(i, 1)
      this.count--
      // 压缩
      if (this.limit > 7 && this.limit / this.count < 0.25) {
        this.resize(this.getPrime(Math.floor(this.limit / 2)))
      }
      return tuple
    }
  }

  // 来到该位置，说明没有对应的数据，返回null
  return null
}

完整实现

/**
 * 哈希函数
 * @param {*} str 
 * @param {*} size 
 * @returns hashCode
 */
function hashFun (str, size) {
  const prime = 37 // 质数
  // 初始化hashCode的值
  let hashCode = 0

  // 霍纳法则
  for (let i = 0; i < str.length; i++) {
    hashCode = prime * hashCode + str.charCodeAt(i)
  }

  // 求模运算
  return hashCode % size
}

/**
 * 哈希表 基于 链地址法
 */
module.exports = class HashTable {
  constructor () {
    this.storage = [] // 存放相关元素
    this.count = 0 // 已存储的数据个数
    this.limit = 7 // 数组的长度

  }

  // 哈希函数，生成哈希code
  hash (str, limit) {
    const prime = 37 // 质数
    // 初始化hashCode的值
    let hashCode = 0

    // 霍纳法则
    for (let i = 0; i < str.length; i++) {
      hashCode = prime * hashCode + str.charCodeAt(i)
    }

    // 求模运算
    return hashCode % limit
  }

  // 插入和修改元素
  put (key, value) {
    // 获取key对应的index
    const index = this.hash(key, this.limit)

    // 获取数组bucket （也可用链表）
    let bucket = this.storage[index]
    if (bucket === undefined) {
      // 数组不存在则初始化数组
      bucket = []
      this.storage[index] = bucket
    }

    // 修改已存在的元素
    for (const tuple of bucket) {
      if (tuple[0] === key) {
        tuple[1] = value
        return
      }
    }

    // 执行到次数则说明元素不存在 新增元素
    bucket.push([key, value])
    // 已存储个数加1
    this.count++

    // 是否需要扩容判断 如果装填因子大于0.75，则扩容
    if (this.count / this.limit > 0.75) {
      this.resize(this.getPrime(this.limit * 2))
    }
  }

  // 根据key获取value
  get (key) {
    const index = this.hash(key, this.limit)

    const bucket = this.storage[index]

    if (bucket === undefined) {
      return null
    }

    // 循环判断bucket中是否有key对应的value
    for (const tuple of bucket) {
      if (tuple[0] === key) {
        return tuple[1]
      }
    }

    // 未找到，返回null
    return null
  }

  // 根据key移除元素
  remove(key) {
    const index = this.hash(key, this.limit)

    const bucket = this.storage[index]
    if (bucket === undefined) {
      return null
    }

    // 遍历bucket，寻找对应的数据并做移除
    for (let i = 0, len = bucket.length; i < len; i++) {
      const tuple = bucket[i]
      if (tuple[0] === key) {
        // 移除元素
        bucket.splice(i, 1)
        this.count--
        // 压缩
        if (this.limit > 7 && this.limit / this.count < 0.25) {
          this.resize(this.getPrime(Math.floor(this.limit / 2)))
        }
        return tuple
      }
    }

    // 来到该位置，说明没有对应的数据，返回null
    return null
  }

  isEmpty () {
    return this.count === 0
  }

  size () {
    return this.count
  }

  // 重新调整哈希表大小，扩容或压缩
  resize (newLimit) {
    // 保存旧的数组内容
    const oldStorage = this.storage

    // 重置所有属性
    this.storage = []
    this.count = 0
    this.limit = newLimit

    for (const bucket of oldStorage) {
      if (bucket) {
        for (const tuple of bucket) {
          this.put(...tuple)
        }
      }
    }
  }

  // 方法1 是否是质数 效率低
  isPrime_unrecommend (num) {
    if (num <= 1) return false
    for (let i = 2; i < num; i++) {
      if (num % i === 0) {
        return false
      }
    }
    return true
  }

  // 方法2 是否是质数
  isPrime (num) {
    if (num <= 1) return false
    const sqrtNum = Math.ceil(Math.sqrt(num))
    for (let i = 2; i < sqrtNum; i++) {
      if (num % i === 0) {
        return false
      }
    }
    return true
  }

  // 获取质数
  getPrime (num) {
    while(!this.isPrime(num)) {
      num++
    }
    return num
  }
}

测试：

const HashTable = require('../../lib/HashTable')

const hashTable = new HashTable()

// put
hashTable.put('tom', '18811')
hashTable.put('jane', '18812')
hashTable.put('lily', '18813')
hashTable.put('steve', '18814')
hashTable.put('shawn', '18815')
hashTable.put('marie', '18816')
hashTable.put('pinky', '18817')
console.log(hashTable)

// get
console.log(hashTable.get('tom'))
console.log(hashTable.get('jane'))
console.log(hashTable.get('lily'))

// remove
console.log(hashTable.get('tom'))
console.log(hashTable.get('ccbean'))

// isEmpty
console.log('isEmpty', hashTable.isEmpty())
// size
console.log('size', hashTable.size())