前言
前段時間在做數據碰撞分析時，遇到一個在數億級的int型數據集中查找30萬個特定int值是否存在的需求，當時嘗試了幾種方式
- 通過分片，然後做增量分析
- HashMap
這兩種方式第一種太慢，即使後面進一步實現了分佈式計算，可仍然無法接受；第二種直接寫爆內存。
後續經過探索嘗試，通過字典查找樹、布隆過濾都可以高效的實現上述需求，接下來分別分享下兩種方式的具體實現。
字典查找樹
簡介
Trie樹，即字典樹，又稱單詞查找樹或鍵樹，是一種樹形結構，是一種哈希樹的變種。典型應用是用於統計和排序大量的字符串，所以經常被搜索引擎系統用於文本詞頻統計。它的優點是：最大限度地減少無謂的字符串比較，查詢效率比哈希表高。
基本特性
- 根節點不包含字符，除根節點外每一個節點都只包含一個字符。
- 從根節點到某一節點，路徑上經過的字符連接起來，為該節點對應的字符串。
- 每個節點的所有子節點包含的字符都不相同。
通過這三個基本性質，我們不難發現Trie的核心思想是空間換時間，利用字符串的公共前綴來降低查詢時間的開銷以達到提高效率的目的。對於龐大的空間消耗，我們可以用鏈表來動態開闢空間，達到空間上利用率的最大化。
代碼實現
具體源碼分享，詳見我分享的另一篇文章——
我們看下字典查找樹如何記錄數據，下面是我們將19825011312, 19825029527
兩個手機號碼添加到樹中。
那麼它的性能如何？
使用profile對TrieTree算法進行性能測試，具體測試結果數據不貼了，說下結論。
500萬條17位數字字符串添加，單次執行微秒級。
500萬數據集中查詢某特定元素是否存在，微妙級
500萬數據集中通過某特定前綴字符串聯想其他元素，毫秒級
布隆過濾
簡介
Burton Howard Bloom 在 1970 年提出了一個叫做 Bloom Filter（中文翻譯：布隆過濾）的算法。它主要就是用於解決判斷一個元素是否在一個集合中，但它的優勢是隻需要佔用很小的內存空間以及有著高效的查詢效率。官方的說法是：它是一個保存了很長的二級制向量，同時結合 Hash 函數實現的。
基本特性
- 屬於概率數據結構，只要返回數據不存在，則肯定不存在，返回數據存在，但只能是大概率存在。
- 無法刪除其中的元素。
- 無法返回元素本身
特性原理介紹，如圖所示：
- 首先需要初始化一個二進制的數組，長度設為 L（圖中栗子為 9），同時初始值全為 0 。
- 當寫入一個 N1=19825011312的數據時，需要進行K次 hash 函數的運算(栗子中進行了2 次）；與 HashMap 有點類似，通過算出的 HashCode 與 L 取模後定位到 0、4 處，將該處的值設為 1。
- N2=19825029527也是同理計算後將 2、7 位置設為 1。
- 當有一個N3=19825011312需要判斷是否存在時，也是做同樣兩次 Hash 運算，定位到 0、4 處，此時他們的值都為 1 ，所以認為N3=1000 存在於集合中。
- 當有一個 N4=18805289099時，也是同理。也是做同樣兩次 Hash 運算，定位到5、7處，可5處的值為 0，所以認為 N4不存在於集合中。
總結講起來就是：
對寫入的數據做 K次 hash 運算定位到數組中的位置，同時將數據改為 1 。當有數據查詢時也是同樣的方式定位到數組中。 若其中的有一次計算hash計算結果所定位的數字為 0 則認為數據肯定不存在於集合，否則數據可能存在於集合中。
代碼實現
python 安裝
pip install pybloom
GitHub鏈接
https://github.com/jaybaird/python-bloomfilter/
樣例分享
模式一 BloomFilter 定容
from pybloom import BloomFilter
# capacity是容量，最多可以記錄多少元素 , 插入超過capacity設定的容量值,會增加誤報的概率;error_rate 是能容忍的誤報率,當誤報率超過error_rate會拋異常;過濾器返回誤報的錯誤率。
bloom = BloomFilter(capacity=1000, error_rate=0.001)
add_card_list = ['19825011312', '19825029527']
# add()添加元素，同時返回對應元素存在狀態。當不存在該元素返回False;大概率存在返回True
print [bloom.add(x) for x in add_card_list]
search_card_list = ['19825011312', '18805289999']
#判斷元素是否存在,返回True僅表示該元素可能存在;若返回False則表示一定不存在。
print[(x in bloom) for x in search_card_list]
輸出
[False, False]
[True, False]
模式二 ScalableBloomFilter 可以自動擴容
from pybloom import ScalableBloomFilter
# SMALL_SET_GROWTH較慢,但是使用的內存較少。LARGE_SET_GROWTH較快，但是使用內存較多。
ScalableBloom=ScalableBloomFilter(mode=ScalableBloomFilter.SMALL_SET_GROWTH)
add_card_list = ['19825011312', '19825029527']
# add()添加元素，同時返回對應元素存在狀態,當不存在該元素返回False;大概率存在返回True
print [ScalableBloom.add(x) for x in add_card_list]
search_card_list = ['19825011312', '18805289999']
#判斷元素是否存在,返回True僅表示該元素可能存在;若返回False則表示一定不存在。
print[(x in ScalableBloom) for x in search_card_list]
輸出
[False, False]
[True, False]
閱讀更多 測試開發技術棧 的文章
