學習JavaScript資料結構與算法（七）——散清單（一）

散列技術是在記錄的存儲位置和它的關鍵字之間建立一個确立的對應關系f，使得每個關鍵字key對應一個存儲位置f(key)。查找時，根據這個确定的對應關系找到給定值key的映射f(key)，若查找集合中存在這個記錄，則必定在f(key)的位置上。其中，對應關系f成為散列函數，又稱為哈希函數。

采用散列技術将記錄存儲在一塊連續的存儲空間中，這塊連續存儲空間稱為散清單或哈希表。關鍵字對應的記錄存儲位置稱為散列位址。

雜湊演算法的作用是盡可能快的在資料結構中找到一個值。

一、建立一個散清單

function HashTable () {

    var table = [];

    /*
    散列函數，是HashTable類中的一個私有方法。
    給定一個參數key，根據組成key的每個字元的ASCII碼值得和得到一個數字。
     */
    var loseloseHashCode = function(key){
        var hash = ;//存儲總和
        //周遊key并将ASCII表查到的每個字元對應的ASCII值加到hash變量中
        for (var i = ; i < key.length; i++) {
            hash += key.charCodeAt(i);
        }
        //為了得到比較小的數值，會使用hash值和一個任意數做除數的餘數
        return hash % ;
    };

    /*
    put(key,value)
    向散清單增加一個新的項（也能更新散清單）。
     */
    this.put = function(key, value){
        var position = loseloseHashCode(key);
        console.log(position + ' - ' + key);
        table[position] = value;
    };

    /*
    remove(key)
    根據鍵值從散清單中移除值。
     */
    this.remove = function(key){
        table[loseloseHashCode(key)] = undefined;
    };

    /*
    get(key)
    傳回根據鍵值檢索到的特定的值。
     */
    this.get = function(key){
        return table[loseloseHashCode(key)];
    };

}
           

二、使用HashTable類

var hash = new HashTable();

hash.put('Jack', '[email protected]');
hash.put('John', '[email protected]');
hash.put('Ben', '[email protected]');

console.log(hash.get('Jack'));
console.log(hash.get('Lily'));

hash.remove('Ben');
console.log(hash.get('Ben'));
           

測試結果如下：

三、散列集合

散列集合由一個集合構成，但是插入、移除或擷取元素時，使用的是散列函數。

散列集合隻存儲唯一的不重複的值。