自己手写一个BloomFilter

2024-06-02 09:18
文章标签 手写 bloomfilter

本文主要是介绍自己手写一个BloomFilter,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1.什么是BloomFilter  布隆过滤器

     布隆过滤器用于判断一个元素是否在一个集合中,它有一定的误判率,不存在的元素,一定不存在。存在的不一定真的存在,
它使用的是数组,它的空间效率是一般算法的1/8左右

2.BloomFilter 的核心思想是什么?
     布隆过滤器的核心思想:
     add 操作: 计算k个hash函数的值,把对应的结果映射到位数组上,将相应的位数组上的值值为1
     contain 操作: 计算k个hash函数的值,判断k个所有的值是否都为1,如果都为1,返回true,如果有一个不等于0 则返回false

自己的实现

/*** @ClassName: MyBloomFilter* @Description: 布隆过滤器用于判断一个元素是否在一个集合中,它有一定的误判率,4* 不存在的元素,一定不存在。存在的不一定真的存在,* 它使用的是数组,它的空间效率是一般算法的1/8左右*  布隆过滤器的核心思想:*  add 操作: 计算k个hash函数的值,把对应的结果映射到位数组上,将相应的位数组上的值值为1*  contain 操作: 计算k个hash函数的值,判断k个所有的值是否都为1,如果都为1,返回true,如果有一个不等于0 则返回false*  参考:*  1.https://www.bilibili.com/video/BV1n5411s7Wb?from=search&seid=7498069184359593981*  2.https://www.cnblogs.com/xiaobaituyun/p/11011393.html* @Author: fuGuoWen* @Date: 2020/5/30 22:36* @Version: v1.0 文件初始创建*/
public class MyBloomFilter {private byte[] data;private int[] slots;/** 初始化容器的大小 */public MyBloomFilter(int num) {this.data = new byte[num*2];slots=new int[3];}/*** @Description: 把对应的元素添加待BloomFilter ** @Date: 2020/5/30 22:50* @Author: fuguowen* @Return * @Throws */public void add(Integer key){/** 计算hash1的函数取模以后的桶为 */int location1 = Math.abs(hash1(key) % data.length);/** 计算hash2的函数取模以后的桶为 */int location2 = Math.abs(hash2(key) % data.length);/** 计算hash3的函数取模以后的桶为 */int location3 = Math.abs(hash3(key) % data.length);/** 把对应的hash函数的桶位置为1 */data[location1]=1;data[location2]=1;data[location3]=1;}/*** @Description: 判断一个元素是否在布隆过滤器中** @Date: 2020/5/30 22:28* @Author: fuGuoWen* @Return java.lang.Boolean  true:在布隆过滤器中  false: 不在布隆过滤器中 * @Throws*/public Boolean contain(Integer key){int location1 = Math.abs(hash1(key) % data.length);int location2 = Math.abs(hash2(key) % data.length);int location3 = Math.abs(hash3(key) % data.length);/** 只要有一个元素部位1,计算结果为0,返回false,否则 计算结果为1,返回true */return data[location1]*data[location2]*data[location3]==1;}/*** @Description: hash1 计算key的hash 值** @Date: 2020/5/30 22:49* @Author: fuGuoWen* @Return * @Throws */public int hash1(Integer key){return key.hashCode();}/*** @Description: hash2 计算key的hash 值* @Date: 2020/5/30 22:49* @Author: fuGuoWen* @Return* @Throws*/public int hash2(Integer key){return key.hashCode()^(key.hashCode() >>>3);}/*** @Description: hash3 计算key的hash 值** @Date: 2020/5/30 22:49* @Author: fuGuoWen* @Return* @Throws*/public int hash3(Integer key){return key.hashCode()^(key.hashCode() >>>16);}}

参考:
1.https://www.bilibili.com/video/BV1n5411s7Wb?from=search&seid=7498069184359593981
2.https://www.cnblogs.com/xiaobaituyun/p/11011393.html

