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

最新評(píng)論