[[260358]]

春招來襲啦！又要面試啦！

程序員面試展示什么最重要？當時是你淵博的計算機學識，以及聰明的小腦瓜。

如果你學富五車，上知深度學習， 下知財務會計，那短短數(shù)小時也絕不夠你表演。所以，你一定得知曉面試官的套路，隨口丟出幾個應景的“冷知識”賣個乖巧。

如果你基礎不行，三天前剛準備轉(zhuǎn)碼，那就更得準備幾個的小把戲，不用打腫臉也能充一回胖子。

基于這兩個需求，今天文摘菌就來給大家介紹三個討巧的數(shù)據(jù)結(jié)構(gòu)。面試當中一提，那可是相當撐場面。

這三個數(shù)據(jù)結(jié)構(gòu)就是。登登登等…

1. 布隆過濾器（bloom filter）

2. 前綴樹（prefix trie）

3. 環(huán)形緩沖（ring buffer）

先來說一下，為什么挑了這三個數(shù)據(jù)結(jié)構(gòu)。

首先我覺得，你提到的數(shù)據(jù)結(jié)構(gòu)要稍微冷門一些，這樣別人就會認為你了解很多不同類型的數(shù)據(jù)結(jié)構(gòu)。但它不能太冷門，以免你的面試官要求你真正解釋實現(xiàn)細節(jié)或原理，那時你就game over了。***是你提到的數(shù)據(jù)結(jié)構(gòu)有點冷門，但你的面試官聽說過，對它有印象。

面試官都希望自己什么都知道，他們聽說過這種數(shù)據(jù)結(jié)構(gòu)但又不太了解，當你向他們介紹時，他們就會覺得你懂得特別多。

除此之外，這些數(shù)據(jù)結(jié)構(gòu)還應該具有實際用例，以便在技術(shù)面試的時候，你能有機會展開介紹。它雖然稍微有點冷門但也不能太low，你如果只知道一些菜雞水平的數(shù)據(jù)結(jié)構(gòu)（比如雙向鏈表），你的面試八成就涼了。

所以，這三個數(shù)據(jù)結(jié)構(gòu)就被***選中啦！

布隆過濾器

布隆過濾器是集合的概率版本。檢測集合是否包含某元素的時間復雜度為O(1)、空間復雜度為O(N)。Bloom過濾器也可以檢測出集合是否可能包含該元素，它的時間復雜度為O(1)，而空間復雜度只需要O(1)！

誰會真正使用布隆過濾器？

Chrome需要在不犧牲速度或空間的情況下保護你免受訪問垃圾郵件網(wǎng)站。

想象一下，如果每次你點擊一個鏈接，Chrome都必須進行網(wǎng)絡通話來檢查它龐大的垃圾郵件URL數(shù)據(jù)庫，然后才允許你訪問這個頁面，這會不會讓你等瘋掉。此外，設想一下，如果Chrome改善延遲的解決方案是在本地存儲整個垃圾郵件URL列表，這根本就是不可行的！

所以，chrome在本地存儲了一個潛在垃圾郵件URL的布隆過濾器，這既節(jié)省時間又節(jié)省空間，可以快速檢查給定的URL是否為垃圾郵件。對于普通的URL，布隆過濾器對“非垃圾郵件”的響應就足夠判定了。如果一個URL被標記為“可能是垃圾郵件”，那么Google可以在跳轉(zhuǎn)之前檢查它真實數(shù)據(jù)庫。事實證明，當你愿意犧牲絕對時，你可以做出偉大的事情！

布隆過濾器的原理

布隆過濾器的維基百科頁用大量的術(shù)語描述了實現(xiàn)細節(jié)，所以在這里我會用簡單的描述一下實現(xiàn)過程。如果你想要更精確的細節(jié)，你應該去看看維基百科。我會略過很多步驟，但我會讓你有一個大致了解。

如果你想在Bloom過濾器中插入一個元素，首先假設有N個不同的確定性哈希函數(shù)。當同一個元素輸入不同哈希函數(shù)時，會得到不同的值（沖突是可以有的）。

使用每個哈希函數(shù)的輸出作為數(shù)組的索引[注釋1，注釋2]，并對應每個索引i將數(shù)組[i]設置為true。插入元素就完成了！插入元素的時間復雜度是O(1)，因為對每個插入元素所做的唯一工作是運行恒定數(shù)量的哈希函數(shù)，并設置恒定數(shù)量的數(shù)組索引。

那該如何檢查布隆過濾器是否包含該元素？ 再次運行所有相同的哈希函數(shù)！

哈希函數(shù)是確定性的，因此相同的輸入應返回相同的輸出。所以相對應每個索引，檢查布隆過濾器的數(shù)組是否在該索引處設置為true即可。如果哈希函數(shù)輸出的數(shù)組的每個單元都為真，那么可以很高的概率說這個元素已經(jīng)插入到了布隆過濾器中。這一方法總是存在誤報的可能性。不過，布隆過濾器的一大特色是永遠不會出現(xiàn)漏報。

