package com.xiaomi.oos.xmstore.oms.controller;

import java.util.BitSet;

public class Bloom {
    private int times = 5; // 哈希次数
    private int len = 100; // 空间长度
    private long count = 64L; // 插入的元素个数
    private double rate = 0.01; // 误报率
    private BitSet bitSet;

    public Bloom() {
        this.init(10000, 0.01);
    }

    public void init(Long count, double rate) {
        this.count = count;
        this.rate = rate;
        int len = -(int) ((Math.log(rate) * count) / (Math.pow(Math.log(2), 2)));
        this.len = Math.max(len, 1);
        int times = (int) (Math.log(2) * (this.len / this.count));
        this.times = Math.max(times, 1);
        this.bitSet = new BitSet(len);
    }

    public void init(int count, double rate) {
        this.init(Long.valueOf(count), rate);
    }

    @Override
    public String toString() {
        return "元素个数:" + this.count + " 误报率:" + this.rate + " 过滤器长度:" + this.len + " 哈希次数:" + this.times;
    }

    public void add(Long id) {
        long[] pos = this.pos(id);
        for (long po : pos) {
            this.bitSet.set(Math.toIntExact(po));
        }
    }

    public void add(int id) {
        this.add(Long.valueOf(id));
    }

    public boolean find(Long id) {
        long[] pos = this.pos(id);
        for (long po : pos) {
            if (!this.bitSet.get(Math.toIntExact(po))) {
                return false;
            }
        }
        return true;
    }

    public boolean find(int id) {
        return this.find(Long.valueOf(id));
    }

    public long[] pos(long id) {
        long prev = id;
        long[] pos = new long[this.times];
        for (int i = 0; i < this.times; i++) {
            int hashCode = Math.abs(String.valueOf(prev).hashCode());
            int mod = hashCode % len;
            prev = hashCode;
            pos[i] = mod;
        }
        return pos;
    }

    public String dumpPos(long id) {
        long[] pos = this.pos(id);
        StringBuffer posS = new StringBuffer();
        for (long po : pos) {
            posS.append(po);
            posS.append(" ");
        }
        return posS.toString();
    }

    public String dumpPos(int id) {
        return this.dumpPos(Long.valueOf(id));
    }

    public static void main(String[] args) {
        Bloom bloom = new Bloom();
        bloom.init(100000, 0.01);

        System.out.println(bloom);

        System.out.println("10的hash分布：  " + bloom.dumpPos(10));

        StringBuffer added = new StringBuffer();

        for (int i = 0; i < 10; i++) {
            final int i1 = (int) (Math.random() * 10000);
            bloom.add(i1);
            added.append(i1);
            added.append(" ");
        }

        System.out.println("插入10个0-10000的随机数: " + added.toString());

        System.out.print("查找: ");
        for (int i = 0; i < 10000; i++) {
            if (bloom.find(i)) {
                System.out.print(i + " ");
            }
        }
    }
}

测试结果：