### 什么是布隆过滤器

• 优点：由于存放的不是完整的数据，所以占用的内存很少，而且新增，查询速度够快；
• 缺点： 随着数据的增加，误判率随之增加；无法做到删除数据；只能判断数据是否一定不存在，而无法判断数据是否一定存在。

### guava实现布隆过滤器

``````        <dependency>

``    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); }``

``````1999501误判了
1999567误判了
1999640误判了
1999697误判了
1999827误判了 1999942误判了 总共的误判数:10314``````

### redis实现布隆过滤器

``````public class RedisMain {
static final int expectedInsertions = 100;//要插入多少数据 static final double fpp = 0.01;//期望的误判率 //bit数组长度 private static long numBits; //hash函数数量 private static int numHashFunctions; static { numBits = optimalNumOfBits(expectedInsertions, fpp); numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits); } public static void main(String[] args) { Jedis jedis = new Jedis("192.168.232.20", 6379); for (int i = 0; i < 100; i++) { long[] indexs = getIndexs(String.valueOf(i)); for (long index : indexs) { jedis.setbit("codebear:bloom", index, true); } } for (int i = 0; i < 100; i++) { long[] indexs = getIndexs(String.valueOf(i)); for (long index : indexs) { Boolean isContain = jedis.getbit("codebear:bloom", index); if (!isContain) { System.out.println(i + "肯定没有重复"); } } System.out.println(i + "可能重复"); } } /** * 根据key获取bitmap下标 */ private static long[] getIndexs(String key) { long hash1 = hash(key); long hash2 = hash1 >>> 16; long[] result = new long[numHashFunctions]; for (int i = 0; i < numHashFunctions; i++) { long combinedHash = hash1 + i * hash2; if (combinedHash < 0) { combinedHash = ~combinedHash; } result[i] = combinedHash % numBits; } return result; } private static long hash(String key) { Charset charset = Charset.forName("UTF-8"); return Hashing.murmur3_128().hashObject(key, Funnels.stringFunnel(charset)).asLong(); } //计算hash函数个数 private static int optimalNumOfHashFunctions(long n, long m) { return Math.max(1, (int) Math.round((double) m / n * Math.log(2))); } //计算bit数组长度 private static long optimalNumOfBits(long n, double p) { if (p == 0) { p = Double.MIN_VALUE; } return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2))); } }``````

``````88可能重复
89可能重复
90可能重复
91可能重复
92可能重复
93可能重复
94可能重复
95可能重复
96可能重复
97可能重复
98可能重复
99可能重复``````
• 发表于 2020-03-22 12:06
• 阅读 ( 189 )
• 分类：网络文章

1. 小编 文章