摘要：定義散列表是字典鍵值對(duì)的一種實(shí)現(xiàn)方式。根據(jù)鍵值從散列表中移除值。分離鏈接分離鏈接法在散列表的每一個(gè)位置創(chuàng)建一個(gè)鏈表并將元素存儲(chǔ)在里面。一個(gè)表現(xiàn)良好的散列函數(shù)應(yīng)該有較好的插入和查找性能且有較低的沖突可能性。

散列表是字典（鍵、值對(duì)）的一種實(shí)現(xiàn)方式。每次在字典中獲取一個(gè)值，都需要重復(fù)遍歷字典，如果用散列表，字典中的每個(gè)key都對(duì)應(yīng)一個(gè)確定的位置，從而不再需要遍歷。
以電子郵件地址簿為例，每個(gè)名字（key）對(duì)應(yīng)一個(gè)郵件地址，用散列函數(shù)計(jì)算每個(gè)key在散列表中的位置（這里使用key的所有字符的ASCII碼值相加），如圖：

put(key,value)：向散列表增加一個(gè)新的項(xiàng)（也能更新散列表）。

remove(key)：根據(jù)鍵值從散列表中移除值。

get(key)：返回根據(jù)鍵值檢索到的特定的值。

function HashTable() {
    // 私有變量table，作為散列表的載體
    var table = [];
    // 散列函數(shù)，計(jì)算key對(duì)應(yīng)的hash值
    var loseloseHashCode = function (key) {
        var hash = 0;
        for (var i = 0; i < key.length; i++) {
            hash += key.charCodeAt(i); // 所有字符的ASCII碼值相加
        }
        // 為了將hash值變?yōu)楦〉闹担砸粋€(gè)數(shù)并取余數(shù)
        // 這里除以素?cái)?shù)37是為了降低計(jì)算出重復(fù)hash的概率（后續(xù)會(huì)處理hash重復(fù)的問題）
        return hash % 37;
    };
    // put方法，向散列表增加一個(gè)新的項(xiàng)（也能更新散列表）
    this.put = function(key, value) {
        var position = loseloseHashCode(key); // 計(jì)算key的hash值作為當(dāng)前數(shù)據(jù)在散列表中的位置
        table[position] = value; // 將當(dāng)前數(shù)據(jù)插入散列表
    };
    // get方法，返回根據(jù)鍵值檢索到的特定的值
    this.get = function (key) {
        return table[loseloseHashCode(key)]; //根據(jù)key計(jì)算出的hash取對(duì)應(yīng)位置中的值
    };
    // remove方法，根據(jù)鍵值從散列表中移除值
    this.remove = function(key) {
        table[loseloseHashCode(key)] = undefined;
    };
}

到這里，一個(gè)基本的的散列表已經(jīng)實(shí)現(xiàn)了，但沒有考慮散列函數(shù)計(jì)算出重復(fù)hash值的問題，這會(huì)導(dǎo)致后添加的數(shù)據(jù)覆蓋先添加的數(shù)據(jù)，比如：

var table = new HashTable();
// Jamie和Sue的hash值都為5，因此Sue的數(shù)據(jù)會(huì)覆蓋Jamie的數(shù)據(jù)
table.put("Jamie", "[email protected]");
table.put("Sue", "[email protected]");

處理上述沖突的方式主要有：分離鏈接、線性探查，雙散列法，這里使用前兩種。

分離鏈接法在散列表的每一個(gè)位置創(chuàng)建一個(gè)鏈表并將元素存儲(chǔ)在里面。它的缺點(diǎn)是在HashTable實(shí)例之外還需要額外的存儲(chǔ)空間。如圖，散列表的每一個(gè)位置都是一個(gè)鏈表，鏈表里可以存儲(chǔ)多個(gè)數(shù)據(jù)。

