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

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

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

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

這段話里加粗的地方暫時(shí)存疑，因?yàn)楹拖乱痪湓捳f(shuō)法有沖突，感覺改為根據(jù)哈希函數(shù)與鍵計(jì)算出來(lái)的值，即哈希值訪問(wèn)內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)會(huì)好點(diǎn)（當(dāng)然也有可能是我閱讀理解不好，哈哈）

哈希表是

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

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

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

數(shù)組是直接尋址

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

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

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

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

直接尋址的缺點(diǎn)在于如果數(shù)據(jù)量很大，占用空間就很大，因?yàn)槭紫饶愕贸跏蓟粋€(gè)巨大的數(shù)組，無(wú)論數(shù)據(jù)是否存入。如果用一句話總結(jié)哈希表就是：hash濃縮為一句話:將元素通過(guò)一個(gè)函數(shù)轉(zhuǎn)換為整數(shù),使得該整數(shù)可以盡量唯一的表達(dá)這個(gè)元素

但是在js中其實(shí)這個(gè)問(wèn)題有待于商榷，因?yàn)閖s的數(shù)組還有對(duì)象都可以存任意鍵值而且無(wú)需提前定義長(zhǎng)度，還可以隨意增刪。所以有的文章就指出其實(shí)js的數(shù)組和對(duì)象就的底層實(shí)現(xiàn)就是哈希表（文章地址），雖然文章中只是提到對(duì)象，但是基于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除以一個(gè)數(shù)mod得到的余數(shù)作為hash值的方法，通過(guò)這個(gè)哈希函數(shù)可以把很大的數(shù)轉(zhuǎn)換為不超過(guò)mod的整數(shù)，這表示數(shù)組的長(zhǎng)度必須不小于mod(js中無(wú)所謂)，當(dāng)mod是一個(gè)素?cái)?shù)時(shí)H(key)能盡可能的覆蓋[0,mod)范圍內(nèi)的每一個(gè)數(shù)。

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

線性探查法

平方探查法

鏈地址法

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

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

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

        _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;//找一個(gè)素?cái)?shù)用來(lái)限制數(shù)組大小
        }
        insert(key,value){
            if(typeof key !="object"){//可以只接受一個(gè)對(duì)象
                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"))
這個(gè)代碼里用了對(duì)象嵌套對(duì)象的形式實(shí)現(xiàn)了鏈地址法處理沖突在C語(yǔ)言中會(huì)選擇數(shù)組+鏈表的形式實(shí)現(xiàn)，當(dāng)后面寫到鏈表的時(shí)候會(huì)重新改一下。其實(shí)就像上文中所述，js中的對(duì)象可能就是封裝一個(gè)哈希表，而且key值是唯一的，連哈希函數(shù)貌似都可以省了了。
參考書目
《算法筆記》
《算法導(dǎo)論》
《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法》
《ECMAScript 6 入門》