Bitmap 算法

目录

Bitmap 算法

1、什么是Bitmap算法

2、基本思想

3、如何如何确定10进制数到二进制的转换

4、代码实现

 

1、什么是Bitmap算法

所谓的BitMap就是用一个bit位来标记某个元素所对应的value，而key即是该元素，由于BitMap使用了bit位来存储数据，因此可以大大节省存储空间。

2、基本思想

首先用一个简单的例子来详细介绍BitMap算法的原理。假设我们要对1-8内的5个元素(5,6，8,1)进行排序(这里假设元素没有重复)。我们可以使用BitMap算法达到排序目的。要表示8个数，我们需要8个byte。


	
首先我们开辟一个字节(8byte)的空间，将这些空间的所有的byte位都设置为0
	
	

	
然后便利这5个元素，第一个元素是4，因为下边从0开始，因此我们把第五个字节的值设置为1
	
	

	
然后再处理剩下的四个元素，最终8个字节的状态如下图
	
1
			
0
			
0
			
0
			
1
			
1
			
0
			
1
		
要达到排序的目的：接下来我们只需要从左到右遍历一次数组，便可得到排序序列（1,5,6,8）。

3、如何如何确定10进制数到二进制的转换

（1）MAP映射：

假设需要排序或则查找的数的总数N=100000000，BitMap中1bit代表一个数字，1个int = 4Bytes = 4*8bit = 32 bit,那么N个数需要N/32 int空间。所以我们需要申请内存空间的大小为int a[1 + N/32]，其中：a[0]在内存中占32为可以对应十进制数0-31，依次类推：

a[0]  对应  0-31

a[1]  对应  32-63

a[2]  对应  64-95

a[3]  对应  96-127

以此类推

（2）用位移将十进制数转换为对应的bit位

1、求十进制数在对应数组a中的下标

十进制数0-31，对应在数组a[0]中，32-63对应在数组a[1]中，64-95对应在数组a[2]中………，使用数学归纳分析得出结论：对于一个十进制数n，其在数组a中的下标为：a[n/32]

2、求出十进制数在对应数a[i]中的下标

例如十进制数1在a[0]的下标为1，十进制数31在a[0]中下标为31，十进制数32在a[1]中下标为0。 在十进制0-31就对应0-31，而32-63则对应也是0-31，即给定一个数n可以通过模32求得在对应数组a[i]中的下标。

3、位移

对于一个十进制数n,对应在数组a[n/32][n%32]中，但数组a毕竟不是一个二维数组，我们通过移位操作实现置1

a[n/32] |= 1 << n % 32

​ 移位操作：

　　a[n>>5] |= 1 << (n & 0x1F)

n & 0x1F 保留n的后五位 相当于 n % 32 求十进制数在数组a[i]中的下标

4、代码实现

public class BitMap {

    private static final int N = 10000000;

    private int[] a = new int[N/32 + 1];

    /**
     * 设置所在的bit位为1
     * @param n
     */
    public void addValue(int n){
        //row = n / 32 求十进制数在数组a中的下标
        int row = n >> 5;
        //相当于 n % 32 求十进制数在数组a[i]中的下标
        a[row] |= 1 << (n & 0x1F);
    }

    // 判断所在的bit为是否为0 
    public boolean exits(int n){
        int row = n >> 5;
        return (a[row] & ( 1 << (n & 0x1F))) != 0;
    }

    public void display(int row){
        System.out.println("BitMap位图展示");
        for(int i=0;i<row;i++){
            List<Integer> list = new ArrayList<Integer>();
            int temp = a[i];
            for(int j=0;j<32;j++){
                list.add(temp & 1);
                temp >>= 1;
            }
            System.out.println("a["+i+"]" + list);
        }
    }

    public static void main(String[] args){
        //int num[] = {1,5,30,32,64,56,159,120,21,17,35,45};
        int num[] = {4,7}
        BitMap map = new BitMap();
        for(int i=0;i<num.length;i++){
            map.addValue(num[i]);
        }

        int temp = 4;
        if(map.exits(temp)){
            System.out.println("value:[" + temp + "] has already exists");
        }
        map.display(3);
    }
}

运行结果：

