# 哈希表的封装
# 哈希表
这里实现链地址法来实现哈希表：
实现的哈希表（基于storage的数组）每个index 对应的是一个数组（bucket）（或者链表）
bucket 中存放什么呢？最好是将 key 和 value 都放进去，格式是这样
[ [ [k, v], [k, v] ], [ [k, v], [k, v], [k, v] ], [ [k, v] ] ]
# 代码解析
- storage 作为数组，数组中存放相关的元素
- count 表示当前已经存了多少数据
- limit 用于标记数组中可以放多少个元素
// 哈希表
class HashTable {
constructor() {
// 哈希表存储数据的变量
this.storage = []
// 当前存放的元素个数
this.count = 0
// 用于标记数组中一共可以存放多少个元素
this.limit = 7
}
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 常见操作
- hashFunc(str, size) 哈希函数
- put(key, value) 插入或修改操作
- get(key) 获取哈希表中特定位置的元素
- remove(key) 删除哈希表中特定位置的元素
- isEmpty() 如果哈希表中不包含任何元素，返回 trun，如果哈希表长度大于 0 则返回 false
- size() 返回哈希表包含的元素个数
- resize(value) 对哈希表进行扩容操作
- isPrime(num) 判断某个数字是否是质数
- getPrime(num) 获取一个质数
# 哈希函数
// 1.哈希函数
hashFn(str, size = 7) {
// 一个质数
const PRIME = 31;
// 1-1.定义hasCode变量
let hashCode = 0
// 1-2.霍纳算法计算 hashCode 的值
for (let i = 0; i < str.length; i++) {
hashCode = PRIME * hashCode + str.charCodeAt(i)
}
// 1-3.取余操作
let index = hashCode % size
return index
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# put 插入&修改
哈希表的插入和修改是同一个函数，因为当使用者传入一个<key, value> 时，
如果原来不存在改 key， 那么执行的是插入操作。如果已经存在，则执行的是修改操作。
实现思路：
- 根据传入的 key 获取对应的 hashCode , 也就是数组的 index
- 从哈希表的 index 位置中取出桶（另外一个数组）
- 查看上一步的 bucket 是否为 null (为 null 表示之前在该位置没有放置过任何的内容，那么就新建一个数组)
- 查看是否之前已经放置 key 对应的 value
- 如果放置过，那么就依次替换，而不是插入新的数据
- 使用一个变量 override 来记录是否是修改操作
- 如果不是修改操作，那么插入新的数据
- 在 bucket 中 push 新的
<key, value>即可 - 注意 这里需要将 count + 1 ，数据增加了一条
- 在 bucket 中 push 新的
// 2.put(key, value) 插入或修改操作
put (key, value) {
// 2-1.根据key获取对应的index
const index = this.hashFn(key, this.limit)
// 2-2.根据index获取bucket
let bucket = this.storage[index]
// 2-3.判断该 bucket 是否为空
if (bucket == null) {
bucket = []
this.storage[index] = bucket
}
// 2-4.判断是否是修改数据, 哈希表里有值就表示修改
// 值已经存在了，表示需要修改，重新赋值
for (let i = 0; i < bucket.length; i++) {
let tuple = bucket[i]
if (tuple[0] === key) {
tuple[1] = value
return
}
}
// 2-5.添加数据
bucket.push([key, value])
this.count += 1
// 2-6.判断是否需要扩容
if (this.count > this.limit * 0.75) {
let newSize = this.limit * 2
let newPrime = this.getPrime(newSize)
this.resize(newPrime)
}
}
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
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
# get 获取元素
实现思路：
- 根据 key 获取对应的 index
- 根据 index 获取 bucket
- 判断 bucket 是否为 null ，如果为 null 返回 null
- 线性查找 bucket 中每个 key 是否等于传入的 key ，如果等于返回对应的 value
- 遍历结束后，依然没有找到对应的 key 直接返回 null
// 3.get(key) 获取哈希表中特定位置的元素
get(key) {
// 3-1.根据key获取对应的index
let index = this.hashFn(key, this.limit)
// 3-2.根据index获取对应的bucket
let bucket = this.storage[index]
// 3-3.判断bucket是否为空
if (bucket === null) {
return null
}
// 3-4.有bucket,进行线性查找
for (let i = 0; i < bucket.length; i++) {
let tuple = bucket[i]
if (tuple[0] === key) {
return tuple[1]
}
}
// 3-5.依然没有找到数据
return null
}
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# remove 删除元素
实现思路：
- 根据 key 获取对应的 index
- 根据 index 获取 bucket
- 判断 bucket 是否存在，如果不存在，那么直接返回null
- 线性查找 bucket 寻找对应数据，并且删除
- 依然没有找到，返回 null
// 4.remove(key) 删除哈希表中特定位置的元素
remove (key) {
// 4-1.根据key获取对应的index
let index = this.hashFn(key, this.limit)
// 4-2.根据index 获取对应的bucket
let bucket = this.storage[index]
// 4-3.判断bucket是否为null
if (bucket === null) {
return null
}
// 4-4.有bucket 线性查找，并且删除
for (let i = 0; i < bucket.length; i++) {
let tuple = bucket[i]
if (tuple[0] === key) {
bucket.splice(i, 1)
this.count--
return tuple[1]
// 缩小容量
// 根据装填因子的大小，判断是否要进行哈希表压缩
if (this.limit > 7 && this.count < this.limit * 0.25) {
let newSize = Math.floor(this.limit / 2)
let newPrime = this.getPrime(newSize)
this.resize(newPrime)
}
}
}
// 4-5.依然没有找到
return null
}
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
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
# 其他方法
// 5.判断是否为空
HashTable.prototype.isEmpty = function () {
return this.count === 0
}
// 6.获取个数
HashTable.prototype.size = function () {
return this.count
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 扩容思想
目前是将所有的数据项放在了长度为 7 的数组中，使用的是链地址法，
装填因子 loadFactor（length / count） 可以大于 1，
所以这个哈希表可以无限制插入数据，但是随着数据的增多，每个 index 对应的 bucket 会越来越长，就会造成效率的降低。
所以需要在合适的情况下对数组进行扩容。
什么情况下需要扩容呢？
比较常见的情况是 loadFactor（装填因子） < 0.75 的时候进行扩容
如何进行扩容？
扩容可以简单的将容量增大两倍，但是这种情况下，所有的数据项一定要进行修改（重新调用哈希函数，来获取最新的位置）
比如 hashCode = 12 的数据项，在 length = 8 的时候， index = 5， 扩容长度到 16 的时候呢？ index = 12
重新对数据项进行修改，是一个耗时的过程，但是如果数组需要扩容，这个过程是必须的。。
# 哈希表扩容
实现思路：
- 定义一个变量，比如 oldStorage 指向原来的 storage
- 创建一个新的容量更大的数组，让 this.storage 指向它
- 将 oldStorage 中的每一个 bucket 中的每一个数据取出来依次添加到 this.storage 指向的新数组中
// 7.resize(newLimit) 对哈希表进行扩容操作
resize (newLimit) {
// 7-1.保存旧数组内容
let oldStorage = this.storage
// 7-2.重置所有的属性
this.storage = []
this.count = 0
this.limit = newLimit
// 7-3.遍历 oldStorage 中所有的 bucket
for (let i = 0; i < oldStorage.length; i++) {
// 7-3.1取出对应滚动 bucket
let bucket = oldStorage[i]
// 7-3.2判断bucket是否为null
if (bucket === null) {
continue;
}
// 7-3.3bucket 中所有的数据，那么取出数据，重新插入
for (let j = 0; j < bucket.length; j++) {
let tuple = bucket[j]
this.put(tuple[0], tuple[1])
}
}
}
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
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
# 容量质数
质数的特点：
- 质数也称为素数
- 质数表示大于 1 的自然数中，只能被 1 和自己整除的数
- 只能被 1 和自己整除，不能被 2 ~ num - 1 之间的数字整除
对于某个数 n, 其实并不需要从 2 依次判断 到 num - 1
一个数若可以进行因数分解 ，那么分解时得到的两个数一定是一个小于等于 sqrt(n) 另一个大于等于sqrt(n)
比如 16 2 * 8 = 16 sqrt(16) = 4 * 4 2 小于 4 8 大于 4
所以不需要从 2 依次判断都 num - 1, 只需要遍历到 sqrt(num) 即可。
// 8.isPrime(num) 判断某个数字是否是质数
isPrime (num) {
if (num <= 1) {
return false
}
// 8-1.获取 num 的平方根
let temp = parseInt(Math.sqrt(num))
// 8-2.循环判断
for (let i = 2; i <= temp; i++) {
if (num % i === 0) {
return false
}
}
return true
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 获取一个质数
// 9.getPrime(num) 获取一个质数
getPrime (num) {
// 14 -> 17
while (!this.isPrime(num)) {
num++
}
return num
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 完整代码
class HashTable {
constructor() {
// 哈希表存储数据的变量
this.storage = []
// 当前存放的元素个数
this.count = 0
// 用于标记数组中一共可以存放多少个元素
this.limit = 7
}
// 1.哈希函数
hashFn(str, size = 7) {
// 一个质数
const PRIME = 31;
// 1-1.定义hasCode变量
let hashCode = 0
// 1-2.霍纳算法计算 hashCode 的值
for (let i = 0; i < str.length; i++) {
hashCode = PRIME * hashCode + str.charCodeAt(i)
}
// 1-3.取余操作
let index = hashCode % size
return index
}
// 2.put(key, value) 插入或修改操作
put (key, value) {
// 2-1.根据key获取对应的index
const index = this.hashFn(key, this.limit)
// 2-2.根据index获取bucket
let bucket = this.storage[index]
// 2-3.判断该 bucket 是否为空
if (bucket == null) {
bucket = []
this.storage[index] = bucket
}
// 2-4.判断是否是修改数据, 哈希表里有值就表示修改
// 值已经存在了，表示需要修改，重新赋值
for (let i = 0; i < bucket.length; i++) {
let tuple = bucket[i]
if (tuple[0] === key) {
tuple[1] = value
return
}
}
// 2-5.添加数据
bucket.push([key, value])
this.count += 1
// 2-6.判断是否需要扩容
if (this.count > this.limit * 0.75) {
let newSize = this.limit * 2
let newPrime = this.getPrime(newSize)
this.resize(newPrime)
}
}
// 3.get(key) 获取哈希表中特定位置的元素
get(key) {
// 3-1.根据key获取对应的index
let index = this.hashFn(key, this.limit)
// 3-2.根据index获取对应的bucket
let bucket = this.storage[index]
// 3-3.判断bucket是否为空
if (bucket === null) {
return null
}
// 3-4.有bucket,进行线性查找
for (let i = 0; i < bucket.length; i++) {
let tuple = bucket[i]
if (tuple[0] === key) {
return tuple[1]
}
}
// 3-5.依然没有找到数据
return null
}
// 4.remove(key) 删除哈希表中特定位置的元素
remove (key) {
// 4-1.根据key获取对应的index
let index = this.hashFn(key, this.limit)
// 4-2.根据index 获取对应的bucket
let bucket = this.storage[index]
// 4-3.判断bucket是否为null
if (bucket === null) {
return null
}
// 4-4.有bucket 线性查找，并且删除
for (let i = 0; i < bucket.length; i++) {
let tuple = bucket[i]
if (tuple[0] === key) {
bucket.splice(i, 1)
this.count--
return tuple[1]
// 缩小容量
// 根据装填因子的大小，判断是否要进行哈希表压缩
if (this.limit > 7 && this.count < this.limit * 0.25) {
let newSize = Math.floor(this.limit / 2)
let newPrime = this.getPrime(newSize)
this.resize(newPrime)
}
}
}
// 4-5.依然没有找到
return null
}
// 5.isEmpty() 如果哈希表中不包含任何元素，返回 trun，如果哈希表长度大于 0 则返回 false
isEmpty () {
return this.count === 0
}
// 6.size() 返回哈希表包含的元素个数
size () {
return this.count
}
// 7.resize(newLimit) 对哈希表进行扩容操作
resize (newLimit) {
// 7-1.保存旧数组内容
let oldStorage = this.storage
// 7-2.重置所有的属性
this.storage = []
this.count = 0
this.limit = newLimit
// 7-3.遍历 oldStorage 中所有的 bucket
for (let i = 0; i < oldStorage.length; i++) {
// 7-3.1取出对应的 bucket
let bucket = oldStorage[i]
// 7-3.2判断bucket是否为null
if (bucket === null) {
continue;
}
// 7-3.3bucket 中所有的数据，那么取出数据，重新插入
for (let j = 0; j < bucket.length; j++) {
let tuple = bucket[j]
this.put(tuple[0], tuple[1])
}
}
}
// 8.isPrime(num) 判断某个数字是否是质数
isPrime (num) {
if (num <= 1) {
return false
}
// 8-1.获取 num 的平方根
let temp = parseInt(Math.sqrt(num))
// 8-2.循环判断 , 不需要到 num -1 ，只需要遍历到sqrt(n)即可
for (let i = 2; i <= temp; i++) {
if (num % i === 0) {
return false
}
}
return true
}
// 9.getPrime(num) 获取一个质数
getPrime (num) {
// 14 -> 17 挨个找，直到找到位置
while (!this.isPrime(num)) {
num++
}
return num
}
}
let ht = new HashTable()
ht.put('abc', '111')
ht.put('bc', '222')
ht.put('bb', '333')
ht.put('cc', '444')
ht.put('tt', '555')
ht.put('tyu', '666')
ht.put('opq', '777')
ht.put('ggg', '888')
ht.put('tyu', '999')
ht.put('iop', '000')
console.log(ht, '测试put方法')
console.log(ht.get('iop'))
// console.log(ht.remove('abc'), ht, '测试remove')
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
186
187
188
189
190
191
192
193
194
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
186
187
188
189
190
191
192
193
194