④. 布隆过滤器原理

• ①. 对象是无穷的,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