简单谈谈BitMap

Briefly talk about BitMap

Posted by if on 2021-12-24
Estimated Reading Time 7 Minutes
Words 1.6k In Total

简单谈谈BitMap

前言

对比——bitmap的使用与否

在咱们之前的储存结构里,需要O(1)复杂度进行查找时,我们一般习惯于用HashMap或者HashSet

如果我们想要储存一个int类型的数据,那么一个数据需要占据4个字节

若是想存储一个long类型的数据,那么一个数据需要占据8个字节

当数据非常大时,使用HashMap的情况下,内存可能撑不住

假设当有10亿个long类型的数据需要去重或者查询某个数据是否在其中时

这些数据一共需要 1000000000*8 个字节的数据,也就是**7629MB**,即约**7.45个G**的内存

如果我们将每一个数据都使用一个bit去储存呢?

10亿bit就是1000000000/8个字节的数据,也就是**119MB,即约0.12G**的内存

可以显著地看见,同样的数据量的情况下,使用bit存储比字节存储节省了约64倍的空间

为什么能节省这么多倍的空间呢?

因为long类型占8个字节,1个字节为8个bit,所以一个long类型占用64个bit

使用bit后,一个long数据只用1个bit存储,所以节省了64倍

复习——位运算符

&与运算

当上下位都为1时才为1,有任何不同则为0

1 1 1 0 0 1

&

0 1 0 0 1 0

=

0 1 0 0 0 0

|或运算

上下位存在至少一个1则为1,都为0时才为0

1 1 1 0 0 1

&

0 1 0 0 1 0

=

1 1 1 0 1 1

~非运算

非运算即取反运算,在二进制中1变0,0变1

~ 1 1 1 0 0 1

=

0 0 0 1 1 0

bitmap简介

下文的图片和文字来源于https://www.cnblogs.com/cjsblog/p/11613708.html

Bit-map的基本思想就是用一个bit位来标记某个元素对应的Value,而Key即是该元素。

由于采用了Bit为单位来存储数据,因此非常节省存储空间

Bitmap主要用于快速检索关键字状态

如何用bitmap表示一个数呢?

每一位表示一个数,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位,然后按位或

换成二进制就是

因此,公式可以概括为:p + (i/8)|(1<<(i%8)) 其中,p表示现在的值,i表示待插入的数

移除元素

假设我们要6移除,该怎么做呢

只需将该数所在的位置为0即可

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

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

查找元素是否存在

前面我们也说了,每一位代表一个数字,1表示有(或者说存在),0表示无(或者说不存在)。

通过把该为置为1或者0来达到添加和清除的效果,那么判断一个数存不存在就是判断该数所在的位是0还是1

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

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
public class MyBitSetTest {

public static void main(String[] args) {
MyBitSet myBitSet=new MyBitSet();

long now1 = System.currentTimeMillis();
for (int i = 1; i <= 2000000000; i++) {
myBitSet.add(i);
}
System.out.println("myBitSet.exists(150) = " + myBitSet.exists(150));
System.out.println("myBitSet.exists(400) = " + myBitSet.exists(400));

System.out.println("myBitSet.remove(150) = " + myBitSet.remove(150));
System.out.println("myBitSet.exists(150) = " + myBitSet.exists(150));
System.out.println("myBitSet.remove(2000) = " + myBitSet.remove(2000));
System.out.println("myBitSet.exists(2000) = " + myBitSet.exists(2000));
long now2 = System.currentTimeMillis();
System.out.println("now2 - now1 = "+(now2-now1)/1000 +"秒处理完成");

}

private static class MyBitSet {
//每个值有64位,即64个数据
private int bigNum=64;
//64是2的6次方,num>>er 表示num/64
private int er = 6;
//初始化大小为两个数组,可以放128个数据后再扩容
private int size;
//扩容大小,默认一倍
private int cap;
//long型8字节,64位,需要和bigNum对应
private long[] array;

public MyBitSet() {
this.size=2;
this.cap=1;
this.array=new long[size];
}
public MyBitSet(int size) {
if(size<1)throw new IllegalArgumentException("The 'size' can not be less than 1");
this.size = size;
this.cap=1;
this.array=new long[size];
}
public MyBitSet(int size, int cap) {
if(size<1||cap<1)throw new IllegalArgumentException("The 'size' or 'cap' can not be less than 1");
this.size = size;
this.cap = cap;
this.array=new long[size];
}

public boolean add(long num){
if(num<0)return false;
int arrayIndex = getArrayIndex(num);
if(arrayIndex>=size){
resize();
}
int itemIndex = getItemIndex(num);
array[arrayIndex] = (array[arrayIndex] | (1<<itemIndex));
return true;
}
public boolean remove(long num){
int arrayIndex = getArrayIndex(num);
if(num<0||arrayIndex>=size)return false;
int itemIndex = getItemIndex(num);
array[arrayIndex] = array[arrayIndex] & ~(1<<itemIndex);
return true;
}

public boolean exists(long num){
int arrayIndex = getArrayIndex(num);
if(num<0||arrayIndex>=size)return false;
int itemIndex = getItemIndex(num);
return (array[arrayIndex] & (1<<itemIndex)) != 0;
}

private int getArrayIndex(long num){
return (int)num >> er;
}
private int getItemIndex(long num){
return (int)num%bigNum;
}
private void resize(){
size<<=cap;
long[] newArray=new long[size];
System.arraycopy(array, 0, newArray, 0, array.length);
array=newArray;
}
}
}

结果

myBitSet.exists(150) = true
myBitSet.exists(400) = true
myBitSet.remove(150) = true
myBitSet.exists(150) = false
myBitSet.remove(2000) = true
myBitSet.exists(2000) = false
now2 - now1 = 9秒处理完成


本个人博客提供的内容仅用于个人学习,不保证内容的正确性。通过使用本站内容随之而来的风险与本站无关!