布隆过滤器

网页黑名单 垃圾邮件过滤系统 爬虫网站判重
哈希函数
特征：

1. 典型的哈希函数都有无限的输入值域。
2. 当给哈希函数传入相同的输入值时，返回值一样。
3. 当给哈希函数传入不同的输入值时，返回值可能一样，也可能不一样。因为输出域统一为 S，所以会有不同的输入值对应 S 中一个元素上。
4. 最重要的性质是很多不同的输入值所得到的返回值会均匀的分布在 S 上。

第 1－3 点性质是哈希函数的基础，第 4 点性质是评价一个哈希函数优劣的关键

bit map

每个 bit 只有 0 和 1 的两种状态。

int[] arr = new int[10]; //32bit * 10 -> bit
//arr[0] = int 0 ~ 31
//arr[1] = int 32 ~ 63

int x = 178;
//拿到 第 178 位的状态
int index = x / 32;
int bitIndex = x % 32;

int now  = (arr[index] >> (bitIndex)) & 1;
//把 178 位状态改成 1 
arr[index] = arr[index] | (1 << (bitIndex));
//把 178 位状态改成 0 
arr[index] = arr[index] & ( ~ (1 << (bitIndex)) );

假设有一个长度为 m 的 bit 类型的数组，即数组中的每一个位置只占一个 bit， 如我们所知，每一个 bit 只有 0。

布隆过滤器的步骤

• 假设一共有 k 个哈希函数，这些函数的输出域 S 都大于或等于 m, 并且这些哈希函数都足够优 秀，彼此之间也完全独立。
• 那么对同一对象输入(假设是一个字符串记为 URL)，经过 k 个哈希函数算出来的结果是独立的，可能相同，也可能不同，但彼此相互独立。
• 对算出来的每一个结果对 m 取余 (% m),然后在 bit array 上把相应的位置设为 1(涂黑)

至此布隆过滤器就基本实现了。

布隆过滤器失误度

数学公式: $ m = n * ln p / (ln 2) ^ 2 $
数学公式: $ k = ln 2 * m / n = 0.7 * m / n; $
数学公式: $ p = 1 - e ^ (-n * k / m) ^ k $