bitmapbitsetBitMap和BitSet

大家好，今天小编来为大家解答bitmap bitset这个问题，BitMap和BitSet很多人还不知道，现在让我们一起来看看吧！

本文目录

BitMap原理与实现Bitmap的原理Redis Bitmap实现每日活跃用户统计BitMap和BitSetBitMap原理与实现比较经典的问题是：在只能够使用2G的内存中，如何完成以下操作：

①：对10亿个不重复的整数进行排序。

②：找出10亿个数字中重复的数字。

无论是排序还是找重复的数字都需要将这10亿个数字加入到内存中在去进行操作，很明显，题目给出的2G内存限制说明了在这样的场景下是不能够将所有数都加入到内存中的

1000000000*4/（1024*1024*1024）=3.725G

那么这时候就需要用到BitMap结构了

bitMap使用一个bit为0/1作为map的value来标记一个数字是否存在,而map的key值正是这个数字本身。

相比于一般的数据结构需要用4个byte去存储数值本身，相当于是节省了4*8：1=32倍的内存空间

bitMap不一定要用bit数组,可以使用int,long等等的基本数据类型实现，因为其实质都是在bit位上存数据，用哪种类型只是决定了最终实现出来的BitMap的内置数组中单个元素存放数据的多少

    例如：java中的BitSet使用Long数组

BitMap的实现当然少不了位运算，先来明确几个常见位运算，这是实现BitMap的基础：

set(bitIndex):添加操作

    1.确定该数处于数组中的哪个元素的位上

    intwordIndex=bitIndex>>5;

因为我用的是int[]实现，所以这里右移5位（2^5=32）

    2.确定相对于该元素中的位置偏移

    intbitPosition=bitIndex&((1<<5)-1);

这里相当于是bitIndex%（1<<5）的取模运算，因为当取模运算的除数是2的次幂，所以可以使用以下的位运算来计算，提升效率（对比HashMap的容量为什么总是2的幂次方的问题，HashMap求下标时也是使用hash&(n-1)）

tips:位运算的优先级是低于+,-等等的，所以要加上括号,防止发生不可描述的错误

    3.将该位置1

    bits[wordIndex]|=1<<bitPosition;

相当于是将指定位置处的bit值置1，其他位置保持不变，也就是将以这个bitIndex为key的位置为1

tips:这里是参考了网上的各位大佬的文章,取余+按位或，又对比了下BitSet的源码：

    words[wordIndex]|=(1L<<bitIndex);

没有取余操作，直接|，这两个一样吗？答案当然是一样的

举个栗子：

    1<<148==1<<20    

    1L<<125==1L<<61

即对于int和long型数据，直接左移其位数相当于是附带了对其的取模操作

总结：使用Bit-map的思想，我们可以将存储空间进行压缩，而且可以对数字进行快速排序、去重和查询的操作。

BloomFliter是Bit-map思想的一种扩展，它可以在允许低错误率的场景下，大大地进行空间压缩，是一种拿错误率换取空间的数据结构

当一个元素加入布隆过滤器中的时候，会进行哪些操作：

当我们需要判断一个元素是否存在于布隆过滤器的时候，会进行哪些操作：

然后，一定会出现这样一种情况：不同的字符串可能哈希出来的位置相同（可以适当增加位数组大小或者调整我们的哈希函数来降低概率）,因此：布隆过滤器可能会存在误判的情况

总结来说就是：布隆过滤器说某个元素存在，小概率会误判。布隆过滤器说某个元素不在，那么这个元素一定不在。

BloomFilter的应用:常用于解决缓存穿透等场景。

Bitmap的原理在网上有一道面试题大概意思就是:存在十亿个数字,现在需要知道哪些数字没有出现在里面.这个问题你可能觉得一个for循环就能解决,但是实际上你可能忽略了一个问题,那就是10亿个数字需要占据的内存空间.例如在java中要存下10亿个数字需要多大空间呢?假设使用int存储,一个int占32个位也就是4个字节.存放10亿个数字则需要:10亿*4/1024/1024/1024=4G左右.面对上面的问题我们肯定不能使用这种方式存储.而使用我们的Bitmap就能很好的解决上面的问题.

Bitmapi简单的说就是使用bit(位)来存储状态,适合用来存储大规模的数据,但是状态又不是很多的情况.举例来说,如果我现在有1,3,4,2,7这五个数字,如果我们使用5个int来存储则需要20个字节的空间.但是我现在使用1字节就能存储上面的五个数字.如下图所示,1个字节可以用8位表示,1位有0和1两种值分别用来表示该位上是否有值,而位的索引用来表示数字(图中以从左到右的顺序计算).

而它的缺点同样也比较明显.它的一个位只能存储一个数据,对于重复的数据无法记录.如果数据分布很稀疏,会造成空间的浪费.例如,如果现在只有{1,3,1000000000}这个三个数据,它有很多空间会被浪费掉.

BitMap在java中提供了BitSet的实现,同时在我们平常使用的Redis中也有实现.它很适合用来做大量的用户统计.例如统计登录人数,签到,在线等等.这些需求都可以通过redis的bit相关指令很简单的就能实现.

