[数据结构与算法]js数据结构学习---哈希表

8.哈希表

8.1哈希表概念

• 哈希化：将大数字转化成数组范围内下标的过程

• 哈希函数：将单词转成大数字，再对大数字进行哈希化函数

• 哈希表：又称散列表。其基本思路是，设要存储的元素个数为n，设置一个长度为m（m>=n）的连续内存单元，以每个元素的关键字k为自变量，通过哈希函数把k映射为内存单元的地址(下标)，并把该元素存储在这个内存单元中，如此构造的存储结构称为哈希表

8.2哈希表的特点

• 基于数组实现，速度比树快，编码比树容易

• 可以提供非常快速的插入-删除-查找操作

• 无论多少数据，插入和删除的时间为O(1)的时间级

• 哈希表中的数据没有顺序，不能以固定的方式去遍历其元素

• 哈希表中key是不允许重复

• 哈希表的实质就是将字符串转成下标值

8.3哈希表的冲突

8.3.1什么是哈希冲突？

例如现要存储某个数，通过哈希函数得到其下标值后，发现此下标已存在有值，这种情况就为哈希冲突，为了能使一个下标对应一个数据项我们只能解决此冲突。另外，通常把这种具有不同关键字而具有相同哈希地址的元素称为同义词，这种冲突也称为同义词冲突

8.3.2如何解决这种冲突？

8.3.2.1链地址法(也称拉链法)

把所有同义词用单链表或数组链接起来

• 链地址法解决冲突的思路

  1）每个数组单元中存储的不再是单个数据，而是通过数组或链表存储的一个链条

  2）当查询时，先根据哈希化后的下标值找到对应的位置，再取出数组或链表，依次查询所需数据

  3）注：当数据插入到前面的话最好使用链表

8.3.2.2开放地址法

通过寻找空白的单元格来添加同义词

如：有一集合为（16，74，60，43，54，29）其哈希函数为h（k）=k mod 13，其中16与29哈希化后为同一下标，因16在29前插入，所以在插入29时会发现下标3已经有值，这时就要通过其他的方法去往后寻找空白位置将29插入，方法为以下三种：

1）线性探测法

概念：从发生冲突的地址开始，依次探测下一个地址（通过下标加1的方法往后查找空白位置）

插入29时：如下图所示，当我们插入29时发现index=3的位置已经有了16，我们就要通过index+1往后查找空白的位置将29放入??

查找29时：

• 先将29哈希化得到index=3，此时将index=3位置的元素与29比较，若相同直接返回

• 若不相同则根据插入时的规则通过index+1的方法往后查找比较，此时要注意，因为线性探测是通过index+1的方式插入的，那么在查找时如果发现离index=3近的第一个单元格为空时就应该停止查找，线性探测不存在跳过空位置

删除29时：

因为在查找时所设条件是当发现离index=3近的第一个单元格为空时就应该停止查找，所以在删除时不能将29所在位置设置为null而是应该设置为其他能判断在此之后还有数值的值，避免当29删除后要查找处在29之后的同义词程序却提示不存在现象。

2）二次探测法

概念：在线性探测的基础上对探测步长进行优化，例如线性探测步长依次为x+1，x+2，而二次探测步长依次为x+1^2，x+2^2从而避免聚集

3）再哈希法

概念：第一次哈希化的值为下标，将关键字用另一个哈希函数再一次进行哈希化，用此次哈希化的结果作为步长，对于指定的关键字，步长在整个探测中是不变的，但是不同的关键字使用不同的步长

特点：哈希函数与第一次哈希化所用函数不同，且输出不为0（为什么输出不能为0？因为当步长为0时每次探测的都是同一个位置，会使程序进行死循环）

哈希函数：step=constant-(key%constant),constant为质数且小于数组的容量

8.4什么是装填因子

• 装填因子表示当前哈希表中已经包含的数据项和整个哈希表长度的比值

• 装填因子=总数据项/哈希表长度

• 开放地址法的装填因子为1，因为它必须寻找到空白单元才能将元素存入

• 链地址法装填因子可以大于1，因为拉链法可以无限延伸下去

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

8.5性能排行

二次探测，再哈希法>线性探测

8.6哈希函数

8.6.1好的哈希函数应该具备哪些优点

• 快速的计算

  因乘法和除法性能较底，所以在函数中尽量少的有乘法和除法（使用霍纳法则）

• 均匀的分布

  当多个元素映射到同一位置时，应尽可能将元素映射到不同位置，让元素在哈希表中均匀分布，因此我们需要在使用常量的地方，尽量使用质数

