简单实用的布隆过滤器

alanoddsoff 发布于2019-08-16 16:08 / 2906人阅读

摘要：前言布隆过滤器是年由布隆提出的。布隆过滤器可以用于检索一个元素是否在一个集合中。而在中有个位向量，我们可以基于实现一个简单实用的布隆过滤器。实现代码布隆过滤器将元素加入到过滤器为时，索引为判断元素是否在过滤器中为存在，为不存在为时，索引为

前言

布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。

布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

而在Java中有个BitSet（位向量），我们可以基于BitSet实现一个简单实用的布隆过滤器。

实现代码

import java.util.BitSet;

/**
 * 布隆过滤器
 * @author RJH
 * create at 2019-03-25
 */
public class BloomFilter {

    private BitSet data;

    public BloomFilter() {
        this.data = new BitSet();
    }

    /**
     * 将元素加入到过滤器
     * @param t
     */
    public void add(T t){
        if(t==null){//为null时，索引为0
            data.set(0);
        }else{
            data.set(t.hashCode());
        }
    }

    /**
     * 判断元素是否在过滤器中

     * @param t
     * @return true为存在，false为不存在
     */
    public boolean filter(T t){
        if(t==null){//为null时，索引为0
            return data.get(0);
        }else{
            return data.get(t.hashCode());
        }
    }
}

GPU云服务器云服务器布隆过滤器 ubbcode简单实用 linux简单实用布隆去重

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/73924.html

区块链学习之密码学安全技术（五）

摘要：非对称加密算法的安全性往往需要基于数学问题来保障，目前主要有基于大数质因子分解离散对数椭圆曲线等经典数学难题进行保护。消息认证码基于对称加密，可以用于对消息完整性进行保护。 Hash 算法与数字摘要 Hash （哈希或散列）算法它能将任意长度的二进制明文串映射为较短的（通常是固定长度的）二进制串（Hash值），并且不同的明文很难映射为相同的Hash值。 Hash 定义 Hash （哈希...

aboutU 2019-06-27 18:29 评论0 收藏0
布隆过滤器简介

摘要：布隆过滤器可以用于检索一个元素是否在一个集合中。举个栗子，比如第一次将存入布隆过滤器，将数组的，位置置为了，只要下次再有存入布隆过滤器，发现已经是全是了，所以可知该字符串已经保存过。最近做爬虫项目过滤重复的url的时候,了解到一个东西,叫布隆过滤器,然后也学习了一下,写下这篇博客记录一下.下面我们将分为几个专题来介绍布隆过滤器:1.什么是布隆过滤器;2.布隆过滤器的使用场景和...

shuibo 2019-08-16 17:30 评论0 收藏0
大白话布隆过滤器

摘要：可以看出，仅仅从布隆过滤器本身而言，根本没有存放完整的数据，只是运用一系列随机映射函数计算出位置，然后填充二进制向量。也就是说布隆过滤器只能判断数据是否一定不存在，而无法判断数据是否一定存在。我向布隆过滤器插入了，然后用来测试误判率。本文是站在小白的角度去讨论布隆过滤器，如果你是科班出身，或者比较聪明，又或者真正想完全搞懂布隆过滤器的可以移步。不知道从什么时候开始，本来默默无闻的布隆过滤器...

meteor199 2019-05-23 16:22 评论0 收藏0