摘要：定義散列表是字典鍵值對的一種實現方式。根據鍵值從散列表中移除值。分離鏈接分離鏈接法在散列表的每一個位置創建一個鏈表并將元素存儲在里面。一個表現良好的散列函數應該有較好的插入和查找性能且有較低的沖突可能性。

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

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

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

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

function HashTable() {
    // 私有變量table，作為散列表的載體
    var table = [];
    // 散列函數，計算key對應的hash值
    var loseloseHashCode = function (key) {
        var hash = 0;
        for (var i = 0; i < key.length; i++) {
            hash += key.charCodeAt(i); // 所有字符的ASCII碼值相加
        }
        // 為了將hash值變為更小的值，除以一個數并取余數
        // 這里除以素數37是為了降低計算出重復hash的概率（后續會處理hash重復的問題）
        return hash % 37;
    };
    // put方法，向散列表增加一個新的項（也能更新散列表）
    this.put = function(key, value) {
        var position = loseloseHashCode(key); // 計算key的hash值作為當前數據在散列表中的位置
        table[position] = value; // 將當前數據插入散列表
    };
    // get方法，返回根據鍵值檢索到的特定的值
    this.get = function (key) {
        return table[loseloseHashCode(key)]; //根據key計算出的hash取對應位置中的值
    };
    // remove方法，根據鍵值從散列表中移除值
    this.remove = function(key) {
        table[loseloseHashCode(key)] = undefined;
    };
}

到這里，一個基本的的散列表已經實現了，但沒有考慮散列函數計算出重復hash值的問題，這會導致后添加的數據覆蓋先添加的數據，比如：

var table = new HashTable();
// Jamie和Sue的hash值都為5，因此Sue的數據會覆蓋Jamie的數據
table.put("Jamie", "Jamie@qq.com");
table.put("Sue", "Sue@gmail.com");

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

分離鏈接法在散列表的每一個位置創建一個鏈表并將元素存儲在里面。它的缺點是在HashTable實例之外還需要額外的存儲空間。如圖，散列表的每一個位置都是一個鏈表，鏈表里可以存儲多個數據。

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

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

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

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

上述散列函數表現并不好，它極易計算出相同的hash值，從而導致沖突。一個表現良好的散列函數應該有較好的插入和查找性能且有較低的沖突可能性。下面的散列函數，被證明是比較合適的。

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