1.什么是布隆过滤器？

2.布隆过滤器原理

• 位数组（Bit Array）：又叫做位图（BitMap）或位集（BitSet），它是一种能够紧凑地存储位的数组，每个位置上的元素只有0和1。其最大的特点是极大地提高了空间效率，在处理大量布尔值时非常有用。
• K个哈希函数：采用K个哈希函数将输入值映射到位数组上，具体映射方式为找到哈希索引：，其中N为位数组的长度，为第i个哈希函数。如果该位置上值为1说明存在，如果为0说明不存在。采用K个哈希函数的主要原因是减少哈希冲突。

3.布隆过滤器的实现

import java.util.BitSet;
import java.util.Random;

public class BloomFilter {
    private final int size; // 过滤器bit长度
    private final BitSet bitSet;  // 位集
    private final int[] hashSeeds;  // 哈希种子数组
    private final int numHashFunctions;  // 哈希函数个数
    // 构造函数，初始化布隆过滤器
    public BloomFilter(int size, int numHashFunctions) {
        this.size = size;
        this.bitSet = new BitSet(size);
        this.numHashFunctions = numHashFunctions;
        this.hashSeeds = new int[numHashFunctions];
        initializeHashSeeds();
    }

    /**
     * 初始化哈希种子
     */
    private void initializeHashSeeds() {
        Random random = new Random();
        for (int i = 0; i < numHashFunctions; i++) {
            hashSeeds[i] = random.nextInt();
        }
    }

    /**
     * 添加元素到布隆过滤器
     * @param value 添加的字符串元素值
     */
    public void add(String value) {
        for (int i = 0; i < numHashFunctions; i++) {
            int hash = hash(value, hashSeeds[i]);
            bitSet.set(Math.abs(hash % size), true);
        }
    }

    /**
     * 检查元素是否存在于布隆过滤器
     * @param value 输入元素
     * @return 是否存在true/false
     */
    public boolean mightContain(String value) {
        for (int i = 0; i < numHashFunctions; i++) {
            int hash = hash(value, hashSeeds[i]);
            if (!bitSet.get(Math.abs(hash % size))) {
                return false;
            }
        }
        return true;
    }

    /**
     * 简单的哈希函数
     * @param value 元素值
     * @param seed 种子值
     * @return 哈希值
     */
    private int hash(String value, int seed) {
        int result = 0;
        for (int i = 0; i < value.length(); i++) {
            result = result * seed + value.charAt(i);
        }
        return result;
    }
}

public class BloomFilterTest {
    public static void main(String[] args) {
        // 创建一个布隆过滤器，大小为1000，使用5个哈希函数
        BloomFilter bloomFilter = new BloomFilter(1000, 5);

        // 添加一些元素
        bloomFilter.add("hello");
        bloomFilter.add("world");

        // 检查元素是否存在
        System.out.println(bloomFilter.mightContain("hello")); // 输出：true
        System.out.println(bloomFilter.mightContain("world")); // 输出：true
        System.out.println(bloomFilter.mightContain("OK")); // 输出：false (可能)
    }
}

4.布隆过滤器的应用场景

4.1 弱密码校验

• 布隆过滤器不能太大，否则前端代码量会变大，最直观的感受就是原来APP是50M，加了过滤器后变为100M，这种情况就要评估是否值得这样做。
• 需要对前端进行混淆和加固，以防被逆向工程提取后推测出弱密码库。

4.2 判断注册账号是否被占用

4.3 判断恶意网址

4.4 大数据系统数据检索

4.5 解决缓存击穿