bitmap和布隆过滤区别bitmap和布隆过滤器

Adam 2023年10月25日 14:42 0

大家好,今天小编来为大家解答以下的问题，关于bitmap和布隆过滤区别，bitmap和布隆过滤器这个很多人还不知道，现在让我们一起来看看吧！

本文目录

bitmap和布隆过滤器的区别布隆过滤器详解5、垃圾回收机制布隆过滤器bitmap和布隆过滤器的区别bitmap更适合用于数字比较。

比如比较两个数组是否有重叠，我们把第一个数组中的1,2,5,7,11分别映射到bitmap位置中

布隆过滤器适合非数字比较（有误判）

布隆过滤器详解布隆过滤器（英语：BloomFilter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。主要用于判断一个元素是否在一个集合中。

通常我们会遇到很多要判断一个元素是否在某个集合中的业务场景，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hashtable）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间也会呈现线性增长，最终达到瓶颈。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为，，。

这个时候，布隆过滤器（BloomFilter）就应运而生。

了解布隆过滤器原理之前，先回顾下Hash函数原理。

哈希函数的概念是：将任意大小的输入数据转换成特定大小的输出数据的函数，转换后的数据称为哈希值或哈希编码，也叫散列值。下面是一幅示意图：

所有散列函数都有如下基本特性：

但是用hash表存储大数据量时，空间效率还是很低，当只有一个hash函数时，还很容易发生哈希碰撞。

BloomFilter是由一个固定大小的二进制向量或者位图（bitmap）和一系列映射函数组成的。

在初始状态时，对于长度为m的位数组，它的所有位都被置为0，如下图所示：

当有变量被加入集合时，通过K个映射函数将这个变量映射成位图中的K个点，把它们置为1（假定有两个变量都通过3个映射函数）。

查询某个变量的时候我们只要看看这些点是不是都是1就可以大概率知道集合中有没有它了

为什么说是可能存在，而不是一定存在呢？那是因为映射函数本身就是散列函数，散列函数是会有碰撞的。

布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了，这样就无法判断究竟是哪个输入产生的，因此误判的根源在于相同的bit位被多次映射且置1。

这种情况也造成了布隆过滤器的删除问题，因为布隆过滤器的每一个bit并不是独占的，很有可能多个元素共享了某一位。如果我们直接删除这一位的话，会影响其他的元素。(比如上图中的第3位)

相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数，另外，散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。

布隆过滤器可以表示全集，其它任何数据结构都不能；

但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。

另外，一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组，每插入一个元素相应的计数器加1,这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

在降低误算率方面，有不少工作，使得出现了很多布隆过滤器的变种。

在程序的世界中，布隆过滤器是程序员的一把利器，利用它可以快速地解决项目中一些比较棘手的问题。

如网页URL去重、垃圾邮件识别、大集合中重复元素的判断和缓存穿透等问题。

布隆过滤器的典型应用有：

知道了布隆过滤去的原理和使用场景，我们可以自己实现一个简单的布隆过滤器

分布式环境中，布隆过滤器肯定还需要考虑是可以共享的资源，这时候我们会想到Redis，是的，Redis也实现了布隆过滤器。

当然我们也可以把布隆过滤器通过bloomFilter.writeTo()写入一个文件，放入OSS、S3这类对象存储中。

Redis提供的bitMap可以实现布隆过滤器，但是需要自己设计映射函数和一些细节，这和我们自定义没啥区别。

Redis官方提供的布隆过滤器到了Redis4.0提供了插件功能之后才正式登场。布隆过滤器作为一个插件加载到RedisServer中，给Redis提供了强大的布隆去重功能。

在已安装Redis的前提下，安装RedisBloom，有两种方式

直接编译进行安装

使用Docker进行安装

使用

布隆过滤器基本指令：

我们只有这几个参数，肯定不会有误判，当元素逐渐增多时，就会有一定的误判了，这里就不做这个实验了。

上面使用的布隆过滤器只是默认参数的布隆过滤器，它在我们第一次add的时候自动创建。

Redis还提供了自定义参数的布隆过滤器，bf.reserve过滤器名error_rateinitial_size

但是这个操作需要在add之前显式创建。如果对应的key已经存在，bf.reserve会报错

