BitMap算法及实现点赞功能

曾经终败给现在 2023-02-13 04:59 3阅读 0赞

### BitMap简介 ###

bitmap听起来是位图的意思，其实就一种基于位的映射，bitmap是一个十分有用的结构。所谓的Bit-map就是用一个bit位来标记某个元素对应的Value， 而Key即是该元素。由于采用了Bit为单位来存储数据，因此可以大大节省存储空间。

**为什么要使用bitmap？**  
举个例子，有一个无序有界int数组\{1,2,5,7\},初步估计占用内存44=16字节，这倒是没什么奇怪的；但是假如有10亿个这样的数呢，10亿4/(102410241024)=3.72G左右。如果这样的一个大的数据做查找和排序，那估计内存也崩溃了，有人说，这些数据可以不用一次性加载，那就是要存盘了，存盘必然消耗IO。

如果用BitMap思想来解决的话，就好很多。一个byte是占8个bit，如果每一个bit的值就是有或者没有，也就是二进制的0或者1，如果用bit的位置代表数组值有还是没有，那么0代表该数值没有出现过，1代表该数组值出现过。也可以描述数据。具体如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw_size_16_color_FFFFFF_t_70]  
现在假如10亿的数据所需的空间就是3.72G/32，一个占用32bit的数据现在只占用了1bit，节省了不少的空间，排序就更不用说了，一切显得那么顺利。这样的数据之间没有关联性，要是读取的，你可以用多线程的方式去读取。时间复杂度方面也是O(Max/n)，其中Max为byte\[\]数组的大小，n为线程大小。

### BitMap的映射 ###

我们使用java的int类型（总共32位）来作为基本类型，一个int能够对应32个数（一位对应一个数），然后组成一个int类型的数组，长度为n，总共能对应32\*n个数

假设需要排序或者查找的最大数MAX=10000000（lz:这里MAX应该是最大的数而不是int数据的总数！），那么我们需要申请内存空间的大小为int a\[1 + MAX/32\]。

### Java实现 ###

###### 内部元素 ######

/**
    	 * bitMap中可以加入的最大数字（范围是从0到MAX_VALUE）
    	 */
    	public static final int MAX_VALUE=10000;
    	
    	/**
    	 * 存放bitmap的数组，每个int有32位，对应32个数字
    	 */
    	private int[] a=new int[MAX_VALUE/32+1];

###### 加入 ######

/**在bitmap中加入元素n
    	 * @param n 范围为[0,MAX_VALUE]
    	 */
    	public void addValue(int n){
        
    		if(n<0||n>MAX_VALUE){
        
    			System.out.println("不再0到"+MAX_VALUE+"的范围内，不能加入");
    			return;
    		}
    		//n对应数组的哪个元素，是n/32
    		int row=n>>5;
    		//n对应的int中的位置，是n mod 32
    		int index=n & 0x1F;
    		//在n对应的int，对应的位置，置1
    		a[row] |=1<<index;				
    	}

###### 查找 ######

/**查找bitmap中是否有元素n
    	 * @param n
    	 * @return 如果存在，返回true  不存在，返回false
    	 */
    	public boolean existValue(int n){
        
    		if(n<0||n>MAX_VALUE){
        
    			System.out.println("不再0到"+MAX_VALUE+"的范围内，一定没有");
    			return false;
    		}
    		//n对应数组的哪个元素，是n/32
    		int row=n>>5;
    		//n对应的int中的位置，是n mod 32
    		int index=n & 0x1F;
    		//result为哪个位置上现在保存的值（为10000(index个0)或者0）
    		int result=a[row] & (1<<index);
    		//如果不为0，则那个位置一定为1
    		return result!=0;
    		
    	}

###### 删除 ######

/**在bitmap中删除元素n
    	 * @param n
    	 */
    	public void removeValue(int n){
        
    		if(n<0||n>MAX_VALUE){
        
    			System.out.println("不再0到"+MAX_VALUE+"的范围内，一定没有");
    			return;
    		}
    		//n对应数组的哪个元素，是n/32
    		int row=n>>5;
    		//n对应的int中的位置，是n mod 32
    		int index=n & 0x1F;
    		//对应位置0，与 111101111进行与运算，那位一定变0
    		a[row] &=~(1<<index);
    	}

