BitMap使用实例代码分析

这篇文章主要介绍“BitMap使用实例代码分析”，在日常操作中，相信很多人在BitMap使用实例代码分析问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”BitMap使用实例代码分析”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！BitMap，即位图，是比较常见的数据结构，简单来说就是按位存储，主要为了解决在去重场景里面大数据量存储的问题。本质其实就是哈希表的一种应用实现，使用每个位来表示某个数字。举个例子假设有个1，3，5，7的数字集合，如果常规的存储方法，要用4个Int的空间。其中一个Int就是32位的空间。3个就是4*32Bit，相当于16个字节。如果用Bitmap存储呢，只用8Bit（1个字节）就够了。bitmap通过使用每一bit位代表一个数，位号就是数值，1标识有，0标识无。如下所示：对于 BitMap 这种经典的数据结构，在 Java 语言里面，其实已经有对应实现的数据结构类 java.util.BitSet 了，而 BitSet 的底层原理，其实就是用 long 类型的数组来存储元素，因为使用的是long类型的数组，而 1 long = 64 bit，所以数据大小会是64的整数倍。这样看可能很难理解，下面参考bitmap源码写了一个例子，并写上了详细的备注，方便理解下面就来简单玩一玩这个自制的BitMap，先尝试插入一个3，并清理掉它，看看底层二进制结构是怎样变化的输出结果如下：再通过数组，插入多个元素看看效果输出结果如下：前面简单了解了一下BitMap，下面就通过源码来看看java是如何实现BitSet的。打开源码，首先映入眼帘的是下面这一段长长的备注，简单翻译一下，便于英语不好的小伙伴理解源码备注翻译如下这个类实现了一个根据需要增长的位向量。位集的每个组件都有一个布尔值。BitSet的位由非负整数索引。可以检查、设置或清除单个索引位。一个位集可用于通过逻辑AND、逻辑inclusive OR和逻辑exclusive OR操作修改另一个位集的内容。默认情况下，集合中的所有位最初的值都为false。每个BitSet都有一个当前大小，即BitSet当前使用的空间位数。请注意，大小与BitSet的实现有关，因此它可能会随着实现而改变。BitSet的长度与BitSet的逻辑长度有关，并且与实现无关。除非另有说明，否则将null参数传递给位集中的任何方法都将导致NullPointerException。如果没有外部同步，BitSet对于多线程使用是不安全的。首先可以看到源码中，最核心的属性信息。在BitSet 中使用的是long[] 作为底层存储的数据结构，并通过一个 int 类型的变量，来记录当前已经使用数组元素的个数。这种类型的属性结构很常见，比如StringBuilder、StringBuffer底层是一个char[] 作为存储，一个int 变量用来计数，相似的还有ArrayList，Vector等再往下看，是一个很重要的方法，是用来获取某个数在数组中的下标，采用的算法是将这个数右移6位，这是因为 bitIndex >> 6 = bitIndex / (2^6) = bitIndex /64，而long就是64个字节接着比较有意思的就是它的空参构造器，BITS_PER_WORD默认是1
最后看到这个很经典也很重要的方法，由于底层是数组，在初始化的时候，并不知道将来会需要存储多大的数据，所以对于这一类底层核心实现结构是数组的实体类，通常会使用动态扩容的方法，具体实现细节也都大同小异，这里实现的动态扩容是原本的两倍，和Vector类似。至于其他的源码细节，因为篇幅有限，就暂且不表，感兴趣的可以自行阅读～根据bitmap的实现原理，其实可以总结出使用bitmap的几个主要原因：针对海量数据的存储，可以极大的节约存储成本！当需要存储一些很大，且无序，不重复的整数集合，那使用Bitmap的存储成本是非常低的。因为其天然去重的属性，对于需要去重存储的数据很友好！因为bitmap每个值都只对应唯一的一个位置，不能存储两个值，所以Bitmap结构天然适合做去重操作。同样因为其下标的存在，可以快速定位数据！比如想判断数字 99999是否存在于该bitmap中，若是使用传统的集合型存储，那就要逐个遍历每个元素进行判断，时间复杂度为O(N)。而由于采用Bitmap存储，只要查看对应的下标数的值是0还是1即可，时间复杂度为O(1)。所以使用bitmap可以非常方便快速的查询某个数据是否在bitmap中。还有因为其类集合的特性，对于一些集合的交并集等操作也可以支持！比如想查询[1,2,3]与[3,4,5] 两个集合的交集，用传统方式取交集就要两层循环遍历。而Bitmap实现的底层原理，就是把01110000和00011100进行与操作就行了。而计算机做与、或、非、异或等等操作是非常快的。虽然bitmap有诸多好处，但是正所谓人无完人，它也存在很多缺陷。只能存储正整数而不能是其他的类型；不适合存储稀疏的集合，简单理解，一个集合存放了两个数[1,99999999]，那用bitmap存储的话就很不划算，这也与它本来节约存储的优点也背离了；不适用于存储重复的数据。既然bitmap的优点如此突出，那应该如何去优化它存在的一些局限呢？针对存储非正整数的类型，如字符串类型的，可以考虑将字符串类型的数据利用类似hash的方法，映射成整数的形式来使用bitmap，但是这个方法会有hash冲突的问题，解决这个可以优化hash方法，采用多重hash来解决，但是根据经验，这个效果都不太好，通常的做法就是针对字符串建立映射表的方式。针对bitmap的优化最核心的还是对于其存储成本的优化，毕竟大数据领域里面，大多数时候数据都是稀疏数据，而我们又经常需要使用到bitmap的特长，比如去重等属性，所以存在一些进一步的优化，比较知名的有WAH、EWAH、RoaringBitmap等，其中性能最好并且应用最为广泛的当属RoaringBitmap为了快速把这个原理说清楚，这里就不继续撸源码了，有兴趣的小伙伴可以自行搜索相关源码阅读，下面简单阐述一下它的核心原理：1个Int 类型相当于有32 bit 也就相当于2^32=2^16 x 2^16，这意味着任意一个Int 类型可以拆分成两个16bit的来存储，每一个拆出来的都不会大于2^16， 2^16就是65536，而Int的正整数实际最大值为 2147483647。而RoaringBitmap的压缩首先做的就是用原本的数去除65536，结果表示成(商，余数)，免费云主机域名其中商和余数是都不会超过65536。如下图所示RoaringBitmap的做法就是将131138 原本32bit的存储结构，拆分成连两个16bit的结构，而拆分出的两个16bit分别存储了131138除65536的商2以及余数66。在RoaringBitmap中，把商所处的16bit 被称为高16位，除数所处的16bit 被称为低16位。并用key和Container去存储的这些拆分出来的数据，其中key是short[] ，存放的就是商，因为bitmap的特性，商和余数不会存在完全相同的情况。通过商来作为key划分不同的Container，就类似划分不同的桶，key就是标识数据应该存在哪个桶，container用来存对应数据的低16位的数字。比如 1000和60666 除以65536后的结果分别是(0,1000)和(0,60666)，所以这两个数据存储到RoaringBitmap中，就会都放到key位0那个container中，container中就是1000和60666。由于container中存放的数字是0~65536的一些数据，可能稀疏可能稠密，所以RoaringBitmap依据不同的场景，提供了 3 种不同的 Container，分别是 ArrayContainer 、 BitmapContainer 、RunContainer。关于三个Container的存储原理如下：ArrayContainer 存储的方式就是 shot类型的数组， 每个数字占16bit 也就是2Byte，当id 数达到4096个时，占用4096×2 = 8196byte 也就是8kb，而id数最大是65536，占用 65536×2 =131072 byte 也就是128kb。BitmapContainer存储的方式就是bitmap类型，bitmap的位数为 65536，能存储0~65535个数字，占用 65536/8/1024=8kb，也就是bitmap container占用空间恒定为8kb。RunContainer存储的必须是连续的数字，比如存储1，2，3…100w，RunContainer就只会存储[1,100w]也就是开头和结尾的一个数字，其压缩效率取决于连续的数字有多长。关于ArrayContainer和BitmapContainer的选择：如图所示，可以看到ArrayContainer 更适合存放稀疏的数据，BitmapContainer 适合存放稠密的数据。在RoaringBitmap中，若一个 Container 里面的元素数量小于 4096，会使用 ArrayContainer 来存储。当 Array Container 超过最大容量 4096 时，会转换为 BitmapContainer，这样能够最大化的优化存储。bitmap就像一柄双刃剑，用的好可以帮助我们破除瓶颈，解决痛点。用的不好不仅会丢失它所有的优点，还要搭上过多的存储，甚至会丧失掉最重要的准确性，所以要针对不同业务场景灵活使用我们的武器，才能事半功倍！下面举例bitmap的一些使用场景，来看看实际开发中，到底怎么正确使用bitmap：假设有用户的标签宽表，对应字段及值如下如果想根据标签划分人群，比如：1001城市 + 下单。通常是对列值进行遍历筛选，如果优化也就是列上建立索引，但是当这张表有很多标签列时，如果要索引生效并不是每列有索引就行，要每种查询组合建一个索引才能生效，索引数量相当于标签列排列组合的个数，当标签列有1、2 k 的时候，这基本就是不可能的。通常的做法是在数仓提前将热点的组合聚合过滤成新字段，或者只对热点组合加索引，但这样都很不灵活。通过采用bitmap的办法，按字段重组成Bitmap。把数据调整成这样的结构，再进行条件组合,那就简单了。比如: 1001城市 + 下单 = Bitmap[00000110] & Bitmap[00001010]= 1 ，这个计算速度相比宽表条件筛选是快很多的，如果数据是比较稠密的，bitmap可以极大的节省底层存储，如果数据比较稀疏，可以采用RoaringBitmap来优化。在支持货拉拉A/B实验平台业务的场景中，会有一个实验对应很多司机的情况，因为要在数仓处理成明细宽表，来支持OLAP引擎的使用，随着维度的增多，数据发散的情况变得很严重，数仓及OLAP的存储与计算资源都消耗巨大。为了解决这个痛点，在架构组同事建议下，引入了BitMap，将组装好的司机id数组转换成RoaringBitmap格式，再传入到OLAP引擎里面使用。在数仓应用层，由于引入了BitMap，重构了原本的数据表结构及链路，并优化了数仓的分层。不仅让整个链路耗时缩短了2个多小时，还节省了后续往OLAP引擎导数的时间，再算上数仓层的计算与存储资源的节省，很完美的实现了降本增效！而在OLAP引擎层，由架构组的同事通过二次开发，支持了Bitmap的使用，也取得了很不错的效果。到此，关于“BitMap使用实例代码分析”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注百云主机网站，小编会继续努力为大家带来更多实用的文章！

相关推荐: Mybatis-plus如何使用

这篇文章主要介绍“Mybatis-plus如何使用”，在日常操作中，相信很多人在Mybatis-plus如何使用问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”Mybatis-plus如何使用”的疑惑有所帮助！接下来，请跟着小编一…