我是一名Javaer，肯定还要用Java来实现的，Java的Redis客户端比较多，有些还没有提供指令扩展机制，笔者已知的Redisson和lettuce是可以使用布隆过滤器的，我们这里用Redisson

为了解决布隆过滤器不能删除元素的问题，布谷鸟过滤器横空出世。论文《CuckooFilter：BetterThanBloom》作者将布谷鸟过滤器和布隆过滤器进行了深入的对比。相比布谷鸟过滤器而言布隆过滤器有以下不足：查询性能弱、空间利用效率低、不支持反向操作（删除）以及不支持计数。

由于使用较少，暂不深入。

https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf

http://www.justdojava.com/2019/10/22/bloomfilter/

https://www.cnblogs.com/cpselvis/p/6265825.html

https://juejin.im/post/5cc5aa7ce51d456e431adac5

5、垃圾回收机制JVM的垃圾回收机制主要涉及三个方面的问题：

1.JVM有哪些垃圾回收算法？各自有什么优势？

2.CMS垃圾回收器是如何工作的？有哪些阶段？

3.服务卡顿的元凶到底是什么？

Java不用程序来管理内存的回收，但这些内存是如何回收的？

其实，JVM有专门的线程在做这件事情。当内容空间达到一定条件时，会自动触发，这个过程就叫GC，负责GC的组件被称为垃圾回收器。JVM规范没有规定垃圾回收器怎么实现，它只需要保证不要把正在使用的对象回收掉就可以。在现在的服务器环境中，经常被使用的垃圾回收器有CMS和G1，但JVM还有其它几个常见的垃圾回收器。

GC的过程是先找到活跃的对象，然后把其他不活跃的对象判定为垃圾，然后删除，所以GC只与活跃的对象有关，和堆的大小无关。

接下来学习下分代垃圾回收的内存划分和GC过程，再有就是常见的垃圾回收

4月13美股交易吗

器。

这篇比较重要，因为几乎所有的垃圾回收器都是在这些基本思想上演化出来的。

GC的第一步就是找出活跃的对象，根据GCRoots遍历所有的可达对象，这个过程就叫作标记。

如上图所示，圆圈代表对象，绿色的代表GCRoots，红色的代表可以追溯到的对象，标记后，有多个灰色的圆圈，代表都是可被回收的对象

新手如何炒虚拟货币

。

清除阶段就是把未被标记的对象回收掉。

这种方式有一个明显的问题，会产生碎片空间。

比如申请了1k、2k、3k、4k、5k的内存

由于某些原因，2k和4k的内存不再使用，交给垃圾回收器回收。

解决碎片问题，就需要进行内存整理。

有一个思路就是提送一个对等的内存空间，将存活的对象复制过去，然后清除员内存空间。

在程序设计时，一般遇到扩缩容或者碎片整理问题时，复制算法都是非常有效的。比如：HashMap的扩容使用的是同样的思路，Redis的rehash也是如此。

整个过程如下图

这种方式看似完美，解决了碎片问题，但是弊端也非常明显，它浪费了一半的内存空间来做这个事情，如果原本资源就有限，这就是一种无法容忍的浪费。

不用分配一个对等的空间也是可以完成内存的整理工作。

可以把内存想象成一个非常大的数组，根据随机的index删除了一些数据，那么对数组的清理不需要另外一个数组来进行支持的，使用程序就可以。

主要思路是移动所有的存活对象，且按照内存地址顺序依次排列，然后将末端内存地址以后的内存全部收回。

对象的引用关系一般是非常复杂的，从效率上来说，一般整理算法是要低于复制算法的。

JVM的垃圾回收器，都是对以上几种朴素算法的结合使用，简单看一下它们的特点：

效率一般，缺点是回造成内存碎片的问题。

复制算法是所有算法里面效率最高的，缺点是造成一定的空间浪费。

效率比前两者要差，但没有空间浪费，也消除了内存碎片问题。

所以没有最优的算法，只有最合适的算法。

JVM是计算节点，而不是存储节点。最理想的情况就是对象使用完成之后，它的生命周期立马就结束了，而那些被频繁访问的资源，我们希望它能够常驻在内存里。

对象大致可以分为两类：

1.大部分对象的生命周期都很短

2.其他对象则很可能会存活很长时间

