javascript数据结构-哈希表

本文最后更新于：8 个月前

本博客参考于洛伊安妮·格罗纳编著的javascript数据结构与算法第三版及codeWay老师视频或其他博客资料，在此对此表示感谢!
github仓库：https://github.com/hzx17/

JavaScript 数据结构与算法（十）哈希表

认识哈希表

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

哈希表通常是基于数组实现的，但是相对于数组，它存在更多优势：

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

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

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

哈希表是什么？

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

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

  • 案例一：公司想要存储 1000 个人的信息，每一个工号对应一个员工的信息。若使用数组，增删数据时比较麻烦；使用链表，获取数据时比较麻烦。有没有一种数据结构，能把某一员工的姓名转换为它对应的工号，再根据工号查找该员工的完整信息呢？没错此时就可以使用哈希表的哈希函数来实现。

  • 案例二：存储联系人和对应的电话号码：当要查找张三（比如）的号码时，若使用数组：由于不知道存储张三数据对象的下标值，所以查找起来十分麻烦，使用链表时也同样麻烦。而使用哈希表就能通过哈希函数把张三这个名称转换为它对应的下标值，再通过下标值查找效率就非常高了。

也就是说：哈希表最后还是基于数据来实现的，只不过哈希表能够通过哈希函数把字符串转化为对应的下标值，建立字符串和下标值的映射关系。

认识哈希化

为了把字符串转化为对应的下标值，需要有一套编码系统，为了方便理解我们创建这样一套编码系统：比如 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。

虽然该方式可以保证字符的唯一性，但是如果是较长的字符（如 aaaaaaaaaa）所表示的数字就非常大，此时要求很大容量的数组，然而其中却有许多下标值指向的是无效的数据（比如不存在 zxcvvv 这样的单词），造成了数组空间的浪费。

两种方案总结：

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

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

哈希表的一些概念

  • 哈希化

    将大数字转化成数组范围内下标的过程，称之为哈希化。

  • 哈希函数

    我们通常会将单词转化成大数字，把大数字进行哈希化的代码实现放在一个函数中，该函数就称为哈希函数。

  • 哈希表

    对最终数据插入的数组进行整个结构的封装，得到的就是哈希表。

地址的冲突

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

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

链地址法（拉链法）

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

链地址法

这样可以根据下标值获取到整个数组或链表，之后继续在数组或链表中查找就可以了。而且，产生冲突的元素一般不会太多。

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

开放地址法

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

开放地址法

根据探测空白单元格位置方式的不同，可分为三种方法：

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

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

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

优秀的哈希函数：

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

哈希化的效率

哈希表中执行插入和搜索操作效率是非常高的。

  • 如果没有发生冲突，那么效率就会更高；
  • 如果发生冲突，存取时间就依赖后来的探测长度；
  • 平均探测长度以及平均存取时间，取决于填装因子，随着填装因子变大，探测长度会越来越长。

装填因子

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

不同探测方式性能的比较

  • 线性探测

    随着装填因子的增大，平均探测长度呈指数形式增长，性能较差。实际情况中，最好的装填因子取决于存储效率和速度之间的平衡，随着装填因子变小，存储效率下降，而速度上升。

  • 二次探测和再哈希化的性能

    二次探测和再哈希法性能相当，它们的性能比线性探测略好。由下图可知，随着装填因子的变大，平均探测长度呈指数形式增长，需要探测的次数也呈指数形式增长，性能不高。

  • 链地址法的性能

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

哈希函数

哈希表的优势在于它的速度，所以哈希函数不能采用消耗性能较高的复杂算法。提高速度的一个方法是在哈希函数中尽量减少乘法和除法。

性能高的哈希函数应具备以下两个优点：

  • 快速的计算；
  • 均匀的分布；

快速计算

霍纳法则：在中国霍纳法则也叫做秦久韶算法，具体算法为：

霍纳法则

求多项式的值时，首先计算最内层括号内一次多项式的值，然后由内向外逐层计算一次多项式的值。这种算法把求 n 次多项式 f(x)的值就转化为求 n 个一次多项式的值。

  • 变换之前：

    • 乘法次数：n(n+1)/2 次；
    • 加法次数：n 次；

  • 变换之后：

    • 乘法次数：n 次；
    • 加法次数：n 次；

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

均匀分布

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

