java项目中布隆过滤器和布谷鸟过滤器

淡淡的烟草味﹌ 2023-02-16 15:26 62阅读 0赞

## 布隆过滤器 ##

布隆过滤器是一个叫“布隆”的人提出的，它本身是一个很长的二进制向量，既然是二进制的向量，那么显而易见的，存放的不是0，就是1。  
现在我们新建一个长度为16的布隆过滤器，默认值都是0，就像下面这样：

通过使用多个不同的哈希函数生成多个哈希值，并对每个生成的哈希值指向的 bit 位置 1

如果1、4、7 位置的bit为1的话，那么我们就认为 “baidu”是存在的，反之就不存在。  
但是这种方法随着存取的值越来越多，会存在一定程度的误判，错误率低于低于1% （布隆过滤器越长、插入数据越少，错误率越低）  
但是布隆过滤器不支持删除，所以相对而言提升了其错误率。

## 应用场景 ##

（1）拼写检查，即判断一个单词是否存在字典。  
（2）垃圾邮件过滤  
假设邮件服务器通过发送方的邮件域或者IP地址对垃圾邮件进行过滤，那么就需要判断当前的邮件域或者IP地址是否处于黑名单之中。  
（3）加快数据库查询过程

## 布隆过滤器的实现方式 ##

**方式一：guava内置布隆过滤器**  
依赖

<dependency>
      <groupId>com.google.guava</groupId>
      <artifactId>guava</artifactId>
      <version>23.0</version>
    </dependency>

使用方式

import com.google.common.hash.BloomFilter;
    import com.google.common.hash.Funnels;
    
    public class AppTest{ 
        private static int size = 1000000;//预计要插入多少数据
        private static double fpp = 0.01;//期望的误判率
        private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);
        public static void main(String[] args) { 
            //插入数据
            for (int i = 0; i < 1000000; i++) { 
                bloomFilter.put(i);
            }
            int count = 0;
            for (int i = 1000000; i < 2000000; i++) { 
                if (bloomFilter.mightContain(i)) { 
                    count++;
                    System.out.println(i + "误判了");
                }
            }
            System.out.println("总共的误判数:" + count);
        }
    }

**方式二：redis实现**  
依赖

<dependency>
      <groupId>com.google.guava</groupId>
      <artifactId>guava</artifactId>
      <version>23.0</version>
    </dependency>
    
    <dependency>
      <groupId>org.springframework.boot</groupId>
      <artifactId>spring-boot-starter-data-redis</artifactId>
    </dependency>
    
    <dependency>
      <groupId>redis.clients</groupId>
      <artifactId>jedis</artifactId>
      <version>2.9.0</version>
    </dependency>

application.properties

#Redis服务器地址
    spring.redis.host=127.0.0.1
    #Redis服务器连接端口
    spring.redis.port=6379
    #Redis数据库索引（默认为0）
    spring.redis.database=0  
    #连接池最大连接数（使用负值表示没有限制）
    spring.redis.jedis.pool.max-active=50
    #连接池中的最大空闲连接
    spring.redis.jedis.pool.max-idle=20
    #连接池中的最小空闲连接
    spring.redis.jedis.pool.min-idle=2

RedisConfiguration

/** * redis中的配置项 */
    @Configuration
    public class RedisConfiguration { 
        @Autowired
        private RedisTemplate redisTemplate;
        /** * 设置redis序列化方式，解决数据存入redis中二进制乱码 * @return */
        @Bean
        public RedisTemplate<String, Object> stringSerializerRedisTemplate() { 
            RedisSerializer<String> stringSerializer = new StringRedisSerializer();
            redisTemplate.setKeySerializer(stringSerializer);
            redisTemplate.setValueSerializer(stringSerializer);
            redisTemplate.setHashKeySerializer(stringSerializer);
            redisTemplate.setHashValueSerializer(stringSerializer);
            return redisTemplate;
        }
        /** * 配置布隆过滤器 * @return */
        @Bean
        public BloomFilterHelper<String> initBloomFilterHelper() { 
            return new BloomFilterHelper<>((Funnel<String>) (from, into) -> into.putString(from, Charsets.UTF_8)
                    .putString(from, Charsets.UTF_8), 1000000, 0.01);
        }
    }

BloomFilterHelper