例如,统计网站的在线人数:

上面的方式不仅简单,而且就算用户数量很大也能又快又好的完成.

Redis Bitmap实现每日活跃用户统计

Bitmap(又名Bitset)

Bitmap或bitset是一个零和一的数组。可以将位集中的位设置为0或者1，并且将阵列中的每个位置称为偏移。诸如逻辑AND，OR，XOR等操作以及其他按位操作对于位图来说是准确的。

人口数量

Bitmap的填充计数是设置索引的位数1。有计算人口数的有效算法。例如，在Windows开发环境上，包含10亿位的90％填充位组的人口数量为21.1ms。

Redis中的位图

Redis允许二进制密钥和二进制值。位图只不过是二进制值。setbit(key,offset,value)操作，需要O(1)时间，一个位的值设置为0或1以指定对于给定的键偏移。

一个简单的例子：每日活跃用户

为了统计今天登录的唯一用户，我们设置了一个位图，其中每个用户都由一个偏移值标识。当用户访问页面或执行保证计数的操作时，将该位设置为1表示用户ID的偏移量。位图的关键是执行的操作用户的名称和时间戳的函数。

假如今天是2019年7月1号，我们设置Redis的位图key为daily_active_20190701,在这个简单的例子中，每次用户登录时我们都会执行redis.setbit(daily_active_20190701,user_id,1)。这会将daily_active_20190701位图中的相应偏移量翻转为1.这是一个O（1）操作。对此进行人口统计会导致今天登录的9个唯一身份用户。关键是daily_active_20190701，值是1011110100100101。

当然，由于每日活跃用户每天都会改变，我们需要一种方法来每天创建一个新的位图。我们只需将日期附加到位图键即可。

每天的活跃用户是存储为daily_active_yyyymmdd为key的bitmap中。要计算每周或每月指标，我们可以简单地计算一周或一个月内所有每天位图的并集，然后计算结果位图的总体数，这将非常轻松地提取更复杂的指标。

使用1.28亿用户进行性能比较

下表显示了针对1.28亿用户在1天，7天和30天内计算的每日独特操作计算的比较。通过组合每日位图计算7和30指标。

示例代码

下面的Java代码片段为给定的用户操作和日期计算唯一用户。

下面的代码片段计算给定给定用户操作的唯一用户和日期列表

BitMap和BitSetBit-map的基本思想就是用一个bit位来标记某个元素对应的Value，而Key即是该元素。由于采用了Bit为单位来存储数据，可以很大力度的节省空间，常用于对大量整数做去重和查询操作。

1byte=8bit

1kb=102

成都一录取分数线

1mb=1024kb

1gb=1024mb

java中int类型占用4个字节=4*8=32bit

从上述结果来看，按位存储比按字节存储数字节约了（7.45/0.233-1约等于31倍空间），而且按字节存储根据内存4G的要求无法一次性在内存中进行处理。

众所周知，每一位的取值无非就是0和1，给每一位编号，那么用0表示数字存在，1表

7座超载2人怎么处罚

假如现在有一个字节也就是8位的空间，那么按照BitMap，可以表示8个数字，

按照上图所示，该字节的8位表示了整数数组[6,5,2,0]。那么java中int类型占用了4个字节，也就是32位，那么就可以最多表示32个数字。超过32位数字呢？那就使用两个以上int去表示。

假设我们要存储的数字最大值位N，则申请inttemp[1+N/32]的数组空间，其中：

temp[0]可表示0~31

temp[1]可表示32-63

.....以此类推

给定任一整数M，M数字所在数组中的下标位置就应该是M/32，M数字所在的位就是M%32

总共两步

1.找到整数所在数组temp的下标

intindex=M/32

2.将temp[index]的第M%32位置1

temp[index]=temp[index]|(1<<(M%32))

根据bitMap的原理可知，想要清除掉一个数字，那就是将对应的位置0

总共两步

1.找到整数所在数组temp的下标

intindex=M/32

2.将temp[index]的第M%32位置0

temp[index]=temp[index]&（~(1<<(M%32))）

根据每一位代表一个数字，1表示存在，0表示不存在，那么只需要判断整数对应位是否位1即可

总共两步

1.找到整数所在数组temp的下标

intindex=M/32

2.将temp[index]的第M%32位置0

temp[index]&(1<<(M%32)！=0？"存在":"不存在"

运行结果

BitSet就是实现了Bit-Map算法。BitSet位于java.util包下，从JDK1.0开始就已经有了。该类实现了一个按需增长的位向量。位集的每一个组件都有一个boolea

两会人工智能

设值

清除

检查

BitSet有三种构造方法，我们直接来看无参构造器

可以看到BitSet是使用long数组存储。那么long类型占用8个字节，即64位，一个long类型可表示64个数字。默认设置BitSet可表示最大的位数为64位。与上述自己实现的基本类似。

再来看set方法

get方法

clear方法

可以看到JDK中的BitSet实现原理与第三节中一样，采用Bit-Map思想，BitSet封装较多的API，可供开发者们随意使用。

如果你还想了解更多这方面的信息，记得收藏关注本站。