布隆，牛逼！布谷鳥，牛逼！
在早期文章里面我曾經(jīng)寫過(guò)布隆過(guò)濾器：
哎，這糟糕透頂?shù)呐虐妫谎噪y盡.......
其實(shí)寫文章和寫代碼一樣。
看到一段辣眼睛的代碼，正想口吐芬芳：這是哪個(gè)煞筆寫的代碼？
結(jié)果定睛一看，代碼上寫的作者居然是自己。
甚至還不敢相信，還要打開看一下 git 的提交記錄。
發(fā)現(xiàn)確實(shí)是自己幾個(gè)月前親手敲出來(lái)，并且提交的代碼。
于是默默的改掉。
出現(xiàn)這種情況我也常常安慰自己：沒事，這是好事啊，說(shuō)明我在進(jìn)步。
好了，說(shuō)正事。
當(dāng)時(shí)的文章里面我說(shuō)布隆過(guò)濾器的內(nèi)部原理我說(shuō)不清楚。
其實(shí)我只是懶得寫而已，這玩意又不復(fù)雜，有啥說(shuō)不清楚的？
布隆過(guò)濾器
布隆過(guò)濾器，在合理的使用場(chǎng)景中具有四兩撥千斤的作用，由于使用場(chǎng)景是在大量數(shù)據(jù)的場(chǎng)景下，所以這東西類似于秒殺，雖然沒有真的落地用過(guò)，但是也要說(shuō)的頭頭是道。
常見于面試環(huán)節(jié)：比如大集合中重復(fù)數(shù)據(jù)的判斷、緩存穿透問(wèn)題等。
先分享一個(gè)布隆過(guò)濾器在騰訊短視頻產(chǎn)品中的真實(shí)案例：
https://toutiao.io/posts/mtrvsx/preview
那么布隆過(guò)濾器是怎么做到上面的這些需求的呢？
首先，布隆過(guò)濾器并不存儲(chǔ)原始數(shù)據(jù)，因?yàn)樗墓δ苤皇轻槍?duì)某個(gè)元素，告訴你該元素是否存在而已。并不需要知道布隆過(guò)濾器里面有那些元素。
當(dāng)然，如果我們知道容器里面有哪些元素，就可以知道一個(gè)元素是否存在。
但是，這樣我們需要把出現(xiàn)過(guò)的元素都存儲(chǔ)下來(lái)，大數(shù)據(jù)量的情況下，這樣的存儲(chǔ)就非常的占用空間。
布隆過(guò)濾器是怎么做到不存儲(chǔ)元素，又知道一個(gè)元素是否存在呢？
說(shuō)破了其實(shí)就很簡(jiǎn)單：一個(gè)長(zhǎng)長(zhǎng)的數(shù)組加上幾個(gè) Hash 算法。
在上面的示意圖中，一共有三個(gè)不同的 Hash 算法、一個(gè)長(zhǎng)度為 10 的數(shù)組，數(shù)組里面存儲(chǔ)的是 bit 位，只放 0 和 1。初始為 0。
假設(shè)現(xiàn)在有一個(gè)元素 [why] ，要經(jīng)過(guò)這個(gè)布隆過(guò)濾器。
首先 [why] 分別經(jīng)過(guò)三個(gè) Hash 算法，得出三個(gè)不同的數(shù)字。
Hash 算法可以保證得出的數(shù)字是在 0 到 9 之間，即不超過(guò)數(shù)組長(zhǎng)度。
我們假設(shè)計(jì)算結(jié)果如下：
Hash1(why)=1 Hash2(why)=4 Hash3(why)=8
對(duì)應(yīng)到圖片中就是這樣的：
這時(shí)，如果 [why] 又來(lái)了，經(jīng)過(guò) Hash 算法得出的下標(biāo)還是 1,4,8，發(fā)現(xiàn)數(shù)組對(duì)應(yīng)的位置上都是 1。表明這個(gè)元素極有可能出現(xiàn)過(guò)。
注意，這里說(shuō)的是極有可能。也就是說(shuō)會(huì)存在一定的誤判率。
我們先再存入一個(gè)元素 [jay]。
Hash1(jay)=0 Hash2(jay)=5 Hash3(jay)=8
此時(shí)，我們把兩個(gè)元素匯合一下，就有了下面這個(gè)圖片：
其中的下標(biāo)為 8 的位置，比較特殊，兩個(gè)元素都指向了它。
這個(gè)圖片這樣看起來(lái)有點(diǎn)難受，我美化一下：
好了，現(xiàn)在這個(gè)數(shù)組變成了這樣：
你說(shuō)，你只看這個(gè)玩意，你能知道這個(gè)過(guò)濾器里面曾經(jīng)有過(guò) why 和 jay 嗎？
別說(shuō)你不知道了，就連過(guò)濾器本身都不知道。
現(xiàn)在，假設(shè)又來(lái)了一個(gè)元素 [Leslie]，經(jīng)過(guò)三個(gè) Hash 算法，計(jì)算結(jié)果如下：
Hash1(Leslie)=0 Hash2(Leslie)=4 Hash3(Leslie)=5
通過(guò)上面的元素，可以知道此時(shí) 0,4,5 這三個(gè)位置上都是 1。
布隆過(guò)濾器就會(huì)覺得這個(gè)元素之前可能出現(xiàn)過(guò)。于是就會(huì)返回給調(diào)用者：[Leslie]曾經(jīng)出現(xiàn)過(guò)。
但是實(shí)際情況呢？
其實(shí)我們心里門清，[Leslie] 不曾來(lái)過(guò)。
這就是誤報(bào)的情況。
這就是前面說(shuō)的：布隆過(guò)濾器說(shuō)存在的元素，不一定存在。
而一個(gè)元素經(jīng)過(guò)某個(gè) hash 計(jì)算后，如果對(duì)應(yīng)位置上的值是 0，那么說(shuō)明該元素一定不存在。
但是它有一個(gè)致命的缺點(diǎn)，就是不支持刪除。
為什么？
假設(shè)要?jiǎng)h除 [why]，那么就要把 1,4,8 這三個(gè)位置置為 0。
但是你想啊，[jay] 也指向了位置 8 呀。
如果刪除 [why] ，位置 8 變成了 0，那么是不是相當(dāng)于把 [jay] 也移除了？
為什么不支持刪除就致命了呢？
你又想啊，本來(lái)布隆過(guò)濾器就是使用于大數(shù)據(jù)量的場(chǎng)景下，隨著時(shí)間的流逝，這個(gè)過(guò)濾器的數(shù)組中為 1 的位置越來(lái)越多，帶來(lái)的結(jié)果就是誤判率的提升。從而必須得進(jìn)行重建。
所以，文章開始舉的騰訊的例子中有這樣一句話：
除了刪除這個(gè)問(wèn)題之外，布隆過(guò)濾器還有一個(gè)問(wèn)題：查詢性能不高。
因?yàn)檎鎸?shí)場(chǎng)景中過(guò)濾器中的數(shù)組長(zhǎng)度是非常長(zhǎng)的，經(jīng)過(guò)多個(gè)不同 Hash 函數(shù)后，得到的數(shù)組下標(biāo)在內(nèi)存中的跨度可能會(huì)非常的大。跨度大，就是不連續(xù)。不連續(xù)，就會(huì)導(dǎo)致 CPU 緩存行命中率低。
這玩意，這么說(shuō)呢。就當(dāng)八股文背起來(lái)吧。
踏雪留痕，雁過(guò)留聲，這就是布隆過(guò)濾器。
如果你想玩一下布隆過(guò)濾器，可以訪問(wèn)一下這個(gè)網(wǎng)站：
https://www.jasondavies.com/bloomfilter/
左邊插入，右邊查詢：
如果要布隆過(guò)濾器支持刪除，那么怎么辦呢？
有一個(gè)叫做 Counting Bloom Filter。
它用一個(gè) counter 數(shù)組，替換數(shù)組的比特位，這樣一比特的空間就被擴(kuò)大成了一個(gè)計(jì)數(shù)器。
用多占用幾倍的存儲(chǔ)空間的代價(jià)，給 Bloom Filter 增加了刪除操作。
這也是一個(gè)解決方案。
但是還有更好的解決方案，那就是布谷鳥過(guò)濾器。
另外，關(guān)于布隆過(guò)濾器的誤判率，有一個(gè)數(shù)學(xué)推理公式。很復(fù)雜，很枯燥，就不講了，有興趣的可以去了解一下。
http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html
布谷鳥 hash
布谷鳥過(guò)濾器，第一次出現(xiàn)是在 2014 年發(fā)布的一篇論文里面：《Cuckoo Filter: Practically Better Than Bloom》
https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
但是在講布谷鳥過(guò)濾器之前，得簡(jiǎn)單的鋪墊一下 Cuckoo hashing，也就是布谷鳥 hash 的知識(shí)。
因?yàn)檫@個(gè)詞是論文的關(guān)鍵詞，在文中出現(xiàn)了 52 次之多。
Cuckoo hashing，最早出現(xiàn)在這篇 2001 年的論文之中：
https://www.cs.tau.ac.il/~shanir/advanced-seminar-data-structures-2009/bib/pagh01cuckoo.pdf
主要看論文的這個(gè)地方：
它的工作原理，總結(jié)起來(lái)是這樣的：
它有兩個(gè) hash 表，記為 T1，T2。
兩個(gè) hash 函數(shù)，記為 h1，h2。
當(dāng)一個(gè)不存在的元素插入的時(shí)候，會(huì)先根據(jù) h1 計(jì)算出其在 T1 表的位置，如果該位置為空則可以放進(jìn)去。
如果該位置不為空，則根據(jù) h2 計(jì)算出其在 T2 表的位置，如果該位置為空則可以放進(jìn)去。
如果該位置不為空，就把當(dāng)前位置上的元素踢出去，然后把當(dāng)前元素放進(jìn)去就行了。
也可以隨機(jī)踢出兩個(gè)位置中的一個(gè)，總之會(huì)有一個(gè)元素被踢出去。
被踢出去的元素怎么辦呢？
沒事啊，它也有自己的另外一個(gè)位置。
論文中的偽代碼是這樣的：
看不懂沒關(guān)系，我們畫個(gè)示意圖：
上面的圖說(shuō)的是這樣的一個(gè)事兒：
我想要插入元素 x，經(jīng)過(guò)兩個(gè) hash 函數(shù)計(jì)算后，它的兩個(gè)位置分別為 T1 表的 2 號(hào)位置和 T2 表的 1 號(hào)位置。
兩個(gè)位置都被占了，那就隨機(jī)把 T1 表 2 號(hào)位置上的 y 踢出去吧。
而 y 的另一個(gè)位置被 z 元素占領(lǐng)了。
于是 y 毫不留情把 z 也踢了出去。
z 發(fā)現(xiàn)自己的備用位置還空著（雖然這個(gè)備用位置也是元素 v 的備用位置），趕緊就位。
所以，當(dāng) x 插入之后，圖就變成了這樣：
上面這個(gè)圖其實(shí)來(lái)源就是論文里面（a）：
這種類似于套娃的解決方式看是可行，但是總是有出現(xiàn)循環(huán)踢出導(dǎo)致放不進(jìn) x 的問(wèn)題。
比如上圖中的（b）。
當(dāng)遇到這種情況時(shí)候，說(shuō)明布谷鳥 hash 已經(jīng)到了極限情況，應(yīng)該進(jìn)行擴(kuò)容，或者 hash 函數(shù)的優(yōu)化。
所以，你再次去看偽代碼的時(shí)候，你會(huì)明白里面的 MaxLoop 的含義是什么了。
這個(gè) MaxLoop 的含義就是為了避免相互踢出的這個(gè)過(guò)程執(zhí)行次數(shù)太多，設(shè)置的一個(gè)閾值。
其實(shí)我理解，布谷鳥 hash 是一種解決 hash 沖突的騷操作。
如果你想上手玩一下，可以訪問(wèn)這個(gè)網(wǎng)站：
http://www.lkozma.net/cuckoo_hashing_visualization/
當(dāng)踢來(lái)踢去了 16 （MaxLoop）次還沒插入完成后，它會(huì)告訴你，需要 rehash 并對(duì)數(shù)組擴(kuò)容了：
布谷鳥 hash 就是這么一回事，一場(chǎng)踢來(lái)踢去的游戲。
接著，我們看布谷鳥過(guò)濾器。
布谷鳥過(guò)濾器
布谷鳥過(guò)濾器的論文《Cuckoo Filter: Practically Better Than Bloom》開篇第一頁(yè)，里面有這樣一段話。
直接和布隆過(guò)濾器正面剛：我布谷鳥過(guò)濾器，就是比你屌一點(diǎn)。
上來(lái)就指著別人的軟肋懟：
標(biāo)準(zhǔn)的布隆過(guò)濾器的一大限制是不能刪除已經(jīng)存在的數(shù)據(jù)。如果使用它的變種，比如 Counting Bloom Filter，但是空間卻被撐大了 3 到 4 倍，巴拉巴拉巴拉......
而我就比較騷了：
這篇論文將要證明的是，與標(biāo)準(zhǔn)布隆過(guò)濾器相比，我支持刪除，在空間或性能上并不需要更高的開銷。
我，布谷鳥過(guò)濾器是一個(gè)實(shí)用的數(shù)據(jù)結(jié)構(gòu)，提供了四大優(yōu)勢(shì)：
1.支持動(dòng)態(tài)的新增和刪除元素。 2.提供了比傳統(tǒng)布隆過(guò)濾器更高的查找性能，即使在空間接近滿的情況下（比如空間利用率達(dá)到 95% 的時(shí)候）。 3.比諸如商過(guò)濾器（quotient filter，另一種過(guò)濾器）之類的替代方案更容易實(shí)現(xiàn)。 4.如果要求錯(cuò)誤率小于 3%，那么在許多實(shí)際應(yīng)用中，它比布隆過(guò)濾器占用的空間更小。
布谷鳥過(guò)濾器的 API 無(wú)非就是插入、查詢和刪除嘛。
其中最重要的就是插入，看一下：
論文中的部分，你大概瞟一眼，看不明白沒關(guān)系，我這不是馬上給你分析一波嗎。
插入部分的偽代碼，可以看到一點(diǎn)布谷鳥 hash 的影子，因?yàn)榫褪腔谶@個(gè)東西來(lái)的。
那么最大的變化在什么地方呢？
無(wú)非就是 hash 函數(shù)的變化。
看的我目瞪狗呆，心想：
首先，我們回憶一下布谷鳥 hash，它存儲(chǔ)的是插入元素的原始值，比如 x。
x 會(huì)經(jīng)過(guò)兩個(gè) hash 函數(shù)，如果我們記數(shù)組的長(zhǎng)度為 L，那么就是這樣的：
p1 = hash1(x) % L p2 = hash2(x) % L
非常容易理解，是我認(rèn)知范圍內(nèi)的東西。
而布谷鳥過(guò)濾器計(jì)算位置是怎樣的呢？
h1(x) = hash(x), h2(x) = h1(x) ⊕ hash(x’s fingerprint).
我們可以看到，計(jì)算 h2（位置2）時(shí)，對(duì) x 的 fingerprint 進(jìn)行了一個(gè) hash 計(jì)算。
“指紋”的概念一會(huì)再說(shuō)，我們先關(guān)注位置的計(jì)算。
這題就稍微有點(diǎn)超綱了，我慢慢說(shuō)。
上面算法中的異或運(yùn)算確保了一個(gè)重要的性質(zhì)：位置 h2 可以通過(guò)位置 h1 和 h1 中存儲(chǔ)的“指紋”計(jì)算出來(lái)。
說(shuō)人話就是：只要我們知道一個(gè)元素的位置（h1）和該位置里面存儲(chǔ)的“指紋”信息，那么我們就可以知道該“指紋”的備用位置（h2）。
因?yàn)槭褂玫漠惢蜻\(yùn)算，所以這兩個(gè)位置具有對(duì)偶性。
由于具有對(duì)偶性，那么其實(shí)我們只要知道其中的任意一個(gè)位置，就能知道對(duì)應(yīng)的另外一個(gè)位置。
只要保證 hash(x’s fingerprint) !=0，那么就可以確保 h2!=h1，也就可以確保不會(huì)出現(xiàn)自己踢自己的死循環(huán)問(wèn)題。
另外，為什么要對(duì)“指紋”進(jìn)行一個(gè) hash 計(jì)算之后，在進(jìn)行異或運(yùn)算呢？
論文中給出了一個(gè)反證法：如果不進(jìn)行 hash 計(jì)算，假設(shè)“指紋”的長(zhǎng)度是 8bit，那么其對(duì)偶位置算出來(lái)，距離當(dāng)前位置最遠(yuǎn)也才 256。
為啥，論文里面寫了：
因?yàn)槿绻爸讣y”的長(zhǎng)度是 8bit，那么異或操作只會(huì)改變當(dāng)前位置 h1(x) 的低 8 位，高位不會(huì)改變。
就算把低 8 位全部改了，算出來(lái)的位置也就是我剛剛說(shuō)的：最遠(yuǎn) 256 位。
所以，對(duì)“指紋”進(jìn)行哈希處理可確保被踢出去的元素，可以重新定位到哈希表中完全不同的存儲(chǔ)桶中，從而減少哈希沖突并提高表利用率。
然后這個(gè) hash 函數(shù)還有個(gè)問(wèn)題你發(fā)現(xiàn)了沒？
它沒有對(duì)數(shù)組的長(zhǎng)度進(jìn)行取模，那么它怎么保證計(jì)算出來(lái)的下標(biāo)一定是落在數(shù)組中的呢？
這個(gè)就得說(shuō)到布谷鳥過(guò)濾器的另外一個(gè)限制了。
其強(qiáng)制數(shù)組的長(zhǎng)度必須是 2 的指數(shù)倍。
2 的指數(shù)倍的二進(jìn)制一定是這樣的：10000000...（n個(gè)0）。
這個(gè)限制帶來(lái)的好處就是，進(jìn)行異或運(yùn)算時(shí)，可以保證計(jì)算出來(lái)的下標(biāo)一定是落在數(shù)組中的。
這個(gè)限制帶來(lái)的壞處就是：
布谷鳥過(guò)濾器：我支持刪除操作。 布隆過(guò)濾器：我不需要限制長(zhǎng)度為 2 的指數(shù)倍。 布谷鳥過(guò)濾器：我查找性能比你高。 布隆過(guò)濾器：我不需要限制長(zhǎng)度為 2 的指數(shù)倍。 布谷鳥過(guò)濾器：我空間利用率也高。 布隆過(guò)濾器：我不需要限制長(zhǎng)度為 2 的指數(shù)倍。 布谷鳥過(guò)濾器：我煩死了，TMD！
接下來(lái)，說(shuō)一下“指紋”。
這是論文中第一次出現(xiàn)“指紋”的地方。
“指紋”其實(shí)就是插入的元素進(jìn)行一個(gè) hash 計(jì)算，而 hash 計(jì)算的產(chǎn)物就是幾個(gè) bit 位。
布谷鳥過(guò)濾器里面存儲(chǔ)的就是元素的“指紋”。
查詢數(shù)據(jù)的時(shí)候，就是看看對(duì)應(yīng)的位置上有沒有對(duì)應(yīng)的“指紋”信息：
刪除數(shù)據(jù)的時(shí)候，也只是抹掉該位置上的“指紋”而已：
由于是對(duì)元素進(jìn)行 hash 計(jì)算，那么必然會(huì)出現(xiàn) hash 碰撞的問(wèn)題，也就是“指紋”相同的情況，也就是會(huì)出現(xiàn)誤判的情況。
沒有存儲(chǔ)原數(shù)據(jù)，所以犧牲了數(shù)據(jù)的準(zhǔn)確性，但是只保存了幾個(gè) bit，因此提升了空間效率。
說(shuō)到空間利用率，你想想布谷鳥 hash 的空間利用率是多少？
在完美的情況下，也就是沒有發(fā)生哈希沖突之前，它的空間利用率最高只有 50%。
因?yàn)闆]有發(fā)生沖突，說(shuō)明至少有一半的位置是空著的。
除了只存儲(chǔ)“指紋”，布谷鳥過(guò)濾器還能怎么提高它的空間利用率的呢？
看看論文里面怎么說(shuō)的：
前面的 (a)、(b) 很簡(jiǎn)單，還是兩個(gè) hash 函數(shù)，但是沒有用兩個(gè)數(shù)組來(lái)存數(shù)據(jù)，就是基于一維數(shù)組的布谷鳥 hash ，核心還是踢來(lái)踢去，不多說(shuō)了。
重點(diǎn)在于 (c)，對(duì)數(shù)組進(jìn)行了展開，從一維變成了二維。
每一個(gè)下標(biāo)，可以放 4 個(gè)元素了。
你可以理解為之前一個(gè)下標(biāo)是一個(gè)圓板凳，上面只能放一個(gè)屁股。
而現(xiàn)在你可以把一個(gè)下標(biāo)看成一個(gè)四方桌，可以坐四個(gè)人，打麻將了。
這樣一個(gè)小小的轉(zhuǎn)變，空間利用率從 50% 直接到了 98%：
我就問(wèn)你怕不怕？
上面截圖的論文中的第一點(diǎn)就是在陳訴這樣一個(gè)事實(shí)：
當(dāng) hash 函數(shù)固定為 2 個(gè)的時(shí)候，如果一個(gè)下標(biāo)只能放一個(gè)元素，那么空間利用率是 50%。
但是如果一個(gè)下標(biāo)可以放 2，4，8 個(gè)元素的時(shí)候，空間利用率就會(huì)飆升到 84%，95%，98%。
到這里，我們明白了布谷鳥過(guò)濾器對(duì)布谷鳥 hash 的優(yōu)化點(diǎn)和對(duì)應(yīng)的工作原理。
看起來(lái)一切都是這么的完美。
各項(xiàng)指標(biāo)都比布隆過(guò)濾器好，主打的是支持刪除的操作。
但是真的這么好嗎？
當(dāng)我看到論文第六節(jié)的這一段的時(shí)候，沉默了：
對(duì)重復(fù)數(shù)據(jù)進(jìn)行限制：如果需要布谷鳥過(guò)濾器支持刪除，它必須知道一個(gè)數(shù)據(jù)插入過(guò)多少次。不能讓同一個(gè)數(shù)據(jù)插入 kb+1 次。其中 k 是 hash 函數(shù)的個(gè)數(shù)，b 是一個(gè)下標(biāo)的位置能放幾個(gè)元素。
比如 2 個(gè) hash 函數(shù)，一個(gè)二維數(shù)組，它的每個(gè)下標(biāo)最多可以插入 4 個(gè)元素。那么對(duì)于同一個(gè)元素，最多支持插入 8 次。
例如下面這種情況：
why 已經(jīng)插入了 8 次了，如果再次插入一個(gè) why，則會(huì)出現(xiàn)循環(huán)踢出的問(wèn)題，直到最大循環(huán)次數(shù)，然后返回一個(gè) false。
怎么避免這個(gè)問(wèn)題呢？
我們維護(hù)一個(gè)記錄表，記錄每個(gè)元素插入的次數(shù)就行了。
雖然邏輯簡(jiǎn)單，但是架不住數(shù)據(jù)量大呀。你想想，這個(gè)表的存儲(chǔ)空間又怎么算呢？
想想就難受。
如果你要用布谷鳥過(guò)濾器的刪除操作，那么這份難受，你不得不承受。
最后，再看一下各個(gè)類型過(guò)濾器的對(duì)比圖吧：
還有，其中的數(shù)學(xué)推理過(guò)程，不說(shuō)了，看的眼睛疼，而且看這玩意容易掉頭發(fā)。
荒腔走板
你知道為什么叫做“布谷鳥”嗎？
布谷鳥，又叫杜鵑。
《本草綱目》有這樣的記載：“鸤鳩不能為巢，居他巢生子”。這里描述的就是杜鵑的巢寄生行為。巢寄生指的是鳥類自己不筑巢，把卵產(chǎn)在其他種類鳥類的巢中，由宿主代替孵化育雛的繁殖方式，包括種間巢寄生（寄生者和宿主為不同物種）和種內(nèi)巢寄生（寄生者和宿主為同一物種）。現(xiàn)今一萬(wàn)多種鳥類中，有一百多種具有巢寄生的行為，其中最典型的就是大杜鵑。
就是說(shuō)它自己把蛋下到別的鳥巢中，讓別的鳥幫它孵小雞。哦不，孵小鳥。
小杜鵑孵出來(lái)了后，還會(huì)把同巢的其他親生鳥蛋推出鳥巢，好讓母鳥專注于喂養(yǎng)它。
我的天吶，這也太殘忍了吧。
但是這個(gè)“推出鳥巢”的動(dòng)作，不正和上面描述的算法是一樣的嗎？
只是我們的算法還更加可愛一點(diǎn)，被推出去的鳥蛋，也就是被踢出去的元素，會(huì)放到另外一個(gè)位置上去。
我查閱資料的時(shí)候，當(dāng)我知道布谷鳥就是杜鵑鳥的時(shí)候我都震驚了。
好多詩(shī)句里面都有杜鵑啊，比如我很喜歡的，唐代詩(shī)人李商隱的《錦瑟》：
錦瑟無(wú)端五十弦，一弦一柱思華年。
莊生曉夢(mèng)迷蝴蝶，望帝春心托杜鵑。
滄海月明珠有淚，藍(lán)田日暖玉生煙。
此情可待成追憶，只是當(dāng)時(shí)已惘然。
自古以來(lái)。對(duì)于這詩(shī)到底是在說(shuō)“悼亡”還是“自傷”的爭(zhēng)論就沒停止過(guò)。
但是這重要嗎？
對(duì)我來(lái)說(shuō)這不重要。
重要的是，在適當(dāng)?shù)臅r(shí)機(jī)，適當(dāng)?shù)臍夥障拢貞浧疬^(guò)去的事情的時(shí)候能適當(dāng)?shù)膩?lái)上一句：“此情可待成追憶，只是當(dāng)時(shí)已惘然”。
而不是說(shuō)：哎，現(xiàn)在想起來(lái)，很多事情沒有好好珍惜，真TM后悔。
哦，對(duì)了。
寫文章的時(shí)候我還發(fā)現(xiàn)了一件事情。
布隆過(guò)濾器是 1970 年，一個(gè)叫做 Burton Howard Bloom 的大佬提出來(lái)的東西。
我寫這些東西的時(shí)候，就想看看大佬到底長(zhǎng)什么樣子。
但是神奇的事情發(fā)生了，我前前后后，花了幾天，墻內(nèi)墻外翻了個(gè)底朝天，居然沒有找到大佬的任何一張照片。
我的尋找，止步于發(fā)現(xiàn)了這個(gè)網(wǎng)站：
https://www.quora.com/Where-can-one-find-a-photo-and-biographical-details-for-Burton-Howard-Bloom-inventor-of-the-Bloom-filter
這個(gè)問(wèn)題應(yīng)該是在 9 年前就被人問(wèn)出來(lái)了，也就是 2012 年的時(shí)候：
確實(shí)是在網(wǎng)上沒有找到關(guān)于 Burton Howard Bloom 的照片。
真是一個(gè)神奇又低調(diào)的大佬。
有可能是一個(gè)傾國(guó)傾城的美男子吧。
最后說(shuō)一句（求關(guān)注）
好了，看到了這里安排個(gè)“一鍵三連”（轉(zhuǎn)發(fā)、在看、點(diǎn)贊）吧，周更很累的，不要白嫖我，需要一點(diǎn)正反饋。
才疏學(xué)淺，難免會(huì)有紕漏，如果你發(fā)現(xiàn)了錯(cuò)誤的地方，可以在后臺(tái)提出來(lái)，我對(duì)其加以修改。
推薦?? ：Github掘金計(jì)劃：Github上的一些優(yōu)質(zhì)項(xiàng)目搜羅
推薦?? ：星球一周年福利
推薦?? ：嘮嘮嗑！大學(xué)那會(huì)接私活賺了3w+
推薦?? ：怎么吃透一個(gè) Java 項(xiàng)目？新人如何上手一個(gè)項(xiàng)目的開發(fā)？