布隆过滤器

特点

它实际上是由一个很长的二进制向量和一系列随机hash映射函数组成(说白了,就是用二进制数组存储数据的特征)。
布隆过滤器,判断存在的元素,可能不存在,但是判断不存在的元素,一定不存在。

优点

判断存在性效率特别高,而且占用空间小

缺点

只能添加,无法删除元素(因为位删除可能导致其它元素不再完整地被映射)。
误判可能;

应用

(邮件等)黑名单;
爬虫;
URL判重,防缓存穿透;

实现

Java 的 BitSet

需要自己包装实现——add,contains方法,自定义hash函数数组,不支持误判。
非分布式存储,使用场景少;

Redis 的 BitSet

redis命令:
setbit key offset value
gitbit key offset

img

但自己还要根据bitset进行包装(同java的实现)

redisson有现成的包装实现,不必重复造轮子。

    <dependencies>
        <dependency>
            <groupId>org.redisson</groupId>
            <artifactId>redisson</artifactId>
            <version>3.11.2</version>
        </dependency>
    </dependencies>

import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;

public class BloomFilterTest {
    public static void main(String[] args) {
        Config config = new Config();
        config.useSingleServer().setAddress("redis://localhost:6379");
        config.useSingleServer().setPassword("password");
        // 相当于创建了redis的连接
        RedissonClient redisson = Redisson.create(config);

        RBloomFilter<String> bloomFilter = redisson.getBloomFilter("myBloomFilter");
        //初始化,预计元素数量为100000000,期待的误差率为4%
        bloomFilter.tryInit(100000000,0.04);
        //将号码10086插入到布隆过滤器中
        bloomFilter.add("12345");

        System.out.println(bloomFilter.contains("123456"));//false
        System.out.println(bloomFilter.contains("12345"));//true
    }
}

google guava 的 BloomFilter

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

import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

public class GuavaBloomFilter {
    public static void main(String[] args) {
        BloomFilter<String> bloomFilter = BloomFilter.create(
                Funnels.stringFunnel(Charsets.UTF_8),1000000,0.04);

        bloomFilter.put("Sam");

        System.out.println(bloomFilter.mightContain("Jane"));
        System.out.println(bloomFilter.mightContain("Sam"));
    }
}

img

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注