1. 哈希表

​ 为什么会有哈希表？

举个栗子：

一个公司里有上千个员工，我想找一个员工的信息一般通过什么方式

通过数组，每一个员工对应一个工号，我可以直接查找工号就可以获取对应的信息

但是我不想通过工号去获取，我想通过员工的名字去获取，这个时候就会想到链表，但是问题来了，链表是一个信息连着一个信息去查找，效率非常的慢

这个时候就可以用到哈希表了，可以把每个员工的名字转成对应的数字，数字对应名字，这样我直接通过数字就可以获取员工的信息了

1.1 哈希化

​ 将大数字转化为数组范围内的下标(这里的范围自己去定义)过程，比如0~100取余10就得到0-9的下标值(方式有多种，比如java采用的位运算)，这个过程我们就称之为哈希化

假如有5000个单词，可能会定义一个长度为5000的数组，但是在实际情况中，我们不能保证这些单词对应的大数完全不相同，所以需要两倍的大小10000，虽然数组的长度已经足够了，但是通过哈希化后的下标还是可能会重复，这个时候就需要去解决冲突(这里的冲突是指大数哈希化后的，而不是大数)

1.2 哈希函数

​ 通常我们会将单词转成大数字(幂的连乘)，大数字在进行哈希化后的代码，通过一个函数进行处理得到想要的数据，这个函数就是哈希函数

为什么要把单词转成大数字：因为我们需要，把对应的单词通过合适的方式转换为一个非常庞大的数字，这样就不会和其他的单词重复，确保了每个单词都有对应的数字(但是数据过于庞大就需要哈希化)

1.3 哈希表

​ 最终将数据都插入到一个数组中，我们就称之为是一个哈希表

1.4 解决冲突

• 什么是冲突，冲突就是哈希化后会有相同的下标值，解决冲突有两种方式，链地址法、开发地址法

• 链地址法

• 链地址法解决冲突的办法，就是每一个数组中存储的数据不再是单个数据，而是一个链表或数组

• 当查询时想，先根据哈希化后的下标找到对应的位置，再在对应位置中进行线性查找

• 问题来了，到底是选择链表还是数组呢，其实都差不多，因为冲突的情况很少(但是我们必要也要解决)，很少就表示了，它后面的链表或者数组的长度都不会很长，都是线性查抄效率其实都差不多

• 选择链表或数组还是看需求，链表和数组都有自己的优缺点，数组适合查抄修改，链表适合插入删除

• 开放地址法

• 开发地址法就是寻找空白的位置来存放冲突的数据，因为经过处理，存放数组的长度是足够存放这些数据的(长度不够会扩容)，但是通过哈希化后存放会有冲突的情况，开发地址法的效率要比链地址法的效率要高一些，开发地址法寻找有三种方式，线性探测、二次探测、再哈希法

• 线性探测

  插入：假设下标为2项中有一个为22的数据，然后我想插入32的数据，这个时候就需要线性探测，线性探测就是线性的查抄空白的单元，假如下标为3项中没有内容，就可以通过线探测让index++(目前指的是2)，当加到3时发现有空位，就把32插进去，线性探测只会从对应的下标开始探测，不是从头开始

  查询：查询的思路和插入一样，如果还有值62，72等也是按照这样的思路，还有就是查询index=2的值，比如我要查有没有102，线性查找当遇到了空的位置还没有找到，那么就停止，因为在插入的时候会排除掉所有的空位置，都已经找到空位置还没有找到，就已经能够表示没有该值了

  删除：删除和查询插入的思路也是一样，但是有一点要注意，在删除后不能将这个下标的内容设置为null，因为设置为null在插入查询和删除时，会找到为空的项，那么它就不会在向后探测了，那我后面还存的62，72呢他就找不到了，所以删除后的需要做特殊处理(比如设置为-1)，表示他是被删除的，后面还可能有相同类型(这里类型指结尾都是2，通过哈希化后分辨的)，然后再次插入时可以放到这个-1的位置

  线性探测的问题：线性探测有一个比较严重的问题，就是聚集，比如在我们没有任何数据的时候，我们插入一些数据22-23-24-25-26-27，那就意味着2-3-4-5-6-7的位置都有元素，这种一连串的数据就叫做聚集，聚集会影响哈希表的性能，无论是插入、删除、查询都会影响，比如我们插入一个32，会发现从2-7都有数据，但是他还是会一位一位的去探测，特别消耗性能，这个时候就需要二次探测了，二次探测可以解决一部分这个问题