value:[4] has already exists
BitMap位图展示
a[0][0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
a[1][0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
a[2][0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 

所谓的BitMap就是用一个bit位来标记某个元素所对应的value，而key即是该元素，由于BitMap使用了bit位来存储数据，因此可以大大节省存储空间。

 

1. 基本思想

假设我们要对0-7内的5个元素(4,7,2,5,3)进行排序(这里假设元素没有重复)。我们可以使用BitMap算法达到排序目的。

7<2^3所以我们需要8个byte（这里我们使用int（32 bit)。


	
首先我们初始化一个int
	
	

	
然后便利这5个元素，第一个元素是4，因为下边从0开始，因此我们把第五个字节的值设置为1
	
	

	
然后再处理剩下的四个元素，最终前8个字节的状态如下图
	


这样便达到了排序的目的

从上面的例子可以看出，BitMap算法的思想还是比较简单的，关键的问题是如何确定10进制数到二进制的转换

MAP映射：

我们接着用int数组为例

　 a[0]-----------------------------> 0-31 bit

　　a[1]------------------------------> 32-63 bit

　　a[2]-------------------------------> 64-95 bit

　　a[3]--------------------------------> 96-127 bit

　　......................................................

那么十进制数如何转换为对应的bit位，下面介绍用位移将十进制数转换为对应的bit位:

　　1.求十进制数在对应数组a中的下标

因为每个int对应32个bit，所以可得下标为n/32 =》a[n/32]

　　2.求出十进制数在对应数a[i]中的下标

　　通过模32求得在对应数组a[i]中的下标，即n%32。

　　3.位移

　　对于一个十进制数n,对应在数组a[n/32][n%32]中，但数组a毕竟不是一个二维数组，我们通过移位操作实现置1

　　a[n/32] |= 1 << n % 32

　　

​ 移位操作：

　　a[n>>5] |= 1 << (n & 0x1F)

　　n & 0x1F 保留n的后五位 相当于 n % 32 求十进制数在数组a[i]中的下标

应用范围: 可以运用在快速查找、去重、排序、压缩数据等。

例题： 力扣41. 缺失的第一个正数

给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。

 

示例 1:

输入: [1,2,0]

输出: 3

示例 2:

输入: [3,4,-1,1]

输出: 2

示例 3:

输入: [7,8,9,11,12]

输出: 1

 

提示：

你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。

普通解法

class Solution {
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        int[] vis = new int[len+2];
        for( int i = 0; i < len ; i++){
            if(nums[i]>=1 & len>=nums[i])
                vis[nums[i]] = 1;
        }
        for( int i = 1; i <= len+1; i++)
            if(vis[i] == 0)
                return i;
        return 1;
    }
}

Bitmap解法

官方题解

 

 

本文参考：Bitmap 算法解释与应用

概念
BitMap 就是用一个 bit 位来标记某个key对应的 value。由于采用bit为单位来存储数据，因此在可以大大的节省存储空间。
使用场景
bitmap排序
假设我们要对5个不重复的数（4，7，2，5，3）排序。

确定最大值是7，数值范围是0~7，共8个数，需要8bit，即1字节。
此时8个字节与集合中的数的对应关系为：

00010000 ： 4
10000000 ： 7
00000100 ： 2
00100000 ： 5
00001000 ： 3

所以最终8个bit的结果为10111100，遍历这8bit，所以排序结果为（7，5，4，3，2）。

bitmap排序只有在数据比较密集的时候才会有有其优势，很多情况下并不适用。比如对（1，1000，10万）这种数据集排序就很不合适。

bitmap查找

找出10亿个数字中是否存在某个值

使用bitmap+布隆过滤器，布隆过滤器可以看笔者另一篇文章 布隆过滤器简介
bitmap去重

已知某个文件内包含很多电话号码，每个号码为8个数字，统计不同号码的个数。

8位最多99999999,占用100,000,000个bit,大小为12MB，这样用12M内存就表示来所有8位数的电话。
bitmap查重

10亿个整数中找出不重复的整数的个数，内存空间不足以同时容纳这10亿个整数。

将bitmap扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出现2次及以上。

在遍历这些数的时候，如果对应位置的值是0，则将其置为1；如果是1，将其置为2；如果是2，则保持不变。

中文：位图算法

参考博客： 
漫画：什么是Bitmap算法？