hash表特点
查找O(1)，插入O(1)，删除O(1)，比较适合无序、需要快速访问的情况，缺点空间复杂度高
hashTable结构
使用开链法解决碰撞处理
[
['A'],
['abc', 'cba'],
['d']
]
构建hashTable
首先选取一个合适的质数作为hashTable长度
function getPrimes(n) {
var res = [];
for (var i = 1; i <= n; i++) {
var flag = true;
for (var j = 1; j <= i; j++) {
if (i % j === 0 && j !== i && j !== 1) {
flag = false;
break;
}
}
flag && res.push(i);
}
return res;
}
getPrimes(1000);
function HashTable(n) {
this.size = n;
this.table = new Array(n);
}
添加方法
根据霍纳算法实现哈希函数，进一步减少数据碰撞
HashTable.prototype = {
// 哈希函数
getHash(str) {
var H = 37;
var hashCode = 0;
for (var i = 0; i < str.length; i++) {
hashCode = H * hashCode + str.charCodeAt(i);
}
return hashCode % this.size;
},
put(key, val) {
var hash = this.getHash(key);
this.table[hash] ?
this.table[hash].push(val) :
(this.table[hash] = [val]);
},
get(key) {
var hash = this.getHash(key);
return this.table[hash];
}
}
测试
var t = new HashTable(137);
for (var i = 0; i < 100; i++) {
t.put(`key${i}`, `val${i}`);
}
t.get('key20');
多说两句
实际上在JS中，数组被实现成了对象。使用hash表的意义不大，不如直接用字典的方式来得好。
function Dict() {
this.table = {};
}
Dict.prototype = {
put(key, val) {
this.table[key] = val;
},
get(key) {
return this.table[key];
}
}
var t = new Dict();
for (var i = 0; i < 100; i++) {
t.put(`key${i}`, `val${i}`);
}
t.get('key20');
