Redis 布隆器安装和简单实现

安装扩展  https://blog.csdn.net/maoyuanming0806/article/details/102798976

在laravel 中的简单使用

Lua 脚本用起来

$sh=<<<LUA
    return redis.call('bf.add',KEYS[1],KEYS[2])
LUA;

$result=Redis::eval($sh,2,"java","php");

实现原理:

 依赖于位图,解决Hash冲突就靠着计算多次Hash值

在java中一个int 变量占8个字节(64位机器) 也就是由 64个二进制码组成 所以就个存储64个位的信息,存储一亿信息的计算公式就为 100000000/64*8/1024/1024 ≈ 11 MB

 但是又一定的错误率,减少错误率的方法是增大空间和每次计算更多的Hash值

JAVA 简单实现

package BF;

import java.util.*;

class BloomFilter {
    private static final int DEFAULT_SIZE = 2<<29; //开辟空间
    private static final int[] seeds = new int[] { 5, 7, 11, 13, 31, 37, 61,22,2,77,3 }; //计算出8个不同的Hash值
    private BitSet bits = new BitSet(DEFAULT_SIZE); //Bit 实现类
    private SimpleHash[] func = new SimpleHash[seeds.length];

    public BloomFilter() {  //构造函数事前模拟出8个人出来
        for (int i = 0; i < seeds.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
        }
    }

    public void add(String value) { //添加一个字符串到布隆器中
        for (SimpleHash f : func) {  //循环每个人计算一下hash值
            bits.set(f.hash(value), true); //将对应的hash位设为1
        }
    }

    public boolean contains(String value) { //判断字符串是否添加过
        if (value == null) {
            return false;
        }
        boolean ret = true;
        for (SimpleHash f : func) { //8个人进行判断,有一个人没见过就不存在
            ret = ret && bits.get(f.hash(value));
        }
        return ret;
    }

    // 内部类，simpleHash
    public static class SimpleHash {
        private int cap; //位图长度
        private int seed; //hash 计算值

        public SimpleHash(int cap, int seed) { //构造函数赋值
            this.cap = cap;
            this.seed = seed;
        }

        public int hash(String value) { //计算Hash值
            int result = 0;
            int len = value.length(); //计算出字符串的长度
            for (int i = 0; i < len; i++) {
                result = seed * result + value.charAt(i); //转为ascii 码
            }
            return (cap - 1) & result; //进行二进制的与运算
        }
    }

    public static void main(String[] args) {

        BloomFilter bf = new BloomFilter();


        bf.add("java");
        for (int i=0;i<100000000;i++){
            bf.add(i+"n");
        }
        int count=0;
        boolean isOk=false;
        for (int i=0;i<100000000;i++){
                 isOk=bf.contains(UUID.randomUUID().toString()+"nphp");
            if (isOk){
                System.out.println("OK");
                count++;
            }
        }
        System.out.println(bf.contains("java"));
        System.out.println(count);

    }

}

!!!