Bloom Filter是由Bloom在1970年提出的一種快速查找算法，通過多個hash算法來共同判斷某個元素是否在某個集合內。可以用於網絡爬蟲的url重復過濾、垃圾郵件的過濾等等。
它相比hash容器的一個優勢就是，不需要存儲元素的實際數據到容器中去來一個個的比較是否存在。
只需要對應的位段來標記是否存在就行了，所以想當節省內存，特別適合海量的數據處理。並且由於省去了存儲元素和比較操作，所以性能也比基於hash容器的高了很多。
但是由於bloom filter沒有去比較元素，只通過多個hash來判斷唯一性，所以存在一定的hash沖突導致誤判。誤判率的大小由hash函數的個數、hash函數優劣、以及存儲的位空間大小共同決定。
並且刪除也比較困難，解決辦法是使用其變種，帶計數的bloom filter，這個這裡就不多說了。
對於bloom filter算法的實現，相當簡單：
首先分配一塊固定的連續空間，大小是m個比特位（m/8+1個字節），然後再提供k個不同hash函數，同時對每個元素進行計算位索引。如果每個位索引對應的位都為1，則存在該元素，否則就是不存在。
可以看出，如果判斷為不存在，那麼肯定是不存在的，只有在判斷為存在的時候，才會存在誤判。
bloom filter主要的難點其實在於估算：
保證指定誤判率的情況下，到底需要多少個hash函數，多少的存儲空間。
首先來看下bloom filter的誤判率計算公式：
假定有k個hash函數，m個比特位的存儲空間，n個集合元素，則有誤判率p：
p = (1 - ((1 - 1/ m) ^ kn))^k ~= (1 - e^(-kn/m))^k
根據這個，官方給出了一個計算k的最優解公式，使其滿足給定p的情況下，存儲空間達到最小：
k = (m / n) * ln2
把它帶入概率公式得到：
p = (1 - e ^-((m/nln2)n/m))^(m/nln2)
簡化為：
lnp = -m/n * (ln2)^2
因此，如果指定p，只需要滿足如果公式，就可以得到最優解：
s = m/n = -lnp / (ln2 * ln2) = -log2(p) / ln2
k = s * ln2 = -log2(p)
理論值：
p < 0.1: k = 3.321928, m/n = 4.79
p < 0.01: k = 6.643856, m/n = 9.58
p < 0.001: k = 9.965784, m/n = 14.37
p < 0.0001: k = 13.287712, m/n = 19.170117
可以看出，這個確實能夠在保證誤判率的前提下，使其存儲空間達到最小，但是使用的hash函數個數k
相對較多，至少也得4個，要滿足p < 0.001，需要10個才行，這個對於字符串hash的計算來講，性能損耗相當大的，實際使用中根本沒法接受。
因此我們需要另外一種推到公式，可以認為指定p和k的情況下，來計算空間使用s=m/n的大小，這樣我們在實際使用的時候，靈活性就大大提高了。
下面來看下，我自己推到出來的公式，首先還是依據誤判率公式：
p = (1 - e^(-kn/m))^k
假定s=m/n，則有
p = (1 - e^(-k/s))^k
兩邊取導，得到：
lnp = k * ln(1 - e^(-k/s))
交換k：
(lnp) / k = ln(1 - e^(-k/s))
重新上e：
e^((lnp) / k) = 1 - e^(-k/s)
化簡：
e^(-k/s) = 1 - e^((lnp) / k) = 1 - (e^lnp)^(1/k) = 1 - p^(1/k)
再求導：
-k/s = ln(1 - p^(1/k))
得出：
s = -k / ln(1 - p^(1/k))
假定`c = p^(1/k)`：
s = -k / ln(1 - c)
利用泰勒展開式：`ln(1 + x) ~= x - 0.5x^2 while x < 1` 化簡得到：
s ~= -k / (-c-0.5c^2) = 2k / (2c + c * c)
最後得出公式：
c = p^(1/k)
s = m / n = 2k / (2c + c * c)
假定有n=10000000的數據量，則有理論值：
p < 0.1 and k = 1: s = m/n = 9.523810
p < 0.1 and k = 2: s = m/n = 5.461082
p < 0.1 and k = 3: s = m/n = 5.245850, space ~= 6.3MB
p < 0.1 and k = 4: s = m/n = 5.552045, space ~= 6.6MB
p < 0.01 and k = 1: s = m/n = 99.502488
p < 0.01 and k = 2: s = m/n = 19.047619
p < 0.01 and k = 3: s = m/n = 12.570636, space ~= 15MB
p < 0.01 and k = 4: s = m/n = 10.922165, space ~= 13MB
p < 0.001 and k = 1: s = m/n = 999.500250
p < 0.001 and k = 2: s = m/n = 62.261118
p < 0.001 and k = 3: s = m/n = 28.571429, space ~= 34MB
p < 0.001 and k = 4: s = m/n = 20.656961, space ~= 24.6MB
p < 0.0001 and k = 1: s = m/n = 9999.500025
p < 0.0001 and k = 2: s = m/n = 199.004975
p < 0.0001 and k = 3: s = m/n = 63.167063, space ~= 75.3MB
p < 0.0001 and k = 4: s = m/n = 38.095238, space ~= 45.4MB
p < 0.0001 and k = 5: s = m/n = 29.231432, space ~= 24.8MB
可以看到，在k=3的情況下，其實已經可以達到我們平常使用所能的接受范圍內了，沒必要非得
使用最優解，除非在空間使用極為苛刻的情況下，而且這個公式，針對程序空間使用的調整，更加的靈活智能。
特別提下，經過實測，如果每個hash的實現非常優質，分布很均勻的情況下，其實際的誤判率比理論值低很多:
就拿TBOX的bloom filter的實現做測試，n=10000000：
p < 0.01 and k = 3的情況下，其實際誤判率為：0.004965
p < 0.001 and k = 3的情況下，其實際誤判率為：0.000967
所以好的hash函數算法也是尤為的重要。
下面來看下TBOX提供的bloom filter的使用，用起來也是相當的方便：
// 總的元素個數
tb_size_t count = 10000000;
/* 初始化bloom filter
*
* TB_BLOOM_FILTER_PROBABILITY_0_01: 預定義的誤判率，接近0.01
* 注：由於內部使用位移數來表示：1 / 2^6 = 0.015625 ~= 0.01
* 所以實際傳入的誤判率，有可能稍微大一點，但是還是相當接近的
*
* 3：為k值，hash函數的個數，最大不超過15個
*
* count：指定的元素規模數
*
* tb_item_func_long()：容器的元素類型，主要是用其內定的hash函數，如果要自定義hash函數，可以替換:
*
* tb_size_t tb_xxxxxx_hash(tb_item_func_t* func, tb_cpointer_t data, tb_size_t mask, tb_size_t index)
* {
* // mask為hash掩碼，index為第index個hash算法的索引
* return compute_hash(data, index) & mask;
* }
*
* tb_item_func_t func = tb_item_func_long();
* func.hash = tb_xxxxxx_hash;
*
* 來進行
*/
tb_bloom_filter_ref_t filter = tb_bloom_filter_init(TB_BLOOM_FILTER_PROBABILITY_0_01, 3, count, tb_item_func_long());
if (filter)
{
tb_size_t i = 0;
for (i = 0; i < count; i++)
{
// 產生隨機數
tb_long_t value = tb_random();
// 設置值到filter內，如果不存在，則返回tb_true表示設置成功
if (tb_bloom_filter_set(filter, (tb_cpointer_t)value))
{
// 添加元素成功，之前元素不存在
// 不會存在誤判
}
else
{
// 添加失敗，添加的元素已經存在
// 這裡可能會存在誤判
}
// 僅僅判斷元素是否存在
if (tb_bloom_filter_get(filter, (tb_cpointer_t)data)
{
// 元素已經存在
// 這裡可能會存在誤判
}
else
{
// 元素不存在
// 不會存在誤判
}
}
// 退出filter
tb_bloom_filter_exit(filter);
}
// 常用預定義的誤判率，也可以指定其他值，注：必須是位移數，而不是實際值
typedef enum __tb_bloom_filter_probability_e
{
TB_BLOOM_FILTER_PROBABILITY_0_1 = 3 ///!< 1 / 2^3 = 0.125 ~= 0.1
, TB_BLOOM_FILTER_PROBABILITY_0_01 = 6 ///!< 1 / 2^6 = 0.015625 ~= 0.01
, TB_BLOOM_FILTER_PROBABILITY_0_001 = 10 ///!< 1 / 2^10 = 0.0009765625 ~= 0.001
, TB_BLOOM_FILTER_PROBABILITY_0_0001 = 13 ///!< 1 / 2^13 = 0.0001220703125 ~= 0.0001
, TB_BLOOM_FILTER_PROBABILITY_0_00001 = 16 ///!< 1 / 2^16 = 0.0000152587890625 ~= 0.00001
, TB_BLOOM_FILTER_PROBABILITY_0_000001 = 20 ///!< 1 / 2^20 = 0.00000095367431640625 ~= 0.000001
}tb_bloom_filter_probability_e;
public class SimpleBloomFilter {
private static final int DEFAULT_SIZE = 2 << 24;
private static final int[] seeds = new int[] { 5, 7, 11, 13, 31, 37, 61 };
private BitSet bits = new BitSet(DEFAULT_SIZE);
private SimpleHash[] func = new SimpleHash[seeds.length];
public static void main(String[] args) {
String value = "[email protected]";
SimpleBloomFilter filter = new SimpleBloomFilter();
System.out.println(filter.contains(value));
filter.add(value);
System.out.println(filter.contains(value));
}
public SimpleBloomFilter() {
for (int i = 0; i < seeds.length; i++) {
func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
}
}
public void add(String value) {
for (SimpleHash f : func) {
bits.set(f.hash(value), true);
}
}
public boolean contains(String value) {
if (value == null) {
return false;
}
boolean ret = true;
for (SimpleHash f : func) {
ret = ret && bits.get(f.hash(value));
}
return ret;
}
public static class SimpleHash {
private int cap;
private int seed;
public SimpleHash(int cap, int seed) {
this.cap = cap;
this.seed = seed;
}
public int hash(String value) {
int result = 0;
int len = value.length();
for (int i = 0; i < len; i++) {
result = seed * result + value.charAt(i);
}
return (cap - 1) & result;
}
}
}
希望能幫到你...余下全文>>
// 利用經典的大數據處理算法bloomfilter進行兩個集合中相同元素的查找，去重#include <stdio.h>#include <string.h>unsigned char mask[8] = {128, 64, 32, 16, 8, 4, 2, 1};// 簡單的哈希算法 int hashfuc(char* s, int key){ int i, seed[4] = {5, 7 ,11, 13}, value = 0; if(key >= 4) key %= 4; for(i = 0; s[i]; i++) value += s[i]*seed[key]; return value;}// 利用bloomfilter算法將字符串s映射到位數組m中，並去掉重復的子串 void bloomfilter(unsigned char *m, char *s){ int i, j, hvalue, brepeat; char substr[32]; for(i = j = 0; ; i++) { if(s[i] != ' ' && s[i] != '\t' && s[i] != 0) substr[j++] = s[i]; else { substr[j] = 0; brepeat = 1; for(j = 0; j < 4; j++) { hvalue = hashfuc(substr, j) & 0X7F; if((m[hvalue>>3] & mask[hvalue&7]) == 0) { m[hvalue>>3] |= mask[hvalue&7]; brepeat = 0; } } // 如果是重復子串 if(brepeat == 1) { j = strlen(substr); strncpy(s+i-j, s+i+1, strlen(s)-i); //printf("有重復子串%s, 去重後是%s\n", substr, s); i = i - j - 1; } if(s[i] == 0) break; j = 0; } }}int main(){ char s1[256], s2[256], substr[32]; int i, j, hvalue; unsigned char m1[16]={0}, m2[16]={0}, m3[16]; printf("First string\n"); gets(s1); printf("Second str......余下全文>>
