布隆过滤器（BloomFilter）和布谷鸟过滤器（CuckooFilter）是两种概率型数据结构，用于快速而高效地检查一个元素是否属于一个集合。尽管它们都能够用于这一目的，但在实现细节、性能特点和使用场景上存在不同。布隆过滤器(BloomFilter)布隆过滤器由一个位数组和几个哈希函数组成。添加元素时，会使用这些哈希函数计算多个位置，并将位数组中对应的位置设为1。检查元素是否存在时，如果所有哈希函数计算出来的位置都是1，则认为该元素可能存在；如果任何一个位置是0，则肯定不存在。布隆过滤器存在一定的假阳性率（false-positiverate），即有可能错误地判断一个不存在的元素为存在，但
一、前言在实际开发中，会遇到很多要判断一个元素是否在某个集合中的业务场景，类似于垃圾邮件的识别，恶意ip地址的访问，缓存穿透等情况。类似于缓存穿透这种情况，有许多的解决方法，如：redis存储null值等，而对于垃圾邮件的识别，恶意ip地址的访问，我们也可以直接用HashMap去存储恶意ip地址以及垃圾邮件，然后每次访问时去检索一下对应集合中是否有相同数据。这种思路对于数据量小的项目来说是没有问题的，但是对于大数据量的项目，如，垃圾邮件出现有十几二十万，恶意ip地址出现有上百万，或者从几十亿电话中检索出指定的电话是否在等操作，那么这十几亿的数据就会占据大几G的空间，这个时候就可以考虑一下布隆过
hash原理与应用一、背景知识二、散列表2.1、散列表的构成2.2、hash函数2.3、散列表的操作流程2.4、hash冲突2.5、hash冲突的处理2.6、STLunordered_*散列表的实现2.7、小结三、布隆过滤器(BloomFilter)3.1、背景3.2、布隆过滤器的构成3.3、布隆过滤器原理3.4、应用场景3.5、应用分析3.6、布隆过滤器的实际使用3.7、小结四、分布式一致性hash4.1、背景4.2、一致性hash原理4.3、应用场景4.4、hash偏移4.5、hash迁移4.6、虚拟结点4.7、思维导图五、思考总结一、背景知识在了解hash算法之前，先思考如下问题：使用w
文章目录一、位图1.1一道面试题1.2位图的概念1.3位图的模拟实现1.4位图的应用1.4.1给定100亿个整数，设计算法找到只出现一次的整数1.4.2给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？1.4.31个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数二、布隆过滤器2.1布隆过滤器的提出2.2布隆过滤器的概念2.3布隆过滤器的插入2.4布隆过滤器的查找2.5布隆过滤器的删除2.6布隆过滤器的优点2.7布隆过滤器的缺陷2.8布隆过滤器的实际应用场景三、哈希切分四、结语一、位图1.1一道面试题给40亿个不重复的无符号整数，没排过序。给一
本文已收录至GitHub，推荐阅读👉Java随想录微信公众号：Java随想录原创不易，注重版权。转载请注明原作者和原文链接目录布隆过滤器简介fpp布隆过滤器原理布隆过滤器的特点布隆过滤器使用布隆过滤器中的数据可不可以删除布隆过滤器应该设计为多大布隆过滤器应该使用多少个哈希函数布隆过滤器的时间复杂度和空间复杂度布隆过滤器实现Guava的布隆过滤器的实现BitMap（位图）在日常生活和工作中，我们经常需要处理海量的数据，筛选出有用的信息。这个时候，布隆过滤器（BloomFilter）就派上了用场。作为一种空间高效的概率型数据结构，布隆过滤器能够快速有效地检测一个元素是否属于一个集合。其应用广泛，从
哈希的应用--位图和布隆过滤器位图1.位图概念2.位图在实际中的应用3.位图相似应用给定100亿个整数，如何找到只出现一次的整数？1个文件100亿int，1G内存，如何找到不超过2次的所有整数布隆过滤器1.布隆过滤器的提出2.布隆过滤器的插入3.布隆过滤器的查找4.布隆过滤器的删除5.布隆过滤器的实现6.布隆过滤器优点7.布隆过滤器缺陷8.布隆过滤器的应用位图1.位图概念位图（Bitset）是一种数据结构，用于表示一组布尔值，其中每个元素通常对应于一个位或一个二进制值，可以存储0或1。位图在计算机科学和计算机工程中经常用于各种应用，特别是在位级别的标志、掩码和快速查找中。以下是位图的一些关键特
🌇个人主页：平凡的小苏📚学习格言：命运给你一个低的起点，是想看你精彩的翻盘，而不是让你自甘堕落，脚下的路虽然难走，但我还能走，比起向阳而生，我更想尝试逆风翻盘。🛸C++专栏：C++内功修炼基地>家人们更新不易，你们的👍点赞👍和⭐关注⭐真的对我真重要，各位路过的友友麻烦多多点赞关注。欢迎你们的私信提问，感谢你们的转发！关注我，关注我，关注我，你们将会看到更多的优质内容！！一、位图的概念所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。1、位图的面试题给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个
目录专栏导读一、布隆过滤器BloomFilter是什么二、布隆过滤器BloomFilter能干嘛？三、布隆过滤器使用场景1、解决缓存穿透问题2、黑名单3、网页爬虫对URL的去重，避免爬取相同的URL地址四、操作布隆过滤器BloomFilter1、使用布隆过滤器2、删除key3、判断是否存在五、代码实例1、使用Redis做缓存2、布隆过滤器六、总结大家好，我是哪吒。专栏导读2023年再不会Redis，就要被淘汰了图解Redis，谈谈Redis的持久化，RDB快照与AOF日志Redis单线程还是多线程？IO多路复用原理Redis集群的最大槽数为什么是16384个？Redis缓存穿透、击穿、雪崩到底
一、布隆过滤器可以用来做什么 布隆过滤器可用来判定一个元素是否属于一个集合，比如在一个大的集合A中，是否存在值a。由于hash碰撞(两个不同输入值的hash值相同)的原因，在判定a是否存在于A中时可能会有误判。如果判定结果是a不存在于A中，a肯定是不在A中；如果判定结果是存在，这时可能是因为与a的hash值相同其他元素存在于A中，而a并不存在。 关于布隆过滤器的使用场景，大多是用来判定“是否需要继续执行读取磁盘等效率低的操作”。比如，Google的BitTable和ApachHBase，都使用布隆过滤器判断查询的数据是否存在，来确定是否需要继续读取磁盘。再比如，用爬
