摘要：簡介哈希表又被稱為散列表，可能是翻譯的問題好多書上一會兒稱散列一會兒稱哈希，更有甚者煞有介事的對此進行區(qū)分。實現(xiàn)哈希表我們將要實現(xiàn)這個類分別實現(xiàn)插入查找刪除打印等方法。

哈希表(hash table)又被稱為散列表，可能是翻譯的問題好多書上一會兒稱散列一會兒稱哈希，更有甚者煞有介事的對此進行區(qū)分。經(jīng)過簡單的搜索（wiki鏈接）發(fā)現(xiàn)這兩個詞是一回事。由此可見學(xué)好英語是多么重要。（我是一名渴望學(xué)好英語的英文渣。。）

這里引用一下維基百科的定義：

散列表（Hash table，也叫哈希表），是根據(jù)鍵（Key）而直接訪問在內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過計算一個關(guān)于鍵值的函數(shù)(Hash function)，將所需查詢的數(shù)據(jù)映射到表中一個位置來訪問記錄，這加快了查找速度。這個映射函數(shù)稱做散列函數(shù)，存放記錄的數(shù)組稱做散列表。

這段話里加粗的地方暫時存疑，因為和下一句話說法有沖突，感覺改為根據(jù)哈希函數(shù)與鍵計算出來的值，即哈希值訪問內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)會好點（當(dāng)然也有可能是我閱讀理解不好，哈哈）

哈希表是

一種動態(tài)（指數(shù)據(jù)存入后，還會進行增刪查改等工作）集合結(jié)構(gòu)

至少需要支持insert，search，delete等操作

普通數(shù)組的推廣概念

數(shù)組是直接尋址

當(dāng)實際存儲的key數(shù)量小于key的總數(shù)量，使用哈希表是直接數(shù)組尋址的有效替代

不是直接把key作為數(shù)組下標，而是根據(jù)哈希函數(shù)與key計算出相應(yīng)的下標

資料找多了會發(fā)現(xiàn)一個很嚴重的問題，它們之間可能會有沖突，從簡介中介紹的名字問題就可以看出。同樣，有些書把直接尋址表也視作一種哈希表，不過哈希表既然是數(shù)組的一種推廣，那也就不要在這些細枝末節(jié)上計較了。

當(dāng)關(guān)鍵詞的數(shù)量比較小時，這種方法是一種簡單有效的方法，在我的文章《如何隨機&&去重返回新數(shù)組》中3.1節(jié)給出的方法就用到了直接尋址處理問題，代碼中數(shù)組indexArr就是。這是一種空間換時間的做法，定義一個大于等于key數(shù)量的數(shù)組，value部分全部初始化為null，然后進行數(shù)據(jù)的存取。這也是我們經(jīng)常使用的。

直接尋址的缺點在于如果數(shù)據(jù)量很大，占用空間就很大，因為首先你得初始化一個巨大的數(shù)組，無論數(shù)據(jù)是否存入。如果用一句話總結(jié)哈希表就是：hash濃縮為一句話:將元素通過一個函數(shù)轉(zhuǎn)換為整數(shù),使得該整數(shù)可以盡量唯一的表達這個元素

但是在js中其實這個問題有待于商榷，因為js的數(shù)組還有對象都可以存任意鍵值而且無需提前定義長度，還可以隨意增刪。所以有的文章就指出其實js的數(shù)組和對象就的底層實現(xiàn)就是哈希表（文章地址），雖然文章中只是提到對象，但是基于js存在key-value形式的數(shù)組，我猜原理應(yīng)該很是類似。

設(shè)哈希函數(shù)為H，數(shù)據(jù)的鍵設(shè)為key，轉(zhuǎn)換后的值為整數(shù)H(key)。常見的有平方取中發(fā)，除留余數(shù)法，線性變化法（H(key)=a*key+b）。這里著重介紹除留余數(shù)法。

公式：
$$ H(key)=key\%mod $$

把key除以一個數(shù)mod得到的余數(shù)作為hash值的方法，通過這個哈希函數(shù)可以把很大的數(shù)轉(zhuǎn)換為不超過mod的整數(shù)，這表示數(shù)組的長度必須不小于mod(js中無所謂)，當(dāng)mod是一個素數(shù)時H(key)能盡可能的覆蓋[0,mod)范圍內(nèi)的每一個數(shù)。

