定义

散列是一种常见的数据存储技术，散列后的数据可以快速插入或者取用。散列使用的数据解构叫做散列表。在散列中插入、删除和取用数据都非常快，但对于查找操作来说却效率低下，比如查找数据中的最大值和最小值。

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();

结果如下：

结果