面试官问：BitMap了解么？在什么场景下用过？碰到过什么问题？

点击上方“芋道源码”&＃xff0c;选择“设为星标”

管她前浪&＃xff0c;还是后浪&＃xff1f;

能浪的浪&＃xff0c;才是好浪&＃xff01;

每天 8:55 更新文章&＃xff0c;每天掉亿点点头发...

源码精品专栏

• 原创 | Java 2020 超神之路&＃xff0c;很肝~
  

• 中文详细注释的开源项目
  

• RPC 框架 Dubbo 源码解析

• 网络应用框架 Netty 源码解析
  

• 消息中间件 RocketMQ 源码解析
  

• 数据库中间件 Sharding-JDBC 和 MyCAT 源码解析

• 作业调度中间件 Elastic-Job 源码解析

• 分布式事务中间件 TCC-Transaction 源码解析

• Eureka 和 Hystrix 源码解析

• Java 并发源码

来源&＃xff1a;cnblogs.com/cjsblog/p/11613708.html

• 添加

• 清除

• 查找

• 快速排序

• 快速去重

• 快速查找

• 小结&回顾

• 补充1

• 补充2

• BloomFilter 流程

Bit-map的基本思想就是用一个bit位来标记某个元素对应的Value&＃xff0c;而Key即是该元素。由于采用了Bit为单位来存储数据&＃xff0c;因此在存储空间方面&＃xff0c;可以大大节省。&＃xff08;PS&＃xff1a;划重点 节省存储空间 &＃xff09;

假设有这样一个需求&＃xff1a;在20亿个随机整数中找出某个数m是否存在其中&＃xff0c;并假设32位操作系统&＃xff0c;4G内存

在Java中&＃xff0c;int占4字节&＃xff0c;1字节&＃61;8位&＃xff08;1 byte &＃61; 8 bit&＃xff09;

如果每个数字用int存储&＃xff0c;那就是20亿个int&＃xff0c;因而占用的空间约为 (2000000000*4/1024/1024/1024)≈7.45 G

如果按位存储就不一样了&＃xff0c;20亿个数就是20亿位&＃xff0c;占用空间约为 (2000000000/8/1024/1024/1024)≈0.23 G

高下立判&＃xff0c;无需多言

那么&＃xff0c;问题来了&＃xff0c;如何表示一个数呢&＃xff1f;

刚才说了&＃xff0c;每一位表示一个数&＃xff0c;0表示不存在&＃xff0c;1表示存在&＃xff0c;这正符合二进制

这样我们可以很容易表示{1,2,4,6}这几个数&＃xff1a;

计算机内存分配的最小单位是字节&＃xff0c;也就是8位&＃xff0c;那如果要表示{12,13,15}怎么办呢&＃xff1f;

当然是在另一个8位上表示了&＃xff1a;

这样的话&＃xff0c;好像变成一个二维数组了

1个int占32位&＃xff0c;那么我们只需要申请一个int数组长度为 int tmp[1&＃43;N/32] 即可存储&＃xff0c;其中N表示要存储的这些数中的最大值&＃xff0c;于是乎&＃xff1a;

tmp[0]&＃xff1a;可以表示0~31

tmp[1]&＃xff1a;可以表示32~63

tmp[2]&＃xff1a;可以表示64~95

。。。

如此一来&＃xff0c;给定任意整数M&＃xff0c;那么M/32就得到下标&＃xff0c;M%32就知道它在此下标的哪个位置

这里有个问题&＃xff0c;我们怎么把一个数放进去呢&＃xff1f;例如&＃xff0c;想把5这个数字放进去&＃xff0c;怎么做呢&＃xff1f;

首先&＃xff0c;5/32&＃61;0&＃xff0c;5%32&＃61;5&＃xff0c;也是说它应该在tmp[0]的第5个位置&＃xff0c;那我们把1向左移动5位&＃xff0c;然后按位或

换成二进制就是

这就相当于 86 | 32 &＃61; 118

86 | (1<<5) &＃61; 118

b[0] &＃61; b[0] | (1<<5)

也就是说&＃xff0c;要想插入一个数&＃xff0c;将1左移带代表该数字的那一位&＃xff0c;然后与原数进行按位或操作

化简一下&＃xff0c;就是 86 &＃43; (5/8) | (1<<(5%8))

因此&＃xff0c;公式可以概括为&＃xff1a;p &＃43; (i/8)|(1<<(i%8)) 其中&＃xff0c;p表示现在的值&＃xff0c;i表示待插入的数

以上是添加&＃xff0c;那如果要清除该怎么做呢&＃xff1f;

还是上面的例子&＃xff0c;假设我们要6移除&＃xff0c;该怎么做呢&＃xff1f;

从图上看&＃xff0c;只需将该数所在的位置为0即可

1左移6位&＃xff0c;就到达6这个数字所代表的位&＃xff0c;然后按位取反&＃xff0c;最后与原数按位与&＃xff0c;这样就把该位置为0了

b[0] &＃61; b[0] & (~(1<<6))

b[0] &＃61; b[0] & (~(1<<(i%8)))

