乐趣区

关于java:BitMap了解么在什么场景下用过碰到过什么问题

Bit-map 的根本思维就是用一个 bit 位来标记某个元素对应的 Value,而 Key 即是该元素。因为采纳了 Bit 为单位来存储数据,因而在存储空间方面,能够大大节俭。(PS:划重点 节俭存储空间

假如有这样一个需要:在 20 亿个随机整数中找出某个数 m 是否存在其中,并假如 32 位操作系统,4G 内存

在 Java 中,int 占 4 字节,1 字节 = 8 位(1 byte = 8 bit)

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

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

高下立判,无需多言

那么,问题来了,如何示意一个数呢?

方才说了,每一位示意一个数,0 示意不存在,1 示意存在,这正合乎二进制

这样咱们能够很容易示意 {1,2,4,6} 这几个数:

计算机内存调配的最小单位是字节,也就是 8 位,那如果要示意 {12,13,15} 怎么办呢?

当然是在另一个 8 位上示意了:

这样的话,如同变成一个二维数组了

《2020 最新 Java 根底精讲视频教程和学习路线!》

1 个 int 占 32 位,那么咱们只须要申请一个 int 数组长度为 int tmp[1+N/32] 即可存储,其中 N 示意要存储的这些数中的最大值,于是乎:

tmp[0]:能够示意 0~31

tmp[1]:能够示意 32~63

tmp[2]:能够示意 64~95

。。。

如此一来,给定任意整数 M,那么 M /32 就失去下标,M%32 就晓得它在此下标的哪个地位

增加

这里有个问题,咱们怎么把一个数放进去呢?例如,想把 5 这个数字放进去,怎么做呢?

首先,5/32=0,5%32=5,也是说它应该在 tmp[0]的第 5 个地位,那咱们把 1 向左挪动 5 位,而后按位或

换成二进制就是

这就相当于 86 | 32 = 118

86 | (1<<5) = 118

b[0] = b[0] | (1<<5)

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

化简一下,就是 86 + (5/8) | (1<<(5%8))

因而,公式能够概括为:p + (i/8)|(1<<(i%8)) 其中,p 示意当初的值,i 示意待插入的数

革除

以上是增加,那如果要革除该怎么做呢?

还是下面的例子,假如咱们要 6 移除,该怎么做呢?

从图上看,只需将该数所在的地位为 0 即可

1 左移 6 位,就达到 6 这个数字所代表的位,而后按位取反,最初与原数按位与,这样就把该地位为 0 了

b[0] = b[0] & (~(1<<6))

b[0] = b[0] & (~(1<<(i%8)))

查找

后面咱们也说了,每一位代表一个数字,1 示意有(或者说存在),0 示意无(或者说不存在)。通过把该为置为 1 或者 0 来达到增加和革除的小伙,那么判断一个数存不存在就是判断该数所在的位是 0 还是 1

假如,咱们想晓得 3 在不在,那么只需判断 b[0] & (1<<3) 如果这个值是 0,则不存在,如果是 1,就示意存在

Bitmap 有什么用

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

疾速排序

假如咱们要对 0 - 7 内的 5 个元素 (4,7,2,5,3) 排序(这里假如这些元素没有反复), 咱们就能够采纳 Bit-map 的办法来达到排序的目标。

要示意 8 个数,咱们就只须要 8 个 Bit(1Bytes),首先咱们开拓 1Byte 的空间,将这些空间的所有 Bit 位都置为 0,而后将对应地位为 1。

最初,遍历一遍 Bit 区域,将该位是一的位的编号输入(2,3,4,5,7),这样就达到了排序的目标,工夫复杂度 O(n)。

长处:

  • 运算效率高,不须要进行比拟和移位;
  • 占用内存少,比方 N =10000000;只需占用内存为 N /8=1250000Byte=1.25M

毛病:

  • 所有的数据不能反复。即不可对反复的数据进行排序和查找。
  • 只有当数据比拟密集时才有劣势

疾速去重

20 亿个整数中找出不反复的整数的个数,内存不足以包容这 20 亿个整数。

首先,依据“内存空间不足以包容这 05 亿个整数”咱们能够疾速的联想到 Bit-map。下边要害的问题就是怎么设计咱们的 Bit-map 来示意这 20 亿个数字的状态了。其实这个问题很简略,一个数字的状态只有三种,别离为不存在,只有一个,有反复。因而,咱们只须要 2bits 就能够对一个数字的状态进行存储了,假如咱们设定一个数字不存在为 00,存在一次 01,存在两次及其以上为 11。那咱们大略须要存储空间 2G 左右。

接下来的工作就是把这 20 亿个数字放进去(存储),如果对应的状态位为 00,则将其变为 01,示意存在一次;如果对应的状态位为 01,则将其变为 11,示意曾经有一个了,即呈现屡次;如果为 11,则对应的状态位放弃不变,仍示意呈现屡次。

最初,统计状态位为 01 的个数,就失去了不反复的数字个数,工夫复杂度为 O(n)。

疾速查找

这就是咱们后面所说的了,int 数组中的一个元素是 4 字节占 32 位,那么除以 32 就晓得元素的下标,对 32 求余数(%32)就晓得它在哪一位,如果该位是 1,则示意存在。

小结 & 回顾

Bitmap 次要用于疾速检索关键字状态,通常要求关键字是一个间断的序列(或者关键字是一个间断序列中的大部分),最根本的状况,应用 1bit 示意一个关键字的状态(可标示两种状态),但依据须要也能够应用 2bit(示意 4 种状态),3bit(示意 8 种状态)。

Bitmap 的次要利用场合:示意间断(或靠近间断,即大部分会呈现)的关键字序列的状态(状态数 / 关键字个数 越小越好)。

32 位机器上,对于一个整型数,比方 int a=1 在内存中占 32bit 位,这是为了不便计算机的运算。然而对于某些利用场景而言,这属于一种微小的节约,因为咱们能够用对应的 32bit 位对应存储十进制的 0 -31 个数,而这就是 Bit-map 的根本思维。Bit-map 算法利用这种思维解决大量数据的排序、查问以及去重。

补充 1

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

<< 左移,相当于乘以 2 的 n 次方,例如:1<<6 相当于 1×64=64,3<<4 相当于 3×16=48

右移,相当于除以 2 的 n 次方,例如:64>>3 相当于 64÷8=8

^ 异或,相当于求余数,例如:48^32 相当于 48%32=16

补充 2

不应用第三方变量,替换两个变量的值

// 形式一
a = a + b;
b = a - b;
a = a - b;

// 形式二
a = a ^ b;
b = a ^ b;
a = a ^ b; 

BitSet

BitSet 实现了一个位向量,它能够依据须要增长。每一位都有一个布尔值。一个 BitSet 的位能够被非负整数索引(PS:意思就是每一位都能够示意一个非负整数)。能够查找、设置、革除某一位。通过逻辑运算符能够批改另一个 BitSet 的内容。默认状况下,所有的位都有一个默认值 false。

能够看到,跟咱们后面想的差不多

用一个 long 数组来存储,初始长度 64,set 值的时候首先右移 6 位(相当于除以 64)计算在数组的什么地位,而后更改状态位

别的看不懂不要紧,看懂这两句就够了:

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

Bloom Filters

Bloom filter 是一个数据结构,它能够用来判断某个元素是否在汇合内,具备运行疾速,内存占用小的特点。

而高效插入和查问的代价就是,Bloom Filter 是一个基于概率的数据结构:它只能通知咱们一个元素相对不在汇合内或可能在汇合内。

Bloom filter 的根底数据结构是一个 比特向量(可了解为数组)。

次要利用于大规模数据下不须要准确过滤的场景,如查看垃圾邮件地址,爬虫 URL 地址去重,解决缓存穿透问题等

如果想判断一个元素是不是在一个汇合里,个别想到的是将汇合中所有元素保存起来,而后通过比拟确定。链表、树、散列表(哈希表)等等数据结构都是这种思路,然而随着汇合中元素的减少,须要的存储空间越来越大;同时检索速度也越来越慢,检索工夫复杂度别离是 O(n)、O(log n)、O(1)。

布隆过滤器的原理是,当一个元素被退出汇合时,通过 K 个散列函数将这个元素映射成一个位数组(Bit array)中的 K 个点,把它们置为 1。检索时,只有看看这些点是不是都是 1 就晓得元素是否在汇合中;如果这些点有任何一个 0,则被检元素肯定不在;如果都是 1,则被检元素很可能在(之所以说“可能”是误差的存在)。

BloomFilter 流程

1、首先须要 k 个 hash 函数,每个函数能够把 key 散列成为 1 个整数;

2、初始化时,须要一个长度为 n 比特的数组,每个比特位初始化为 0;

3、某个 key 退出汇合时,用 k 个 hash 函数计算出 k 个散列值,并把数组中对应的比特地位为 1;

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

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>28.1-jre</version> 
</dependency>

链接地址:https://www.cnblogs.com/cjsblog/p/11613708.html

退出移动版