• 二次探测

  二次探测其实就是线性探测的改良版：线性探测是 x+1、x+2、x+3这种一步一步探测的，而二次探测是 x+1(平方)、x+2(平方)、x+3(平方)这种成倍探测的，其他的操作和线性探测都是一样的，就是步长不一样

  二次探测的问题：如果我们插入的是32-112-42-92-2这种数据呢，这种情况也会造成一种，步长不一样的聚焦，这个时候就需要再哈希法来根本的解决问题了

• 再哈希法

  再哈希法：线性探测和二次探测都会有对应的聚焦问题，为了解决这些问题，就需要在哈希法，再哈希法是根据关键字来进行探测，不同的关键字即使映射到相同的数组下标(冲突)，也可以使用不同的探测序列(步长)，不同的关键字使用不同的步长，第二次哈希化和第一个哈希函数不同，也不能输出为0，因为输出为0就代表没有步长，算法就进入了死循环

  新的哈希函数：stepSize= constant - (key % constant)，其中key是数据的长度，constant是质数，且小于数组的容量，例如stepSize= 5- (key % 5)，结果无乱如何都不可能为0

1.5 哈希化的效率

• 如果没有发生冲突，那么效率就会非常的高
• 如果发生冲突，存取时间就依赖于后来的探测长度，平均探测长度以及平均存取时间，取决于装填因子，随着装填因子变大，探测长度也越来越长
• 装填因子 = 总数据项 / 哈希表长度
• 开放地址法的装填因子最大只能是1，因为它必须寻找到空白的单元才能将元素放入
• 链地址法的装填因子可以大于1，因为链地址法的拉链可以无限的延伸下去(到后面效率越来越低)

1.6 优秀的哈希函数

• 快速的计算

  • 在计算机中使用乘法是非常消耗性能的

  • 把对应数据转为大数，使用的就是幂的连乘，这里会用到非常多的乘法，比如

    cats = 3 * 27^3 + 1*27^2 + 20 * 27^1 + 17 * 27^0 = 60337

    说明：27自己选择的幂的底数，^表示幂，3、1、20、17表示对应单词的编码

    每个单词都是这样转换的，可以用 n 来表示 经过一系列化简运算乘法次数变为：n(n+1)/2次，加法次数为：n次

  • 霍纳法则：为了解决这类求值问题的高效算法，在中国霍纳法则也被称为秦九韶算法

    通过霍纳法则变化后，乘法次数变为：n次，加法次数为：n次

    如果使用大O表示时间复杂度的话，直接从O(N^2)降到了O(N)

• 均匀的分布

  • 在哈希表中，无论是链地址法还是开放地址法，当多个元素映射到同一个位置时，都会影响效率

  • 所以，优秀的哈希函数应该尽可能将元素映射到不同的位置，当元素在哈希表中均匀的分布

  • 为了均匀的分布，在使用常量的时候尽量使用质数

    哈希表的长度，幂的底数，这些都使用质数，为了让哈希表分布更均匀，再哈希法也更容易查找

    举个栗子：

    如果容器长度为15(下标值0~14)，通过再哈希法的函数计算要查找的步长：5 - (15 % 5) = 5(步长)

    探测顺序：0 - 5 - 10 - 0 - 5 - 10……如果0、5、10这些里面都有数据那么程序就会变成死循环

    如果容器长度为13(下标值0~12)，查找的步长：5 - (13 % 5) = 2(步长)

    探测顺序：0 - 2 - 4 - 6 - 8 - 10 - 12 - 1 - 3 - 5 - 7 - 9 - 11，会把每一个位置都探测到

    在试一个，容器长度为7(下标值0~6)，查找的步长：5 - (7 % 5) = 3(步长)

    探测顺序：0 - 3 - 6 - 2 - 5 - 1 - 4，也会把每一个位置都探测到

    这样不仅不会产生循环，而且可以让数据在哈希表中更加均匀的分布(这里面设计到数学的知识)

1.7 哈希表扩容

