关于java:牛逼哄哄的-BitMap到底强在哪里

1. 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.233G

高下立判，无需多言

那么，问题来了，如何示意一个数呢？

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

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

图片

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

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

图片

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

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，就示意存在

2. 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;  

3. BitSet

BitSet 实现了一个位向量，它能够依据须要增长。每一位都有一个布尔值。一个 BitSet 的位能够被非负整数索引（PS：意思就是每一位都能够示意一个非负整数）。能够查找、设置、革除某一位。通过逻辑运算符能够批改另一个 BitSet 的内容。默认状况下，所有的位都有一个默认值 false。另外举荐：Java 进阶视频资源

图片

图片

图片

图片

图片

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

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

别的看不懂不要紧，看懂这两句就够了：

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

4. 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>

（感激浏览，心愿对你所有帮忙)