抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

哈希表

JS数据结构

发布于：2023年5月9日

次浏览

一：什么是哈希表？

哈希表是一种常见的数据结构，它通过将键映射到值的方式来存储和组织数据。具体来说，哈希表使用哈希函数将每个键映射到一个索引（在数组中的位置），然后将该键值对存储在该索引处。当需要检索某个键的值时，哈希表会再次使用哈希函数将该键转换为相应的索引，并在该索引处查找其关联的值。由于哈希函数通常能够较快地计算出索引，因此哈希表在插入和查找操作上具有很高的效率。

在 JavaScript 中，哈希表通常是通过对象来实现的。对象的属性名就是键，而属性值则是与之关联的值。然而，在某些情况下，如果需要更多的控制权或者需要处理大量的数据，可以使用第三方库或自己实现哈希表数据结构。

二：哈希化

哈希化是将任意长度的消息（例如一个字符串、文件或数据记录）转换为固定长度的值（通常是较小的整数），该值称为哈希值。哈希函数执行哈希化操作，它将输入键映射到唯一的索引值，这个索引值可以用来在哈希表中查找对应的值。

哈希化具有以下特点：

  1. 哈希化是单向的：从哈希值无法推断出原始输入值，而且很难找到两个不同的输入值生成相同的哈希值。
  2. 哈希化是确定性的：对于给定的输入，哈希函数总是返回相同的哈希值。这个特性使得哈希表能够高效地进行查找和插入等操作。
  3. 哈希化是均匀的：好的哈希函数应该将输入数据均匀地分布在哈希空间中，以避免碰撞（即两个不同的输入值生成相同的哈希值）。

总而言之

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

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

哈希表：最终将数据插入到的这个数组，对整个结构的封装，我们就称之为是一个哈希表

三：哈希函数

好的哈希函数应该具备：

快速的计算：哈希表的优势就在于效率，所以快速获取到对应的hashCode非常重要。我们需要通过快速的计算来获取到元素对应的hashCode。

均匀的分布：哈希表中，无论是链地址法还是开放地址法，当多个元素映射到同一个位置的时候，都会影响效率，所以，优秀的哈希函数应该尽可能将元素映射到不同的位置，让元素在哈希表中均匀的分布。

哈希函数设计

  • 将字符串转换成比较大的数字：hashCode
  • 将大的数字hashCode压缩到数组范围之内
  • 传入两个参数：str 字符串；size 数组大小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
function hashFunc(str, size) { //参数1 字符串 参数2 数组大小
       //1.定义hashcode
       let hashCode = 0;

       //2.霍纳法则，来计算hashCode的值
       // 将str转成Unicode编码
       for (let i = 0; i <str.length ; i++) {
           //  哈希表的长度使用质数 43 47 47 31 等等都可，目前最多使用的还是37
           hashCode = 37*hashCode + str.charCodeAt(i)
       }
       //3.取余操作
       let index = hashCode % size
       return index
   }

四：实现哈希表（链地址法）

1.逻辑

实现的哈希表（基于storage的数组）每个index对应的是一个是数组（bucket）。
bucket中存放什么呢？我们最好将key和value都放进去，我们继续使用一个数组
最终我们的哈希表的数据格式是这样：[[[k,v],[k,v],[k,v]],[[k,v],[k,v]],[[k,v]]]

2.扩容和扩容时机

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

扩容时机

比较常见的情况是填装因子 > 0.75 的时候扩容

3.属性和方法

定义属性：

storage： 作为我们的数组，数组中存放相关的元素；
count：表示当前数组中已经存放了多少数据，用于计算填装因子的值，以便扩容等操作；
limit：用于标记数组的长度；

