布隆过滤器简述

一. 什么是布隆过滤器1.作用布隆过滤器本质上是一个快速判断一个元素是否存在的数据结构。比如判断一个电话是否在黑名单。2.组成① 一个很大的位数组 BitSet例如[0][0][1][0][0][0][0][0]0没有数据映射到这里1有数据映射到这里② 多个哈希函数private static final int[] SEEDS { 2,6,17,8,41,58 };这些 seed 代表不同的哈希算法。布隆过滤器不会只使用一次 Hash。因为一次 Hash 容易产生冲突。所以一个数据会经过多个 Hash 运算。例如手机号131经过 6 个哈希函数hash1 → 100hash2 → 500hash3 → 800hash4 → 200hash5 → 900hash6 → 300然后把位数组对应位置改成 1[0][0][0][1][0][0][1][0][1]3.添加元素流程假设添加一个手机号1380013800步骤① 通过多个哈希函数计算位置hash1 → 3hash2 → 6hash3 → 8② 修改 BitSet把位数组对应位置设置为 1位置3 1位置6 1位置8 1完成添加。4.查询元素流程① 通过相同的种子数在进过哈希函数计算出不同数组下标值② 判断数组下标值所对应标记处的二进制数只要有任意一个位置为 0该元素一定不存在所有位置都为 1该元素可能存在 (但存在误判可能);查询手机号1380013800再次经过哈希函数hash1 → 3 hash2 → 6 hash3 → 8检查这些位置情况13、6、8 都是1说明这个元素可能存在。情况2某一个位置是0说明这个元素一定不存在。5.特点① 存在误判判断元素“可能存在”或者“一定不存在”。原因不同元素经过哈希后可能落在相同的位置。② 不支持删除因为删除比较困难。二. 布隆过滤器的优点和缺点1.优点速度非常快。① 占用空间小布隆过滤器只保存0和1节省大量内存。② 查询速度快时间复杂度O(k)(k 是哈希函数数量一般只有几个哈希计算。2.缺点① 存在误判可能不存在的数据判断为存在② 不支持删除普通布隆过滤器无法准确删除元素想要删除元素需要升级。③ 容量固定DEFAULT_CAP初始化后容量固定如果数据量增加可能导致Hash冲突增加误判率升高三. 100万手机号黑名单判断方案1.先模拟100w个手机号码。2.把黑名单手机号全部加入布隆过滤器情况1布隆过滤器判断不存在说明这个手机号一定不是黑名单。情况2布隆过滤器判断可能存在。3.存在大量两个手动存进去的手机号码以及少量其他号码查重效果正常。private static ListString mockPhoneNumber(int count) { ListString list new ArrayList(count); String phone1 13700001794; String phone2 13700001795; for (int i 0; i count; i) { if (i % 1000 0) { list.add(phone1); } else if (i % 1500 0) { list.add(phone2); } else { // 随机生成一个手机号码 String phone 1 (30 (int) (Math.random() * 9)) String.format(%08d, (int) (Math.random() * 100000000)); list.add(phone); } } return list; }