散列表的英文叫“Hash Table”，我們平時也叫它“哈希表”或者“Hash 表”吩翻。

散列表用的是數(shù)組支持按照下標隨機訪問數(shù)據(jù)的特性兜看，所以散列表其實就是數(shù)組的一種擴展，由數(shù)組演化而來狭瞎∠敢疲可以說，如果沒有數(shù)組熊锭，就沒有散列表弧轧。

鍵、散列函數(shù)碗殷、散列值的關(guān)系

散列函數(shù)

散列函數(shù)精绎，我們可以把它定義成hash(key)，其中 key 表示元素的鍵值亿扁，hash(key) 的值表示經(jīng)過散列函數(shù)計算得到的散列值捺典。

三點散列函數(shù)設(shè)計的基本要求

• 散列函數(shù)計算得到的散列值是一個非負整數(shù)；
• 如果 key1 = key2从祝，那 hash(key1) == hash(key2)襟己；
• 如果 key1 ≠ key2引谜，那 hash(key1) ≠ hash(key2)；

第三點理解起來可能會有問題擎浴，我著重說一下员咽。這個要求看起來合情合理，但是在真實的情況下贮预，要想找到一個不同的 key 對應的散列值都不一樣的散列函數(shù)贝室，幾乎是不可能的。即便像業(yè)界著名的MD5仿吞、SHA滑频、CRC等哈希算法，也無法完全避免這種散列沖突唤冈。而且峡迷，因為數(shù)組的存儲空間有限，也會加大散列沖突的概率你虹。

所以我們幾乎無法找到一個完美的無沖突的散列函數(shù)绘搞，即便能找到，計算成本也是很大的傅物，所以針對散列沖突問題夯辖，我們需要通過其他途徑來解決。

散列沖突

再好的散列函數(shù)也無法避免散列沖突董饰。那究竟該如何解決散列沖突問題呢蒿褂？我們常用的散列沖突解決方法有兩類，開放尋址法（open addressing）和鏈表法（chaining）尖阔。

1. 開放尋址法

它的核心思想是如果出現(xiàn)了散列沖突贮缅，我們就重新探測一個空閑位置榨咐，將其插入介却。

那如何重新探測新的位置呢？我先講一個比較簡單的探測方法块茁，線性探測（Linear Probing）齿坷。

當我們往散列表中插入數(shù)據(jù)時，如果某個數(shù)據(jù)經(jīng)過散列函數(shù)散列之后数焊，存儲位置已經(jīng)被占用了永淌，我們就從當前位置開始，依次往后查找佩耳，看是否有空閑位置遂蛀，直到找到為止。

舉一個例子具體給你說明一下干厚。這里面黃色的色塊表示空閑位置李滴，橙色的色塊表示已經(jīng)存儲了數(shù)據(jù)螃宙。

在散列表中查找元素的過程有點兒類似插入過程。我們通過散列函數(shù)求出要查找元素的鍵值對應的散列值所坯，然后比較數(shù)組中下標為散列值的元素和要查找的元素谆扎。如果相等，則說明就是我們要找的元素芹助；否則就順序往后依次查找堂湖。如果遍歷到數(shù)組中的空閑位置，還沒有找到状土，就說明要查找的元素并沒有在散列表中无蜂。

散列表跟數(shù)組一樣，不僅支持插入蒙谓、查找操作酱讶，還支持刪除操作。對于使用線性探測法解決沖突的散列表彼乌，刪除操作稍微有些特別泻肯。我們不能單純地把要刪除的元素設(shè)置為空。

還記得我們剛講的查找操作嗎慰照？在查找的時候灶挟，一旦我們通過線性探測方法，找到一個空閑位置毒租，我們就可以認定散列表中不存在這個數(shù)據(jù)稚铣。但是，如果這個空閑位置是我們后來刪除的墅垮，就會導致原來的查找算法失效惕医。本來存在的數(shù)據(jù)，會被認定為不存在算色。這個問題如何解決呢抬伺？

我們可以將刪除的元素，特殊標記為 deleted灾梦。當線性探測查找的時候峡钓，遇到標記為 deleted 的空間，并不是停下來若河，而是繼續(xù)往下探測能岩。

你可能已經(jīng)發(fā)現(xiàn)了，線性探測法其實存在很大問題萧福。當散列表中插入的數(shù)據(jù)越來越多時拉鹃，散列沖突發(fā)生的可能性就會越來越大，空閑位置會越來越少，線性探測的時間就會越來越久膏燕。極端情況下炭庙，我們可能需要探測整個散列表，所以最壞情況下的時間復雜度為 O(n)煌寇。同理焕蹄，在刪除和查找時，也有可能會線性探測整張散列表阀溶，才能找到要查找或者刪除的數(shù)據(jù)腻脏。