/** * <布隆过滤器> * * 算法过程： * 1. 首先需要k个hash函数，每个函数可以把key散列成为1个整数 * 2. 初始化时，需要一个长度为n比特的数组，每个比特位初始化为0 * 3. 某个key加入集合时，用k个hash函数计算出k个散列值，并把数组中对应的比特位置为1 * 4. 判断某个key是否在集合时，用k个hash函数计算出k个散列值，并查询数组中对应的比特位，如果所有的比特位都是1，认为在集合中。 * */
    public class BloomFilterHelper<T> { 
        private int numHashFunctions;
        private int bitSize;
        private Funnel<T> funnel;
        public BloomFilterHelper(Funnel<T> funnel, int expectedInsertions, double fpp) { 
            Preconditions.checkArgument(funnel != null, "funnel不能为空");
            this.funnel = funnel;
            // 计算bit数组长度
            bitSize = optimalNumOfBits(expectedInsertions, fpp);
            // 计算hash方法执行次数
            numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize);
        }
        public int[] murmurHashOffset(T value) { 
            int[] offset = new int[numHashFunctions];
            long hash64 = Hashing.murmur3_128().hashObject(value, funnel).asLong();
            int hash1 = (int) hash64;
            int hash2 = (int) (hash64 >>> 32);
            for (int i = 1; i <= numHashFunctions; i++) { 
                int nextHash = hash1 + i * hash2;
                if (nextHash < 0) { 
                    nextHash = ~nextHash;
                }
                offset[i - 1] = nextHash % bitSize;
            }
            return offset;
        }
        /** * 计算bit数组长度 */
        private int optimalNumOfBits(long n, double p) { 
            if (p == 0) { 
                // 设定最小期望长度
                p = Double.MIN_VALUE;
            }
            int sizeOfBitArray = (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
            return sizeOfBitArray;
        }
        /** * 计算hash方法执行次数 */
        private int optimalNumOfHashFunctions(long n, long m) { 
            int countOfHash = Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
            return countOfHash;
        }
    }

RedisService

/** * 〈Redis-操作工具类〉 * * @create 2019/1/22 * @since 1.0.0 */
    @Service
    public class RedisService { 
        @Autowired
        private RedisTemplate redisTemplate;
        /** * 根据给定的布隆过滤器添加值 */
        public <T> void addByBloomFilter(BloomFilterHelper<T> bloomFilterHelper, String key, T value) { 
            Preconditions.checkArgument(bloomFilterHelper != null, "bloomFilterHelper不能为空");
            int[] offset = bloomFilterHelper.murmurHashOffset(value);
            for (int i : offset) { 
                //System.out.println("key : " + key + " " + "value : " + i);
                redisTemplate.opsForValue().setBit(key, i, true);
            }
        }
        /** * 根据给定的布隆过滤器判断值是否存在 */
        public <T> boolean includeByBloomFilter(BloomFilterHelper<T> bloomFilterHelper, String key, T value) { 
            Preconditions.checkArgument(bloomFilterHelper != null, "bloomFilterHelper不能为空");
            int[] offset = bloomFilterHelper.murmurHashOffset(value);
            for (int i : offset) { 
                //System.out.println("key : " + key + " " + "value : " + i);
                if (!redisTemplate.opsForValue().getBit(key, i)) { 
                    return false;
                }
            }
            return true;
        }
    }

RedisRunner:以插入username为例

@Component
    public class RedisRunner implements CommandLineRunner { 
        @Autowired
        private RedisService redisService;
        @Autowired
        private UserInfoPojoMapper userInfoPojoMapper;
        @Autowired
        private BloomFilterHelper bloomFilterHelper;
        //日志记录器
        private static Logger logger= LogManager.getLogger(LogManager.ROOT_LOGGER_NAME);
        /** * 将username放在指定的布隆过滤器中 * @param args * @throws Exception */
        @Override
        public void run(String... args) throws Exception { 
            logger.info("**** RedisRunner ****");
            List<UserInfoPojo> wbUsers = userInfoPojoMapper.selectList(null);
            long startTime=System.currentTimeMillis();   //获取开始时间
            // 初始化布隆过滤器内容
            for (UserInfoPojo user : wbUsers) { 
                redisService.addByBloomFilter(bloomFilterHelper, "bloom", user.getUserName());
            }
            long endTime=System.currentTimeMillis(); //获取结束时间
            logger.info("插入布隆过滤器，总数据条数："+wbUsers.size()+"用时："+(endTime-startTime)+"ms");
        }
    }

## 布谷鸟过滤器 ##

布谷鸟过滤器使用两个 hash 算法将新来的元素映射到数组的两个位置. 如果两个位置中有一个位置位空, 那么就可以将元素直接放进去.  
但是如果这两个位置都满了, 它就会随机踢走一个, 然后自己霸占了这个位置.  
布谷鸟过滤器支持删除，对空间利用效率更高，但是存在误删的可能性。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDk5MDgxOA_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDk5MDgxOA_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/2020081223275752.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDk5MDgxOA==,size_16,color_FFFFFF,t_70#pic_center