Java 中的 HashMap 采用的是链地址法，哈希化采用的是公式为：index = HashCode(key) & (Length-1) 即将数据化为二进制进行与运算，而不是取余运算。这样计算机直接运算二进制数据，效率更高。但是 JavaScript 在进行较大数据的与运算时会出现问题，所以我们使用 JavaScript 实现哈希化时采用取余运算。

封装哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
function HashTable () {
   // 属性
  this.storage = [] //存放的数组
  this.count = 0  // 当前存放的长度
  this.limit = 7  //当前数组的长度
   /* 哈希函数 */
  HashTable.prototype.hashFun =  function (str,size) {
    // 定义哈希值
    let hashCode = 0

    // 使用霍纳算法（秦九韶算法）计算哈希值
    for( let i = 0;i<str.length ;i++ ){
      hashCode = 37 * hashCode + str.charCodeAt(i)
    }
    // 取余操作
    let index= hashCode % size
    // 返回哈希化后的值
    return index
  }

   // 方法
  // 插入或者修改操作方法
  HashTable.prototype.put = function (key,value) {
    // 根据key与value获取对应的index
    let index = this.hashFun(key, this.limit)
    // 根据index，取出对应位置下的bucket
    let bucket = this.storage[index]
    // 判断数组该位置下是否存在元素
    if(!bucket) {
      bucket = []
      this.storage[index] = bucket
    }
    // 判断是否修改数据
    for(let i=0;i<bucket.length;i++){
      let tuple = bucket[i]
      if(tuple[0] == key){
        tuple[1] = value
        return true
      }
    }
    // 插入操作
    bucket.push([key,value])
    this.count +=1
    let newPrime = this.getPrime(this.limit*2)
    if(this.count > this.limit *0.75){
      this.resize(newPrime)
    }
  }

  // 获取操作
  HashTable.prototype.get = function(key) {
    // 计算传入的key的对应位置
    let index = this.hashFun(key,this.limit)
    // 根据计算得到的位置，取出bucket
    let bucket = this.storage[index]
    // 判断取出的bucket
    if(!bucket) {
      return null
    }else{
      for(let i=0;i<bucket.length;i++) {
        let tuple=bucket[i]
        if(tuple[0]==key) {
          return tuple[1]
        }
      }
      return null
    }
  } 
  /* 判断质数 */
  HashTable.prototype.isPrime = function(number) {
    for(let i =2 ; i<=Math.sqrt(number);i++) {
      if(number % i==0){
        return false
      }
    }
    return number
  }
  // 获取质数的方法
  HashTable.prototype.getPrime = function (number) {
    if(number<7){
      number = 7
    }
    while(!this.isPrime(number)){
      number +=1
    }
   return number

  }
  // 删除操作
  HashTable.prototype.remove = function(key) {
    // 计算传入key所在位置
    let index = this.hashFun(key,this.limit)
    // 根据计算的位置，取出
    let bucket = this.storage[index]
    // 判断是否为空
    if(!bucket) {
      return false
    }else {
      for (let i=0 ;i<bucket.length ;i++) {
        let tuple = bucket[i]
        if(tuple[0] ==key) {
          bucket.splice(i,1)
          this.count -=1
          // 判断缩小容量
          if(this.limit>7 && this.count <this.limit *0.25){
            let newLimit = this.getPrime(Math.floor(this.limit / 2))
            this.resize(newLimit)
          }
          return tuple[1]
        }
      }
      return false
  }
  }

  // 判断是否为空
  HashTable.prototype.isEmpty = function (){
    return this.count ==0
  }
  // 获取哈希表中的个数
  HashTable.prototype.size = function () {
    return this.count
  }
  // 哈希表扩容
  HashTable.prototype.resize = function (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) {
        continue
      }
     // 取出数据
     for(let i=0;i<bucket.length;i++){
       // 调用哈希函数方法
       let tuple = bucket[i]
       let index = new this.hashFun(tuple[0],this.limit)
       // 调用添加方法
       this.put(tuple[0],tuple[1])
     }
    }
  }
}

测试哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 测试哈希函数 */
const hashtable = new HashTable()
hashtable.put('nba',18)
// hashtable.put('cba',19)
// hashtable.put('cuba',20)
hashtable.put('nbl',21)
// hashtable.put('dba',22)
hashtable.put('gba',23)

// hashtable.put('dba',20)
// hashtable.put('dba',80)
console.log(hashtable.remove('nbl'))

// hashtable.resize(17)
console.log(hashtable)
console.log(hashtable.get('nba'))