• 在链地址法中，装填因子是可以大于1的
• 但是随着数据量的增多，每一个index对应的bucket(桶)也会越来越长，这样一来效率就会降低
• 所以在这个时候就需要对数组进行扩容
• 比较常见的情况是，装填因子 > 0.75 的时候进行扩容，在这个时候进行扩容效率最高
• 扩容之后要把之前数组中的数据清空，在重新添加到新的数组中
• 有了扩容当然也会有对应的缩容，缩容的实现原理和扩容其实是一样的
• 当 装填因子 < 0.25 的时候进行缩容
• 因为如果没有缩容，只有扩容的话，我先一直添加数据，然后数组会不断的扩容，然后我在一直删除数据，这个时候数组中就会有很多空的位置，就浪费掉了很多不必要的空间，所以也需要用到缩容

1.8 哈希表的封装(链地址法)

• 哈希函数

  // 封装哈希函数
  // str：要转为大数的数据
  // size：数组的长度
  function hashFn(str, size) {
    // 存储大数
    let hashCode = 0
  
    // 霍纳法则：高效的计算
    // ((...(((anx + an - 1)x + an - 2)x + an - 3)...)x + a1)x + a0
    for (let i = 0; i < str.length; i++) {
      // charCodeAt --> 转Unicode编码
      // 37 自己选择的质数，选择37的比较多
      hashCode = hashCode * 37 + str.charCodeAt(i)
    }
  
    // 数组的长度取模(哈希化)，方便存放不同对应的位置
    let index = hashCode % size
    return index
  }
  

• 高效的判断质数

  function isPrime(num) {
    // sqrt(n) --> 指的是n的开方
    // 一个数n如果可以进行因式分解，那么分解的得到的两个数
    // 一定是一个小于等于sqrt(n)，一个大于等于sqrt(n)
    let temp = parseInt(Math.sqrt(num))
    
    for (let i = 2; i <= temp; i++) {
      if (num % i == 0) {
        return false
      }
    }
    return true
  }
  

