生意紅火

有一天你和你的鄰居同時(shí)開了一個(gè)快遞驛站，不過(guò)你的運(yùn)氣很好，每天都有很多快遞到你這里來(lái)，生意紅紅火火，然而，你的鄰居生意很冷清。

快遞一多，為了取件人方便找到快遞，于是你按照快遞手機(jī)號(hào)碼的最后兩位數(shù)字來(lái)給快遞分類，例如尾號(hào)為 01 的放到柜子 1 中，尾號(hào)為 02 的放到柜子 2 。如果有人來(lái)取快遞，他只需要報(bào)出他的手機(jī)號(hào)碼，就可以快速找到對(duì)應(yīng)的柜子，然后再根據(jù)完整的手機(jī)號(hào)碼在這個(gè)柜子里找到對(duì)應(yīng)的快件了。

心聲惡意的鄰居

日子一天天過(guò)去，你的店鋪越來(lái)越火，然而，你鄰居的生意冷清到哭暈在廁所里，但是你并沒(méi)有去在意你的鄰居，也沒(méi)有分擔(dān)點(diǎn)生意給他，于是，你的鄰居心生壞意，決定搞搞你。

他知道你是采用按照快件手機(jī)號(hào)碼末尾兩位來(lái)分類的，于是他分批買了大量非常廉價(jià)的物品，并且把大部分快遞的手機(jī)號(hào)碼的末尾的兩位弄成是一樣的。

于是，你收到了大量的快遞，并且大量的快遞都被分到了同一個(gè)柜子里，導(dǎo)致有些柜子里堆放了大量的快件，擠滿到不得不把一些放地下了，然而有些柜子里卻是空蕩蕩的。

這也不僅導(dǎo)致了資源分配不均勻，每次顧客來(lái)取快件的時(shí)候，還得找好久才能找到。

于是你老爸和你說(shuō)：要不加大柜子的容量吧。

你：加大容量沒(méi)用，雖然能短暫不會(huì)出現(xiàn)擠滿放地下的情況，但本質(zhì)問(wèn)題并沒(méi)有解決。

更換策略

為了解決這個(gè)問(wèn)題，于是你采取了別的策略，把手機(jī)號(hào)碼當(dāng)做一個(gè)數(shù)值，然后對(duì)這個(gè)數(shù)值進(jìn)行取余，例如 手機(jī)號(hào) % 99 = 柜子的編號(hào)。

每次客人來(lái)的時(shí)候，你把他的手機(jī)號(hào)碼也進(jìn)行取余，然后告訴他，去對(duì)應(yīng)的柜子取，取余這個(gè)操作雖然麻煩了點(diǎn)，工作量比之前大了，但，躲開了你鄰居的攻擊，也算值得。

問(wèn)題的本質(zhì)

然而好景不長(zhǎng)，你的鄰居通過(guò)觀察與測(cè)試，發(fā)現(xiàn)你是通過(guò)手機(jī)號(hào)碼取余來(lái)映射到對(duì)應(yīng)的柜子上的，于是，它又找了一堆手機(jī)號(hào)碼取余后值相同的手機(jī)號(hào)碼來(lái)搞定，于是，你又奔潰了。

你知道你侄子是學(xué)計(jì)算機(jī)專業(yè)的，于是你把這件事告訴了你的侄子，你的侄子一聽(tīng)到這個(gè)，就來(lái)了勁，于是管不住嘴吹了下面這一大堆：

告訴你，你的這種映射策略相當(dāng)于我平時(shí)學(xué)的哈希算法,不管你如何改變你的算法策略，只要被別人知道了你的哈希算法，那么，都會(huì)容易遭受到別人的攻擊，像你的鄰居的那種攻擊方式，就叫做哈希洪荒攻擊。

我們都知道，在各種數(shù)據(jù)結(jié)構(gòu)里，有平均時(shí)間復(fù)雜度和最差時(shí)間復(fù)雜度之分，對(duì)于哈希算法，我們插入 n 個(gè)到元素到數(shù)組里的話，平均時(shí)間復(fù)雜度是 O(n)，而最差的時(shí)間復(fù)雜度是 O(n^2);查找某個(gè)元素的平均復(fù)雜度是 O(1)，最差時(shí)間復(fù)雜度是 O(n)，而哈希洪荒攻擊就是攻擊者有意給出一些特殊值，使得我們每次都遇到了最差時(shí)間復(fù)雜度。

如何防御?

剛才說(shuō)了，哈希洪荒攻擊的本質(zhì)就是攻擊者掌握了你的哈希算法，所以如何想要防御的話，就需要我們?cè)O(shè)計(jì)出優(yōu)秀的哈希算法了，什么才算優(yōu)秀的哈希算法?

1、映射出來(lái)的哈希碼分布均勻。

2、不容易被破解。

當(dāng)然，不管你如何設(shè)計(jì)，一旦攻擊者掌握了你的算法細(xì)節(jié)，那么你都得涼。

那有沒(méi)有比較好的防御措施呢?

其實(shí)，我們可以通過(guò)生成一些隨機(jī)值來(lái)加強(qiáng)我們的哈希算法，例如，我們每次建立一張哈希表的時(shí)候，我們就隨機(jī)生成一個(gè)新的隨機(jī)值，來(lái)作為哈希算法的一部分。這樣一來(lái)，即使是同樣的內(nèi)容，放在不同的表里也會(huì)產(chǎn)生完全不同的哈希碼。

這樣一來(lái)，攻擊者就很難進(jìn)行預(yù)測(cè)了，即使發(fā)生了碰撞，也是小概率的巧合，而不是攻擊者在主動(dòng)控制，我們也把這個(gè)隨機(jī)的值稱之為哈希種子(Hash Seed)。而這類使用哈希種子的哈希算法，我們稱之為帶密鑰哈希算法(Keyed Hash Function)。

當(dāng)然，上面這種方式只是防御哈希洪荒攻擊的一種方式，對(duì)于哈希碰撞，在面試中問(wèn)的最多的應(yīng)該就是 Java 中的哈希表了，我跟大家補(bǔ)充講講 Java8 中是如何解決哈希碰撞的吧。

Java 中的哈希表如果出現(xiàn)了哈希沖突，就會(huì)用一個(gè)鏈表來(lái)存放哈希碼相同的元素，但是如果出現(xiàn)大量哈希碼相同的話，那么大量的元素都放在了同一條鏈表里，這樣會(huì)導(dǎo)致哈希表的查找時(shí)間復(fù)雜度是 O(n)，為了解決這個(gè)問(wèn)題，當(dāng)鏈表中的元素大于等于 8 的時(shí)候，就把用紅黑樹來(lái)取代鏈表，這樣一來(lái)，可以把最差時(shí)間復(fù)雜度控制在 O(logn)。

尾聲

你侄子吹了一大堆專業(yè)名詞，對(duì)于只讀過(guò)小學(xué)的你，想不懵逼都難，這個(gè)時(shí)候你憋不住了，拋了一句給你侄子：能不能講點(diǎn)人話?你只需要告訴我，我該怎么做就行了。

你侄子：我來(lái)去給你設(shè)計(jì)一個(gè)程序吧，你到時(shí)候只需要把你的手機(jī)號(hào)碼進(jìn)去就可以了，它會(huì)把你自動(dòng)映射出對(duì)應(yīng)的柜子。

最后，鄰居把店鋪拆了，開了一家網(wǎng)吧…..