8.6.2哈希函数的实现

哈希函数主要为了实现以下事情：

• 使所有元素尽可能分布在m个连续内存单元上

• 将字符串转成较大的数字：hashCode

• 将hashCode压缩到数组范围之内

function hasFunc (str, size) {
 ? ?var hasCode = 0//定义hashCode变量
 ? ?for (var i = 0; i < str.lenght; i++) {
 ? ? ? ?hasCode = 37 * hasCode + str.charCodeAt(i)//先对单词进行编码
 ? ? ? ?//37为质数，通过质数来确保元素尽可能分布在连续内存单元上
 ?  }
 ? ?var index = hasCode % size//取余操作
 ? ?return index
}

8.7哈希表的实现

使用链地址法进行哈希表构造如下图所示

8.7.1哈希表整体实现预览

function hasMap () {
 ? ?//属性
 ? ?this.storage = [] //存储元素
 ? ?this.count = 0 //记录表中已存在多少元素
 ? ?//装载因子大于0.75时要进行扩容，当小于0.25时要进行容量缩减
 ? ?this.limit = 7 //表的最大容量是多少
 ? ?hasMap.prototype.hasFunc = function (str, size) {}
 ? ?hasMap.prototype.put = function (key, value) {}
 ? ?hasMap.prototype.get = function (key) {}
 ? ?hasMap.prototype.del = function (key) {}
    hasMap.prototype.resize = function (newLimit) {}
    hasMap.prototype.isPrime = function (num) {}
    hasMap.prototype.getPrime = function (num) {}
 ?  }

8.7.2插入或修改操作

思路：

• 根据key获取索引值（目的：找到对应的位置）

• 根据索引值取出bucket(由链表或数组构造)，如果桶不存在则创建桶并且将桶插入到该索引的位置

• 判断是新增还是修改原来的值，如果key已经存在则进行修改操作，否则进行插入操作

 //插入与修改操作
 ? ?hasMap.prototype.put = function (key, value) {
 ? ? ? ?//1.根据key获取对应的index
 ? ? ? ?var index = this.hasFunc(key, this.limit)
 ? ? ? ?//2.根据index取出对应的bucket
 ? ? ? ?var bucket = this.storage[index]
 ? ? ? ?//3.判断该bucket是否存在
 ? ? ? ?if (bucket == null) {
 ? ? ? ? ? ?bucket = []
 ? ? ? ? ? ?this.storage[index] = bucket
 ? ? ?  }
 ? ? ? ?//判断是否是修改数据
 ? ? ? ?for (var i = 0; i < bucket.length; i++) {
 ? ? ? ? ? ?var tuple = bucket[i]
 ? ? ? ? ? ?if (tuple[0] == key) {//tuple[0]==key说明bucket中已经存在有该数据所以进行修改
 ? ? ? ? ? ? ? ?tuple[1] = value
 ? ? ? ? ? ? ? ?return
 ? ? ? ? ?  }
 ? ? ?  }
 ? ? ? ?//进行添加操作
 ? ? ? ?bucket.push([key, value])
 ? ? ? ?this.count += 1
 ? ? ? ?//当装载因子>0.75时进行扩容
 ? ? ? ?if (this.count > this.limit * 0.75) {
 ? ? ? ? ? ?var newLimit = this.getPrime(this.limit * 2)
 ? ? ? ? ? ?this.resize(newLimit)
 ? ? ?  }
 ?  }

8.7.3获取数据操作

思路：

• 根据key获取对应的index

• 根据index获取对应的bucket

• 判断bucket是否为null，如果为null说明该值或相关同义词还未插入直接返回相关提示（null或false）

• bucket不为null的话说明该值或相关同义词已插入，这时对bucket中的元素进行线性搜索判断，若找到与传入的key相等的key则返回该key所对应的值，否则返回相关提示（null或false）

 hasMap.prototype.get = function (key) {
 ? ? ? ?//1.根据key获取对应的index
 ? ? ? ?var index = this.hasFunc(key, this.limit)
 ? ? ? ?//2.根据index取出对应的bucket
 ? ? ? ?var bucket = this.storage[index]
 ? ? ? ?//3.判断该bucket是否为null
 ? ? ? ?if (bucket == null) return false
 ? ? ? ?//4.有bucket则进行线性查找
 ? ? ? ?for (var i = 0; i < bucket.length; i++) {
 ? ? ? ? ? ?var tuple = bucket[i]
 ? ? ? ? ? ?if (tuple[0] == key)
 ? ? ? ? ? ? ? ?return tuple[1]
 ? ? ?  }
 ? ? ? ?return false
 ?  }

