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

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

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

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

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

哈希表是

一種動態（指數據存入后，還會進行增刪查改等工作）集合結構

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

普通數組的推廣概念

數組是直接尋址

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

不是直接把key作為數組下標，而是根據哈希函數與key計算出相應的下標

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

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

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

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

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

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

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

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

線性探查法

平方探查法

鏈地址法

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

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

  function hashFunc(s="hello word"){
        let id=0,len,arr=[];
        len=s.length;
        arr=s.split("");
        for(let i=0;i
js實現這個函數還是很方便的，就是字符ascii碼相加即可。當然還可以使用更復雜的方式來避免沖突。
3.5js實現哈希表
我們將要實現hashTable這個類分別實現插入、查找、刪除、打印等方法。
    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;//找一個素數用來限制數組大小
        }
        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"))
這個代碼里用了對象嵌套對象的形式實現了鏈地址法處理沖突在C語言中會選擇數組+鏈表的形式實現，當后面寫到鏈表的時候會重新改一下。其實就像上文中所述，js中的對象可能就是封裝一個哈希表，而且key值是唯一的，連哈希函數貌似都可以省了了。
參考書目
《算法筆記》
《算法導論》
《學習JavaScript數據結構與算法》
《ECMAScript 6 入門》