摘要：的擴(kuò)展知識(shí)對(duì)于哈希表來(lái)說(shuō)，最重要的莫過(guò)于生成哈希串的哈希算法和處理沖突的策略了。由于鏈表的查找需要遍歷，如果我們將鏈表?yè)Q成樹(shù)或者哈希表結(jié)構(gòu)，那么就能大幅提高沖突元素的查找效率。

最近在整理數(shù)據(jù)結(jié)構(gòu)和算法相關(guān)的知識(shí)，小茄專門在github上開(kāi)了個(gè)repo https://github.com/qieguo2016...，后續(xù)內(nèi)容也會(huì)更新到這里，歡迎圍觀加星星！

js中的對(duì)象是基于哈希表結(jié)構(gòu)的，而哈希表的查找時(shí)間復(fù)雜度為O(1)，所以很多人喜歡用對(duì)象來(lái)做映射，減少遍歷循環(huán)。

比如常見(jiàn)的數(shù)組去重：

function arrayUnique(target) {
  var result = [target[0]];
  var temp = {};
  temp[target[0]] = true;
  for (var i = 1, targetLen = target.length; i < targetLen; i++) {
    if (typeof temp[target[i]] === "undefined") {
      result.push(target[i]);
      temp[target[i]] = true;
    }
  }
  return result;
}

這里使用了一個(gè)temp對(duì)象來(lái)保存出現(xiàn)過(guò)的元素，在循環(huán)中每次只需要判斷當(dāng)前元素是否在temp對(duì)象內(nèi)即可判斷出該元素是否已經(jīng)出現(xiàn)過(guò)。

上面的代碼看起來(lái)沒(méi)有問(wèn)題，但有點(diǎn)經(jīng)驗(yàn)的同學(xué)可能會(huì)說(shuō)了，假如目標(biāo)數(shù)組是[1,"1"], 這是2個(gè)不同類型元素，所以我們的期望值應(yīng)該是原樣輸出的。但結(jié)果卻是[1]。
同理的還有true、null等，也就是說(shuō)對(duì)象中的key在obj[key]時(shí)都被自動(dòng)轉(zhuǎn)成了字符串類型。
所以，如果要區(qū)分出不同的類型的話，temp里面的屬性值就不能是一個(gè)簡(jiǎn)單的true了，而是要包含幾種數(shù)據(jù)類型。比如可以是：

    temp[target[0]]={};
    temp[target[0]][(typeof temp[target[i]])] = 1;

在判斷的時(shí)候除了要判斷鍵是否存在之外，也要判斷對(duì)應(yīng)的數(shù)據(jù)類型計(jì)數(shù)是否大于1，以此來(lái)判斷元素是否重復(fù)。

另外，上面的代碼語(yǔ)法也有點(diǎn)問(wèn)題，不知道你發(fā)現(xiàn)了沒(méi)？
我們?cè)斓倪@個(gè)temp對(duì)象并不是完全空白，他是基于Object原型鏈繼承而來(lái)的，所以自帶了一個(gè)__proto__屬性，如果你的目標(biāo)數(shù)組里面恰好有"__proto__"這個(gè)值，返回的結(jié)果就有問(wèn)題了，具體結(jié)果可以自己測(cè)試確認(rèn)。解決方法有兩種：

1） 想辦法去掉這個(gè)磨人的__proto__。顯然，我們需要去掉原型鏈，那么可以使用Object.create(null)的方式來(lái)創(chuàng)建一個(gè)完全空白、無(wú)原型的空對(duì)象。

2） 使用!temp.hasOwnProperty(target[i])代替typeof temp[target[i]] === "undefined"，這時(shí)候代表原型鏈的__proto__屬性就不能干擾到我們的結(jié)果判斷了。 感謝@天生愛(ài)走神的指正，obj.hasOwnProperty(__proto__)會(huì)得到false，但是假如我們的目標(biāo)數(shù)組里面包含__proto__的話，就不能對(duì)__proto__進(jìn)行去重了。

上面說(shuō)了js中使用對(duì)象的一點(diǎn)小竅門，核心在于對(duì)象的hashmap結(jié)構(gòu)，那hashmap是怎樣的一個(gè)結(jié)構(gòu)呢？且聽(tīng)小茄細(xì)細(xì)道來(lái)。

在真實(shí)世界中，我們描述一個(gè)事物最常用的方式是使用屬性-值（key-value）這樣的鍵值對(duì)數(shù)據(jù)，面向?qū)ο缶幊讨袑?duì)象的定義和js中的對(duì)象都是這種模式。比如我們描述一個(gè)人是這樣的：