那么，你需要多少個哈希函數(shù)，又需要多大的數(shù)組呢？這你就得好好算一番了。維基百科對它們的解釋更詳細，你值得一讀。

注釋1：如何使用哈希函數(shù)的輸出作為索引：設哈希函數(shù)輸出整數(shù)值M，取長度N。N%M（N mod M）得到一個值Q，即0≤Q

注釋2：實際上，你應該使用位數(shù)組而不是普通數(shù)組。數(shù)組的每個元素至少需要1個字節(jié)，而你只需要為“數(shù)組”的每個元素存儲true / false。因此，你可以通過將其存儲為位數(shù)組來節(jié)省空間，這是這個數(shù)據(jù)結(jié)構(gòu)的重點。如果你想要聽起來很聰明，那么位數(shù)組（也就是位向量）也值得你在面試時提出。嗯，真正的面試專家建議總是在腳注中。

注釋3：嚴格來說，如果你的所有哈希函數(shù)都在O（1）時間內(nèi)運行，那么插入的復雜度才是O（1）。

前綴樹（prefix trie）

前綴樹是一種數(shù)據(jù)結(jié)構(gòu)，允許你通過其前綴快速查找字符串，還可以查找有公共前綴的字符串。

我對介紹這一數(shù)據(jù)結(jié)構(gòu)的***條建議是，將它稱為“前綴樹”，而不僅僅是“樹”。這樣，你就讓面試官知道你是那種了解與前綴和后綴相關算法的人，并且你也希望對你的fancy數(shù)據(jù)結(jié)構(gòu)進行準確描述。后綴樹也是一個非常有趣的話題，但實現(xiàn)細節(jié)十分殘暴。這就是為什么我只是談論前綴樹，并且假裝了解后綴樹。

誰會真的用前綴樹？

基因組學研究人員！

事實證明，現(xiàn)代基因組研究在很大程度上依賴于字符串算法和數(shù)據(jù)結(jié)構(gòu)，因為你試圖從組成基因組序列的數(shù)百萬個核苷酸中探索奧秘。對于基因組數(shù)據(jù)，你經(jīng)常需要對齊序列，找到差異或找到重復的模式。如果你想了解更多相關信息，可以先閱讀生物信息學讀物，然后參與“DNA測序算法”或“生物信息學算法”等課程。

如果你想要閱讀一些真正有意思的讀物，我強烈建議你讀一讀藥物基因組學。隨著基因組測序和字符串算法的進步，我們實際上可以預測使用個體的基因組，來確定它們是否具有對藥物正確反應的正確基因。例如，如果他們的基因組缺少用于產(chǎn)生處理某種藥物的酶的基因，那么藥物可能會對他們產(chǎn)生副作用。如果我們知道什么基因是重要的，我們可以給他們一種不同的藥物！

我承認，前綴樹和基因組學之間的聯(lián)系不太緊密。其實前綴樹的最直接用法就是用來查字典啦！但光這么講不是忒無聊了點么。

前綴樹的原理

想象一下，你有一棵樹，每個節(jié)點都有一個包含26個子節(jié)點的數(shù)組，每個子節(jié)點對應一個英文字母。（如果要包含其他字符，可以將26更改為不同的值。）要在你的樹中表示單詞，你將從根節(jié)點開始，沿著路徑向下走，并在每個節(jié)點添加一個字母。

例如（圖片來源維基百科），對于“tea”這個詞，你從根開始，被引導到t節(jié)點，然后是e，***是a。因此，搜索單詞需要O（N）的時間（其中N是單詞的長度），如果單詞的前綴不存在，則可以提前結(jié)束。如果我查詢“zzzzzzzz”，樹可以在“zz”之后結(jié)束查詢。

環(huán)形緩沖區(qū)（ring buffer）

環(huán)形緩沖區(qū)是使用普通數(shù)組的一種非常好的方式，它主要被用于處理數(shù)據(jù)流。

誰會真的使用環(huán)形緩沖區(qū)？

說不定Netflix會用？

我用google搜索“netflix ring buffer”，發(fā)現(xiàn)了他們發(fā)布了一些開源環(huán)緩沖區(qū)代碼。但問題是，公司真的會用他們已經(jīng)開源的代碼嘛？

環(huán)形緩沖區(qū)的原理

好啦好啦。真的還有人在讀這篇文章嘛。

如果你讀到了這兒，說明你基礎一定還不錯，那就直接去維基百科瞅一眼這個數(shù)據(jù)結(jié)構(gòu)吧，比前兩個簡單多了！

總結(jié)一下，今天文摘菌介紹了三個重要的數(shù)據(jù)結(jié)構(gòu)：布隆過濾器（bloom filter），前綴樹（prefix trie），環(huán)形緩沖（ring buffer）。

想當一個聰明程序員，這些結(jié)構(gòu)你值得擁有！

【本文是51CTO專欄機構(gòu)大數(shù)據(jù)文摘的原創(chuàng)譯文，微信公眾號“大數(shù)據(jù)文摘（ id: BigDataDigest）”】

戳這里，看該作者更多好文