金点网络-全网资源,一网打尽
  • 网站首页
    • 金点部落
    • 小游戏
    • OpenAPI
    • 设计资产导航
    • 升级会员
  • 技能学习
    • 体育运动
    • 办公教程
    • 口才演讲
    • 小吃技术
    • 建站教程
    • 摄影教程
    • 棋牌教程
    • 网赚教程
      • 爆粉引流
      • 自媒体
      • 贴吧引流
  • 网站源码
    • 商城/淘客/交易
    • 小说/漫画/阅读
    • 影视/音乐/视频
    • 微信/微商/微擎
    • 理财/金融/货币
    • 模板/主题/插件
  • 游戏源码
    • 精品网单
    • 端游源码
    • 手游源码
    • 页游源码
  • 素材资料
    • 电子文档
    • 综合资料
    • 考研资料
    • 设计素材
    • 音频讲座
      • 人文艺术
      • 名师讲座
      • 说书小说
  • 软件工具
    • Windows软件
    • MacOS软件
    • Android软件
  • 寄售资源
    • 游戏源码
    • 网站源码
    • 软件源码
  • 公益服
登录/注册
  • 专享大神特权
立即开通开通会员抄底价

Java 理论概念·BloomFilter 判断元素存在

作者 : jamin 本文共2648个字,预计阅读时间需要7分钟 发布时间: 2020-10-18 共1384人阅读

BloomFilter 判断元素存在

本文为个人学习摘要笔记。
原文地址:到底是存在还是不存在之 BloomFilter

什么是 BloomFilter

布隆过滤器(Bloom Filter)是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。主要用于判断一个元素是否在一个集合中。通常我们会遇到很多要判断一个元素是否在某个集合中的业务场景,这个时候往往我们都是采用 Hashmap,Set 或者其他集合将数据保存起来,然后进行对比判断,但是如果元素很多的情况,我们如果采用这种方式就会非常浪费空间。这个时候我们就需要 BloomFilter 来帮助我们了。

BloomFilter 原理

BloomFilter 是由一个固定大小的二进制向量或者位图(bitmap)和一系列(通常好几个)映射函数组成的。布隆过滤器的原理是,当一个变量被加入集合时,通过 K 个映射函数将这个变量映射成位图中的 K 个点,把它们置为 1。查询某个变量的时候我们只要看看这些点是不是都是 1,就可以大概率知道集合中有没有它了,如果这些点有任何一个 0,则被查询变量一定不在;如果都是 1,则被查询变量很可能在。注意,这里是可能存在,不一定一定存在!这就是布隆过滤器的基本思想。

简而言之,如果检测结果都为 1,该元素不一定在集合中;但如果检测结果存在 0,该元素一定不在集合中。每个检测请求返回有 “在集合内(可能错误)” 和 “不在集合内(绝对不在集合内)” 两种情况。

如下图所示,字符串 “ziyou” 在经过四个映射函数操作后在位图上有四个点被设置成了 1。当我们需要判断 “ziyou” 字符串是否存在的时候只要在一次对字符串进行映射函数的操作,得到四个 1 就说明 “ziyou” 是可能存在的。

映射函数

为什么说是可能存在,而不是一定存在呢?那是因为映射函数本身就是散列函数,散列函数是会有碰撞的,意思也就是说会存在一个字符串可能是 “ziyou01” 经过相同的四个映射函数运算得到的四个点跟 “ziyou” 是一样的,这种情况下我们就说出现了误算。另外还有可能这四个点位上的 1 是四个不同的变量经过运算后得到的,这也不能证明字符串 “ziyou” 是一定存在的,如下图框出来的 1 也可能是字符串“张三”计算得到,同理其他几个位置的 1 也可以是其他字符串计算得到。

散列碰撞

结论

所以通过上面的例子我们就可以明确:

  • 一个元素如果判断结果为存在的时候元素不一定存在,但是判断结果为不存在的时候则一定不存在。
  • 布隆过滤器可以添加元素,但是不能删除元素。因为删掉元素会导致误判率增加。

使用场景

网页 URL 去重

我们在使用网页爬虫的时候,往往需要记录哪些 URL 是已经爬取过的,哪些还是没有爬取过,这个时候我们就可以采用 BloomFilter 来对已经爬取过的 URL 进行存储,这样在进行下一次爬取的时候就可以判断出这个 URL 是否爬取过。

黑白名单存储

工作中经常会有一个特性针对不同的设备或者用户有不同的处理方式,这个时候可能会有白名单或者黑名单存在,所以根据 BloomFilter 过滤器的特性,我们也可以用它来存在这些数据,虽然有一定的误算率,但是在一定程度上还是可以很好的解决这个问题的。

其实还有很多场景,比如热点数据访问,垃圾邮件过滤等等,其实这些场景的统一特性就是要判断某个元素是否在某个集合中,原理都是一样的。

简单实现

import java.util.BitSet;