計(jì)算機(jī)存儲(chǔ)空間有兩個(gè)屬性：存儲(chǔ)地址和所存儲(chǔ)的值，機(jī)器可以根據(jù)給定的存儲(chǔ)地址去讀寫(xiě)該地址下的值。根據(jù)這種結(jié)構(gòu)，假如我們將一塊存儲(chǔ)空間分成一個(gè)一個(gè)的格子，然后將這些數(shù)據(jù)依次塞到每個(gè)格子里，接下來(lái)我們就可以根據(jù)格子編號(hào)直接訪問(wèn)格子的內(nèi)容了。這種方式就是數(shù)組（也叫線性連續(xù)表）：數(shù)組頭保存整個(gè)數(shù)組儲(chǔ)存空間的起始地址，不同下標(biāo)代表不同的儲(chǔ)存地址的偏移量，訪問(wèn)不同下標(biāo)所對(duì)應(yīng)的地址就能實(shí)現(xiàn)數(shù)組元素的讀寫(xiě)。所以，很自然就會(huì)想到將上述的鍵值對(duì)數(shù)據(jù)的key映射成數(shù)組下標(biāo)，接著讀寫(xiě)數(shù)組就變成了讀寫(xiě)value值。將key的字符串轉(zhuǎn)換成代表下標(biāo)數(shù)值比較簡(jiǎn)單，可以用特定的碼表（如ASCII）進(jìn)行轉(zhuǎn)換。

上述小明的屬性名（key）經(jīng)過(guò)變換，可能就變成了這樣：

由于key的值不同長(zhǎng)度不一，所以轉(zhuǎn)換后的下標(biāo)的值也相差巨大，另外key的個(gè)數(shù)不確定，也就意味著下標(biāo)的個(gè)數(shù)也有很大的范圍，甚至無(wú)窮多，就有了下面的問(wèn)題：

如果我們直接取下標(biāo)值作為存儲(chǔ)數(shù)組的下標(biāo)，雖然簡(jiǎn)單，但是你會(huì)發(fā)現(xiàn)這個(gè)長(zhǎng)度為10010的數(shù)組只存了8個(gè)值，太浪費(fèi)！如果我們想要縮短數(shù)組的長(zhǎng)度，比如縮為10，最簡(jiǎn)單的方式可以使用取模的方式來(lái)確定下標(biāo)：69 % 10 = 9，7 % 10 = 7, 198 % 10 = 8……。這個(gè)取模就是哈希算法、也叫散列算法。

通過(guò)這樣的方式得到的下標(biāo)分別為9、7、8、3、6、2、0，可以得到保存小明數(shù)據(jù)的數(shù)組：

但是這種方式很容易出現(xiàn)重復(fù)，假如我們?cè)黾右粋€(gè)屬性phone，對(duì)應(yīng)的映射值是29，那么29跟69算出來(lái)的下標(biāo)就重復(fù)了。也就是哈希算法中的沖突，也叫碰撞。好的哈希算法能極大減少沖突，但由于輸入幾乎是無(wú)窮的，而輸出卻要求在有限的空間內(nèi)，所以沖突是不可避免的。

還是上面這個(gè)例子，29和69發(fā)生了沖突，但是我們可以將他們組成一個(gè)鏈表，鏈表的頭部放在數(shù)組中，得到。鏈表結(jié)構(gòu)中，每個(gè)元素（除單向鏈表的尾部）都包含了相連元素的內(nèi)存地址和本身的值，上文中的沖突放入一個(gè)鏈表中，可以得到這樣的結(jié)構(gòu)：

最終得到的這個(gè)數(shù)據(jù)結(jié)構(gòu)，也就是我們常說(shuō)哈希表了。這種將數(shù)組與鏈表結(jié)合生成哈希表的方法，叫拉鏈法。

比如想知道小明的name屬性，即小明.name。流程是這樣的：

1）根據(jù)字符映射關(guān)系得到映射值為69
2）使用哈希算法得到下標(biāo) index=hash(69)=9
3）遍歷數(shù)組中下標(biāo)為9的鏈表，鏈表的第一個(gè)元素的key剛好就是我們要找的name，所以返回value值小明

哈希表中增刪一個(gè)元素并不會(huì)影響到其他的元素，不像數(shù)組一樣需要改變后面所有的元素下標(biāo)。在拉鏈?zhǔn)降墓１碇校瑢傩缘脑鰟h就是鏈表的增刪，非常方便。而在純數(shù)組形式的哈希表中，對(duì)屬性的刪并不是真的刪除，而是做一個(gè)空標(biāo)志而已，所以不影響其他元素。

對(duì)于哈希表來(lái)說(shuō)，最重要的莫過(guò)于生成哈希串的哈希算法和處理沖突的策略了。下面進(jìn)行簡(jiǎn)單的介紹。

根據(jù)上面的例子得知，哈希算法的目的就是將不定的輸入轉(zhuǎn)換成特定范圍的輸出，并且要求輸出盡量均勻分布。由于散列算法是應(yīng)用在每一次數(shù)據(jù)定位中的，它的使用頻率非常的高，這意味著我們必須要選擇簡(jiǎn)單的算法。散列算法有很多，這里簡(jiǎn)單介紹幾種。

1，除法散列法
最直觀的一種，小茄上文使用的就是這種散列法，公式：
index = key % 16

