java hash算法原理 Java 布隆过滤器

2023-02-23 411

你在么？在！一定在么？不在！一定不在么？

你想要100%的准去性，还是99%的准确性附带较高的速度和较小的资源消耗。

任何算法java hash算法原理，任何经营收到的背后，都是时间效益资源消耗准确性的平衡（1天的时间 10元的投入生产10个单位的产品，还是 0.6天的时间 6元的投入生产9个单位的产品）

存在即合理，只是在不同场景下的不同选择。

百度百科

    布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向
    量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的
    优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难

维基百科

    A Bloom filter is a space-efficient probabilistic data structure, conceived
     by Burton Howard Bloom in 1970, that is used to test whether an element is 
    a member of a set. False positive matches are possible, but false negatives 
    are not, thus a Bloom filter has a 100% recall rate. In other words, a query
     returns either “possibly in set” or “definitely not in set”.
    空间效率高的概率型数据结构，用来检查一个元素是否在一个集合中。
    对于一个元素检测是否存在的调用，BloomFilter会告诉调用者两个结果之一：

用途

存值，与set map类似（set map 存储大量数据时浪费空间）。

校验值是否存在（不存在一定不存在，存在可能不一定存在【有一定误差】）。

原理

存值：

k = m/n * ln2 【m是数组长度，n是插入的元素个数，k是hash函数的个数】

假设想要将“张三”放入数组中，经计算k=3的情况java hash算法原理，大体存储如下图。

java hash算法原理_java集合中的hash算法_一致性hash算法

校验：

1.同样的k值计算，获取hash函数个数java hash算法原理 Java 布隆过滤器，计算落点位置。

2.逐个落点校验，每个落点位置都标记为1则元素可能存在，只要有一个落点标记为0则不存在。

看到这大家是不是一下子明白的啥叫没有就是没有哈。

---------------------------------------------------------------------------------------------------------------------------------

2.Guava Bloom

import com.google.common.hash.BloomFilter;

    import com.google.common.hash.Funnels;
    import org.junit.Test;
    import java.nio.charset.Charset;
    public class BloomFilterTest {
        @Test
        public void test() {
            // 100w bit长度 ,0.01%误判率
            // bf对象则会生成 299534 个long数组,使用13次hash计算.
            BloomFilter bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()), 100 * 10000, 0.0001d);
            System.out.println(bloomFilter.mightContain("test1")); // false
            bloomFilter.put("test1");
            System.out.println(bloomFilter.mightContain("test1")); // true
            bloomFilter.put("test12");
        }

---------------------------------------------------------------------------------------------------------------------------------

1.pom依赖包

org.

--boot-

3.16.7

2.yml配置（redis配置）

redis:

host: 39.106.174.189

port: 60002

: @!@#

ssl: false

3.Java 测试代码

import lombok.extern.slf4j.Slf4j;

    import org.junit.Test;
    import org.junit.runner.RunWith;
    import org.redisson.api.RBloomFilter;
    import org.redisson.api.RedissonClient;
    import org.springframework.boot.test.context.SpringBootTest;
    import org.springframework.test.context.ActiveProfiles;
    import org.springframework.test.context.junit4.SpringRunner;
    import javax.annotation.Resource;
    @SpringBootTest
    @RunWith(SpringRunner.class)
    @ActiveProfiles("test")
    @Slf4j
    public class RedisBloomFilterTest {
        @Resource
        private RedissonClient redissonClient;
        @Test
        public void testBloomFilter() {
            // 预期插入数量
            long expectedInsertions = 100L;
            // 错误比率
            double falseProbability = 0.01;
            RBloomFilter bloomFilter = redissonClient.getBloomFilter("blackList");
            bloomFilter.tryInit(expectedInsertions, falseProbability);
            // 布隆过滤器增加元素
            for (long i = 0; i < expectedInsertions; i++) {
                bloomFilter.add("test" + i);
            }
            long elementCount = bloomFilter.count();
            log.info("elementCount = {}.", elementCount);
            // 统计误判次数
            int count = 0;
            for (long i = expectedInsertions; i < expectedInsertions * 2; i++) {
                if (bloomFilter.contains("test" + i)) {
                    count++;
                }
            }
            log.info("误判次数 = {}.", count);
            bloomFilter.delete();
        }

文章来源:https://blog.csdn.net/qq_34253002/article/details/129100806

风也温柔