下面，重寫put、get、remove方法，實(shí)現(xiàn)散列表的分離鏈接（其中鏈表類的實(shí)現(xiàn)參照鏈表）。

    // 首先要添加一個(gè)新的輔助類來實(shí)例化添加到鏈表的元素
    var ValuePair = function(key, value){
        this.key = key;
        this.value = value;
    };
    // 改寫put方法
    this.put = function(key, value){
        var position = loseloseHashCode(key);
        if (table[position] == undefined) {
            // 在當(dāng)前位置示例化一個(gè)鏈表
            table[position] = new LinkedList();
        }
        // 在鏈表中添加元素
        table[position].append(new ValuePair(key, value));
    };
    // 改寫get方法
    this.get = function(key) {
        var position = loseloseHashCode(key);
        if (table[position] !== undefined){
            // 獲取鏈表的第一個(gè)元素
            var current = table[position].getHead();
            // 遍歷鏈表（這里不能遍歷到最后一個(gè)元素，后續(xù)特殊處理）
            while(current.next){
                // 如果鏈表中存在當(dāng)前key對(duì)應(yīng)的元素，返回其值
                if (current.element.key === key){
                    return current.element.value;
                }
                // 處理下一個(gè)元素
                current = current.next;
            }
            // 處理鏈表只有一個(gè)元素的情況或處理鏈表的最后一元素
            if (current.element.key === key){
                return current.element.value;
            }
        }
        // 不存在值，返回undefined
        return undefined;
    };
    // 改寫remove方法
    this.remove = function (key) {
        var position = loseloseHashCode(key);
        if (table[position] !== undefined) {
            // 獲取當(dāng)前位置鏈表的第一個(gè)元素
            var current = table[position].getHead();
            // 遍歷鏈表（這里不能遍歷到最后一個(gè)元素，后續(xù)特殊處理）
            while (current.next) {
                if (current.element.key === key) {
                    // 遍歷到對(duì)應(yīng)元素，從鏈表中刪除
                    table[position].remove(current.element);
                    if (table[position].isEmpty()) {
                        // 如果鏈表已經(jīng)空了，將散列表的當(dāng)前位置置為undefined
                        table[position] = undefined;
                    }
                    // 返回true表示刪除成功
                    return true;
                }
                // 處理下一個(gè)元素
                current = current.next;
            }
            // 處理鏈表只有一個(gè)元素的情況或處理鏈表的最后一元素
            if (current.element.key === key) {
                table[position].remove(current.element);
                if (table[position].isEmpty()) {
                    table[position] = undefined;
                }
                return true;
            }
        }
        // 要?jiǎng)h除的元素不存在，返回false
        return false;
    };

線性探查法在向散列表中插入元素時(shí)，如果插入位置position已經(jīng)被占據(jù)，就嘗試插入position+1的位置，以此類推，直到找到空的位置。下面用線性探查的方式重寫put、get、remove方法

    // 重寫put方法
    this.put = function(key, value){
        var position = loseloseHashCode(key);
        // 依次查找，如果當(dāng)前位置不為空，position + 1，直到找到為空的位置為止
        while (table[position] != undefined){
            position++;
        }
        table[position] = new ValuePair(key, value);
    };
    // 重寫get方法
    this.get = function(key) {
        var position = loseloseHashCode(key);
        var len = table.length;
        // 只要當(dāng)前位置小于散列表長度就要查找
        if (position < len){
            // 由于查找的值可能是以 position + 1 的形式類推，找到空位后插入的
            // 因此需要從當(dāng)前位置（position）開始查找，直到找到key相同的位置，或者找完整個(gè)散列表
            while (position < len && (table[position] === undefined || table[position].key !== key)){
                position++;
            }
            // 如果最終position >= len，說明沒找到
            if (position >= len) {
                return undefined
            } else {
                // 否則說明找到了，返回對(duì)應(yīng)值
                return table[position].value;
            }
        }
        // 如果當(dāng)前位置為空，說明添加時(shí)沒有累加position，直接返回undefined
        return undefined;
    };
    // 改寫remove方法
    this.remove = function(key) {
        var position = loseloseHashCode(key);
        var len = table.length;
        if (position < len){
            // 從當(dāng)前位置（position）開始查找，直到找到key相同的位置，或者找完整個(gè)散列表
            while (position < len && (table[position] === undefined || table[position].key !== key)){
                position++;
            }
            // 如果最終position < len，說明找到了,將對(duì)應(yīng)位置數(shù)據(jù)刪除
            if (position < len) {
                table[position] = undefined;
            }
        }
    };

上述散列函數(shù)表現(xiàn)并不好，它極易計(jì)算出相同的hash值，從而導(dǎo)致沖突。一個(gè)表現(xiàn)良好的散列函數(shù)應(yīng)該有較好的插入和查找性能且有較低的沖突可能性。下面的散列函數(shù)，被證明是比較合適的。

var djb2HashCode = function (key) {
    var hash = 5381; // 一個(gè)較大的素?cái)?shù)基準(zhǔn)值
    for (var i = 0; i < key.length; i++) {
        hash = hash * 33 + key.charCodeAt(i); // 基準(zhǔn)值乘以33再加ASCII碼值
    }
    return hash % 1013; //除以1013取余
};