欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

BloomFilter过滤器过滤算法的简单实现(学习笔记)

程序员文章站 2022-07-05 23:29:33
BloomFilter主要包括两种操作:   add():添加元素到其中   contains():判断一个元素是否在其中,(没有就是没有,说了有但实际...
BloomFilter主要包括两种操作:

 

add():添加元素到其中

 

contains():判断一个元素是否在其中,(没有就是没有,说了有但实际上有可能没有)

 

关于contains()函数:

 

①,如果结果返回false:则元素一定不再其中

 

②,如果返回true,则不一定就在其中,这就是误差

 

 

 

BloomFilter实现(m(byte数组的大小)+k(hash次数)+n(需要存储的数据量))byte映射,多个hash函数

        既然涉及到byte存储,那么必然需要一种映射关系了,也就是需要知道一个元素用哪些byte来表示,这也就是hash函数所干的事情。直观地想,一个元素一个byte基本上不可能,一般情况下这样的hash函数可以说不存在,所以这里假设用k位来表示,一般采用k次hash来确定这些byte。实际上,BloomFilter中一般包含m(byte数组的大小),k(hash次数)和n(需要存储的数据量)。 在元素加入实现add()操作时,连续k次hash,将得到的对应k位全置为1。当查询元素是否在集合中时,也是连续k次hash,如果这k次得到的位不是全为1,那么返回false;否则返回 true。传统的算法优化都是以时间换空间或者以空间换时间,BloomFilter则是以正确率换空间。

 

原文链接:https://bjyjtdj.iteye.com/blog/1455029

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

 

BloomFilter简单的java例子实现;

 

package com.me;

 

import java.util.BitSet;

 

//BloomFilter主要有两种操作:add(),contains()

public class BloomFilter {

    private int defaultSize = 2 << 20;

    private int basic = defaultSize - 1;

    private BitSet bitSet;

 

    public BloomFilter() {

        bitSet = new BitSet(defaultSize);

    }

 

    // 将元素加入其中,

    public void add(String url) {

        if (url == null) {

            return;

        }

        int key1 = hashA(url);

        int key2 = hashB(url);

        int key3 = hashC(url);

        bitSet.set(key1);

        bitSet.set(key2);

        bitSet.set(key3);

    }

 

    // 判断一个元素是不是在其中

    public boolean contains(String url) {

        if (url == null) {

            return true;

        }

        int key1 = hashA(url);

        int key2 = hashB(url);

        int key3 = hashC(url);

        if (bitSet.get(key1) && bitSet.get(key2) && bitSet.get(key3)) {

            return true;

        }

        return false;

    }

 

    private int check(int speed) {

        return basic & speed;

    }

 

    public boolean ifNotContainsSet(String url) {

        if (url == null) {

            return true;

        }

        int key1 = hashA(url);

        int key2 = hashB(url);

        int key3 = hashC(url);

        if (bitSet.get(key1) && bitSet.get(key2) && bitSet.get(key3)) {

            return true;

        }

        bitSet.set(key1);

        bitSet.set(key2);

        bitSet.set(key3);

        return false;

    }

 

    private int hashA(String url) {

        int speed = 0;

        for (int i = 0; i < url.length(); i++) {

            speed = 13 * speed + url.charAt(i);

        }

        return check(speed);

    }

 

    private int hashB(String url) {

        int speed = 0;

        for (int i = 0; i < url.length(); i++) {

            speed = 23 * speed + url.charAt(i);

        }

        return check(speed);

    }

 

    private int hashC(String url) {

        int speed = 0;

        for (int i = 0; i < url.length(); i++) {

            speed = 34 * speed + url.charAt(i);

        }

        return check(speed);

    }

 

    public static void main(String[] args) {

        String bd = "https://www.baidu.com";

        BloomFilter bloomFilter = new BloomFilter();

 

        

        //not contains

        String tb = "https://www.taobao.com";

        System.out.println(bloomFilter.contains(tb));

        

        //if not contains then add

        System.out.println(bloomFilter.contains(bd));

        bloomFilter.add(bd);

        System.out.println(bloomFilter.contains(bd));

        

        //if not contains  then set (ifNotSet)

        String gg = "https://www.google.com";

        System.out.println(bloomFilter.ifNotContainsSet(gg));

        System.out.println(bloomFilter.contains(gg));

        

    }

}