很多人談起“哈希表”，就會直接聚焦到hash函數(shù)、“散列”/“雜湊”之類不明所以的大詞上，搞的初學者一頭霧水，完全不明白這東西是干嘛用的，更不知道什么時候該用它、怎么用它、出現(xiàn)問題如何解決。

那么，這里我就從問題開始，一步步把哈希表的來龍去脈剖析清楚。

想象一下：有一天，你開車到某商場去買東西。買完東西，你想不起自己的車在哪了。

這家商場非常非常大，樓下停車場少說停了上萬臺車；而你的健忘癥又比較厲害……

那么，問題來了：你怎樣才能找到自己的車？

一個理想的情形是，你從頭到尾一行一行一輛一輛按順序走一遍就找到了；運氣最差時，你搜遍樓下N輛車，發(fā)現(xiàn)你的車在末尾——拿術(shù)語說，這個復(fù)雜度是O(N)。

能不能更快一些呢？

很簡單，假如所有車按車牌號順序排列，你直接往停車場中間走就行了；如果你的車牌號大于中間那輛車，那么你就往停車場后半部分的中間走，否則就往前半場走……依此類推。

如此一來，你最多只需要走ln（N）次“中間”，就能找到你的車了。黑話叫復(fù)雜度O(ln N)。

還能不能更給力一些？

可以。

假設(shè)這個停車場非常非常大，大到可以給每個車牌號分配一個固定的停車位；那么只要你把自己的車牌號報給看門老頭，他拎著你的衣領(lǐng)子往后一丟，你就“吧唧”一下掉自己車頂上了——嗯，你看，一車一位，就是這么任性。

這就叫“查找復(fù)雜度O(1)”。

如果用程序?qū)崿F(xiàn)的話，就是這么一個數(shù)組：

car park[MAX_CAR_NUM]

第一個場景，你要直接以一個循環(huán)遍歷park中的每個元素。

第二個場景，你只需先訪問MAX_CAR_NUM除以2的那個位置，再根據(jù)車牌號大小訪問數(shù)組前半拉或者后半拉中間的元素即可。

第三個場景，你的車牌號就是數(shù)組下標，所以你只需直接訪問park[CAR_NUMBER]即可。

那么，第三個設(shè)計是不是完全解決問題了呢？

并不是。

很容易看出，第三個方案需要一個超級大的存儲空間。

這個空間得有多大呢？

它必須大到足以和過去未來的一切有效車牌號一一對應(yīng)，你才可能做到“直接按號訪問”。

假設(shè)車牌號共8位，每位可以使用26個英文字母或10個阿拉伯數(shù)字，那么不同的車牌號共有36^8=2821109907456種。

哪怕每輛車只需一個字節(jié)的存儲空間，這也是接近3T的空間！

而事實上，哪怕最大的超市，修一個夠停一萬輛車的停車場也都太夸張了。

你看，這完全行不通啊。

那么，有沒有辦法在得到O(1)的查找效率的同時、又不付出太大的空間代價呢？

沒錯，的確是有的。這就是哈希表。

哈希表是怎么玩的呢？

很簡單，我們把你的車牌號看作一個8位36進制的數(shù)字；為了方便，我們可以把它轉(zhuǎn)換成十進制。

那么，你的車牌號就是一個不大于2821109907456的數(shù)字。

現(xiàn)在，我們把你的車牌號除以一萬，只取余數(shù)——你看，你的車牌號是不是就和0~10000之間的數(shù)字對應(yīng)起來了？

很好，你的車就停在這個數(shù)字對應(yīng)的停車位上，過去開就是了——O(1)的查找效率！

這個“把你的車牌號映射進0~10000之間”的操作，就是所謂的“散列”“雜湊”“哈?！被蛘遠ash（當然，實踐上，為了盡量減少沖突，哈希表的空間大小會盡量取質(zhì)數(shù)）。

相對于“以key為下標直接訪問的數(shù)組”，哈希表是“時間換空間”；相對于二分法查找，哈希表又是“以空間換時間”。這種“中庸”的定位使得它在許多場合極為好用。

等等，你發(fā)覺不對：我的車尾號3456，我朋友的車也是這個尾號。我們總不能停在同一個位置吧？

你這個方案有瑕疵啊！

沒錯，hash可能會把不同的數(shù)據(jù)映射到同一個點上，術(shù)語稱其為“碰撞”。

由于hash自身的基本原理，碰撞是不可避免的。

怎么解決這個“碰撞”問題呢？

幾種解決思路：

1、臨時加個“立體車庫”，哪里碰撞往哪放。于是車子就可以在同一位置“撂起來”存了。這叫“開鏈表法”。

2、車庫面積肯定是夠的。3456號被人占了，你存3457不就好了！

換句話說，過去的散列函數(shù)是 （車牌號 模除 10000），發(fā)現(xiàn)碰撞了就換散列函數(shù) （車牌號加1 模除 10000）試一試——這叫“再散列法”。

3、再修個小車庫，碰撞了的停小車庫去（小車庫可以隨便停，也可以搞一套別的機制）

總之，如此一來，我們就同時得到了“O（1）的查找效率”和“可接受的空間消耗”。

任何時候，當你有“數(shù)量有限”但“不同索引數(shù)量極大”的一些數(shù)據(jù)，必需極高的訪問效率同時又不想無端消耗太多的存儲空間時，你就可以考慮使用哈希表了。

當然，請注意，因為沖突的存在，哈希表雖然有著優(yōu)異的平均訪問時間（常數(shù)訪問效率！）；但它的“最大訪問時間”卻是沒有保證的——你可能一個微秒甚至幾個納秒就拿到了數(shù)據(jù)，也可能幾十個毫秒了還在鏈表上狂奔。因此實時性要求嚴格的場合，用它前需要謹慎考慮。

