布隆过滤器的优缺点及哈希切割问题

1.布隆过滤器优点

1. 增加和查询元素的时间复杂度为:O(K)(K为哈希函数的个数，一般较小)，与数据量大小无关
2. 哈希函数相互之间没有关系，方便硬件并行运算
3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有着很大的空间优势
5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

2.布隆过滤器缺陷

1. 有误判，不能准确判断元素是否在集合中(解决办法：建立一个白名单，存储可能会误判的数据)
2. 不能获取元素本身
3. 一般情况下不能从布隆过滤器中删除元素
4. 采用计数方式删除，存在计数回绕问题

3.哈希切割

一个超过100G大小存有字符串IP的文件

1. 找到出现次数最多的IP地址
2. 如何找到出现次数最多的前K个IP？

解决办法

哈希切分成500个小文件 每个文件大小约为200M 依次读取原文件的字符串 通过函数计算出下标
Hashi = hashfunc(string) % 500 不通的下标分到不同的文件中

为避免单个文件太大的情况 进一步处理

1、统计过程中抛内存异常 说明单个小文件过大 冲突太多 用另一个哈希函数进行二次切分
2、没有抛异常 正常统计 统计完一个小文件 记录次数最大的

Top K问题 Top K问题