读【数据结构与算法】之散列
散列是一种常用的数据存储技术，散列的数据可以快速的插入或者取用。散列使用的数据结构是散列表。在散列表上插入、删除和取用数据都很快，但是查找数据操作就慢了。
散列表是基于数组进行设计的，长度是预先定义好的，但是如果需要的话，也是可以增加的。元素根据该元素的键保存在数组的特定位置。使用散列表时，需要通过使用一个散列函数将键映射为一个数字，这个数字长度是从0到散列表长度。
在散列表中，如果存在将两个键映射为同一个值的现象，这种现象称为碰撞（collision）。
散列表中数组的长度应该是一个质数。
基本散列表
基本实现：
/**
* Class HashTable
* 散列 HashTable
*/
function HashTable() {
this.table = new Array(137); // 用于存储数据的数组
}
HashTable.prototype = {
constructor: HashTable,
/**
* 简单散列函数
* @param {String} data 键
* @return {Number} 键值
*/
simpleHash: function simpleHash(data) {
var total = 0;
for (var i = 0, len = data.length; i < len; i++) {
total += data.charCodeAt(i);
}
return total % this.table.length;
},
/**
* 更好的散列函数（霍纳算法）
* @param {String} str 键
* @return {Number} 键值
*/
betterHash: function betterHash(str) {
var H = 37, total = 0, i = 0, len = str.length;
for ( ; i < len; i++) {
total += H * total + str.charCodeAt(i);
}
total = total % this.table.length;
if (total < 0) total += this.table.length - 1;
return parseInt(total);
},
/**
* 得到显示散列表中数据
* @return {Array} 结果数组
*/
showDistro: function showDistro() {
var ret = [], i = 0, len = this.table.length;
for ( ; i < len; i++) {
if (this.table[i] != undefined) {
ret.push(i + ': ' + this.table[i]);
}
}
return ret;
},
/**
* 将数据存入散列表
* @param {String} key 键
* @param {String} data 数据
* @return {Undefined} undefined
*/
put: function put(key, data) {
// 简单哈希 可能产生碰撞
// this.table[this.simpleHash(data)] = data;
this.table[this.betterHash(key)] = data;
},
/**
* 从散列表中取出数据
* @param {[type]} key 键
* @return {[type]} 对应的键值
*/
get: function get(key) {
return this.table[this.betterHash(key)];
}
};
碰撞处理
散列函数对于多个输入可能产生相同的结果，这样就产生了碰撞。这里介绍两种碰撞解决办法：开链法和线性探测法。
开链法
实现开链法的方法是：在创建存储散列过的键值的数组时，通过调用一个函数创建新的空数组，然后将该数组赋值给散列表里的每个数组元素。这样也就创建了二维数组。
线性探测法
线性探测法隶属于一种更一般化的散列技术：开放寻址散列。当发生碰撞时，线性探测法会检测下一个位置是否为空，如果为空，那么就将数据存入该位置，否则，就继续检查下一个位置，直到找到一个空的位置。
当存储数据使用的数组比较大时，选择线性探测法要比开链法好。选择办法：如果数组的大小时待存储数据个数的1.5倍，那么使用开链法；如果数组的大小时待存储数据的两倍以及两倍以上时，使用线性探测法。
加入了两种方法之后的散列实现代码：
/**
* Class HashTable
* 散列 HashTable
*/
function HashTable() {
this.table = new Array(137); // 用于存储数据的数组
}
HashTable.prototype = {
constructor: HashTable,
/**
* 简单散列函数
* @param {String} data 键
* @return {Number} 键值
*/
simpleHash: function simpleHash(data) {
var total = 0;
for (var i = 0, len = data.length; i < len; i++) {
total += data.charCodeAt(i);
}
return total % this.table.length;
},
/**
* 更好的散列函数（霍纳算法）
* @param {String} str 键
* @return {Number} 键值
*/
betterHash: function betterHash(str) {
var H = 37, total = 0, i = 0, len = str.length;
for ( ; i < len; i++) {
total += H * total + str.charCodeAt(i);
}
total = total % this.table.length;
if (total < 0) total += this.table.length - 1;
return parseInt(total);
},
/**
* 得到显示散列表中数据
* @return {Array} 结果数组
*/
showDistro: function showDistro() {
var ret = [], i = 0, len = this.table.length,
chained = this._chained, tmp;
for ( ; i < len; i++) {
if (chained) tmp = this.table[i][0];
else tmp = this.table[i];
if (tmp != undefined) {
ret.push(i + ': ' + tmp);
}
}
return ret;
},
/**
* 将数据存入散列表
* @param {String} key 键
* @param {String} data 数据
* @return {Undefined} undefined
*/
put: function put(key, data) {
// 简单哈希 可能产生碰撞
// this.table[this.simpleHash(data)] = data;
var pos = this.betterHash(key);
if (this._chained) {
var index = 0;
while (this.table[pos][index] != undefined) {
++index;
}
this.table[pos][index] = key;
this.table[pos][index + 1] = data;
return;
}
if (this.values) {
while (this.table[pos] != undefined) {
pos++;
}
this.table[pos] = key;
this.values[pos] = data;
return;
}
this.table[pos] = data;
},
/**
* 从散列表中取出数据
* @param {[type]} key 键
* @return {[type]} 对应的键值
*/
get: function get(key) {
var pos = this.betterHash(key);
if (this._chained) {
var index = 0;
while (this.table[pos][index] != undefined && this.table[pos][index] != key) {
index += 2;
}
return this.table[pos][index + 1];
}
if (this.values) {
if (pos > -1) {
for (var i = pos; this.table[i] != undefined; i++) {
if (this.table[i] == key) {
return this.values[i];
}
}
}
return undefined;
}
return this.table[pos];
},
/**
* 构建链-新数组（开链法）
* @return {Undefined} undefined
*/
buildChains: function buildChains() {
for (var i = 0, len = this.table.length; i < len; i++) {
this.table[i] = [];
}
this._chained = true;
this.values = undefined;
},
/**
* 创建values数组（线性探测法法）
* @return {Undefined} undefined
*/
createValues: function createValues() {
this.values = [];
this._chained = false;
}
};
具体运行例子请看demojs实现散列