这篇关于自己手写一个BloomFilter的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1023555

相关文章

stl的sort和手写快排的运行效率哪个比较高?

STL的sort必然要比你自己写的快排要快,因为你自己手写一个这么复杂的sort,那就太闲了。STL的sort是尽量让复杂度维持在O(N log N)的,因此就有了各种的Hybrid sort algorithm。 题主你提到的先quicksort到一定深度之后就转为heapsort,这种是introsort。 每种STL实现使用的算法各有不同,GNU Standard C++ Lib

JS手写实现深拷贝

手写深拷贝 一、通过JSON.stringify二、函数库lodash三、递归实现深拷贝基础递归升级版递归---解决环引用爆栈问题最终版递归---解决其余类型拷贝结果 一、通过JSON.stringify JSON.parse(JSON.stringify(obj))是比较常用的深拷贝方法之一 原理:利用JSON.stringify 将JavaScript对象序列化成为JSO

T1打卡——mnist手写数字识别

🍨 本文为🔗365天深度学习训练营中的学习记录博客🍖 原作者:K同学啊 1.定义GPU import tensorflow as tfgpus=tf.config.list_physical_devices("GPU")if gpus:gpu0=gpus[0]tf.config.experimental.set_memort_groth(gpu0,True) #设置GPU现存用量按需

【DL--22】实现神经网络算法NeuralNetwork以及手写数字识别

1.NeuralNetwork.py #coding:utf-8import numpy as np#定义双曲函数和他们的导数def tanh(x):return np.tanh(x)def tanh_deriv(x):return 1.0 - np.tanh(x)**2def logistic(x):return 1/(1 + np.exp(-x))def logistic_derivati

【tensorflow CNN】构建cnn网络,识别mnist手写数字识别

#coding:utf8"""构建cnn网络,识别mnistinput conv1 padding max_pool([2,2],strides=[2,2]) conv2 x[-1,28,28,1] 卷积 [5,5,1,32] -> [-1,24,24,32]->[-1,28,

【tensorflow 全连接神经网络】 minist 手写数字识别

主要内容: 使用tensorflow构建一个三层全连接传统神经网络,作为字符识别的多分类器。通过字符图片预测对应的数字,对mnist数据集进行预测。 # coding: utf-8from tensorflow.examples.tutorials.mnist import input_dataimport tensorflow as tfimport matplotlib.pyplot

微信小程序手写签名

微信小程序手写签名组件 该组件基于signature_pad封装,signature_pad本身是web端的插件,此处将插件代码修改为小程序端可用。 signature_pad.js /*!* Signature Pad v5.0.3 | https://github.com/szimek/signature_pad* (c) 2024 Szymon Nowak | Released

手写全排列(递归 | 非递归)

博客搬家:最爱午后红茶 以下内容转自:点击打开链接 用C++写一个函数, 如 Foo(const char *str), 打印出 str 的全排列,  如 abc 的全排列: abc, acb, bca, dac, cab, cba 一.全排列的递归实现 为方便起见,用123来示例下。123的全排列有123、132、213、231、312、321这六种。首先考虑213和321这

《西瓜书》第三章 线性模型 手写版笔记

《西瓜书》第三章 线性模型 手写版笔记 文章目录 《西瓜书》第三章 线性模型 手写版笔记3.0 知识点总览3.1 线性回归(Linear Regression)求解的推导过程3.1.1 单变量线性回归3.1.2 多变量线性回归3.1.3 对数线性回归 3.2 逻辑回归(Logistic Regression)3.3 线性判别(LDA)3.4 多分类学习的拆分策略3.5 处理类别不平衡问题三

手写服务器httpserver_xml配置文件_sax解析基础应用JAVA205-206

来源:http://www.bjsxt.com/ 一、S02E205_01手写服务器httpserver_xml配置文件_sax解析基础 XML package com.test.xml;import java.io.IOException;import java.util.List;import javax.xml.parsers.ParserConfigurationExcepti