定义方法：

  • put(key,value)：新增和修改方法。哈希表的插入和修改是同一个函数,因为，当使用者传入一个<key,value>时，如果原来不存在该key，那么就是插入操作；如果已经存在该key，那么就是修改操作
    • 根据传入的key获取对应的hashCode，也就是数组的index；

  • 从哈希表的index位置中取出bucket(一个数组)；

  • 查看上一步取出的数组是否为null ，如果为null，则表示之前在该位置没有放置过任何的内容，那么就新建一个数组[]；

  • 查看是否之前已经放置过key对应的value：如果放置过，那么就是依次替换操作，而不是插入新数据；
    如果不是修改操作，那么插入新的数据 ：在数组中push新的[key,value]即可。注意： 这里需要将count+1，因为数据增加了一项。

  • 最后判断是否需要扩容： loadFactor > 0.75 的时候扩容

    是则加一再判断，直到是质数，则跳出返回这个质数

  • get(key)：获取数据方法
    • 根据传入的key获取对应的hashCode，也就是数组的index；
    • 根据index拿到对应的bucket；
    • 判断bucket是否为null，如果是null则返回null；
    • 如果不是null，则遍历bucket，判断里面是否包含key对应的数据，有则返回；
    • 如果bucket中没有找到，那么返回null；
  • remove(key)：删除方法
    • 根据传入的key获取对应的hashCode，也就是数组的index；
    • 根据index拿到对应的bucket；
    • 判断bucket是否存在，如果不存在则返回null；
    • 如果存在则遍历bucket，找到里面包含key对应的数据，有则删除，并且数量减一，同时需要判断是否需要缩容，返回被删除的数据；
    • 如果不存在则返回null
  • isEmpty()：判断是否为空
    • 返回 count是否等于0
  • size()：获取哈希表大小
    • 返回count值
  • resize(newLimit)：扩容和缩容方法
    • 先存储原数组
    • 原属性重置
    • 遍历原数组，把里面每个索引中的每个bucket中的每一个值都取出来重新添加进扩容后的数组中
  • isPrime(num)：判断是否为质数
    • 将传入的num开平方根，然后遍历2和开平方根之后的值之间的数值，如果传入的num值可以和这中间一个值除尽，那么就跳出返回false不是质数。遍历结束返回true，是质数。
  • getPrime(num)：获取质数size
    • 循环遍历判断传入的值是否为质数，如果不

