散列及碰撞處理

散列是一種常用的資料存儲技術。散列使用的資料結構叫做散清單。在散清單上插入、删除、取用資料都非常快，但是對于查找來說效率很低。

散清單的長度是預先設定的，存儲資料時，通過一個散列函數将鍵映射為一個數字，這個數字的長度為0到散清單的長度。編寫散列函數前需要先确定散清單數組的長度，我們對數大小常見的限制是：數組長度應該是一個質數。數組長度的确定政策都是基于處理碰撞問題的。

1、散列函數

我們采取的散列方式為除留餘數法，基于這個方法的散列函數可以更加均勻的分布随機的整數鍵。對于字元串類型的鍵，散列值可以設為每個字元的ASCII碼值的和除以數組長度的餘數。散列函數定義如下：

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

于是，HashTable類的構造函數如下：

function HashTable() {
        this.table = new Array(137);this.simpleHash = simpleHash;
        this.showDistro = showDistro;
        this.put = put;
        //this.get=get;
    }
    function simpleHash(data) {
        var total = 0;
        for ( var i = 0; i < data.length; ++i) {
            total += data.charCodeAt(i);
        }
        return total % this.table.length;
    }
    function put(data) {
        var pos = this.simpleHash(data);
        this.table[pos] = data;
    }
    function showDistro() {
        for ( var i = 0; i < this.table.length; ++i) {
            if (this.table[i] != undefined) {
                document.write(i + ": " + this.table[i]);
                document.write("<br />");
            }
        }
    }      

simpleHash()散列函數通過JavaScript的charCodeAt()函數，傳回每個字元的ASCII碼值，相加得到散列值，put()方法通過調用simpleHash()得到數組的索引，并将資料存儲到該索引對應的位置。通過實驗可以發現，這個散列函數散列的資料并不是均勻分布的，向數組的兩端集中，并且更嚴重的問題是，容易引發碰撞！是以需要優化一下散列函數來避免碰撞。

為了避免碰撞：

1、首先要保證散清單中用來存儲資料的數組大小是個質數。這個計算散列值時采取的取餘運算有關。

2、有了合适的散清單大小後，接下來就需要有一個更好的散列函數。霍納算法很好的解決了這個問題。新的散列函數在每次求值前都先乘以一個質數，這裡建議使用一個較小的質數。

使用霍納算法的散列函數：

function betterHash(data) {
        const H = 37;
        var total = 0;
        for ( var i = 0; i < data.length; ++i) {
            total += total*H + data.charCodeAt(i);
        }
        total = total % this.table.length;
　　　　　return parseInt(total);      

}      

2、從散清單中存取資料

使用散清單來存儲資料，我們需要重新定義put() 方法，使其可以同時接受鍵和資料作為參數，對鍵值散列後，将資料存儲到散清單中：

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

get() 方法同樣需要對鍵值進行散列化，得到資料在散清單中存儲的位置：

function get(key) {
        return this.table[this.betterHash(key)];
    }      

3、碰撞處理

1）開鍊法

開鍊法是指，實作散清單的底層數組中，每個數組元素又是一個新的數組結構。

實作開鍊法的方法：在建立存儲散列過的鍵值的數組時，通過調用一個函數建立一個空的新數組，将該數組指派給散清單裡的每個數組元素，建立一個二維數組。我們稱這個數組為鍊。函數buildChains() 定義如下：

function buildChains() {
        for ( var i = 0; i < this.table.length; ++i) {
            this.table[i] = new Array();
        }
    }      

 使用了開鍊法後，我們需要重新定義put()和get()方法。

put()方法先将鍵值散列，散列後的值對應數組中的一個位置，先檢視該位置上數組的第一個單元格是否有值，如果有值則會搜尋下一個位置，直到找到可以存放資料的單元格，并将數組存儲進去，新的put()方法實作如下：

function put(key, data) {
        var pos = this.betterHash(key);
        var index = 0;
        if (this.table[pos][index] == undefined) {
            this.table[pos][index] = key;
            this.table[pos][index + 1] = data;
        } else {
            while (this.table[pos][index] != undefined) {
                ++index;
            }
            this.table[pos][index] = key;
            this.table[pos][index + 1] = data;
        }
    }      

新的put()方法不同于之前的方法，之前的方法僅存放資料，而新的put()方法使用鍊中兩個相同的單元格同時存放了散列後的鍵值和資料，第一個單元格存放鍵值，第二個單元格存放資料。這樣便于在碰撞出現時，鍊中存放多條資料時，從散清單中取值。

get()方法先對鍵值散列，根據散列後的值找到散清單中相應的位置，查找該位置的鍊中是否存在這個鍵值，如果有，則把緊跟在鍵值後面的單元格的資料傳回，沒找到就傳回undefined。新的get()方法實作如下：

function get(key) {
        var index = 0;
        var pos = this.betterHash(key);
        if(this.table[pos][index] == key) {
            console.log(this.table[pos][index + 1]);
            return;
        } else {
            while (this.table[pos][index] != key) {
                index += 2;
            }
            console.log(this.table[pos][index + 1]);
            return;
        }
        document.write('undefined');
        return;
    }      

散清單現在使用的是多元數組存儲資料，為了更好的顯示使用了開鍊法後鍵值的分布，則需要對showDistro()方法進行如下修改：

function showDistro() {
        for ( var i = 0; i < this.table.length; ++i) {
            if (this.table[i][0] != undefined) {
                document.write(i + ": " + this.table[i]);
                document.write("<br />");
            }
        }
    }      

2）線性探測法

線性探測法隸屬于一種更一般化的散列技術：開放尋址散列。當發生碰撞時，線性探測法會檢查散清單中下一個位置是否為空，如果為空，則将資料存儲在該位置，如果不為空，則繼續檢查下一個位置，直到找到空位置為止。當存儲資料的數組特别大時，選擇線性探測法要比開鍊法好，有一個公式可以幫助我們來判斷使用那種碰撞處理方法：如果數組的大小是待存儲資料的1.5倍，使用開鍊法；如果數組的大小是待存儲資料的兩倍或兩倍以上，則選擇線性探測法。

下面用代碼說明線性探測法的工作原理，重新定義put()和get()方法，在構造函數中新增加一個數組

this.values = [];      

數組value和table并行工作，table用來存儲鍵值，value用來存儲對應的資料。put()方法定義如下：

function put(key, data) {
        var pos = this.betterHash(key);
        if (this.table[pos] == undefined) {
            this.table[pos] = key;
                this.values[pos] = data;
        } else {
            while (this.table[pos] != undefined) {
                pos++;
            }
            this.table[pos] = key;
            this.values[pos] = data;
        }
    }      

get()方法先搜尋散列後的鍵值在散清單中的位置，如果在table中找到key，則傳回values中對應位置上的資料，如果沒找到則循環搜尋，直到找到了table中對應的鍵，或者table中對應的值為undefined時，表示鍵值和資料沒有存儲到散清單。get()方法如下：

function get(key) {
        var hash= -1;
        var hash= this.betterHash(key);
        if(hash > -1) {
            for (var i=hash; this.table[i] != undefined; i++) {
                        if (this.table[i] == key) {
                                return this.values[i];
                        }
                }
        }
        return undefined;
    }