Skip to content

Commit 21b4016

Browse files
taokexiataokexia
committed
add hashtable
1 parent 442c595 commit 21b4016

4 files changed

Lines changed: 215 additions & 41 deletions

File tree

‎JavaScript/HashTable.js‎

Lines changed: 0 additions & 41 deletions
This file was deleted.

‎JavaScript/HashTable/HashFunc.js‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
// 哈希算法
2+
module.exports = function hashFunc(str, max) {
3+
// 初始化hashCode
4+
var hashCode = 0;
5+
6+
// 用霍纳算法, 来计算hashCode的数值
7+
for(var i = 0; i < str.length; i++) {
8+
hashCode = 37 * hashCode + str.charCodeAt(i);
9+
}
10+
11+
// 取模运算
12+
hashCode = hashCode % max;
13+
return hashCode;
14+
}

‎JavaScript/HashTable/HashTable.js‎

Lines changed: 175 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,175 @@
1+
/*
2+
* 定义散列表
3+
*/
4+
module.exports = function HashTable() {
5+
// 定义属性
6+
this.storage = [];
7+
this.count = 0;
8+
this.limit = 8;
9+
10+
this.isPrime = isPrime;
11+
this.getPrime = getPrime;
12+
this.hashFunc = hashFunc;
13+
this.put = put;
14+
this.get = get;
15+
this.remove = remove;
16+
this.size = size;
17+
this.isEmpty = isEmpty;
18+
this.resize = resize;
19+
}
20+
21+
// 判断是否是质数
22+
function isPrime(num) {
23+
var temp = parseInt(Math.sqrt(num));
24+
// 循环判断
25+
for (var i = 2; i <= temp; i++) {
26+
if (num % i == 0) {
27+
return false;
28+
}
29+
}
30+
return true;
31+
}
32+
// 获取质数
33+
function getPrime(num) {
34+
while (!isPrime(num)) {
35+
num++;
36+
}
37+
return num;
38+
}
39+
40+
// 哈希函数
41+
function hashFunc(str, max) {
42+
// 初始化hashCode的值
43+
var hashCode = 0;
44+
// 霍纳算法, 来计算hashCode的数值
45+
for (var i = 0; i < str.length; i++) {
46+
hashCode = 37 * hashCode + str.charCodeAt(i);
47+
}
48+
// 取模运算
49+
hashCode = hashCode % max;
50+
return hashCode;
51+
}
52+
53+
// 插入数据方法
54+
function put(key, value) {
55+
// 获取key对应的index
56+
var index = this.hashFunc(key, this.limit);
57+
// 取出数组(也可以使用链表)
58+
// 数组中放置数据的方式: [[ [k,v], [k,v], [k,v] ] , [ [k,v], [k,v] ], [ [k,v] ] ]
59+
var bucket = this.storage[index];
60+
// 判断这个数组是否存在
61+
if (bucket === undefined) {
62+
// 如果不存在，则创建桶
63+
bucket = [];
64+
this.storage[index] = bucket;
65+
}
66+
// 判断传递的数据是新增还是修改原来的值.
67+
var override = false
68+
for (var i = 0; i < bucket.length; i++) {
69+
var tuple = bucket[i];
70+
if (tuple[0] === key) {
71+
// 匹配到数据，则进行修改
72+
tuple[1] = value;
73+
override = true;
74+
}
75+
}
76+
// 如果前面没有匹配到数据，则说明是新增的数据
77+
if (!override) {
78+
// 桶中加入新增数据
79+
bucket.push([key, value]);
80+
this.count++;
81+
// 如果数量超过限制的75%，则要进行扩容
82+
if (this.count > this.limit * 0.75) {
83+
// 扩容大小近似于原来的两倍
84+
var primeNum = this.getPrime(this.limit * 2);
85+
this.resize(primeNum);
86+
}
87+
}
88+
}
89+
90+
// 获取存放的数据
91+
function get(key) {
92+
// 获取key对应的index;
93+
var index = this.hashFunc(key, this.limit);
94+
// 获取对应的bucket
95+
var bucket = this.storage[index];
96+
// 3.如果bucket为null, 那么说明这个位置没有数据
97+
if (bucket == null) {
98+
return null;
99+
}
100+
// 有bucket, 判断是否有对应的key
101+
for (var i = 0; i < bucket.length; i++) {
102+
var tuple = bucket[i];
103+
if (tuple[0] === key) {
104+
return tuple[1];
105+
}
106+
}
107+
// 没有找到, return null
108+
return null;
109+
}
110+
111+
// 删除数据
112+
function remove(key) {
113+
// 获取key对应的index
114+
var index = this.hashFunc(key, this.limit);
115+
// 获取对应的bucket
116+
var bucket = this.storage[index];
117+
// 判断同是否为null, 为null则说明没有对应的数据
118+
if (bucket == null) {
119+
return null;
120+
}
121+
// 遍历bucket, 寻找对应的数据
122+
for (var i = 0; i < bucket.length; i++) {
123+
var tuple = bucket[i];
124+
if (tuple[0] === key) {
125+
bucket.splice(i, 1);
126+
this.count--;
127+
// 当限制量大于7，且小于限制的25%
128+
// 缩小数组的容量
129+
if (this.limit > 7 && this.count < this.limit * 0.25) {
130+
var primeNum = this.getPrime(Math.floor(this.limit / 2));
131+
this.resize(primeNum);
132+
}
133+
}
134+
return tuple[1];
135+
}
136+
// 5.来到该位置, 说明没有对应的数据, 那么返回null
137+
return null;
138+
}
139+
140+
// isEmpty方法
141+
function isEmpty() {
142+
return this.count === 0;
143+
}
144+
145+
// size方法
146+
function size() {
147+
return this.count;
148+
}
149+
150+
// 哈希表扩容
151+
function resize(newLimit) {
152+
// 保存旧的数组内容
153+
var oldStorage = this.storage;
154+
// 重置属性
155+
this.limit = newLimit;
156+
this.count = 0;
157+
this.storage = [];
158+
// 由于表大小发生变化，哈希值要重新计算
159+
// 遍历旧数组中的所有数据项, 并且重新插入到哈希表中
160+
oldStorage.forEach(function (bucket) {
161+
// bucket为null, 说明这里面没有数据
162+
if (bucket == null) {
163+
return;
164+
}
165+
// bucket中有数据, 那么将里面的数据重新哈希化插入
166+
for (var i = 0; i < bucket.length; i++) {
167+
var tuple = bucket[i]
168+
this.put(tuple[0], tuple[1])
169+
}
170+
}).bind(this);
171+
}
172+
173+
174+
175+

‎JavaScript/HashTable/Test.js‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
// 测试哈希算法
2+
var hashFunc = require('./HashFunc');
3+
console.log(hashFunc('abc', 7)); // 4
4+
console.log(hashFunc('cde', 7)); // 4 发生碰撞
5+
console.log(hashFunc('bda', 7));
6+
console.log(hashFunc('abc', 7));
7+
console.log(hashFunc('bda', 7));
8+
9+
// 测试哈希表
10+
var HashTable = require('./HashTable');
11+
12+
var ht = new HashTable();
13+
// 插入数据
14+
ht.put("abc", "1");
15+
ht.put("cba", "2");
16+
ht.put("nba", "3");
17+
ht.put("mba", "4");
18+
ht.put("dba", "5");
19+
// 获取数据
20+
console.log(ht.get("abc")); // 1
21+
ht.put("abc", "2");
22+
console.log(ht.get("abc")); // 2
23+
// 删除数据
24+
console.log(ht.remove("abc")); // 2
25+
console.log(ht.get("abc")); // null
26+
console.log(ht.storage);

0 commit comments

Comments
 (0)