布隆过滤器
布隆过滤器常常被用来检测某个元素是否是巨量数据集合中的成员
1、基本原理：
(1)将长度为m的位数组元素全部置为0；
(2)对集合S中的某个成员a，分别用k个哈希函数对其计算，如果hi(a)=x(1<=i<=k, 1<=x<=m),则将位数组的第x位置为1，对于成员a来说，可能会将位数组中w（w<=k）个位置设置为1。
2、误判率：
布隆过滤器存在误判现象，因此在百分之百精确判断集合成员的场景下不能使用。
3、改进：
基本BF存在一个缺点：无法删除集合成员，只能增加成员并对其查询
计算布隆过滤器：
基本思想：将基本信息由多个比特位来存储，在集合成员加入时，经过k个哈希函数计算后，将对应位加1。在查询时，只要该位置不为0，则表示该成员属于该集合。删除时，只需要对应位减1即可
转载于
//www.cnblogs.com/youhongpp/p/8909432.html
我会带着你远行
ゝ一世哀愁。
系统管理员
亦凉
还没有评论，来说两句吧...