大數據文摘出品
來源：amy.dev
編譯：劉佳瑋、lvy、錢天培
春招來襲啦！又要面試啦！
程序員面試展示什麽最重要？當時是你淵博的計算機學識，以及聰明的小腦瓜。
如果你學富五車，上知深度學習， 下知財務會計，那短短數小時也絕不夠你表演。所以，你一定得知曉面試官的套路，隨口丟出幾個應景的“冷知識”賣個乖巧。
如果你基礎不行，三天前剛準備轉碼，那就更得準備幾個的小把戲，不用打腫臉也能充一回胖子。
基於這兩個需求，今天文摘菌就來給大家介紹三個討巧的數據結構。面試當中一提，那可是相當撐場面。
這三個數據結構就是。登登登等…
1. 布隆過濾器（bloom filter）
2. 前綴樹（prefix trie）
3. 環形緩衝（ring buffer）
先來說一下，為什麽挑了這三個數據結構。
首先我覺得，你提到的數據結構要稍微冷門一些，這樣別人就會認為你了解很多不同類型的數據結構。但它不能太冷門，以免你的面試官要求你真正解釋實現細節或原理，那時你就game over了。最好是你提到的數據結構有點冷門，但你的面試官聽說過，對它有印象。
面試官都希望自己什麽都知道，他們聽說過這種數據結構但又不太了解，當你向他們介紹時，他們就會覺得你懂得特別多。
除此之外，這些數據結構還應該具有實際用例，以便在技術面試的時候，你能有機會展開介紹。它雖然稍微有點冷門但也不能太low，你如果只知道一些菜雞水準的數據結構（比如雙向鏈表），你的面試八成就涼了。
所以，這三個數據結構就被完美選中啦！
布隆過濾器
布隆過濾器是集合的概率版本。檢測集合是否包含某元素的時間複雜度為O(1)、空間複雜度為O(N)。Bloom過濾器也可以檢測出集合是否可能包含該元素，它的時間複雜度為O(1)，而空間複雜度只需要O(1)！
誰會真正使用布隆過濾器？
Chrome需要在不犧牲速度或空間的情況下保護你免受訪問垃圾郵件網站。
想象一下，如果每次你點擊一個鏈接，Chrome都必須進行網絡通話來檢查它龐大的垃圾郵件URL數據庫，然後才允許你訪問這個頁面，這會不會讓你等瘋掉。此外，設想一下，如果Chrome改善延遲的解決方案是在本地存儲整個垃圾郵件URL列表，這根本就是不可行的！
所以，chrome在本地存儲了一個潛在垃圾郵件URL的布隆過濾器，這既節省時間又節省空間，可以快速檢查給定的URL是否為垃圾郵件。對於普通的URL，布隆過濾器對“非垃圾郵件”的響應就足夠判定了。如果一個URL被標記為“可能是垃圾郵件”，那麽Google可以在跳轉之前檢查它真實數據庫。事實證明，當你願意犧牲絕對時，你可以做出偉大的事情！
布隆過濾器的原理
布隆過濾器的維基百科頁用大量的術語描述了實現細節，所以在這裡我會用簡單的描述一下實現過程。如果你想要更精確的細節，你應該去看看維基百科。我會略過很多步驟，但我會讓你有一個大致了解。
如果你想在Bloom過濾器中插入一個元素，首先假設有N個不同的確定性哈希函數。當同一個元素輸入不同哈希函數時，會得到不同的值（衝突是可以有的）。
使用每個哈希函數的輸出作為陣列的索引[注釋1，注釋2]，並對應每個索引i將陣列[i]設置為true。插入元素就完成了！插入元素的時間複雜度是O(1)，因為對每個插入元素所做的唯一工作是運行恆定數量的哈希函數，並設置恆定數量的陣列索引。
那該如何檢查布隆過濾器是否包含該元素？ 再次運行所有相同的哈希函數！
哈希函數是確定性的，因此相同的輸入應返回相同的輸出。所以相對應每個索引，檢查布隆過濾器的陣列是否在該索引處設置為true即可。如果哈希函數輸出的陣列的每個單元都為真，那麽可以很高的概率說這個元素已經插入到了布隆過濾器中。這一方法總是存在誤報的可能性。不過，布隆過濾器的一大特色是永遠不會出現漏報。
那麽，你需要多少個哈希函數，又需要多大的陣列呢？這你就得好好算一番了。維基百科對它們的解釋更詳細，你值得一讀。
注釋1：如何使用哈希函數的輸出作為索引：設哈希函數輸出整數值M，取長度N。N%M（N mod M）得到一個值Q，即0≤Q
注釋2：實際上，你應該使用位陣列而不是普通陣列。陣列的每個元素至少需要1個字節，而你只需要為“陣列”的每個元素存儲true / false。因此，你可以通過將其存儲為位陣列來節省空間，這是這個數據結構的重點。如果你想要聽起來很聰明，那麽位陣列（也就是位向量）也值得你在面試時提出。嗯，真正的面試專家建議總是在腳注中。
注釋3：嚴格來說，如果你的所有哈希函數都在O（1）時間內運行，那麽插入的複雜度才是O（1）。
前綴樹（prefix trie）
前綴樹是一種數據結構，允許你通過其前綴快速查找字元串，還可以查找有公共前綴的字元串。
我對介紹這一數據結構的第一條建議是，將它稱為“前綴樹”，而不僅僅是“樹”。這樣，你就讓面試官知道你是那種了解與前綴和後綴相關算法的人，並且你也希望對你的fancy數據結構進行準確描述。後綴樹也是一個非常有趣的話題，但實現細節十分殘暴。這就是為什麽我只是談論前綴樹，並且假裝了解後綴樹。
誰會真的用前綴樹？
基因組學研究人員！
事實證明，現代基因組研究在很大程度上依賴於字元串算法和數據結構，因為你試圖從組成基因組序列的數百萬個核苷酸中探索奧秘。對於基因組數據，你經常需要對齊序列，找到差異或找到重複的模式。如果你想了解更多相關信息，可以先閱讀生物信息學讀物，然後參與“DNA測序算法”或“生物信息學算法”等課程。
如果你想要閱讀一些真正有意思的讀物，我強烈建議你讀一讀藥物基因組學。隨著基因組測序和字元串算法的進步，我們實際上可以預測使用個體的基因組，來確定它們是否具有對藥物正確反應的正確基因。例如，如果他們的基因組缺少用於產生處理某種藥物的酶的基因，那麽藥物可能會對他們產生副作用。如果我們知道什麽基因是重要的，我們可以給他們一種不同的藥物！
我承認，前綴樹和基因組學之間的聯繫不太緊密。其實前綴樹的最直接用法就是用來查字典啦！但光這麽講不是忒無聊了點麽。
前綴樹的原理
想象一下，你有一棵樹，每個節點都有一個包含26個子節點的陣列，每個子節點對應一個英文字母。（如果要包含其他字元，可以將26更改為不同的值。）要在你的樹中表示單詞，你將從根節點開始，沿著路徑向下走，並在每個節點添加一個字母。
例如（圖片來源維基百科），對於“tea”這個詞，你從根開始，被引導到t節點，然後是e，最後是a。因此，搜索單詞需要O（N）的時間（其中N是單詞的長度），如果單詞的前綴不存在，則可以提前結束。如果我查詢“zzzzzzzz”，樹可以在“zz”之後結束查詢。
環形緩衝區（ring buffer）
環形緩衝區是使用普通陣列的一種非常好的方式，它主要被用於處理數據流。
誰會真的使用環形緩衝區？
說不定Netflix會用？
我用google搜索“netflix ring buffer”，發現了他們發布了一些開源環緩衝區代碼。但問題是，公司真的會用他們已經開源的代碼嘛？
環形緩衝區的原理
好啦好啦。真的還有人在讀這篇文章嘛。
如果你讀到了這兒，說明你基礎一定還不錯，那就直接去維基百科瞅一眼這個數據結構吧，比前兩個簡單多了！
總結一下，今天文摘菌介紹了三個重要的數據結構：布隆過濾器（bloom filter），前綴樹（prefix trie），環形緩衝（ring buffer）。
想當一個聰明程序員，這些結構你值得擁有！
相關報導：
志願者介紹
香港九龍灣馬來街興發大廈15樓D室