對于開放尋址沖突解決方法，除了線性探測方法之外银锻，還有另外兩種比較經(jīng)典的探測方法永品，二次探測（Quadratic probing）和雙重散列（Double hashing）。

所謂二次探測击纬，跟線性探測很像鼎姐，線性探測每次探測的步長是 1，那它探測的下標序列就是 hash(key)+0更振，hash(key)+1炕桨，hash(key)+2……而二次探測探測的步長就變成了原來的“二次方”，也就是說肯腕，它探測的下標序列就是

所謂雙重散列实撒，意思就是不僅要使用一個散列函數(shù)姊途。我們使用一組散列函數(shù) hash1(key)，hash2(key)知态，hash3(key)……我們先用第一個散列函數(shù)捷兰，如果計算得到的存儲位置已經(jīng)被占用，再用第二個散列函數(shù)负敏，依次類推贡茅，直到找到空閑的存儲位置。

不管采用哪種探測方法原在，當散列表中空閑位置不多的時候友扰，散列沖突的概率就會大大提高彤叉。為了盡可能保證散列表的操作效率庶柿，一般情況下，我們會盡可能保證散列表中有一定比例的空閑槽位秽浇。我們用裝載因子（load factor）來表示空位的多少浮庐。

裝載因子的計算公式是：

散列表的裝載因子 = 填入表中的元素個數(shù) / 散列表的長度

裝載因子越大，說明空閑位置越少泌霍，沖突越多更啄，散列表的性能會下降晾嘶。

2. 鏈表法

鏈表法是一種更加常用的散列沖突解決辦法南片，相比開放尋址法诈胜，它要簡單很多遮精。我們來看這個圖啰扛，在散列表中疙描，每個“桶（bucket）”或者“槽（slot）”會對應一條鏈表璧坟，所有散列值相同的元素我們都放到相同槽位對應的鏈表中既穆。

當插入的時候，我們只需要通過散列函數(shù)計算出對應的散列槽位雀鹃，將其插入到對應鏈表中即可幻工，所以插入的時間復雜度是 O(1)。

當查找黎茎、刪除一個元素時囊颅，我們同樣通過散列函數(shù)計算出對應的槽，然后遍歷鏈表查找或者刪除傅瞻。那查找或刪除操作的時間復雜度是多少呢踢代？

實際上，這兩個操作的時間復雜度跟鏈表的長度 k 成正比嗅骄，也就是 O(k)奸鬓。對于散列比較均勻的散列函數(shù)來說，理論上講掸读，k=n/m串远，其中 n 表示散列中數(shù)據(jù)的個數(shù)，m 表示散列表中“槽”的個數(shù)儿惫。

開篇解答

Word 文檔中單詞拼寫檢查功能是如何實現(xiàn)的澡罚？

常用的英文單詞有 20 萬個左右，假設(shè)單詞的平均長度是 10 個字母肾请，平均一個單詞占用 10 個字節(jié)的內(nèi)存空間留搔，那 20 萬英文單詞大約占 2MB 的存儲空間，就算放大 10 倍也就是 20MB铛铁。對于現(xiàn)在的計算機來說隔显，這個大小完全可以放在內(nèi)存里面。所以我們可以用散列表來存儲整個英文單詞詞典饵逐。

當用戶輸入某個英文單詞時括眠，我們拿用戶輸入的單詞去散列表中查找。如果查到倍权，則說明拼寫正確掷豺；如果沒有查到，則說明拼寫可能有誤，給予提示当船。借助散列表這種數(shù)據(jù)結(jié)構(gòu)题画，我們就可以輕松實現(xiàn)快速判斷是否存在拼寫錯誤。

內(nèi)容小結(jié)

今天我講了一些比較基礎(chǔ)德频、比較偏理論的散列表知識苍息，包括散列表的由來、散列函數(shù)壹置、散列沖突的解決方法档叔。

散列表來源于數(shù)組，它借助散列函數(shù)對數(shù)組這種數(shù)據(jù)結(jié)構(gòu)進行擴展蒸绩，利用的是數(shù)組支持按照下標隨機訪問元素的特性衙四。散列表兩個核心問題是散列函數(shù)設(shè)計和散列沖突解決。散列沖突有兩種常用的解決方法患亿，開放尋址法和鏈表法传蹈。散列函數(shù)設(shè)計的好壞決定了散列沖突的概率，也就決定散列表的性能步藕。

針對散列函數(shù)和散列沖突惦界，今天我只講了一些基礎(chǔ)的概念、方法咙冗，下一節(jié)我會更貼近實戰(zhàn)沾歪、更加深入探討這兩個問題。

課后思考

• 假設(shè)我們有 10 萬條 URL 訪問日志雾消，如何按照訪問次數(shù)給 URL 排序灾搏？

• 有兩個字符串數(shù)組，每個數(shù)組大約有 10 萬條字符串立润，如何快速找出兩個數(shù)組中相同的字符串狂窑？