④. 布隆过滤器原理
- ①. 对象是无穷的,hashCode方法的方法返回值是int,把无穷的对象放入到hashCode中,就会导致不同的对象有相同的hashCode值
public class HashCodeConflictDemo{ public static void main(String[] args){ Set<Integer> hashCodeSet = new HashSet<>(); for (int i = 0; i <200000; i++) { int hashCode = new Object().hashCode(); if(hashCodeSet.contains(hashCode)) { System.out.println("出现了重复的hashcode: "+hashCode+"\t 运行到"+i); break; } hashCodeSet.add(hashCode); } System.out.println("Aa".hashCode()); System.out.println("BB".hashCode()); System.out.println("柳柴".hashCode()); System.out.println("柴柕".hashCode()); } }
②. 布隆过滤器实现原理和数据结构
布隆过滤器(Bloom Filter) 是一种专门用来解决去重问题的高级数据结构。
实质就是一个大型位数组和几个不同的无偏hash函数(无偏表示分布均匀)。由一个初值都为零的bit数组和多个个哈希函数构成,用来快速判断某个数据是否存在。但是跟 HyperLogLog 一样,它也一样有那么一点点不精确,也存在一定的误判概率
③. 添加key时
使用多个hash函数对key进行hash运算得到一个整数索引值,对位数组长度进行取模运算得到一个位置,每个hash函数都会得到一个不同的位置,将这几个位置都置1就完成了add操作
④. 查询key时
只要有其中一位是零就表示这个key不存在,但如果都是1,则不一定存在对应的key
结论:有,是可能有,无,是肯定无
进一步解释:
(1). 当有变量被加入集合时,通过N个映射函数将这个变量映射成位图中的N个点,把它们置为 1(假定有两个变量都通过 3 个映射函数)
(2). 查询某个变量的时候我们只要看看这些点是不是都是 1, 就可以大概率知道集合中有没有它了。
如果这些点,有任何一个为零则被查询变量一定不在,如果都是 1,则被查询变量很可能存在
为什么说是可能存在,而不是一定存在呢?那是因为映射函数本身就是散列函数,散列函数是会有碰撞的。
⑤. 再次详解初始化、添加、判断是否存在
步骤如下:
(1). 初始化:布隆过滤器 本质上 是由长度为 m 的位向量或位列表(仅包含 0 或 1 位值的列表)组成,最初所有的值均设置为0
当我们向布隆过滤器中添加数据时,为了尽量地址不冲突,会使用多个hash函数对key进行运算,算得一个下标索引值,然后对位数组长度进行取模运算得到一个位置,每个hash函数都会算得一个不同的位置。再把位数组的这几个位置都置为1就完成了add操作
例如,我们添加一个字符串wmyskxz