看3.2.1的公式就可以知道，必然會出現(xiàn)兩個不同的key1，key2他們的hash的值H(key1)=H(key2)。如果直接把hash值作為數(shù)組下表標則會出現(xiàn)覆蓋的情況，我們稱之為沖突，由此看出hash函數(shù)不是單射，這樣也就表明hash值是不可逆的。

線性探查法

平方探查法

鏈地址法

1，2都要重新計算hash值，3不需要，而且3是C語言里常見的解決方法，思想是把所有H(key)相同的key連成一條單鏈表（當(dāng)然用一個數(shù)組也是可以的），然后查找時遍歷單鏈表尋找數(shù)據(jù)。這些都是底層，大部分語言都封裝有庫。

字符串hash是指將一個字符串S映射為一個整數(shù)，使得該整數(shù)可以盡可能唯一地代表字符串S。為什么要這么做呢，因為好多語言的數(shù)組的下標只能接受整數(shù)，例如C語言這種靜態(tài)的語言和js這種動態(tài)語言數(shù)據(jù)存儲上差異很大。js中使用對象存儲key-value形式的數(shù)據(jù)增刪查改都非常方便，但是在C語言中需要很多數(shù)據(jù)結(jié)構(gòu)配合的使用才能實現(xiàn)。

  function hashFunc(s="hello word"){
        let id=0,len,arr=[];
        len=s.length;
        arr=s.split("");
        for(let i=0;i
js實現(xiàn)這個函數(shù)還是很方便的，就是字符ascii碼相加即可。當(dāng)然還可以使用更復(fù)雜的方式來避免沖突。
3.5js實現(xiàn)哈希表
我們將要實現(xiàn)hashTable這個類分別實現(xiàn)插入、查找、刪除、打印等方法。
    class HashTable {
        constructor() {
            this.table = {"3212":{"ffffd":"ffffd","ee":"2312"}};//測試遞歸是否正常
        }

        _hashFunc(key) {
            let id = 0, len, arr = [];
            len = key.length;
            arr = key.split("");
            for (let i = 0; i < len; i++) {
                id += arr[i].charCodeAt();//str.charCodeAt(index)用于獲取字符的ascii碼
            }
            return id%57;//找一個素數(shù)用來限制數(shù)組大小
        }
        insert(key,value){
            if(typeof key !="object"){//可以只接受一個對象
                let id = this._hashFunc(key);
                if(!this.table[id]){
                    this.table[id]={};
                }
                if(!this.table[id][key]){
                    this.table[id][key]=value;
                }
            }else{
                for(let i in key){
                    this.insert(i,key[i])
                }
            }

        }
        search(key){
            let id = this._hashFunc(key);
            if(!this.table[id] || !this.table[id][key]) return null;
            return this.table[id][key];
        }
        delete(key){
            let id = this._hashFunc(key);
            if(this.table[id])
                if(this.table[id][key])
                   return delete this.table[id][key]
        }
        print(table=this.table){//遞歸輸出hashtable的值
            if(typeof table=="object"){
                for(let key in table){
                    this.print(table[key])
                    if(typeof table[key]!="object")
                    console.log(key,"+",table[key])
                }
            }

        }
    }
    let hash = new HashTable()
    hash.insert({"abc":"ffffd@qq.com","bac":"33@qq.com","ddic":"2343@gmail.com"});
    hash.print();
    console.warn("delete abc")
    hash.delete("abc");
    hash.print();
    console.log(hash.search("bac"))
這個代碼里用了對象嵌套對象的形式實現(xiàn)了鏈地址法處理沖突在C語言中會選擇數(shù)組+鏈表的形式實現(xiàn)，當(dāng)后面寫到鏈表的時候會重新改一下。其實就像上文中所述，js中的對象可能就是封裝一個哈希表，而且key值是唯一的，連哈希函數(shù)貌似都可以省了了。
參考書目
《算法筆記》
《算法導(dǎo)論》
《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法》
《ECMAScript 6 入門》