前面我们也说了&＃xff0c;每一位代表一个数字&＃xff0c;1表示有&＃xff08;或者说存在&＃xff09;&＃xff0c;0表示无&＃xff08;或者说不存在&＃xff09;。通过把该为置为1或者0来达到添加和清除的小伙&＃xff0c;那么判断一个数存不存在就是判断该数所在的位是0还是1

假设&＃xff0c;我们想知道3在不在&＃xff0c;那么只需判断 b[0] & (1<<3) 如果这个值是0&＃xff0c;则不存在&＃xff0c;如果是1&＃xff0c;就表示存在

Bitmap有什么用

大量数据的快速排序、查找、去重

假设我们要对0-7内的5个元素(4,7,2,5,3)排序&＃xff08;这里假设这些元素没有重复&＃xff09;,我们就可以采用Bit-map的方法来达到排序的目的。

要表示8个数&＃xff0c;我们就只需要8个Bit&＃xff08;1Bytes&＃xff09;&＃xff0c;首先我们开辟1Byte的空间&＃xff0c;将这些空间的所有Bit位都置为0&＃xff0c;然后将对应位置为1。

最后&＃xff0c;遍历一遍Bit区域&＃xff0c;将该位是一的位的编号输出&＃xff08;2&＃xff0c;3&＃xff0c;4&＃xff0c;5&＃xff0c;7&＃xff09;&＃xff0c;这样就达到了排序的目的&＃xff0c;时间复杂度O(n)。

优点:

• 运算效率高&＃xff0c;不需要进行比较和移位&＃xff1b;

• 占用内存少&＃xff0c;比如N&＃61;10000000&＃xff1b;只需占用内存为N/8&＃61;1250000Byte&＃61;1.25M

缺点:

• 所有的数据不能重复。即不可对重复的数据进行排序和查找。

• 只有当数据比较密集时才有优势

20亿个整数中找出不重复的整数的个数&＃xff0c;内存不足以容纳这20亿个整数。

首先&＃xff0c;根据“内存空间不足以容纳这05亿个整数”我们可以快速的联想到Bit-map。下边关键的问题就是怎么设计我们的Bit-map来表示这20亿个数字的状态了。其实这个问题很简单&＃xff0c;一个数字的状态只有三种&＃xff0c;分别为不存在&＃xff0c;只有一个&＃xff0c;有重复。因此&＃xff0c;我们只需要2bits就可以对一个数字的状态进行存储了&＃xff0c;假设我们设定一个数字不存在为00&＃xff0c;存在一次01&＃xff0c;存在两次及其以上为11。那我们大概需要存储空间2G左右。

接下来的任务就是把这20亿个数字放进去&＃xff08;存储&＃xff09;&＃xff0c;如果对应的状态位为00&＃xff0c;则将其变为01&＃xff0c;表示存在一次&＃xff1b;如果对应的状态位为01&＃xff0c;则将其变为11&＃xff0c;表示已经有一个了&＃xff0c;即出现多次&＃xff1b;如果为11&＃xff0c;则对应的状态位保持不变&＃xff0c;仍表示出现多次。

最后&＃xff0c;统计状态位为01的个数&＃xff0c;就得到了不重复的数字个数&＃xff0c;时间复杂度为O(n)。

这就是我们前面所说的了&＃xff0c;int数组中的一个元素是4字节占32位&＃xff0c;那么除以32就知道元素的下标&＃xff0c;对32求余数&＃xff08;%32&＃xff09;就知道它在哪一位&＃xff0c;如果该位是1&＃xff0c;则表示存在。

Bitmap主要用于快速检索关键字状态&＃xff0c;通常要求关键字是一个连续的序列&＃xff08;或者关键字是一个连续序列中的大部分&＃xff09;&＃xff0c; 最基本的情况&＃xff0c;使用1bit表示一个关键字的状态&＃xff08;可标示两种状态&＃xff09;&＃xff0c;但根据需要也可以使用2bit&＃xff08;表示4种状态&＃xff09;&＃xff0c;3bit&＃xff08;表示8种状态&＃xff09;。

Bitmap的主要应用场合&＃xff1a;表示连续&＃xff08;或接近连续&＃xff0c;即大部分会出现&＃xff09;的关键字序列的状态&＃xff08;状态数/关键字个数 越小越好&＃xff09;。

32位机器上&＃xff0c;对于一个整型数&＃xff0c;比如int a&＃61;1 在内存中占32bit位&＃xff0c;这是为了方便计算机的运算。但是对于某些应用场景而言&＃xff0c;这属于一种巨大的浪费&＃xff0c;因为我们可以用对应的32bit位对应存储十进制的0-31个数&＃xff0c;而这就是Bit-map的基本思想。Bit-map算法利用这种思想处理大量数据的排序、查询以及去重。

在数字没有溢出的前提下&＃xff0c;对于正数和负数&＃xff0c;左移一位都相当于乘以2的1次方&＃xff0c;左移n位就相当于乘以2的n次方&＃xff0c;右移一位相当于除2&＃xff0c;右移n位相当于除以2的n次方。

