当需要判断某个元素是否处于某个集合中时，为了快速查询可以使用散列表Map来进行存储元素
散列表本身就是空间换时间的数据结构，当元素数量多且元素所占空间非常大时，使用散列表会占用大量空间
比如爬虫要爬取很多网络地址，想要过滤掉已经访问过的地址时，可以使用布隆过滤器
布隆过滤器
什么是布隆过滤器呢？布隆过滤器并不是LOL中布隆拿着的大盾牌
布隆过滤器由位数组与多个哈希函数构成
当将某个元素加入集合时，使用多个哈希函数对该元素得到索引位置，将位数组该索引位置变为1
判断该元素是否加入集合时，也使用多个哈希函数对该元素得到索引位置，判断位数组中索引位置是否为1，都为1说明加入过集合，否则未加入
由于索引位置上的1可能是其他元素设置的，布隆过滤器存在一定误差， 误差率随着位数组长度的增大而减小
布隆过滤器的时间复杂度为O（n个哈希函数），空间复杂度为O（位数组长度）
实现
定义类
定义布隆过滤器类
使用long数组充当位数组，hashSize记录hash函数数量，泛型存储对应类型元素
public class BloomFilter<T> { /** * 位数组 */ private long[] bit; /** * 一共有多少个二进制位 */ private int bitSize; /** * hash函数数量 */ private int hashSize; }
添加元素
put添加元素，先对元素进行检查，再循环使用多个哈希函数生成索引设置为1
/** * 添加元素 * * @param value * @return 发生变化返回true，未发生变化返回false */ public boolean put(T value) { //空指针检查 nullCheck(value); // 利用元素生成2个整数,将这2个整数经过hash函数生成的索引赋值为1 int hash1 = value.hashCode(); int hash2 = hash1 >>> 16; boolean result = false; for (int i = 1; i <= hashSize; i++) { //相当于hash函数 生成一个二进位的索引index int combinedHash = hash1 + (i * hash2); if (combinedHash < 0) { combinedHash = ~combinedHash; } int index = combinedHash % bitSize; // 设置index位置的二进位为1 if (set(index)) { result = true; } } return result; }
/** * 设置index位置的二进位为1 * * @param index * @return */ private boolean set(int index) { //找到对应的long值value 用value | (1<<k) //找到索引所在数组位置,一个long是64位 long value = bit[index / Long.SIZE]; //获得long值对应要修改为1的索引 （0-63） int k = index % Long.SIZE; bit[index / Long.SIZE] = value | (1 << k); // 101010101010010001 // | 000000000000000100 1 << k // 101010111010010101 //如果原来value与1<<k对应的位置是0则返回true，是1则返回false return (value & (1 << k))==0 ; }
判断元素是否存在
/** * 判断元素value是否存在 * @param value * @return false：一定不存在 true：可能存在 */ public boolean contains(T value) { nullCheck(value); //先按照Put前面的步骤找到value对应的索引位置 int hash1 = value.hashCode(); int hash2 = hash1 >>> 16; for (int i = 1; i <= hashSize; i++) { int combinedHash = hash1 + (i * hash2); if (combinedHash < 0) { combinedHash = ~combinedHash; } int index = combinedHash % bitSize; if (!get(index)) { return false; } } return true; } /** * 判断index位置的二进制位数是否为1 * @param index * @return */ private boolean get(int index){ long value = bit[index / Long.SIZE]; int k = index % Long.SIZE; //如果value与1<<k对应的位置是1则返回true，是0则返回false return (value & (1 << k)) != 0; }
总结
布隆过滤器由位数组与多个哈希函数构成
布隆过滤器适用于判断多元素是否加入过集合，特点是占用空间小， 速度快，可能出现误差
本篇文章将被收入数据结构专栏，觉得不错感兴趣的同学可以收藏专栏哟~
觉得菜菜写的不错，可以点赞、关注支持哟~
有什么问题可以在评论区交流喔~