4.代码

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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
//哈希表
   function HashTable ()
   {
     //属性
     //哈希表的基准数组
     this.storage = []
     //哈希表中的元素总数，[key,val]
     this.count = 0
     //基准数组的大小
     this.limit = 7

     //哈希函数： 将str字符串转换成大的数字hashcode，再将大的数字压缩到数组大小(limit)范围以内index
     HashTable.prototype.hashFunc = function (str, size)
     {
       //1.定义hashcode
       let hashCode = 0

       //2.霍纳法则来计算hashcode
       //将str转换成Unicode编码
       for (let i = 0; i < str.length; i++) {
         //哈希表的长度使用质数43 47 等等，
         hashCode = 37 * hashCode + str.charCodeAt(i)
       }

       //3.取余操作
       let index = hashCode % size
       return index
     }

     //put方法，添加&修改：如果storage中原先不存在key即插入添加操作，如果存在即修改操作
     HashTable.prototype.put = function (key, value)
     {
       //1.根据key调用哈希函数来计算index值
       let index = this.hashFunc(key, this.limit)
       //2.根据索引值index获取在storage中对应的bucket数组
       let bucket = this.storage[index]
       //3.判断bucket是否为null,如果是null，那就创建[]
       if (bucket === null || bucket === undefined) {
         bucket = []
         //并且storage[index]创建[]
         this.storage[index] = bucket
       }
       //4.bucket不为空，遍历bucket，找到对应key，如果存在key，那就修改，不存在即添加插入
       //拉链法中的元素存储结构为，[[[k,v],[k2,v2],[k3,v3]]],即bucket数组，[[k,v],[k2,v2],[k3,v3]]
       for (let i = 0; i < bucket.length; i++) {
         let tuple = bucket[i]
         if (tuple[0] === key) {
           tuple[1] = value
           return
         }
       }
       //5.如果没有跳出，那就说明没有找到对应的key,那就添加
       bucket.push([key, value])
       //6.计数器this.count++
       this.count++
       //7.判断是否需要扩容 loadFactor(填装因子) > 0.75时候扩容
       if (this.count > this.limit * 0.75) {
         //扩容后新的数组大小为原来的两倍
         const newSize = this.limit * 2
         //getPrime获取质数方法，目的为了使哈希表的长度为质数
         const primeSize = this.getPrime(newSize)
         //调用resize扩容或缩容的方法
         this.resize(primeSize)
       }
     }
     //get方法：通过key来获取哈希table中的value值
     HashTable.prototype.get = function (key)
     {
       //1.通过key来调用哈希函数获取index
       let index = this.hashFunc(key, this.limit)
       //2.通过index来获取到对应的bucket
       let bucket = this.storage[index]
       //3.判断bucket是否为空
       if (bucket === null || bucket === undefined) {
         return null
       }
       //4.如果存在遍历获取
       for (let i = 0; i < bucket.length; i++) {
         let tuple = bucket[i]
         if (tuple[0] === key) {
           return tuple[1]
         }
       }
       //5.如果在bucket中没有找到，那么返回null
       return null
     }
     //remove方法：删除方法
     HashTable.prototype.remove = function (key)
     {
       //1.通过Key来调用哈希函数获取index
       let index = this.hashFunc(key, this.limit)
       //2.通过Index获取对应的bucket
       let bucket = this.storage[index]
       //3.判断bucket是否为空
       if (bucket === null || bucket === undefined) {
         return null
       }
       //4.如果存在就遍历查抄，删除
       for (let i = 0; i < bucket.length; i++) {
         let tuple = bucket[i]
         if (tuple[0] === key) {
           bucket.splice(i, 1)
           this.count--
           //判断是否需要缩容
           if (this.count < this.limit * 0.25) {
             const newSize = Math.floor(this.limit / 2)
             const primeSize = this.getPrime(newSize)
             this.resize(primeSize)
           }
           return tuple[1]
         }
       }
       //5.如果bucket中不存在返回null
       return null

     }

     //isEmpty 判断是否为空方法
     HashTable.prototype.isEmpyt = function ()
     {
       return this.count === 0
     }

     //size方法 获取size的方法
     HashTable.prototype.size = function ()
     {
       return this.count
     }

     //resize方法 扩容或者缩容的方法
     HashTable.prototype.resize = function (newLimit)
     {
       //存储原数组
       const oldStorage = this.storage
       //原属性重置
       this.storage = []
       this.limit = newLimit
       this.count = 0
       //遍历原数组，把每个索引的bucket中的每个值都取出来添加到扩容或者缩容的数组中
       for (let i = 0; i < oldStorage.length; i++) {
         //获取到bucket
         const bucket = oldStorage[i]
         //判断bucket是否为空
         if (bucket === null || bucket === undefined) {
           continue
         }
         //遍历每个bucket的每个值
         for (let j = 0; j < bucket.length; j++) {
           let tuple = bucket[j]
           this.put(tuple[0], tuple[1])
         }
       }
     }

     //isPrime方法  判断是否是质数
     HashTable.prototype.isPrime = function (num)
     {
       const temp = parseInt(Math.sqrt(num))
       for (let i = 2; i < temp; i++) {
         if (temp % 2 === 0) {
           return false
         }
       }
       return true
     }

     //getPrime 获取到质数size
     HashTable.prototype.getPrime = function (num)
     {
       while (!this.isPrime(num)) {
         num++
       }
       return num
     }

   }

   const hashTable = new HashTable()
   hashTable.put('abc', 18)
   hashTable.put('aaa', 20)
   hashTable.put('vvv', 1111)
   console.log(hashTable);
   console.log(hashTable.get('vvv'));
   hashTable.remove('aaa')
   console.log(hashTable);

image-20230522212904108

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://awesomeboy.cn/2023/05/09/哈希表/

更新于：2023年8月5日

JS

数据结构

评论