现在的垃圾回收器都会在物理上或者逻辑上，把这两类对象进行分区。我们把死的快的对象所占的区域叫年轻代（YoungGeneration）。把其他活的长的对象所占的区域叫作老年代（OldGeneration），老年代在有时候会叫作TenuredGeneration。

年轻代使用的垃圾回收算法是复制算法，因为年轻代发生GC后，会有非常少的对象存活，复制这部分对象是非常高效的

年轻代的内部分区

如图所示，年轻代分为：一个伊甸园空间（Eden），两个幸存者空间（Survivor）。

当年轻代中的Eden区分配满的时候，就会触发年轻代的GC（MinorGC），具体过程如下

1.在Eden区执行了第一次GC之后，存活的对象会被移动到其中一个Suvivor分区（from）；

2.Eden区再次GC，这是会采用复制算法，将Eden和from区一起清理，存活的对象会被复制到to区；接下来只需要清空from区就可以了

在整个过程中总会有一个Survivor分区是空置的。Eden、from、to的默认比例是8:1:1,所以只会造成10%的空间浪费。

这个比例是由参数-XX:SurvivorRatio进行配置的（默认为8）。

补充下不常提到的TLAB。TLAB全称是ThreadLocalAllocationBuffer，JVM默认给每个线程开辟一个buffer区域，用来加速对象分配。这个buffer就放在Eden区中。

这个道理和Java语言中的ThreadLocal类似，避免了对公共区的操作，以及一些锁竞争。

老年代一般使用"标记-清除"、"标记-整理"算法。因为老年代的对象存活率一般是比较高的，空间又比较大，拷贝起来并不划算，不如采取就地收集的方式。

对象进入老年代的途径分类

如果对象够老，会通过"提升"进入老年代。关于对象老不老，是通过它的年龄来判断的。每发生一次MinorGC，存活下来的对象年龄都会加1,直到达到一定的阀值，就会提升到老年代，

这些对象如果变的不可达，直到老年代发生GC的时候才会被清理掉。

这个阀值可以通过参数-XX:+MaxTenuringThreshold进行配置，最大值是15，因为它是用4bit存储的（所以把这个值调的很大的文章，是没有什么根据的）。

每次存活的对象，都会放入其中一个幸存区，这个区域默认比例是10%，但无法保证每次存活的对象都小于10%，当Survivor空间不够，就需要依赖其它内存（老年代）进行分配担保。这个时候，对象也会直接在老年代上分配。

超出某个大小的对象直接在老年代分配，通过参数设置-XX:PretenureSizeThreshold进行配置的，默认为0，默认全部在Eden区进行分配。

有的垃圾回收算法，并不要求age必须达到15才能晋升到老年代，它会使用一些动态的计算方法。比如，如果幸存区中相同年龄对象大小的和，大于幸存区的一半，大于或者等于age的对象将会直接进入老年代。

这些动态判定一半不受外部控制

对象的引用关系时一个巨大的网状，有的对象在Eden区，有的可能在老年代，那么这种跨代的引用是如何处理的呢？由于MinorGC是单独发生的，如果一个老年代的对象引用了它，如何确保能够让年轻代的对象存活呢？

对于是、否的判断，我们通常都会用到Bitmap（位图）和布隆过滤器来加快搜索的速度，需要另外再学习下（如果不知道这两个概念的话）

JVM也是用了类似的方法。其实，老年代是被分成众多的卡页（CardPage）的（一般数量是2的次幂）

卡表（CardTable）就是用于标记卡页状态的一个集合，每个卡表对应一个卡页。

如果年轻代有对象分配，而且老年代有对象指向这个新对象，那么这个老年代对象所对应内存的卡页就会被标识为dirty，卡表只需要非常小的存储空间就可以保留这些状态，垃圾回收时，就可以先读这个卡表，进行快速的判断。

接下来学习HotSpot的几个垃圾回收器，每种回收器都有各自的特点。在平常的GC优化时，一定要清楚现在用的是那种垃圾回收器。

下图包含了年轻代和老年代的划分，方便接下来的学习参考

处理GC的只有一条线程，并且在垃圾回收的过程中暂停一切用户线程。

这是最简单的垃圾回收器，虽然简单，但十分高效，通常用在客户端应用上。因为客户端应用不会频繁创建很多对象，用户也不会感觉出明显的卡顿。相反，它使用的资源更少，也更轻量级。