###### 展示 ######

/** 展示第row行的情况，元素的二进制情况，和有的元素
    	 * @param row
    	 */
    	public void displayRow(int row){
        
    		System.out.print("bitmap展示第"+row+"行:"+Integer.toBinaryString(a[row])+" 有：");
    		//对应row：32*row到32*row+31
    		int now=row<<5;
    		//temp为与对应位进行与运算的数字
    		int temp=1;
    		for(int i=0;i<32;i++){
        
    			int result=a[row] & temp;
    			if(result!=0){
        
    				System.out.print("  "+now+"  ");
    			}
    			now++;
    			temp=temp<<1;
    		}
    		System.out.println();
    		
    	}

###### 测试 ######

package datastructure.bitmap;
     
    public class Main {
        
     
    	public static void main(String[] args) {
        
     
    		BitMap bitMap=new BitMap();
    		bitMap.addValue(0);
    		bitMap.addValue(31);
    		bitMap.displayRow(0);
    		System.out.println(bitMap.existValue(1));
    		System.out.println(bitMap.existValue(31));
    		bitMap.removeValue(0);
    		System.out.println(bitMap.existValue(0));
    		bitMap.displayRow(0);
    		
    		bitMap.addValue(34);
    		bitMap.displayRow(1);
    	}
     
    }=

### Redis使用BitMap实现点赞功能 ###

redis不仅能存储String，Hash，List，set，zset这几周数据类型，还能存储，bitmap，geo，hyperloglog，这里我们使用bitmap来作为点赞的存储结构

###### 点赞/取消点赞 ######

假设用户的数字id为1000，对照片id为100的照片点赞。首先根据照片id生成赞数据存储的redis key，比如生成策略为like\_photo:\{photo\_id\}，id为1000的用户点赞，只需要将like\_photo:100的第1000位置为1即可（取消赞则置为0）。

**redis setbit操作的时间复杂度为O(1)，所以这种点赞方式十分高效。**

redis.setbit("like_photo:100", 1000, 1);

###### 当前是否点赞 ######

用户打开图片的时候需要查询当前是否点赞过该照片，查询是否点赞可以通过redis getbit操作来实现。比如查询用户id为1000的用户是否点赞过照片id为100的照片，只需要对like\_photo:100bitmap的第1000位取值即可。

**redis getbit操作的时间复杂度同样是O(1)。**

redis.getbit("like_photo:100", 1000);

###### 查询点赞总次数 ######

比如需要显示照片id为100的照片的获赞次数，只需要对like\_photo:100bitmap进行位图计数操作即可。

**redis bitcount操作的时间复杂度虽然是O(N)的，但是大部分数据量的情况下是不需要担心bitcount效率问题的**

redis.bitcount("like_photo:100");

###### bittop ######

比如要计算同时点赞了100和101两张照片的用户，可以通过如下操作实现

redis.bitop("AND", "like_photo:100&101", "like_photo:100", "like_photo:101");

得到的like\_photo:100&101这个临时key中即是同时点赞100和101的用户bitmap.

###### 局限性 ######

这种方案虽然比较高效，实现起来也比较简单，但是也有一定的局限性。  
1.需要用户有类似于数据库自增id的数字id，当然如果你是从10000之类的开始自增的，在bitmap操作的时候可以统一将用户id减掉10000，这样可以稍微节省一些redis内存占用；  
2.当用户量很大的时候，比如千万级用户量的情况下，一个用户的bitmap需要消耗的内存为：10000000/8/1024/1024=1.19MB，当bitmap数量较多的时候，内存占用还是很可观的。不过在用户量较少的时候这种方案还是不错的  
**我这里测试使用八位数千万级别的id=28000000设置到bitmap里面，然后dump出了redis的rdb文件如下：**  
![在这里插入图片描述][20200527162343671.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200527155505386.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw,size_16,color_FFFFFF,t_70
[20200527162343671.png]: https://img-blog.csdnimg.cn/20200527162343671.png