• 哈希表

  // 哈希表的增、删、改、查思路是一样的
  // 1.通过哈希函数转换，取出对应的下标，也就是要存放的数据的桶
  // 2.查看该桶是不是空的
  //  (1)添加操作中，如果桶空就创建一个桶(这里使用的是数组，数组和链表的效率差不多)
  //  (2)在哈希表中，添加和修改是同一个方法，因为是通过key去添加或修改数据，
  //      如果没有key就添加，等同于添加操作，有key的话就修改value，就等同于修改操作
  //  (3)在查询和删除中，如果没有该桶就返回操作失败对应的操作
  // 3.遍历该桶，在进行增、删、改、查，第二点说的是桶，第三点说的是桶中的数据，思路都一样
  // 4.添加和删除才会存在的操作
  //  (1)添加，内容长度加1，然后查看是否需要扩容
  //  (2)删除，内容长度减1，删除查看是否需要缩容
  //  (3)扩容或缩容，后的数据也必须是质数
  
  // 哈希表类
  class HashTable {
    constructor() {
      // 最外层大数组(哈希表)
      this.storage = []
      // 数据量(数据内容的总长度)
      this.count = 0
      // 哈希表长度
      this.limit = 7
    }
  
    // 封装哈希函数
    // str：要转为大数的数据
    // size：数组的长度
    hashFn(str, size) {
      // 存储大数
      let hashCode = 0
  
      // 霍纳法则：高效的计算
      // ((...(((anx + an - 1)x + an - 2)x + an - 3)...)x + a1)x + a0
      for (let i = 0; i < str.length; i++) {
        // charCodeAt --> 转Unicode编码
        // 37 自己选择的质数，选择37的比较多
        hashCode = hashCode * 37 + str.charCodeAt(i)
      }
  
      // 数组的长度取模(哈希化)，方便存放不同对应的位置
      let index = hashCode % size
      return index
    }
  
    // 1.put(key, value)：插入和修改数据
    put(key, value) {
      // 取出对应要放入的下标
      let index = this.hashFn(key, this.limit)
  
      // 桶：因为选择的链地址法，每一个对应的下标都要存放一个数组(桶)
      let bucket = this.storage[index]
  
      // 如果这个桶不存在表示第一次插入值，需要创建这个桶，并放在对应下标的位置
      if (bucket == null) {
        bucket = []
        this.storage[index] = bucket
      }
  
      // 如果是第一次添加数据循环不会进来(bucket.length == 0)
      for (let i = 0; i < bucket.length; i++) {
        // 每一项数据存放的也是一个数组，[key, value]
        let data = bucket[i]
        // 发现有相同的key，那么就做修改操作
        if (data[0] == key) {
          data[1] = value
          return
        }
      }
      // 没有就添加
      bucket.push([key, value])
  
      // 添加数据内容加一
      this.count++
      // 当装填因子 > 0.75 时，对数组哈希表进行扩容
      if (this.count > this.limit * 0.75) {
        // 查看这个数是不是质数，是就返回不是就变为质数
        let prime = this.setPrime(this.limit * 2)
        this.resize(prime)
      }
    }
  
    // 2.get(key)：获取数据
    get(key) {
      // 取出对应要查找的下标
      let index = this.hashFn(key, this.limit)
  
      // 取出当前桶
      let bucket = this.storage[index]
  
      // 如果桶为空直接返回
      if (bucket == null) {
        console.log("桶为空");
        return
      }
  
      for (let i = 0; i < bucket.length; i++) {
        let data = bucket[i]
        // 查找key相等就返回value
        if (data[0] == key) {
          return data[1]
        }
      }
  
      return "没有该数据"
    }
  
    // 3.remove(key)：删除数据，并返回该数据
    remove(key) {
      let index = this.hashFn(key, this.limit)
  
      let bucket = this.storage[index]
  
      if (bucket == null) {
        console.log("桶为空");
        return
      }
  
      for (let i = 0; i < bucket.length; i++) {
        let data = bucket[i]
        if (data[0] == key) {
          // 匹配到了就删除当前项
          bucket.splice(i, 1)
          this.count--
  
          // 哈希表最小长度为7(因为太小了没必要)
          // 当装填因子 < 0.25 时，缩容
          if (this.limit > 7 && this.count < this.limit * 0.25) {
            let prime = this.setPrime(Math.floor(this.limit / 2))
            this.resize(prime)
          }
  
          return data[1]
        }
      }
      return "没有该数据"
    }
  
    // 4.isEmpty()：查看哈希表是否为空，为空返回true，不为空返回false
    isEmpty() {
      return this.count == 0
    }
  
    // 5.size()：获取哈希表中的元素个数
    size() {
      return this.count
    }
  
    // resize(newLimit)：哈希表扩容/缩容
    resize(newLimit) {
      // 先保存原数据
      let oldStorage = this.storage
  
      // 初始化，然后改变哈希表长度
      this.storage = []
      this.count = 0
      this.limit = newLimit
  
      // 
      for (let i = 0; i < oldStorage.length; i++) {
        let bucket = oldStorage[i]
  
        // 如果为空就跳过
        if (bucket == null) {
          continue
        }
  
        // 如果有值就全部在添加，到新的哈希表长度中
        for (let i = 0; i < bucket.length; i++) {
          let data = bucket[i]
          this.put(data[0], data[1])
        }
      }
    }
  
    // isPrime(num)：判断一个数是否为质数，是true，不是false
    isPrime(num) {
      // sqrt(n) --> 指的是n的开方
      // 一个数n如果可以进行因式分解，那么分解的得到的两个数
      // 一定是一个小于等于sqrt(n)，一个大于等于sqrt(n)
      let temp = parseInt(Math.sqrt(num))
      
      for (let i = 2; i <= temp; i++) {
        if (num % i == 0) {
          return false
        }
      }
      return true
    }
  
    // setPrime(num)：把一个数变为质数
    setPrime(num) {
      while (!this.isPrime(num)) {
        num++
      }
      return num
    }
  }
  
  // 测试
  let hashTable = new HashTable()
  
  hashTable.put("小红", "1")
  hashTable.put("小白", "12")
  hashTable.put("小蓝", "123")
  hashTable.put("小绿", "1234")
  hashTable.put("小黑", "12345")
  hashTable.put("小天", "123456")
  hashTable.put("小黄", "1234567")
  
  // console.log(hashTable.get("大狗"));
  // hashTable.get("小黑")
  
  console.log(hashTable.remove("小红"));
  console.log(hashTable.remove("小白"));
  console.log(hashTable.remove("小绿"));
  console.log(hashTable.remove("小黑"));
  
  // console.log(hashTable.isEmpty());
  
  // console.log(hashTable.size());
  
  console.log(hashTable);