海量數(shù)據(jù)處理中常用到的技術(shù)
1. Bloom Filtering
基本的Bloom Filtering支持快速的插入和查找操作，是一種hash表技術(shù)?；镜臄?shù)據(jù)結(jié)構(gòu)非常簡單，容量為m的位數(shù)組，k個hash函數(shù)，將輸入的n個元素存儲在位數(shù)組里面。
每次插入一個新的元素，先計算該元素的k個hash指，將位數(shù)組對應hash值位置為1. 查找某個元素時，同樣的先計算k個hash值，然后查詢看是否對應位數(shù)組中得k位是否都是1，是則斷定元素存在。
基本的Bloom Filtering算法可以用于允許誤差的快速判重操作。集合的交集、并集的計算。
Bloom Filtering有個改進的版本counting bloom filtering可以支持數(shù)據(jù)的刪除操作，countering bloom filtering和基本的bloom filtering相比，位數(shù)組中每一位的取值擴展成多位，基本的bloom filtering用1bit表示一位。插入一個元素時，所有的k位都加1，刪除時都減1，查找時如果k個值都大于0則判定為存在。CBF中有個很重要的參數(shù)，即每一位的位數(shù)為多少?？梢酝ㄟ^理論證明，位數(shù)一般取4就足夠了，可以支持同一個數(shù)據(jù)插入16次。
bitmap可以看做bloom filtering的特例
2. Hash表技術(shù)
d-left hash hash表負載均衡技術(shù)。將hash表分成d段，設(shè)計d個hash函數(shù)，更具負載選擇一個合適的段存放數(shù)據(jù)。查找時要計算d個hash值，分別在d段中找。
常用于統(tǒng)計次數(shù)。
3. 堆技術(shù)
堆有兩個典型的應用：
多路歸并排序
求TopK
多路歸并排序時，降序排序時用最大堆，升序排序用最小堆。
TopK時，求TopK最大時，用最小堆，求TopK最小時用最大堆。求topK最大時，利用最小堆堆維護K個值，當新掃描的值大于堆頂元素時，堆頂元素刪除，插入新的值。這樣掃描完一遍數(shù)據(jù)，既可以求得topK最大。
4. 雙層桶（多層桶）設(shè)計
hash表技術(shù)是一種direct addr 技術(shù)，但是當數(shù)據(jù)范圍分布過廣、且數(shù)據(jù)量非常大的時候，采用hash表直接direct addr技術(shù)就不行了，這是可以使用多層hash技術(shù)。將原始數(shù)據(jù)范圍分成小段，每一段內(nèi)存可以裝載，段內(nèi)可以使用direct addr table技術(shù)。可以用多層分級快速定位到小段。

最新評論