知道了哈希表的設(shè)計思路，我們就可以進入稍微困難一些的部分了。

我們已經(jīng)知道，所謂“哈希表”，實際上是我們把對象（value）的“鍵值（key)”轉(zhuǎn)換成了“數(shù)組下標”；然后就可以借助這個下標一步到位的找到對應(yīng)對象（value）了。

但這中間有“瑕疵”存在：和身份證號和公民一一對應(yīng)不同，鍵值和下標并不是一對一的關(guān)系。就好像你的車牌尾號是23456而你朋友是53456，結(jié)果把你們安排到同一個停車位一樣。

很容易想到，很多數(shù)據(jù)的鍵值（key）分布存在一定的規(guī)律。

比如，身份證其中4位是你的出生年份，這四位其實只能當兩位用；再如，手機號碼前3位只可能是135、132、153等少數(shù)數(shù)字……

那么，如果我們的“鍵值轉(zhuǎn)換數(shù)組下標的函數(shù)（也就是哈希函數(shù)）”選擇不當（比如給手機前幾位、身份證的出生年份字段這些相對缺乏變化的數(shù)據(jù)過高權(quán)值），就很容易使得“碰撞”頻繁出現(xiàn)。

這就對哈希函數(shù)的選擇提出了要求。

但是哈希函數(shù)本身也不應(yīng)該過于復(fù)雜，不然每次計算耗時太久——O(1)雖然是常數(shù)時間；但如果時間常數(shù)太長，它可能就不如O（lnN）查找算法快。

要知道，在一百萬數(shù)據(jù)里面做二分法搜索，最差時也不過需要20次搜索而已；如果你的哈希函數(shù)本身需要的計算時間已經(jīng)超過了這個限度，那么改用二分法顯然是個更為理智的選擇：不僅更快，還更省空間。

工程問題，向來是需要根據(jù)實際情況靈活選擇、做出合理折衷的。

扯遠了。

繼續(xù)說哈希函數(shù)。

很顯然，用于哈希表的哈希函數(shù)可不能是MD5或者sha1系列函數(shù)，太慢；但也不能直接模除一個整數(shù)，太容易出現(xiàn)沖突。

簡單說就是：哈希表用到的哈希函數(shù)，一方面要能盡量把key均勻散布在表空間中（從而盡量減少沖突），另一方面又要有盡量快的計算速度。

這類函數(shù)有很多種，稍微搜一搜就能找到很多。

無論如何，原理所限，哈希表中碰撞無法絕對避免。

當碰撞發(fā)生時，就不得不使用開鏈表法或再散列法存儲沖突數(shù)據(jù)；而這必將影響哈希表的性能。

很容易想到，如果哈希表很大、里面卻沒存幾條數(shù)據(jù)，那么它出現(xiàn)沖突（碰撞）的幾率就會很?。环粗?，如果哈希表已經(jīng)接近滿了，那么每條新加入的數(shù)據(jù)都會產(chǎn)生碰撞。

換句話說，在哈希函數(shù)選擇合理的前提下，想要減少碰撞，就只能擴大哈希表占用的空間。

哈希表實際所存數(shù)據(jù)量和哈希表最大容量之間的比值，叫做哈希表的“加載因子”。

加載因子越小，沖突的概率就越低，但浪費大量空間；加載因子越高，沖突概率越大，但空間浪費就越少。這是一個需要根據(jù)工程實踐靈活選擇的折衷值。很多語言提供的hash表允許你主動調(diào)節(jié)這個值。

一般來說，一個較為平衡的加載因子大約是0.7~0.8左右。這樣既不會浪費太多空間，也不至于出現(xiàn)太多沖突。

另一方面，因為哈希表使用的哈希函數(shù)較為簡單，因此對惡意的攻擊者來說，他可以精心構(gòu)造一大堆數(shù)據(jù)提交給你——所有這些數(shù)據(jù)散列后全都存在一個格子里。

我們前面提到過，當遇到這種沖突/碰撞時，為了避免彼此覆蓋，這些數(shù)據(jù)就要存在鏈表中（或者再散列后存在同一個哈希表中）。

當這些數(shù)據(jù)被存進鏈表時，對它們的訪問效率將降到O(N)——因為鏈表搜索效率只有O(N)。

之前就發(fā)生過這種攻擊，包括Java在內(nèi)的許多種語言全部落馬。

解決方案也很簡單：

1、提高哈希函數(shù)復(fù)雜度，想辦法加入隨機性（相當于每次使用一個不同的哈希函數(shù)），避免被人輕易捕捉到弱點

2、不要用開鏈表法存儲沖突數(shù)據(jù)，采用“再散列法”，并且使用不同的哈希函數(shù)再散列、還可以把沖突數(shù)據(jù)存入另一個表——要構(gòu)造同時讓兩個以上不同的哈希函數(shù)沖突的攻擊數(shù)據(jù)，難度就大得多了。

總之，哈希表是用途廣泛的一種數(shù)據(jù)結(jié)構(gòu)，也是很多編程語言提供的基礎(chǔ)服務(wù)之一（比如python的dict）。

你完全可以傻瓜式的使用它，無須搞懂它的一切；但想要把它用精、用好，你還是需要真正理解它的來龍去脈——千萬不要 像某種最好的語言的作者那樣，拿函數(shù)名長度當哈希值（哎呀一不小心又黑人了，頂鍋逃……

想揍人你們找他：賀師?。篜HP黑系列之二：PHP 為什么函數(shù)命名是如此不一致？

RECOMMEND

- 點個在看你最好看 -