1. Bloom Filter
【Bloom Filter】
Bloom Filter（BF）是一種空間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，它利用位數(shù)組很簡潔地表示一個(gè)集合，并能判斷一個(gè)元素是否屬于這個(gè)集合。它是一個(gè)判斷元素是否存在集合的快速的概率算法。Bloom Filter有可能會(huì)出現(xiàn)錯(cuò)誤判斷，但不會(huì)漏掉判斷。也就是Bloom Filter判斷元素不再集合，那肯定不在。如果判斷元素存在集合中，有一定的概率判斷錯(cuò)誤。因此，Bloom Filter不適合那些“零錯(cuò)誤”的應(yīng)用場合。
而在能容忍低錯(cuò)誤率的應(yīng)用場合下，Bloom Filter比其他常見的算法（如hash，折半查找）極大節(jié)省了空間。
Bloom Filter的詳細(xì)介紹：海量數(shù)據(jù)處理之Bloom Filter詳解
【適用范圍】
可以用來實(shí)現(xiàn)數(shù)據(jù)字典，進(jìn)行數(shù)據(jù)的判重，或者集合求交集
【基本原理及要點(diǎn)】