8.7.4删除数据操作

思路：

• 根据key获取对应的index

• 根据index获取对应的bucket

• 判断bucket是否为null，如果为null说明该值或相关同义词不存在返回相关提示（null或false）

• bucket不为null的话说明该值或相关同义词已存在，这时对bucket中的元素进行线性搜索判断，若找到与传入的key相等的key则删除bucket[i]并且count减1，否则返回相关提示（null或false）

hasMap.prototype.del = function (key) {
 ? ? ? ?//1.根据key获取对应的index
 ? ? ? ?var index = this.hasFunc(key, this.limit)
 ? ? ? ?//2.根据index取出对应的bucket
 ? ? ? ?var bucket = this.storage[index]
 ? ? ? ?//3.判断该bucket是否为null
 ? ? ? ?if (bucket == null) return false
 ? ? ? ?//4.有bucket则进行线性查找
 ? ? ? ?for (var i = 0; i < bucket.length; i++) {
 ? ? ? ? ? ?var tuple = bucket[i]
 ? ? ? ? ? ?if (tuple[0] == key)
 ? ? ? ? ? ? ? ?bucket.splice(i, 1)
 ? ? ? ? ? ?this.count--
 ? ? ? ? ? ? //缩小容量
 ? ? ? ? ? ? ? ?if (this.limit > 7 && this.count < this.limit * 0.25)
 ? ? ? ? ? ? ?  {var newLimit = this.getPrime(Math.floor(this.limit / 2))
 ? ? ? ? ? ? ? ?this.resize(newLimit)
 ? ? ? ? ? ? ?  }
 ? ? ? ? ? ?return tuple[1]
 ? ? ?  }
 ? ? ? ?return false
 ?  }

8.7.5扩容操作

8.7.5.1为什么要扩容

• 目前，我们使用链地址法将所有的数据项所存放在长度为7的数组中，根据链地址法的性质可知装载因子可以大于1，所以此哈希表可以无限制的插入新数据，随着数据量的增多，每一个index对应的bucket会越来越长，也会造成低效率，因此需要进行扩容操作

• 什么情况下进行扩容：当装载因子>0.75或装载因子<0.25的时候

8.7.5.2扩容操作

思路：

• 先将原先的数组(storage)进行保存

• 再对原有哈希表中的属性进行重置操作

• 再将原数组的值重新赋值进行插入操作（因为index与limit有关，当limit改变之后各个元素所对应的index也会发现改变）

• 注：为了保证哈希表中的元素能够均匀分布，所以在进行扩容操作时要为新limit赋质数（只能被1和自身整除的数）

• 判断某数是否为质数

   hasMap.prototype.isPrime = function (num) {
   ? ? ? ?var temp = parseInt(Math.sqrt(num))
   ? ? ? ?for (var i = 2; i <= temp; i++) {
   ? ? ? ? ? ?if (num % i == 0) {
   ? ? ? ? ? ? ? ?return false
   ? ? ? ? ?  }
   ? ? ?  }
   ? ? ? ?return true
   ?  }

• 获取质数

  hasMap.prototype.getPrime = function (num) {
   ? ? ? ?while (!this.isPrime(num)) {
   ? ? ? ? ? ?num++
   ? ? ?  }
   ? ? ? ?return num
   ?  }

• 扩容

  hasMap.prototype.resize = function (newLimit) {
   ? ? ? ?//1.保存旧的数组内容
   ? ? ? ?var oldstorage = this.storage
   ? ? ? ?//2.重置所有属性
   ? ? ? ?this.storage = []
   ? ? ? ?this.count = 0
   ? ? ? ?this.limit = newLimit
   ? ? ? ?//3.遍历oldstorage中所有的bucket
   ? ? ? ?for (var i = 0; i < oldstorage.length; i++) {
   ? ? ? ? ? ?//取出对应的bucket
   ? ? ? ? ? ?var bucket = oldstorage[i]
   ? ? ? ? ? ?//判断bucket是否为null
   ? ? ? ? ? ?if (bucket == null) continue
   ? ? ? ? ? ?//bucket中有数据，取出数据，重新插入
   ? ? ? ? ? ?for (var j = 0; j < bucket.length; j++) {
   ? ? ? ? ? ? ? ?var tuple = bucket[j]
   ? ? ? ? ? ? ? ?this.put(tuple[0], tuple[1])
   ? ? ? ? ?  }
   ? ? ?  }
   ?  }