JS實作散清單資料結構

雜湊演算法的作用是盡可能快的在資料結構中找到一個值。在連結清單等資料結構中獲得一個值，需要周遊整個資料結構來找到他。但是散清單中，使用散列函數，就可以知道值的具體位置，是以能夠快速檢索到值。散列函數的作用是給定一個鍵值，然後傳回值在表中的位址。

代碼實作：

function HashTable(){
    var table = [];
    // 實作一個散列函數
    var hashCode = function(key){
        var hash = 0;
        for(var i = 0; i < key.length; i++){
            hash += key.charCodeAt(i);
        }
        return hash % 37;
    }
    // 向散清單中增加一個新的項
    this.put = function(key, value){
        var pos = hashCode(key);
        console.log(pos + "---" + key);
        table[pos] = value;
    }
    // 根據鍵值檢索到特定的值
    this.get = function(key){
        console.log(table[hashCode(key)])
        return table[hashCode(key)];
    }
    // 根據鍵值從散清單中移除值
    this.remove = function(key){
        table[hashCode[key]] = undefined;
    }
    // 列印散清單
    this.print = function(){
        for(var i = 0; i < table.length; i++){
            if(table[i] !== undefined){
                console.log(i + ':' +table[i]);
            }
        }
    }
}

測試：

var hash = new HashTable();
hash.put('abc', '[email protected]');         //35---abc
hash.put('aab', '[email protected]');        //33---aab
hash.get('abc');                      //[email protected]

處理散清單中的沖突

有時候，一些鍵會有相同的散列值。不同的值在散清單中對應相同位置的時候，我們稱其為沖突。

處理沖突的方法：

（1）分離連結

（2）線性探查

（3）雙散列法

分離連結

分離連結法包括為散清單的每一個位置建立一個連結清單并将元素存儲在裡面。它是解決沖突的最簡單的方法，但是它需要額外的存儲空間。

代碼實作：

// 實作LinkList類
function LinkList(){
    let Node = function(ele){
        this.ele = ele;
        this.next = null;
    }
    let length = 0;
    let head = null;
    // 向連結清單尾部追加元素
    this.append = function(ele){
        let node = new Node(ele);
        let current;
        if(head == null){
            head = node;
        }else{
            current = head;
            while(current.next){
                current = current.next;
            }
            current.next = node;
        }
        length++;
    }
    // 從連結清單中移出元素(從特定位置移出)
    this.removeAt = function(pos){
        // 檢查越界值
        if(pos >-1 && pos< length){
            let current = head,
            pre,
            index = 0;
            if(pos === 0){
                head = current.next;
            }else{
                while(index++ < pos){
                    pre = current;
                    current = current.next;
                }
                pre.next = current.next;
            }
            length--;
            return current.ele;
        }else{
            return null;
        }
    }
    // 在任意位置插入元素
    this.insert = function(pos, ele){
        if(pos >= 0 && pos <= length){
            let node = new Node(ele),
            current = head,
            pre,
            index = 0;
            if(pos == 0){
                node.next = current;
                head = node;
            }else{
                while(index++ < pos){
                    pre = current;
                    current = current.next;
                }
                node.next = current;
                pre.next = node;
            }
            length++;
            return true;
        }else{
            return false;
        }
    }
    // 将LinkList對象轉換成一個字元串
    this.toString = function(){
        let current = head,
        string = '';
        while(current){
            string += current.ele;
            current = current.next;
        }
        console.log(string);
        return string;
    }
    // 該方法接收一個值，如果在清單中能找到它，就傳回元素的位置，否則傳回-1
    this.indexOf = function(ele){
        let current = head,
        index = 0;
        while(current){
            if(current.ele == ele){
                return index;
            }
            index++;
            current = current.next;
        }
        return -1;
    }
    // 從連結清單中移出元素(通過特定的元素)
    this.remove = function(ele){
        let index = this.indexOf(ele);
        return this.removeAt(index);
    }
    this.isEmpty = function(){
        if(length == 0){
            console.log('空')
        }else{
            console.log('不為空')
        }
        return length == 0;
    }
    this.size = function(){
        console.log(length)
        return length;
    }
    this.getHead = function(){
        console.log(head);
        return head;
    }
}

