Javascript数据结构算法之散列（霍纳算法，开链法，线性探测-寻址法）

使用散列存储数据时，通过一个散列函数将键映射为一个数字，这个数字的范围时0到散列表的长度。理想情况下，散列函数会将每个键值映射为唯一的数组索引。一个更现实的目标是将键均匀分布。

在散列上插入，删除和取用数据都非常快，但是对于查找操作效率低下。

散列的JS实现

最经典的散列函数为霍纳算法+除留余数法。在该算法中，先计算字符串中个字符的ASCII码值，不过求和时要乘以一个质数。之后将和对散列表长度求余，求得的余数即可作为该字符串的索引。

//hashtable.js function HashTable(){ this.dataStore = new Array(137);//散列表的长度一般都为质数 this.values = []; this.betterHash = betterHash;//霍纳算法+除留余数法 this.showDistro = showDistro;//显示散列表数据的存储方式 this.put = put; this.get = get; } function betterHash(string){ const H = 37; var total = 0; for(var i=0; i<string.length; i++) { total += H*total + string.charCodeAt(i); } total = total % this.dataStore.length; return total; } function put(key, data){ var pos = this.betterHash(key); this.dataStore[pos] = data; } function get(key){ var pos = this.betterHash(key); return this.dataStore[pos]; } function showDistro(){ var str = ""; for(var i=0; i<this.dataStore.length; i++) { if(this.dataStore[i] === undefined) {} else{ str += i+":"+this.dataStore[i]+"\n"; } } return str; }

处理散列碰撞

即使使用高效的散列函数，仍然存在将两个键映射为一个值的可能，这种现象成为碰撞。

开链法

在创建存储散列过的键值数组时，创建一个新的空数组，然后将该数组付给散列表中的每个数组元素，这样创建了一个二维数组，也称第二个数组为链。

//hashtable.js function KLHashTable(){ this.dataStore = new Array(137); this.values = []; this.buildChains = buildChains; this.putKL = putKL; this.getKL = getKL; this.showDistroKL = showDistroKL; } function buildChains(){ for(var i=0; i<this.dataStore.length; i++) { this.dataStore[i] = new Array(); } } function putKL(key, data){ var pos = this.betterHash(key); var index = 0; if(this.dataStore[pos][index] === undefined) { this.dataStore[pos][index] = key; this.dataStore[pos][index+1] = data; } else{ while(this.dataStore[pos][index] !== undefined) { index++; } this.dataStore[pos][index] = key; this.dataStore[pos][index+1] = data; } } function getKL(key){ var pos = this.betterHash(key); var index = 0; while(this.dataStore[pos][index] !== undefined) { if(this.dataStore[pos][index] == key) { return this.dataStore[pos][index+1]; break; } index++; } } function showDistroKL(){ var str = ""; for(var i=0; i<this.dataStore.length; i++) { if(this.dataStore[i][0] === undefined) {} else{ str += i+":"+this.dataStore[i]+"\n"; } } return str; }

寻址法（线性探测法）

当发生碰撞时，检测下一个位置是否为空。如果为空，就将此数据存入该位置；如果不为空，则继续检查下一个位置，直到找到下一个空的位置为止。

//hashtable.js function XZHashTable(){ this.dataStore = new Array(137); this.values = []; this.putXZ = putXZ; this.getXZ = getXZ; this.showDistroXZ = showDistroXZ; } function putXZ(key, data){ var pos = this.betterHash(key); while(this.dataStore[pos] !== undefined) { pos++; } this.dataStore[pos] = key; this.values[pos] = data; } function getXZ(key){ var pos = this.betterHash(key); while(this.dataStore[pos] !== undefined) { if(this.dataStore[pos] == key) { return this.values[pos]; } pos++; } } function showDistroXZ(){ var str = ""; for(var i=0; i<this.dataStore.length; i++) { if(this.dataStore[i] === undefined) {} else{ str += i+"->"+this.dataStore[i]+":"+this.values[i]+"\n"; } } return str; }

网页展示