寒光博客

[java] 布隆过滤器 (简化版本布隆过滤器的实现)
BloomFilter 前言 Data structures are nothing different. Th...
扫描右侧二维码阅读全文
10
2019/11

[java] 布隆过滤器 (简化版本布隆过滤器的实现)

BloomFilter

前言

Data structures are nothing different. They are like the bookshelves of your application where you can organize your data. Different data structures will give you different facility and benefits. To properly use the power and accessibility of the data structures you need to know the trade-offs of using one.

大意是不同的数据结构有不同的适用场景和优缺点,你需要仔细权衡自己的需求之后妥善适用它们,布隆过滤器就是践行这句话的代表。

什么是布隆过滤器

本质上布隆过滤器是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”。

相比于传统的 List、Set、Map 等数据结构,它更高效、占用空间更少,但是缺点是其返回的结果是概率性的,而不是确切的。


布隆过滤器数据结构 关于删除 如何选择哈希函数个数和布隆过滤器长度 大Value拆分

简化版BloomFilter

package _10_Hash;

import java.math.BigInteger;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.ArrayList;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 * 简化版本布隆过滤器的实现
 */
public class BloomFilter {
    public static final int NUM_SLOTS = 1024 * 1024 * 8;//位图的长度
    public static final int NUM_HASH = 8;//hash函数的个数,一个Hash函数的结果用于标记一个位
    private BigInteger bitmap = new BigInteger("0");//可能超出Int 所以用big

    public static void main(String[] args) {

        BloomFilter bf = new BloomFilter();
        ArrayList<String> contents = new ArrayList<>();
        contents.add("dxoca.cn");
        contents.add("as34h3f");
        contents.add("ah34a,yj,");
        contents.add("a.7fh.f");
        contents.add("3srtsdbnv.s");

        for (int i = 0; i < contents.size(); i++) {
            bf.addElement(contents.get(i));
        }
        System.out.println(bf.check("dxoca.cn"));
        System.out.println(bf.check("2019年11月10日 17:55:01"));

    }

    /**
     * 将message+n映射到0~NUM_SLOTS-1之间的一个数值
     *
     * @param message
     * @param n
     * @return
     */
    private int hash(String message, int n) {

        message = message + n;
        try {
            MessageDigest md5 = MessageDigest.getInstance("md5");//将任意输入映射成128位(16个字节 [2^128 -1]很大的数字)整数的hash函数
            byte[] bytes = message.getBytes();
            md5.update(bytes);
            BigInteger bi = new BigInteger(md5.digest());//至此 过的message+n的md5结果 (128位整数)
            return Math.abs(bi.intValue()) % NUM_SLOTS;//小于NUM_SLOTS长度
        } catch (NoSuchAlgorithmException ex) {
            Logger.getLogger(BloomFilter.class.getName()).log(Level.SEVERE, null, ex);
        }
        return -1;
    }

    /**
     * 处理原始数据 生成图
     * 1.hash1(msg)标注一个位....   hash的值域0~NUM_SLOTS-1
     *
     * @param message
     */
    public void addElement(String message) {
        for (int i = 0; i < NUM_HASH; i++) {
            int hashCode = hash(message, i);//代表若干hash 1..2.3 代表一个位
            //用于标注位图该位为1
            if (!bitmap.testBit(hashCode)) {//r判断hashCode位是否为1 如果不为1 这则把该位标记为 1
                bitmap = bitmap.or(new BigInteger("1").shiftLeft(hashCode));//先生成hashCode位为1的二进制数 再和 bitmap或运算  hashCode 位变成1
            }
        }
    }

    /**
     * 查找
     * @param message 新的串~
     * @return
     */
    public boolean check(String message) {
        for (int i = 0; i < NUM_HASH; i++) {
            //hashCode代表一个位置 便利每个位置
            int hashCode = hash(message, i);
            //如果位图的hashCode位为0 那么message一定不存在
            if (!this.bitmap.testBit(hashCode)) {//判断 hashCode位是否为1
                return false;
            }
        }
        return true;//对应位不精确 有可能误判
    }
}

参考文献

https://hackernoon.com/probabilistic-data-structures-bloom-filter-5374112a7832

本文作者:Author:     文章标题:[java] 布隆过滤器 (简化版本布隆过滤器的实现)
本文地址:https://dxoca.cn/java/315.html       百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:November 10th, 2019 at 10:18 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment