面试重要程度：⭐⭐⭐⭐⭐

常见提问方式： "设计防重系统" "解决缓存穿透问题" "布隆过滤器的误判率"

预计阅读时间：35分钟

🎯 布隆过滤器基本原理

基本概念

布隆过滤器（Bloom Filter）是一种空间效率极高的概率型数据结构，用于判断一个元素是否在集合中。

核心特点：

• 可能误判存在（假阳性），但不会误判不存在（无假阴性）
• 空间效率高，时间复杂度O(k)，k为哈希函数个数
• 不支持删除操作（标准版本）

基础实现

/**
 * 布隆过滤器基础实现
 */
public class BloomFilter {
    
    private final BitSet bitSet;
    private final int bitSetSize;
    private final int hashFunctionCount;
    
    /**
     * 构造函数
     * @param expectedElements 预期元素数量
     * @param falsePositiveRate 期望假阳性率
     */
    public BloomFilter(int expectedElements, double falsePositiveRate) {
        // 计算最优bit数组大小
        this.bitSetSize = calculateOptimalBitSetSize(expectedElements, falsePositiveRate);
        
        // 计算最优哈希函数个数
        this.hashFunctionCount = calculateOptimalHashFunctionCount(expectedElements, bitSetSize);
        
        this.bitSet = new BitSet(bitSetSize);
        
        System.out.println("BloomFilter initialized:");
        System.out.println("  Expected elements: " + expectedElements);
        System.out.println("  False positive rate: " + falsePositiveRate);
        System.out.println("  Bit set size: " + bitSetSize);
        System.out.println("  Hash function count: " + hashFunctionCount);
    }
    
    /**
     * 添加元素
     */
    public void add(String element) {
        for (int i = 0; i < hashFunctionCount; i++) {
            int hash = hash(element, i);
            bitSet.set(Math.abs(hash % bitSetSize));
        }
    }
    
    /**
     * 检查元素是否可能存在
     */
    public boolean mightContain(String element) {
        for (int i = 0; i < hashFunctionCount; i++) {
            int hash = hash(element, i);
            if (!bitSet.get(Math.abs(hash % bitSetSize))) {
                return false; // 确定不存在
            }
        }
        return true; // 可能存在
    }
    
    /**
     * 计算当前假阳性率
     */
    public double getCurrentFalsePositiveRate() {
        int setBits = bitSet.cardinality();
        double ratio = (double) setBits / bitSetSize;
        return Math.pow(ratio, hashFunctionCount);
    }
    
    /**
     * 多重哈希函数
     */
    private int hash(String element, int hashIndex) {
        // 使用双重哈希避免计算多个独立哈希函数
        int hash1 = element.hashCode();
        int hash2 = hash1 >>> 16;
        
        return hash1 + hashIndex * hash2;
    }
    
    /**
     * 计算最优bit数组大小
     */
    private int calculateOptimalBitSetSize(int expectedElements, double falsePositiveRate) {
        return (int) Math.ceil(-expectedElements * Math.log(falsePositiveRate) / (Math.log(2) * Math.log(2)));
    }
    
    /**
     * 计算最优哈希函数个数
     */
    private int calculateOptimalHashFunctionCount(int expectedElements, int bitSetSize) {
        return Math.max(1, (int) Math.round((double) bitSetSize / expectedElements * Math.log(2)));
    }
}

🛡️ 缓存穿透防护

缓存穿透问题解决

/**
 * 使用布隆过滤器防止缓存穿透
 */
@Service
public class CacheService {
    
    private final BloomFilter bloomFilter;
    private final RedisTemplate<String, Object> redisTemplate;
    private final UserRepository userRepository;
    
    // 缓存配置
    private static final String CACHE_PREFIX = "user:";
    private static final Duration CACHE_TTL = Duration.ofHours(1);
    
    public CacheService(RedisTemplate<String, Object> redisTemplate, 
                       UserRepository userRepository) {
        this.redisTemplate = redisTemplate;
        this.userRepository = userRepository;
        
        // 初始化布隆过滤器
        this.bloomFilter = new BloomFilter(1000000, 0.01); // 100万用户，1%误判率
        
        // 预加载所有用户ID到布隆过滤器
        initializeBloomFilter();
    }
    
    /**
     * 获取用户信息（防缓存穿透）
     */
    public User getUserById(String userId) {
        // 1. 布隆过滤器快速检查
        if (!bloomFilter.mightContain(userId)) {
            System.out.println("User " + userId + " definitely not exists (Bloom Filter)");
            return null; // 确定不存在，直接返回
        }
        
        // 2. 查询缓存
        String cacheKey = CACHE_PREFIX + userId;
        User cachedUser = (User) redisTemplate.opsForValue().get(cacheKey);
        if (cachedUser != null) {
            System.out.println("Cache hit for user: " + userId);
            return cachedUser;
        }
        
        // 3. 查询数据库
        System.out.println("Cache miss, querying database for user: " + userId);
        User user = user