定義

散列是一種常見(jiàn)的數(shù)據(jù)存儲(chǔ)技術(shù)，散列后的數(shù)據(jù)可以快速插入或者取用。散列使用的數(shù)據(jù)解構(gòu)叫做散列表。在散列中插入、刪除和取用數(shù)據(jù)都非?？?，但對(duì)于查找操作來(lái)說(shuō)卻效率低下，比如查找數(shù)據(jù)中的最大值和最小值。

HashTable類(lèi)

我們使用一個(gè)類(lèi)來(lái)表示散列表，該類(lèi)包含計(jì)算散列值得方法、向散列中插入數(shù)據(jù)的方法、從散列表中讀取數(shù)據(jù)的方法、顯示散列表中數(shù)據(jù)分布的方法，以及其他一些可能會(huì)用到的工具方法。
HashTable 類(lèi)構(gòu)造方法如下：

// hashtable 類(lèi)
function HashTable() {
    this.table = new Array(137);
    this.simpleHash = simpleHash;
    this.showDistro = showDistro;
    this.put = put;
    // this.get = get;
}

我們首先選擇一個(gè)簡(jiǎn)單的散列函數(shù)，將字符串中每個(gè)字符的ASCII碼值相加然后除以數(shù)組長(zhǎng)度取余。

function simpleHash(data) {
    var total = 0;
    for(var i=0; i<data.length; i++) {
        total += data.charCodeAt(i);
    }
    return total%this.table.length;
}

現(xiàn)在，我們可以為HashTable 類(lèi)新增 put 方法了：

function put(data) {
    var pos = this.simpleHash(data);
    this.table[pos] = data;
}

還可以實(shí)現(xiàn)一個(gè)顯示散列表的數(shù)據(jù)的方法：

function showDistro() {
    for (var i = 0; i<this.table.length; i++) {
        if (this.table[i]) {
            console.log(i+':'+this.table[i]);
        }
    }
}

現(xiàn)在我們可以來(lái)使用這個(gè)散列了：

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

上面打印的結(jié)果如下：

結(jié)果

上面的散列函數(shù)可能經(jīng)常出現(xiàn)碰撞的現(xiàn)象，所以需要一種更好的散列函數(shù)來(lái)取代它，使用霍納算法是一個(gè)不錯(cuò)的選擇， 所以我們有了一個(gè)更好的散列函數(shù)：

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 函數(shù)稍微改造一下：

function betterPut(data) {
    var pos = this.betterHash(data);
    this.table[pos] = data;
}

現(xiàn)在我們來(lái)使用 霍納算法 的散列函數(shù)表

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

結(jié)果如下：

結(jié)果