定义
散列是一种常见的数据存储技术，散列后的数据可以快速插入或者取用。散列使用的数据解构叫做散列表。在散列中插入、删除和取用数据都非常快，但对于查找操作来说却效率低下，比如查找数据中的最大值和最小值。
HashTable类
我们使用一个类来表示散列表，该类包含计算散列值得方法、向散列中插入数据的方法、从散列表中读取数据的方法、显示散列表中数据分布的方法，以及其他一些可能会用到的工具方法。
HashTable 类构造方法如下：
// hashtable 类
function HashTable() {
this.table = new Array(137);
this.simpleHash = simpleHash;
this.showDistro = showDistro;
this.put = put;
// this.get = get;
}
我们首先选择一个简单的散列函数，将字符串中每个字符的ASCII码值相加然后除以数组长度取余。
function simpleHash(data) {
var total = 0;
for(var i=0; i<data.length; i++) {
total += data.charCodeAt(i);
}
return total%this.table.length;
}
现在，我们可以为HashTable 类新增 put 方法了：
function put(data) {
var pos = this.simpleHash(data);
this.table[pos] = data;
}
还可以实现一个显示散列表的数据的方法：
function showDistro() {
for (var i = 0; i<this.table.length; i++) {
if (this.table[i]) {
console.log(i+':'+this.table[i]);
}
}
}
现在我们可以来使用这个散列了：
var names = ['jones', 'jane', 'michael', 'marry', 'xiaoli'];
var hTable = new HashTable();
for(var i=0; i<names.length; i++) {
hTable.put(names[i]);
}
hTable.showDistro();
上面打印的结果如下：
结果
上面的散列函数可能经常出现碰撞的现象，所以需要一种更好的散列函数来取代它，使用霍纳算法是一个不错的选择， 所以我们有了一个更好的散列函数：
function betterHash(data) {
var total = 0;
var H = 37;
for (var i=0; i<data.length; i++) {
total += H*total + data.charCodeAt(i);
}
total = total%this.table.length;
if (total == 0) {
total = this.table.length - 1;
}
return parseInt(total);
}
我们将 put 函数稍微改造一下：
function betterPut(data) {
var pos = this.betterHash(data);
this.table[pos] = data;
}
现在我们来使用 霍纳算法 的散列函数表
var names1 = ['jones', 'jane', 'michael', 'marry', 'xiaoli'];
var hTable1 = new HashTable();
for(var j=0; j<names1.length; j++) {
hTable1.betterPut(names1[j]);
}
hTable1.showDistro();
结果如下：
结果
