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

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

js中的對象是基于哈希表結(jié)構(gòu)的，而哈希表的查找時間復(fù)雜度為O(1)，所以很多人喜歡用對象來做映射，減少遍歷循環(huá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;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3）再哈希法

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

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

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

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

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