<<左移&＃xff0c;相当于乘以2的n次方&＃xff0c;例如&＃xff1a;1<<6  相当于1×64&＃61;64&＃xff0c;3<<4 相当于3×16&＃61;48

>> 右移&＃xff0c;相当于除以2的n次方&＃xff0c;例如&＃xff1a;64>>3 相当于64÷8&＃61;8

^ 异或&＃xff0c;相当于求余数&＃xff0c;例如&＃xff1a;48^32 相当于 48%32&＃61;16

不使用第三方变量&＃xff0c;交换两个变量的值

// 方式一
a &＃61; a &＃43; b;
b &＃61; a - b;
a &＃61; a - b;// 方式二
a &＃61; a ^ b;
b &＃61; a ^ b;
a &＃61; a ^ b;


BitSet

BitSet实现了一个位向量&＃xff0c;它可以根据需要增长。每一位都有一个布尔值。一个BitSet的位可以被非负整数索引&＃xff08;PS&＃xff1a;意思就是每一位都可以表示一个非负整数&＃xff09;。可以查找、设置、清除某一位。通过逻辑运算符可以修改另一个BitSet的内容。默认情况下&＃xff0c;所有的位都有一个默认值false。

可以看到&＃xff0c;跟我们前面想的差不多

用一个long数组来存储&＃xff0c;初始长度64&＃xff0c;set值的时候首先右移6位&＃xff08;相当于除以64&＃xff09;计算在数组的什么位置&＃xff0c;然后更改状态位

别的看不懂不要紧&＃xff0c;看懂这两句就够了&＃xff1a;

int wordIndex &＃61; wordIndex(bitIndex);
words[wordIndex] |&＃61; (1L << bitIndex);


Bloom Filters

Bloom filter 是一个数据结构&＃xff0c;它可以用来判断某个元素是否在集合内&＃xff0c;具有运行快速&＃xff0c;内存占用小的特点。

而高效插入和查询的代价就是&＃xff0c;Bloom Filter 是一个基于概率的数据结构&＃xff1a;它只能告诉我们一个元素绝对不在集合内或可能在集合内。

Bloom filter 的基础数据结构是一个 比特向量&＃xff08;可理解为数组&＃xff09;。

主要应用于大规模数据下不需要精确过滤的场景&＃xff0c;如检查垃圾邮件地址&＃xff0c;爬虫URL地址去重&＃xff0c;解决缓存穿透问题等

如果想判断一个元素是不是在一个集合里&＃xff0c;一般想到的是将集合中所有元素保存起来&＃xff0c;然后通过比较确定。链表、树、散列表&＃xff08;哈希表&＃xff09;等等数据结构都是这种思路&＃xff0c;但是随着集合中元素的增加&＃xff0c;需要的存储空间越来越大&＃xff1b;同时检索速度也越来越慢&＃xff0c;检索时间复杂度分别是O(n)、O(log n)、O(1)。

布隆过滤器的原理是&＃xff0c;当一个元素被加入集合时&＃xff0c;通过 K 个散列函数将这个元素映射成一个位数组&＃xff08;Bit array&＃xff09;中的 K 个点&＃xff0c;把它们置为 1 。检索时&＃xff0c;只要看看这些点是不是都是1就知道元素是否在集合中&＃xff1b;如果这些点有任何一个 0&＃xff0c;则被检元素一定不在&＃xff1b;如果都是1&＃xff0c;则被检元素很可能在&＃xff08;之所以说“可能”是误差的存在&＃xff09;。

1、 首先需要 k 个 hash 函数&＃xff0c;每个函数可以把 key 散列成为 1 个整数&＃xff1b;

2、初始化时&＃xff0c;需要一个长度为 n 比特的数组&＃xff0c;每个比特位初始化为 0&＃xff1b;

3、某个 key 加入集合时&＃xff0c;用 k 个 hash 函数计算出 k 个散列值&＃xff0c;并把数组中对应的比特位置为 1&＃xff1b;

4、判断某个 key 是否在集合时&＃xff0c;用 k 个 hash 函数计算出 k 个散列值&＃xff0c;并查询数组中对应的比特位&＃xff0c;如果所有的比特位都是1&＃xff0c;认为在集合中。

com.google.guavaguava28.1-jre



欢迎加入我的知识星球&＃xff0c;一起探讨架构&＃xff0c;交流源码。加入方式&＃xff0c;长按下方二维码噢&＃xff1a;

已在知识星球更新源码解析如下&＃xff1a;

最近更新《芋道 SpringBoot 2.X 入门》系列&＃xff0c;已经 20 余篇&＃xff0c;覆盖了 MyBatis、Redis、MongoDB、ES、分库分表、读写分离、SpringMVC、Webflux、权限、WebSocket、Dubbo、RabbitMQ、RocketMQ、Kafka、性能测试等等内容。

提供近 3W 行代码的 SpringBoot 示例&＃xff0c;以及超 4W 行代码的电商微服务项目。

获取方式&＃xff1a;点“在看”&＃xff0c;关注公众号并回复 666 领取&＃xff0c;更多内容陆续奉上。

兄弟&＃xff0c;艿一口&＃xff0c;点个赞&＃xff01;????