public class BloomFilterTest {

    /**
     * 初始化布隆过滤器的 bitmap 大小
     */
    private static final int DEFAULT_SIZE = 2 << 24;
    /**
     * 为了降低错误率,这里选取一些数字作为基准数
     */
    private static final int[] seeds = {3, 5, 7, 11, 13, 31, 37, 61};
    /**
     * 设置 bitmap
     */
    private static BitSet bitset = new BitSet(DEFAULT_SIZE);
    /**
     * 设置 hash 函数数量
     */
    private static HashFunction[] functions = new HashFunction[seeds.length];


    /**
     * 添加数据
     *
     * @param value 需求加入的值
     */
    public static void put(String value) {
        if (value != null) {
            for (HashFunction f : functions) {
                //计算 hash 值并修改 bitmap 中相应位置为 true
                bitset.set(f.hash(value), true);
            }
        }
    }

    /**
     * 判断相应元素是否存在
     *
     * @param value 需要判断的元素
     * @return 结果
     */
    public static boolean check(String value) {
        if (value == null) {
            return false;
        }
        boolean ret = true;
        for (HashFunction f : functions) {
            ret = bitset.get(f.hash(value));
            //一个 hash 函数返回 false 则跳出循环
            if (!ret) {
                break;
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        String value = "test";
        for (int i = 0; i < seeds.length; i++) {
            functions[i] = new HashFunction(DEFAULT_SIZE, seeds[i]);
        }
        put(value);
        System.out.println(check("value"));
    }
}

class HashFunction {

    private int size;
    private int seed;

    public HashFunction(int size, int seed) {
        this.size = size;
        this.seed = seed;
    }

    public int hash(String value) {
        int result = 0;
        int len = value.length();
        for (int i = 0; i < len; i++) {
            result = seed * result + value.charAt(i);
        }
        int r = (size - 1) & result;
        return (size - 1) & result;
    }

}

上面简单的 BloomFilter,通过 put 方法录入数据,通过 check 方法判断元素是否存在。

此外,常用工具库 Guava 和 Hutool 都提供了 BloomFilter 实现。

Atom ExecutorService ForkJoin Java ReentrantLock synchronized ThreadLocal volatile 后台
本站所提供的部分资源来自于网络,版权争议与本站无关,版权归原创者所有!仅限用于学习和研究目的,不得将上述内容资源用于商业或者非法用途,否则,一切后果请用户自负。您必须在下载后的24个小时之内,从您的电脑中彻底删除上述内容资源。如果上述内容资对您的版权或者利益造成损害,请提供相应的资质证明,我们将于3个工作日内予以删除。本站不保证所提供下载的资源的准确性、安全性和完整性,源码仅供下载学习之用!如用于商业或者非法用途,与本站无关,一切后果请用户自负!本站也不承担用户因使用这些下载资源对自己和他人造成任何形式的损失或伤害。如有侵权、不妥之处,请联系站长以便删除!
金点网络-全网资源,一网打尽 » Java 理论概念·BloomFilter 判断元素存在

常见问题FAQ

免费下载或者VIP会员专享资源能否直接商用?
本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。
是否提供免费更新服务?
持续更新,永久免费
是否经过安全检测?
安全无毒,放心食用
jamin

jamin 大神

下一篇
网络协议-组播介绍

相关推荐

烈焰神皇单机一键端+GM工具

烈焰神皇单机一键端+GM工具

魔力宝贝单机端+GM命令+修改工具

魔力宝贝单机端+GM命令+修改工具

Java 理论概念·经典排序算法

Java 理论概念·经典排序算法

单机热血战纪一键服务端有GM修改工具+安装视频教程+外网运营

单机热血战纪一键服务端有GM修改工具+安装视频教程+外网运营

天龙八部3 新凤鸣单机版联网版免虚拟机一键端PC电脑端游3D无限元宝

天龙八部3 新凤鸣单机版联网版免虚拟机一键端PC电脑端游3D无限元宝

标签云
Android Atom ExecutorService ForkJoin GM GM后台 GM授权后台 H5 Java Javascript Linux手工服务端 pipbestcom Python ReentrantLock synchronized ThreadLocal volatile Win一键即玩服务端 一键端 传奇 写作 创业 单机 后台 商业端 外网 安卓 安卓苹果双端 工具 手工端 手游 搭建教程 教程 数据分析 文案 游戏源码 端游 经典 网单 职场 自媒体 视频教程 详细搭建教程 运营后台 页游

近期文章

  • 回合手游【逍遥西游之繁华西游】最新整理单机一键既玩镜像服务端_Linux手工端_GM后台_教程
  • 最新整理精品回合制手游【天书奇谈3D混沌完整版】VM一键单机版_linux手工外网端_隐盟视频教程_授权GM后台_双端
  • 典藏修真页游【诸仙列传OL】最新整理Win系服务端_GM工具_详细外网搭建教程
  • MT3换皮MH【浮生若梦尊享挂机修复版】最新整理单机一键即玩镜像端_Linux手工服务端_安卓苹果双端_GM后台_详细搭建教程
  • 大话回合手游【最新引擎之缥缈西游渡劫版】最新整理Linux手工服务端_安卓苹果双端_管理后台_CDK后台_详细搭建教程_视频教程

分类

  • | wordpress插件 |
  • | wordpress模板 |
  • | 其它模板 |
  • | 帝国模板 |
  • | 织梦插件 |
  • | 织梦模板 |
  • A5源码
  • Android软件
  • APP引流
  • E语言
  • H5
  • LUA
  • QQ营销
  • SEO推广
  • Windows软件
  • 体育运动
  • 信息数据
  • 创业专题
  • 办公教程
  • 口才演讲
  • 名师讲座
  • 商城/淘客/交易
  • 小吃技术
  • 小说/漫画/阅读
  • 建站教程
  • 引流脚本
  • 影视/音乐/视频
  • 影视资源
  • 微信/微商/微擎
  • 微信小程序
  • 微信营销
  • 微擎模块
  • 手游源码
  • 技能学习
  • 抖音课程
  • 摄影教程
  • 棋牌教程
  • 模板/主题/插件
  • 游戏源码
  • 爆粉引流
  • 理财/金融/货币
  • 生活老师
  • 电商客
  • 电子文档
  • 电脑教程
  • 社群营销
  • 站长工具
  • 精品网单
  • 系统工具
  • 素材资料
  • 综合资料
  • 编程经验
  • 网站源码
  • 网络安全
  • 网赚教程
  • 网赚源码
  • 考研资料
  • 脚本/AI/智能
  • 自媒体
  • 英语学习
  • 营销软件
  • 设计素材
  • 说书小说
  • 贴吧引流
  • 软件工具
  • 软文营销
  • 逆向软件
  • 音频讲座
  • 页游源码

提供最优质的资源集合

立即加入 友好社区
金点网络-全网资源,一网打尽

新一代全网资源综合门户网(www.pipbest.com-金点网络)专注服务于互联网,提供各类最新最全的免费源码下载(PHP、ASP、JSP、.NET),更提供免费工具,免费源码下载,软件下载,素材下载,赚钱教程下载,交流论坛等网站运营相关的一切内容,为网友搜罗最有价值的网站源码下载与技术教程等服务!

服务目录
  • 金点OpenAPI
  • 金点云
  • 金点支付
友情链接
  • 数媒派
  • 国家电网
快速搜索

本站由Nice强力驱动

声明: 本站部分内容属于原创转载请注明出处 如有侵权行为请严格参照本站【版权声明】与我们联系,我们将在48小时内容进行处理!

本站部分内容属于原创转载请注明出处 如有侵权行为请严格参照本站【版权声明】与我们联系,我们将在48小时内容进行处理!
© 2016-2023 PipBest.Com - 金点网络 & 金点部落. All rights reserved 京ICP备2022005359号-1
  • 关注有礼
  • 签到
  • 客服
    官方QQ群 常见问题 FAQ

    在线客服

    点我联系

    直接说出您的需求!
    切记!带上资源连接与问题!

    工作时间: 9:30-21:30

  • 暗黑
    模式
  • 全屏
  • 投稿
    赚钱
  • 首页

  • 签到

  • 切换

  • 客服

金点网络-全网资源,一网打尽
  • 登录
  • 注册
or
or
忘记密码?
金点网络-全网资源,一网打尽
  • 网站首页 ►
    • 金点部落
    • 小游戏
    • OpenAPI
    • 设计资产导航
    • 升级会员
  • 技能学习 ►
    • 体育运动
    • 办公教程
    • 口才演讲
    • 小吃技术
    • 建站教程
    • 摄影教程
    • 棋牌教程
    • 网赚教程 ►
      • 爆粉引流
      • 自媒体
      • 贴吧引流
  • 网站源码 ►
    • 商城/淘客/交易
    • 小说/漫画/阅读
    • 影视/音乐/视频
    • 微信/微商/微擎
    • 理财/金融/货币
    • 模板/主题/插件
  • 游戏源码 ►
    • 精品网单
    • 端游源码
    • 手游源码
    • 页游源码
  • 素材资料 ►
    • 电子文档
    • 综合资料
    • 考研资料
    • 设计素材
    • 音频讲座 ►
      • 人文艺术
      • 名师讲座
      • 说书小说
  • 软件工具 ►
    • Windows软件
    • MacOS软件
    • Android软件
  • 寄售资源
    ►
    • 游戏源码
    • 网站源码
    • 软件源码
  • 公益服
×
u3** 刚刚下载了 爆款吸金文案训练

    全网资源·一网打尽

  • 金点出品,必属精品!
  • 发布原创内容,获取高额提成!
  • 我们与你共创美好数字生态!
  • 无特殊说明密码默认:pipbest.com