2，平方散列法
求index是非常頻繁的操作，而乘法的運(yùn)算要比除法來(lái)得省時(shí)（對(duì)現(xiàn)在的CPU來(lái)說(shuō)，估計(jì)我們感覺(jué)不出來(lái)），所以我們考慮把除法換成乘法和一個(gè)位移操作。公式：
index = (key * key) >> 28
如果數(shù)值分配比較均勻的話這種方法能得到不錯(cuò)的結(jié)果，另外key如果很大，key * key會(huì)發(fā)生溢出。但我們這個(gè)乘法不關(guān)心溢出，因?yàn)槲覀兏静皇菫榱双@取相乘結(jié)果，而是為了獲取index。

3，斐波那契（Fibonacci）散列法
平方散列法的缺點(diǎn)是顯而易見(jiàn)的，所以我們能不能找出一個(gè)理想的乘數(shù)，而不是拿value本身當(dāng)作乘數(shù)呢？答案是肯定的。

1，對(duì)于16位整數(shù)而言，這個(gè)乘數(shù)是40503
2，對(duì)于32位整數(shù)而言，這個(gè)乘數(shù)是2654435769
3，對(duì)于64位整數(shù)而言，這個(gè)乘數(shù)是11400714819323198485

這幾個(gè)“理想乘數(shù)”是如何得出來(lái)的呢？這跟一個(gè)法則有關(guān)，叫黃金分割法則，而描述黃金分割法則的最經(jīng)典表達(dá)式無(wú)疑就是著名的斐波那契數(shù)列，即如此形式的序列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,233, 377, 610， 987, 1597, 2584, 4181, 6765, 10946，…。

對(duì)我們常見(jiàn)的32位整數(shù)而言，公式：
index = (key* 2654435769) >> 28

上文介紹了拉鏈法來(lái)處理沖突，處理沖突的方法其實(shí)也有很多，下面簡(jiǎn)單介紹一下另外幾種：

1）拉鏈法變種。由于鏈表的查找需要遍歷，如果我們將鏈表?yè)Q成樹(shù)或者哈希表結(jié)構(gòu)，那么就能大幅提高沖突元素的查找效率。不過(guò)這樣做則會(huì)加大哈希表構(gòu)造的復(fù)雜度，也就是構(gòu)建哈希表時(shí)的效率會(huì)變差。

2）開(kāi)放尋址： 當(dāng)關(guān)鍵字key的哈希地址p=H（key）出現(xiàn)沖突時(shí)，以p為基礎(chǔ)，產(chǎn)生另一個(gè)哈希地址p1，如果p1仍然沖突，再以p為基礎(chǔ)，產(chǎn)生另一個(gè)哈希地址p2，…，直到找出一個(gè)不沖突的哈希地址pi，將相應(yīng)元素存入其中。這種方法有一個(gè)通用的函數(shù)形式：

Hi=（H（key）+di）% m i=1，2，…，n

根據(jù)di的不同，又可以分為線性的、平方的、隨機(jī)數(shù)之類的。。。這里不再展開(kāi)。

開(kāi)發(fā)尋址的好處是存儲(chǔ)空間更加緊湊，利用率高。但是這種方式讓沖突元素之間產(chǎn)生了聯(lián)系，在刪除元素的時(shí)候，不能直接刪除，否則就打亂了沖突元素的尋址鏈。

3）再哈希法

這種方法會(huì)預(yù)先定義一組哈希算法，發(fā)生沖突的時(shí)候，調(diào)用下一個(gè)哈希算法計(jì)算一直計(jì)算到不發(fā)生沖突的時(shí)候則插入元素，這種方法跟開(kāi)放尋址的方法優(yōu)缺點(diǎn)類似。函數(shù)表達(dá)式：

index=Hi（key） , i=1，2，…，n

哈希算法常用的場(chǎng)景除了上文所說(shuō)的快速查找之外，還有一個(gè)非常重要的應(yīng)用就是加密算法，這個(gè)加密更準(zhǔn)確的說(shuō)法是加簽，也即是“消息摘要”。

根據(jù)上文的基礎(chǔ)介紹可知，哈希算法就是將任意數(shù)據(jù)轉(zhuǎn)換成一定范圍數(shù)據(jù)的算法，這種算法的副作用就是會(huì)產(chǎn)生沖突。但是呢，在快速查找中出現(xiàn)的副作用，卻是加密功能中的核心，因?yàn)橛袥_突，所以從結(jié)果就無(wú)法逆推出輸入值，這樣就實(shí)現(xiàn)了數(shù)據(jù)的單向加密。而輸入數(shù)據(jù)的變化卻又會(huì)影響到哈希串的值，所以我們可以用哈希串來(lái)進(jìn)行數(shù)據(jù)的校驗(yàn)。

關(guān)于js對(duì)象與哈希相關(guān)的東西就說(shuō)到這里了，用文字總結(jié)一下之后發(fā)現(xiàn)很多知識(shí)點(diǎn)都明確了很多，尤其是要用最平白的語(yǔ)言組織出來(lái)，就必須有自己的理解才行。任何一個(gè)細(xì)節(jié)都可以看出很多東西，謹(jǐn)以此文與君共勉！