ParNew是Serial的多线程版本，由多条GC线程并行地进行垃圾清理。清理过程依然要停止用户线程。追求低停顿时间，与Serial唯一区别就是使用了多线程进行垃圾回收，在多CPU环境下性能比Serial会有一定程度的提升；但线程切换需要额外的开销，因此在单CPU环境中表现不如Serial。

另一个多线程版本的垃圾回收器。但与ParNew是有区别的

1.ParallelScavenge:追求CPU吞吐量，能够在较短时间内完成指定任务，适合没有交互的后台计算，弱交互强计算。

2.ParNew:追求降低用户停顿时间，适合交互式应用，强交互弱计算。

与年轻代的Serial垃圾回收器对应，都是单线程版本，同样适合客户端使用。

年轻代Serial，使用复制算法。

老年代的OldSerial，使用标记-整理算法。

ParallelOld回收器是ParallelScavenge的老年代版本，追求CPU吞吐量。

CMS(ConcurrentMarkSweep)回收器是以获取最短GC停顿时间为目标的收集器，它在垃圾回收时使得用户线程和GC线程能够并发执行，因此在垃圾回收过程中用户也不会感到明显的卡顿。

长期看来，CMS垃圾回收器，是要被G1等垃圾回收器替换掉的，在Java8之后，使用它将会抛出一个警告！

除了上面几个垃圾回收器，我们还有G1、ZGC等更加高级的垃圾回收器，它们都有专门的配置参数来使其生效。

通过-XX：PrintCommandLineFlags参数，可以查看当前Java版本默认使用的垃圾回收器。在Java13中，默认的回收器就是G1。

以下是一些配置参数：

1.-XX:+UseSerialGC年轻代和年老代回收器

2.-XX:+UseParNewGC年轻代使用ParNew，老年代使用SerialOld。

3.-XX:+UseParallelOldGC年轻代和老年代哦都市用并行回收器。

4.-XX:+UseConcMarkSweepGC表示年轻代使用ParNew，老年代使用CMS。

5.-XX:+UseG1GC使用G1垃圾回收器

6.-XX:+UseZGC使用ZGC垃圾回收器

这些垃圾回收器的关系还是比较复杂的，请看下图

目前Java8还是主流使用版本，从Java8升级到高版本的Java体系是有一定成本的，所以CMS垃圾回收器还会持续一段时间

抛个问题，如果在垃圾回收的时候，又有新的对象进入怎么办？

为了保住程序不乱套，最好的办法就是暂停用户的一切线程，也就是在这段时间，是不能new对象的，只能等待，表象是在JVM上就是短暂的卡顿，什么都干不了，这个现象叫作StopTheWorld。

标记阶段，大多数是要STW的。如果不暂停用户进程，在标记对象的时候

金刚狼游戏攻略

，有可能有其它用户线程会产生一些新的对象和引用，造成混乱。

现在的垃圾回收器，都会尽量去减少这个过程。但即使最先进的ZGC回收器，也会有短暂的STW过程。我们要做的就是在现有基础设施上，尽量减少GC停顿。

举例说明下

某个高并发服务的峰值流量是10万次/秒，后面有10台负载均衡的机器，那么每台机器平均下来需要1w/s。假如某台机器在这段时间内发生了STW，持续了一秒，那么至少需要10ms就可以返回的1万个请求，需要至少等待1秒。

在用户那里的表现就是系统发生了卡顿。如果我们的GC非常的频繁。这种卡顿就会特别的明显，严重影响用户体验。

虽然说Java为我们提供了非常棒的自动内存管理机制，但也不能滥用，因为它是有STW硬伤的。

介绍了堆的具体分区，年轻代和老年代。介绍了多个常用的垃圾回收器，不同的垃圾回收器有不同的特点。各种垃圾回收器都是为了解决头疼的STW问题，让GC时间更短，停顿更短，吞吐量更大。

接触了很多名词，总结如下

1.Mark

2.Sweep

3.Copy

4.Compact

1.Younggeneration

2.Survivor

3.Eden

4.OldGeneration|TenuredGeneration

5.GC

--1.MinorGC

--2.MajorGC

1.weakgenerationalhypothesis

2.分配担保

3.提升

4.卡片标记

5.STW

布隆过滤器布隆过滤器（英语：BloomFilter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。主要用于判断一个元素是否在一个集合中。