function HashTable(){
    var table = [];
    var hashCode = function(key){
        var hash = 0;
        for(var i = 0 ; i<key.length; i++){
            hash += key[i].charCodeAt();
        }
        return hash % 37;
    };
    // 輔助類表示将要加入的LinkList執行個體的元素
    var ValueList = function(key, value){
        this.key = key;
        this.value = value;
        this.toString = function(){
            return '[' + this.key +'-'+ this.value +']';
        }
    }
    // 實作put方法
    // 在這個方法中，将要驗證新元素的位置是否被占據，如果這個位置是第一次被加入，我們會在這個位置上初始化一個ValueList類的執行個體。
    this.put = function(key, value){
        var pos = hashCode(key);
        if(table[pos] == undefined){
            table[pos] = new LinkList();
        }
        table[pos].append(new ValueList(key, value));
    }
    // 實作get方法,用來擷取特定的值
    this.get = function(key){
        var pos = hashCode(key);
        if(table[pos] !== undefined){
            // 周遊連結清單尋找鍵值
            var current = table[pos].getHead();
            while(current.next){
                if(current.ele.key  === key){
                    console.log(current.ele.value);
                    return current.ele.value;
                }
                current = current.next;
            }
            // 檢查元素在連結清單第一個或最後一個節點的情況
            if(current.ele.key == key){
                console.log(current.ele.value)
                return current.ele.value;
            }
        }
        console.log('undefined');
        return undefined;
    };
    // 實作remove方法
    // 我們需要從連結清單中移除一個元素
    this.remove = function(key){
        var pos = hashCode(key);
        if(table[pos] !== undefined){
            var current = table[pos].getHead();
            while(current.next){
                if(current.ele.key === key){
                    table[pos].remove(current.ele);
                    if(table[pos].isEmpty()){
                        table[pos] = undefined;
                    }
                    return true;
                }
                current = current.next;
            }
            // 檢查是否為第一個或最後一個元素
            if(current.ele.key === key){
                table[pos].remove(current.ele);
                if(table[pos].isEmpty()){
                    table[pos] = undefined;
                }
                return true;
            }
        }
        return false;
    }
     // 列印散清單
     this.print = function(){
        for(var i = 0; i < table.length; i++){
            if(table[i] !== undefined){
                console.log(i + ':' +table[i]);
            }
        }
    }
}

測試：

var hash = new HashTable();
hash.put('Jamie', '110');
hash.put('Tom','112');
hash.put('Sue', '119');
hash.get('Sue');

結果：

JS實作散清單資料結構

線性探查

線性探查：當想向表中某個位置加入一個新元素的時候，如果索引為index的位置已經被占據了，就嘗試index+1的位置。如果index+1的位置也被占據了，就嘗試index+2的位置，以此類推.

代碼實作：

function HashTable(){
    var table = [];
    var hashCode = function(key){
        var code = 0;
        for(var i = 0; i<key.length;i++){
             code += key[i].charCodeAt(); 
        }
        return code % 37;
    }
    var ValueHash = function(key, value){
        this.key = key;
        this.value = value;
        this.tostring = function(){
            console.log(this.key + '----'+ this.value)
        }
    }
    this.put = function(key, value){
        var pos = hashCode(key);
        if(table[pos] == undefined){
            table[pos] = new ValueHash(key ,value);
        }else{
            var index = ++pos;
            while(table[index] != undefined){
                index++;
            }
            table[index] = new ValueHash(key, value);
        }
    }
    this.get = function(key){
        var pos = hashCode(key);
        if(table[pos] !== undefined){
            if(table[pos].key === key){
                console.log(table[pos].value);
                return table[pos].value;
            }else{
                var index = ++pos;
                while(table[index] === undefined || table[index].key !== key){
                    index++;
                }
                if(table[index].key === key){
                    console.log(table[index].value);
                    return table[index].value;
                }
            }
        }
        return undefined;
    }
    this.remove = function(key){
        var pos = hashCode(key);
        if(table[pos] !== undefined){
            if(table[pos].key === key){
                console.log('移出的元素為:',table[pos].value);
                table[pos].value = undefined;
            }else{
                var index = ++pos;
                while(table[index] === undefined || table[index].key !== key){
                    index++;
                }
                if(table[index].key === key){
                    console.log('移出的元素為:',table[index].value);
                    table[index] = undefined;
                }
            }
        }
        return undefined;
    }
    this.print = function(){
        for(var i = 0; i<table.length; i++){
            if(table[i] !== undefined){
                console.log(i + '-----' +table[i].key + '------' + table[i].value);
            }
        }
    }
}

測試：

var hash = new HashTable();
hash.put('Jamie','110');
hash.put('Sue','112');
hash.put('Tom','114');
hash.put('Jonathan','119');
hash.print();
hash.get('Sue');
hash.remove('Sue');
hash.print();

結果：

JS實作散清單資料結構

建立更好的散列函數

一個表現良好的散列函數是由幾個方面構成的：

（1）插入和檢索元素的時間

（2）較低的沖突可能性

djb2散列函數:

// 一個更好的散列函數
    var djb2HashCode = function(key){
        var hash = 5381;
        for(var i = 0; i < key.length; i++){
            hash = hash * 33 + key[i].charCodeAt();
        }
        return hash % 1013;
    }

JS實作散清單資料結構

繼續閱讀

D. Ehab the Xorcist(構造+思維)

關于 underscore 中模闆引擎的應用示例

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【JavaScript文法】函數對象的淺拷貝、深拷貝

【資料結構】醫院選址

JS--運算符

數組和類數組

[轉]ISUP信令的IAM消息詳細内容

jquery_126_demo

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器