【算法系列 | 7】深入解析查找算法之—布隆过滤器

 

序言

心若有阳光,你便会看见这个世界有那么多美好值得期待和向往。

决定开一个算法专栏,希望能帮助大家很好的了解算法。主要深入解析每个算法,从概念到示例。

我们一起努力,成为更好的自己!

今天第3讲,讲一下排序算法的选择排序(Selection Sort)

1 基础介绍

查找算法是很常见的一类问题,主要是将一组数据按照某种规则进行排序。

以下是一些常见的查找算法及其应用场景:

  1. 布隆过滤器(Bloom Filter):适用于判断一个元素是否存在于一个大规模的数据集中,时间复杂度为O(1),但有一定的误判率。
  2. 二分查找(Binary Search):适用于有序数组中查找元素,时间复杂度为O(log n);
  3. 哈希表查找(Hash Table:适用于快速查找和插入元素,时间复杂度为O(1),但需要额外的存储空间;
  4. 线性查找(Linear Search):适用于无序数组中查找元素,时间复杂度为O(n);
  5. 插值查找(Interpolation Search):适用于有序数组中查找元素,时间复杂度为O(log log n),但是对于分布不均匀的数据集效果不佳;
  6. 斐波那契查找(Fibonacci Search):适用于有序数组中查找元素,时间复杂度为O(log n),但需要额外的存储空间;
  7. 树表查找(Tree Search):适用于快速查找和插入元素,时间复杂度为O(log n),但需要额外的存储空间;
  8. B树查找(B-Tree):适用于大规模数据存储和查找,时间复杂度为O(log n),但需要额外的存储空间;

一、布隆过滤器介绍

1.1 原理介绍

布隆过滤器(Bloom Filter)是一种概率型数据结构,用于快速判断一个元素是否可能存在于一个集合中,同时具有高效的插入和查询操作。它的原理基于位数组和哈希函数。

布隆过滤器的核心是一个位数组(bit array)或称为位向量(bit vector),用于表示元素的存在状态。初始时,所有位都被置为0。

布隆过滤器使用一系列不同的哈希函数(hash functions),这些哈希函数将输入的元素映射为位数组中的不同位置。哈希函数的数量和定义根据具体的应用场景而定,通常会选择一些独立的哈希函数。

插入元素时,将元素经过哈希函数的映射,得到一系列位数组中的位置,然后将这些位置的位设置为1,表示对应的元素存在于布隆过滤器中。

查询元素时,将要查询的元素经过哈希函数的映射,得到一系列位数组中的位置,然后检查这些位置的位是否都为1。

如果有任何一个位置的位为0,则可以确定该元素一定不存在于布隆过滤器中;如果所有位置的位都为1,则该元素可能存在于布隆过滤器中,但不是确定存在。

因此,布隆过滤器的查询结果可能会有误判,即将不存在的元素误判为存在,但不会将存在的元素误判为不存在。

优点

由于布隆过滤器使用位数组和哈希函数,具有以下特点:

  1. 空间效率高:布隆过滤器只需使用位数组存储元素的存在状态,不需要存储元素本身,因此占用的空间相对较小。

  2. 查询效率高:布隆过滤器查询的时间复杂度是常数级别的,与集合中元素的数量无关。

  3. 插入效率高:布隆过滤器插入的时间复杂度也是常数级别的。

缺点

然而,布隆过滤器也存在一些缺点:

  1. 误判率(False Positive):布隆过滤器的查询结果可能会有误判,将不存在的元素误判为存在。

  2. 不支持元素的删除:布隆过滤器的设计目标是快速判断元素的存在性,不支持元素的删除操作。

  3. 难以扩展:一旦布隆过滤器被创建,就很难动态地调整其大小。

总的来说,布隆过滤器适用于对查询效率要求较高、可以容忍一定的误判率以及元素不经常变动的场景,如缓存、防止缓存击穿、爬虫的去重等应用。

图解原理

以下是一个简单的图解布隆过滤器的示意图:

图表示一个初始状态的布隆过滤器,位数组中的所有位都被初始化为0。

 

接下来,我们插入一个元素 "apple" 和 "orange",假设我们选择了三个哈希函数,并且得到的哈希值分别为 1、5 和 7。我们将对应的位设置为1,表示这些位置上的元素存在。

 现在,我们查询元素 "apple" 和 "banana"。根据哈希函数得到的位位置分别为 1、4 和 7。我们检查这些位置上的位,如果其中有任何一个位为0,则可以确定该元素不存在于布隆过滤器中;如果所有位置上的位都为1,则该元素可能存在于布隆过滤器中。

根据图示,我们可以确定 "apple" 可能存在于布隆过滤器中,因为对应的位置上的位都为1。而 "banana" 可能不存在于布隆过滤器中,因为其中一个位置上的位为0。

这就是布隆过滤器的基本原理。

通过使用位数组和哈希函数,布隆过滤器可以快速判断一个元素是否可能存在于一个集合中,具有高效的插入和查询操作。

1.2 复杂度 

布隆过滤器的时间和空间复杂度如下:

时间复杂度:

  • 插入操作的时间复杂度是O(k),其中k是哈希函数的数量。
  • 查询操作的时间复杂度也是O(k)。

空间复杂度:

  • 布隆过滤器的空间复杂度主要取决于位数组的大小和哈希函数的数量。通常情况下,位数组的大小取决于预期的元素数量和期望的误判率。位数组的大小会随着元素数量的增加而增加,以及期望的误判率的降低而增加。

1.3使用场景

布隆过滤器适用于以下场景:

  1. 数据量大,但内存有限:由于布隆过滤器只需要使用位数组来表示元素存在状态,相对于其他数据结构,它具有较小的内存占用。这使得它在内存有限的情况下能够存储大量的元素。

  2. 快速判断元素是否存在:布隆过滤器可以在常数时间内判断一个元素是否可能存在于集合中,无需实际存储元素本身,这使得它具有非常高的查询效率。它可以用于加速对大型数据集或数据库的查询操作。

  3. 容忍一定的误判率:布隆过滤器的查询结果可能会有误判,将不存在的元素误判为存在(即假阳性)。因此,它适用于那些可以容忍一定误判率的应用场景。例如,网页爬虫可以使用布隆过滤器来去重,避免重复爬取相同的网页;缓存系统可以使用布隆过滤器来判断某个数据是否已经缓存,从而避免无谓的IO操作。

  4. 不需要删除操作:布隆过滤器不支持元素的删除操作。一旦元素被插入到布隆过滤器中,就无法删除。因此,它适用于那些不需要频繁删除元素的场景。

需要注意的是,布隆过滤器在某些情况下可能会出现误判,将不存在的元素误判为存在。因此,在一些对准确性要求很高的场景下,布隆过滤器可能不适用。

二、代码实现

2.1 Python 实现

代码示例

import math
import mmh3
from bitarray import bitarrayclass BloomFilter:def __init__(self, num_items, false_positive_rate):self.num_items = num_itemsself.false_positive_rate = false_positive_rateself.bit_array_size = self.calculate_bit_array_size(num_items, false_positive_rate)self.num_hash_functions = self.calculate_num_hash_functions(self.bit_array_size, num_items)self.bit_array = bitarray(self.bit_array_size)self.bit_array.setall(0)def calculate_bit_array_size(self, num_items, false_positive_rate):numerator = num_items * math.log(false_positive_rate)denominator = math.log(2) ** 2return int(-(numerator / denominator))def calculate_num_hash_functions(self, bit_array_size, num_items):numerator = (bit_array_size / num_items) * math.log(2)return int(numerator)def add(self, item):for seed in range(self.num_hash_functions):index = mmh3.hash(item, seed) % self.bit_array_sizeself.bit_array[index] = 1def contains(self, item):for seed in range(self.num_hash_functions):index = mmh3.hash(item, seed) % self.bit_array_sizeif self.bit_array[index] == 0:return Falsereturn True

代码讲解

现在逐行解释代码的各个部分:

  1. 导入所需的模块:代码使用了 math 模块来进行数学计算,mmh3 模块用于实现哈希函数,bitarray 模块用于表示位数组。

  2. BloomFilter 类的初始化方法:在初始化过程中,我们需要指定预期的元素数量 num_items 和期望的误判率 false_positive_rate。根据这两个参数,我们通过调用 calculate_bit_array_size 和 calculate_num_hash_functions 方法来计算位数组的大小和哈希函数的数量。然后,我们创建一个位数组 bit_array,并将所有位初始化为0。

  3. calculate_bit_array_size 方法:根据预期元素数量和期望的误判率,使用公式 -num_items * log(false_positive_rate) / (log(2) ** 2) 计算位数组的大小,并将结果转换为整数。

  4. calculate_num_hash_functions 方法:根据位数组的大小和预期元素数量,使用公式 (bit_array_size / num_items) * log(2) 计算哈希函数的数量,并将结果转换为整数。

  5. add 方法:用于向布隆过滤器中添加元素。对于每个元素,我们使用不同的种子值(从0到num_hash_functions-1)来计算哈希值,并将对应的位数组位置设置为1。

  6. contains 方法:用于检查元素是否存在于布隆过滤器中。对于每个元素,我们使用与添加操作相同的种子值来计算哈希值,并检查对应的位数组位置。如果任何一个位置上的位为0,则可以确定元素不存在于布隆过滤器中;否则,我们认为元素可能存在于布隆过滤器中。

这就是一个简单的布隆过滤器的 Python 实现。你可以根据自己的需求进行调整和扩展。请注意,这个实现中并没有考虑动态调整布隆过滤器大小或删除元素的功能。

测试代码

import randomdef generate_random_string(length):letters = "abcdefghijklmnopqrstuvwxyz"return ''.join(random.choice(letters) for _ in range(length))num_items = 1000
false_positive_rate = 0.01bloom_filter = BloomFilter(num_items, false_positive_rate)# 添加元素
for _ in range(num_items):item = generate_random_string(10)bloom_filter.add(item)# 检查元素是否存在
positive_count = 0
for _ in range(1000):item = generate_random_string(10)if bloom_filter.contains(item):positive_count += 1false_positive_rate_actual = positive_count / 1000
print("实际误判率:", false_positive_rate_actual)

我们首先定义了预期的元素数量 num_items 和期望的误判率 false_positive_rate。然后,我们创建了一个 BloomFilter 实例并使用 add 方法向布隆过滤器中添加了随机生成的元素。

接下来,我们使用 contains 方法进行随机测试。我们随机生成了1000个字符串,并检查它们是否存在于布隆过滤器中。我们计算了实际的误判率,即在这1000个随机字符串中错误判断为存在的比例,并将其打印出来。

测试结果会输出一个实际的误判率,应该接近于设定的期望误判率。

请注意,由于布隆过滤器的特性,即使在没有添加的情况下,也可能会有一定的误判率。因此,实际误判率可能略高于设定的期望误判率。

运行结果

实际误判率: 0.009

2.2Java实现

代码示例

import java.util.BitSet;
import java.util.Random;public class BloomFilter {private BitSet bitSet;private int size;private int numHashFunctions;private Random random;public BloomFilter(int expectedNumItems, double falsePositiveRate) {size = calculateBitSetSize(expectedNumItems, falsePositiveRate);numHashFunctions = calculateNumHashFunctions(size, expectedNumItems);bitSet = new BitSet(size);random = new Random();}public void add(String item) {for (int i = 0; i < numHashFunctions; i++) {int hash = hash(item, i);bitSet.set(hash, true);}}public boolean contains(String item) {for (int i = 0; i < numHashFunctions; i++) {int hash = hash(item, i);if (!bitSet.get(hash)) {return false;}}return true;}private int hash(String item, int seed) {random.setSeed(seed);return Math.abs(random.nextInt()) % size;}private int calculateBitSetSize(int expectedNumItems, double falsePositiveRate) {int size = (int) Math.ceil((expectedNumItems * Math.log(falsePositiveRate)) / Math.log(1.0 / (Math.pow(2.0, Math.log(2.0)))));return size;}private int calculateNumHashFunctions(int size, int expectedNumItems) {int numHashes = (int) Math.ceil((size / expectedNumItems) * Math.log(2.0));return numHashes;}
}

代码讲解

解释一下以上代码的各个部分:

  • BloomFilter 类的构造函数:在构造函数中,我们传入预期的元素数量 expectedNumItems 和期望的误判率 falsePositiveRate。然后,我们使用 calculateBitSetSize 和 calculateNumHashFunctions 方法计算位集合的大小和哈希函数的数量。接着,我们创建一个位集合 bitSet,并初始化一个 Random 对象。

  • add 方法:用于向布隆过滤器中添加元素。对于每个元素,我们使用不同的种子值(从0到numHashFunctions-1)来计算哈希值,并将对应的位设置为1。

  • contains 方法:用于检查元素是否存在于布隆过滤器中。对于每个元素,我们使用与添加操作相同的种子值来计算哈希值,并检查对应的位是否为1。如果任何一个位为0,则可以确定元素不存在于布隆过滤器中;否则,我们认为元素可能存在于布隆过滤器中。

  • hash 方法:用于计算哈希值。我们使用种子值作为随机数种子,并使用 Random 对象生成一个哈希值。然后,我们对哈希值取绝对值,并对位集合大小取模,以确保哈希值在位集合范围内。

  • calculateBitSetSize 方法:根据预期元素数量和期望的误判率,使用公式 (expectedNumItems * log(falsePositiveRate)) / log(1.0 / (Math.pow(2.0, Math.log(2.0)))) 计算位集合的大小,并返回结果。

  • calculateNumHashFunctions 方法:根据位集合的大小和预期元素数量,使用公式 (size / expectedNumItems) * log(2.0) 计算哈希函数的数量,并返回结果。

这是一个简单的布隆过滤器的 Java 实现。你可以根据自己的需求进行调整和扩展。注意,这个实现中没有考虑动态调整布隆过滤器大小或删除元素的功能。

测试代码

public class Main {public static void main(String[] args) {int expectedNumItems = 1000;double falsePositiveRate = 0.01;BloomFilter bloomFilter = new BloomFilter(expectedNumItems, falsePositiveRate);// 添加元素bloomFilter.add("apple");bloomFilter.add("banana");bloomFilter.add("orange");// 检查元素是否存在System.out.println(bloomFilter.contains("apple"));   // 输出: trueSystem.out.println(bloomFilter.contains("banana"));  // 输出: trueSystem.out.println(bloomFilter.contains("orange"));  // 输出: trueSystem.out.println(bloomFilter.contains("grape"));   // 输出: falseSystem.out.println(bloomFilter.contains("melon"));   // 输出: false}
}

运行结果

true
true
true
false
false

三、图书推荐

图书名称:

  • 《漫画算法:小灰的算法之旅》

图书介绍

 

本书是《漫画算法:小灰的算法之旅》的续作,通过主人公小灰的心路历程,用漫画的形式讲述了多个数据结构、算法及复杂多变的算法面试题目。

第1章介绍了几种典型的排序算法,包括选择排序、插入排序、希尔排序、归并排序、基数排序。

第2章介绍了“树”结构的高级应用,包括二叉查找树、AVL树、红黑树、B树和B+树。

第3章介绍了“图”结构的概念,以及深度优先遍历、广度优先遍历、单源最短路径、多源最短路径算法。

第4章介绍了“查找”相关的算法和数据结构,包括二分查找算法、RK算法、KMP算法,以及“跳表”这种用于高效查找的数据结构。

第5章介绍了多种职场上流行的算法面试题目及详细的解题思路,例如螺旋遍历二维数组、寻找数组中第k大元素、求股票交易的更大收益等。

等不及的小伙伴,可以点击下方链接,先睹为快:漫画算法2

 参与方式 

图书数量:本次送出 4 本   !!!⭐️⭐️⭐️
活动时间:截止到 2023-08-11 12:00:00

抽奖方式:

  • 评论区随机抽取小伙伴!

留言内容,以下方式都可以:

  • 根据文章内容进行高质量评论

参与方式:关注博主、点赞、收藏,评论区留言 

中奖名单 

🍓🍓 获奖名单🍓🍓

 中奖名单:请关注博主动态

名单公布时间:2023-08-11 下午

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/79784.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【数据结构】链表(一)

链表&#xff08;一&#xff09; 文章目录 链表&#xff08;一&#xff09;01 引入02 概念及结构03 单向不带头不循环链表实现3.1 创建节点类型3.2 简易创建一个链表3.3 遍历链表每个节点3.4 获取链表长度3.5 查找是否包含关键字key是否在单链表当中3.6 头插法3.7 尾插法3.8 任…

MySQL 重置root 密码

5.7 版本 首先要把服务mysql57 关闭 net stop MySQL57 在安装的mysql57的程序的bin中 运行cmd&#xff08;管理员运行&#xff09; mysqld --defaults-file‘mysql存放数据的位置\my.ini’ --skip-grant-tables 上图 错误 注意&#xff1a;如果遇到mysqld: Can’t change dir…

【从零学习python 】02. 开发工具介绍

文章目录 编写Python代码一、常见的代码编辑工具二、运行Python程序三、Pycharm的下载和安装PyCharm的主要功能区域进阶案例 编写Python代码 根据我们之前介绍的知识&#xff0c;我们知道&#xff0c;所谓代码其实就是将一段普通文本按照一定的规范编写&#xff0c;然后交给电…

Cesium 加载ArcGIS Server切片服务错级问题

1.首先上官方api说明 ArcGisMapServerImageryProvider - Cesium Documentation 里面没有 zoomoffset参数!!! 2.如果按照互联网栅格切片规则 3857、4326、4490常用切片层级参数,则直接加载显示地图 viewer.imageryLayers.addImageryProvider(new Cesium.ArcGisMapServerI…

【Spring Boot】(三)深入理解 Spring Boot 日志

文章目录 前言一、日志文件的作用二、Spring Boot 中的日志2.1 查看输出的日志信息2.2 日志格式二、Spring Boot 中的日志2.1 查看输出的日志信息2.2 日志格式 三、自定义日志输出3.1 日志框架3.2 日志对象的获取3.3 使用日志对象打印日志 四、日志级别4.1 日志级别的作用4.2 日…

Oracle-expdp报错ORA-39077、06502(Bug-16928674)

问题: 用户在使用expdp进程导出时&#xff0c;出现队列报错ORA-39077、ORA-06502 ORA-31626: job does not exist ORA-31638: cannot attach to job SYS_EXPORT_SCHEMA_01 for user SYS ORA-06512: at "SYS.DBMS_SYS_ERROR", line 95 ORA-06512: at "SYS.KUPV$…

【修正-高斯拉普拉斯滤波器-用于平滑和去噪】基于修正高斯滤波拉普拉斯地震到达时间自动检测研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

解密HTTP代理爬虫中的IP代理选择与管理策略

在当今数据驱动的世界中&#xff0c;HTTP代理爬虫作为一项重要的数据采集工具&#xff0c;其成功与否往往取决于IP代理的选择与管理策略。作为一家专业的HTTP代理产品供应商&#xff0c;我们深知IP代理在数据采集中的重要性。在本文中&#xff0c;我们将分享一些关于HTTP代理爬…

图像膨胀+滤波达到边缘外扩模糊效果

有一个扯淡需求, 根据某些格网值渲染对应的颜色, 我们做的实现方案是按照色代码渐变做颜色映射, 但是某些厂家不顾结果正确性与否, 应是为了好看做的好看, 将边界膨胀模糊, 一个非风场,力场类似场数据做了一个类似场的渲染效果, 也不知道说啥好, 例如原始图渲染如下 经过一系列…

Spring Boot配置文件与日志文件

1. Spring Boot 配置文件 我们知道, 当我们创建一个Spring Boot项目之后, 就已经有了配置文件存在于目录结构中. 1. 配置文件作用 整个项目中所有重要的数据都是在配置文件中配置的&#xff0c;比如: 数据库的连接信息 (包含用户名和密码的设置) ;项目的启动端口;第三方系统的调…

资深测试总结,Web自动化测试POM设计模式封装框架,看这篇就够了...

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 线性脚本 import…

ParallelCollectionRDD [0] isEmpty at KyuubiSparkUtil.scala:48问题解决

ParallelCollectionRDD [0] isEmpty at KyuubiSparkUtil.scala:48问题解决 这个问题出现在使用Kyubi Spark Util处理ParallelCollectionRDD的过程中&#xff0c;具体是在KyubiSparkUtil.scala文件的第48行调用isEmpty方法时出现的。该问题可能是由以下几个原因引起的&#xff1…

FFmpeg将编码后数据保存成mp4

以下测试代码实现的功能是&#xff1a;持续从内存块中获取原始数据&#xff0c;然后依次进行解码、编码、最后保存成mp4视频文件。 可保存成单个视频文件&#xff0c;也可指定每个视频文件的总帧数&#xff0c;保存多个视频文件。 为了便于查看和修改&#xff0c;这里将可独立的…

[CKA]考试之检查可用节点数量

由于最新的CKA考试改版&#xff0c;不允许存储书签&#xff0c;本博客致力怎么一步步从官网把答案找到&#xff0c;如何修改把题做对&#xff0c;下面开始我们的 CKA之旅 题目为&#xff1a; Task 检查集群中有多少节点为Ready状态&#xff08;不包括被打上 Taint&#xff1…

FPGA学习——Altera IP核调用之PLL篇

文章目录 一、IP核1.1 IP核简介1.2 FPGA中IP核的分类1.3 IP核的缺陷 二、PLL简介2.1 什么是PLL2.2 PLL结构图2.3 C4开发板上PLL的位置 三、IP核调用步骤四、编写测试代码五、总结 一、IP核 1.1 IP核简介 IP核&#xff08;知识产权核&#xff09;&#xff0c;是在集成电路的可…

视频监控汇聚平台EasyCVR视频分享页面WebRTC流地址播放不了是什么原因?

开源EasyDarwin视频监控TSINGSEE青犀视频平台EasyCVR能在复杂的网络环境中&#xff0c;将分散的各类视频资源进行统一汇聚、整合、集中管理&#xff0c;在视频监控播放上&#xff0c;TSINGSEE青犀视频安防监控汇聚平台可支持1、4、9、16个画面窗口播放&#xff0c;可同时播放多…

机器学习笔记之优化算法(八)简单认识Wolfe Condition的收敛性证明

机器学习笔记之优化算法——简单认识Wolfe Condition收敛性证明 引言回顾&#xff1a; Wolfe \text{Wolfe} Wolfe准则准备工作推导条件介绍推导结论介绍 关于 Wolfe \text{Wolfe} Wolfe准则收敛性证明的推导过程 引言 上一节介绍了非精确搜索方法—— Wolfe \text{Wolfe} Wolf…

【Python】从同步到异步多核:测试桩性能优化,加速应用的开发和验证

目录 测试工作中常用到的测试桩mock能力 应用场景 简单测试桩 http.server扩展&#xff1a;一行命令实现一个静态文件服务器 性能优化&#xff1a;使用异步响应 异步响应 能优化&#xff1a;利用多核 gunicorn 安装 gunicorn 使用 gunicorn 启动服务 性能优化&#…

linuxARM裸机学习笔记(2)----汇编LED灯实验

MX6ULL 的 IO IO的复用功能 这里的只使用了低五位&#xff0c;用来配置io口&#xff0c;其中bit0~bit3(MUX_MODE)就是设置 GPIO1_IO00 的复用功能的&#xff0c;GPIO1_IO00 一共可以复用为 9种功能 IO&#xff0c;分别对应 ALT0~ALT8。每种对应了不同的功能 io的属性配置 HY…

MATLAB(R2023a)添加工具箱TooLbox的方法-以GPOPS为例

一、找到工具箱存放位置 首先我们需要找到工具箱的存放位置&#xff0c;点击这个设置路径可以看到 我们的matlab工具箱的存放位置 C:\Program Files\MATLAB\R2023a\toolbox\matlab 从资源管理器中打开这个位置&#xff0c;可以看到里面各种工具箱 二、放入工具箱 解压我们…