Repository navigation
Expand file tree
/
Copy pathHashTable.js
More file actions
175 lines (162 loc) · 4.58 KB
/
Copy pathHashTable.js
File metadata and controls
175 lines (162 loc) · 4.58 KB
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
/*
* 定义散列表
*/
module.exports = function HashTable() {
// 定义属性
this.storage = [];
this.count = 0;
this.limit = 8;
this.isPrime = isPrime;
this.getPrime = getPrime;
this.hashFunc = hashFunc;
this.put = put;
this.get = get;
this.remove = remove;
this.size = size;
this.isEmpty = isEmpty;
this.resize = resize;
}
// 判断是否是质数
function isPrime(num) {
var temp = parseInt(Math.sqrt(num));
// 循环判断
for (var i = 2; i <= temp; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
// 获取质数
function getPrime(num) {
while (!isPrime(num)) {
num++;
}
return num;
}
// 哈希函数
function hashFunc(str, max) {
// 初始化hashCode的值
var hashCode = 0;
// 霍纳算法, 来计算hashCode的数值
for (var i = 0; i < str.length; i++) {
hashCode = 37 * hashCode + str.charCodeAt(i);
}
// 取模运算
hashCode = hashCode % max;
return hashCode;
}
// 插入数据方法
function put(key, value) {
// 获取key对应的index
var index = this.hashFunc(key, this.limit);
// 取出数组(也可以使用链表)
// 数组中放置数据的方式: [[ [k,v], [k,v], [k,v] ] , [ [k,v], [k,v] ], [ [k,v] ] ]
var bucket = this.storage[index];
// 判断这个数组是否存在
if (bucket === undefined) {
// 如果不存在，则创建桶
bucket = [];
this.storage[index] = bucket;
}
// 判断传递的数据是新增还是修改原来的值.
var override = false
for (var i = 0; i < bucket.length; i++) {
var tuple = bucket[i];
if (tuple[0] === key) {
// 匹配到数据，则进行修改
tuple[1] = value;
override = true;
}
}
// 如果前面没有匹配到数据，则说明是新增的数据
if (!override) {
// 桶中加入新增数据
bucket.push([key, value]);
this.count++;
// 如果数量超过限制的75%，则要进行扩容
if (this.count > this.limit * 0.75) {
// 扩容大小近似于原来的两倍
var primeNum = this.getPrime(this.limit * 2);
this.resize(primeNum);
}
}
}
// 获取存放的数据
function get(key) {
// 获取key对应的index;
var index = this.hashFunc(key, this.limit);
// 获取对应的bucket
var bucket = this.storage[index];
// 3.如果bucket为null, 那么说明这个位置没有数据
if (bucket == null) {
return null;
}
// 有bucket, 判断是否有对应的key
for (var i = 0; i < bucket.length; i++) {
var tuple = bucket[i];
if (tuple[0] === key) {
return tuple[1];
}
}
// 没有找到, return null
return null;
}
// 删除数据
function remove(key) {
// 获取key对应的index
var index = this.hashFunc(key, this.limit);
// 获取对应的bucket
var bucket = this.storage[index];
// 判断同是否为null, 为null则说明没有对应的数据
if (bucket == null) {
return null;
}
// 遍历bucket, 寻找对应的数据
for (var i = 0; i < bucket.length; i++) {
var tuple = bucket[i];
if (tuple[0] === key) {
bucket.splice(i, 1);
this.count--;
// 当限制量大于7，且小于限制的25%
// 缩小数组的容量
if (this.limit > 7 && this.count < this.limit * 0.25) {
var primeNum = this.getPrime(Math.floor(this.limit / 2));
this.resize(primeNum);
}
}
return tuple[1];
}
// 5.来到该位置, 说明没有对应的数据, 那么返回null
return null;
}
// isEmpty方法
function isEmpty() {
return this.count === 0;
}
// size方法
function size() {
return this.count;
}
// 哈希表扩容
function resize(newLimit) {
// 保存旧的数组内容
var oldStorage = this.storage;
// 重置属性
this.limit = newLimit;
this.count = 0;
this.storage = [];
// 由于表大小发生变化，哈希值要重新计算
// 遍历旧数组中的所有数据项, 并且重新插入到哈希表中
oldStorage.forEach(function (bucket) {
// bucket为null, 说明这里面没有数据
if (bucket == null) {
return;
}
// bucket中有数据, 那么将里面的数据重新哈希化插入
for (var i = 0; i < bucket.length; i++) {
var tuple = bucket[i]
this.put(tuple[0], tuple[1])
}
}).bind(this);
}