数据库开始用位图吧
前言
Github：https://github.com/HealerJean
1、位图的简单计算
1.1、增&删&查
package com.hlj.util.Z005BitSet;
import lombok.extern.slf4j.Slf4j;
/**
* @author zhangyujin
* @date 2022/6/30 18:02.
*/
@Slf4j
public class StatusEnums {
private final static long INIT = 1L << 0;
private final static long CHSI_VERIFY = 1L << 1;
private final static long GRADUATE = 1L << 2;
static {
System.out.println(Long.toBinaryString(INIT));
System.out.println(Long.toBinaryString(CHSI_VERIFY));
System.out.println(Long.toBinaryString(GRADUATE));
System.out.println();
}
/**
* 是否包含状态
*
* @param holder 当前状态
* @param position 标志位状态
* @return
*/
public static boolean hasStatus(long holder, long position) {
return (holder & position) == position;
}
/**
* 添加状态
*
* @param holder 当前状态
* @param position 添加状态标志位
* @return 新状态
*/
public static long addStatus(long holder, long position) {
if (hasStatus(holder, position)) {
return holder;
}
return holder | position;
}
/**
* 移除状态
*
* @param holder 当前状态
* @param position 移除状态标志位
* @return 新状态
*/
public static long removeStatus(long holder, long position) {
if (!hasStatus(holder, position)) {
return holder;
}
//异或移除
return holder ^ position;
}
public static void main(String[] args) {
long holder = 7L;
System.out.println(Long.toBinaryString(holder));
//0111
System.out.println(StatusEnums.hasStatus(holder, INIT));
// true -> 0001 在 0111 中
System.out.println(StatusEnums.hasStatus(holder, CHSI_VERIFY));
// true -> 0010 在 0111 中
System.out.println(StatusEnums.hasStatus(holder, GRADUATE));
// tuue -> 0100 在 0111 中
holder = StatusEnums.removeStatus(holder, INIT);
holder = StatusEnums.removeStatus(holder, CHSI_VERIFY);
holder = StatusEnums.removeStatus(holder, GRADUATE);
System.out.println(Long.toBinaryString(holder));
//0000
System.out.println(StatusEnums.hasStatus(holder, INIT));
// false -> 0001 不在 0111 中
System.out.println(StatusEnums.hasStatus(holder, CHSI_VERIFY));
// false -> 0010 不在 0111 中
System.out.println(StatusEnums.hasStatus(holder, GRADUATE));
// false -> 0100 不在 0111 中
}
}
1.2、模拟签到
package com.hlj.util.Z005BitSet;
import java.util.*;
/**
* @author zhangyujin
* @date 2022/6/30 18:15.
*/
public class Sign {
//int最多可以容纳32位，0b表示需jdk1.8+支持,左边第一位永远为0，即正整数，无日期含义；右边31位表示日期，从左到右1-31天
private final static int monthSignRecord = 0b01111111111111111111111111111000;
private final static int DAY28 = 0x7ffffff8;
private final static int DAY29 = 0x7ffffffc;
private final static int DAY30 = 0x7ffffffe;
private final static int DAY31 = 0x7fffffff;
private final static int MONTH_MODEL = 0x40000000;
private final static Calendar CALENDAR = Calendar.getInstance(Locale.CHINA);
/**
* 签到总数
*
* @param holder 签到记录
* @return
*/
public static int signCount(int holder) {
return Integer.bitCount(holder);
}
/**
* 获取指定月是否全签到
*
* @param holder 签到记录
* @return
*/
public static boolean isSignFullInFixedMonth(int holder, int month) {
CALENDAR.set(Calendar.MONTH, month - 1);
int days = CALENDAR.getActualMaximum(Calendar.DATE);
switch (days) {
case 28:
return (holder & DAY28) == DAY28;
case 29:
return (holder & DAY29) == DAY29;
case 30:
return (holder & DAY30) == DAY30;
case 31:
return (holder & DAY31) == DAY31;
}
throw new IllegalArgumentException("month is illegal");
}
/**
* 获取指定月漏签次数
*
* @param holder 签到记录
* @return
*/
public static int unSignCountInFixedMonth(int holder, int month) {
CALENDAR.set(Calendar.MONTH, month - 1);
return CALENDAR.getActualMaximum(Calendar.DATE) - Integer.bitCount(holder);
}
/**
* 指定天是否签到
*
* @param holder 当前签到标识
* @param position 签到天标识位
* @return
*/
public static boolean isSignInFixedDay(int holder, int position) {
return (holder & position) == position;
}
/**
* 按照天签到
*
* @param holder 当前签到标识
* @param position 签到天标识位
* @return 新签到标识
*/
public static int signInFixedDay(int holder, int position) {
if (isSignInFixedDay(holder, position)) {
return holder;
}
return holder | position;
}
/**
* 批量签到，适合补签场景
*
* @param holder 当前签到标识
* @param days 批量签到序号
* @return 新签到标识
*/
public static int batchSign(int holder, List<Integer> days) {
Iterator<Integer> it = days.iterator();
while (it.hasNext()) {
holder = holder | getPosition(it.next());
}
return holder;
}
public static int getPosition(int position) {
//0b01000000000000000000000000000000 == 0x40000000 左边第一位永远为0，即正整数，无日期含义；右边31位表示日期，从右到左1-31天
return MONTH_MODEL >>> (position - 1);
}
public static void main(String[] args) {
int month = 5;
System.out.printf("签到记录：【%s】 %n", Integer.toBinaryString(monthSignRecord));
// 签到记录：【1111111111111111111111111111000】
System.out.printf("签到总数：【%d】 %n", signCount(monthSignRecord));
// 签到总数：【28】
System.out.printf("%d月漏签总数 %d %n", month, unSignCountInFixedMonth(monthSignRecord, month));
// 4月漏签总数 2
System.out.printf("全月是否全部签到 %b %n", isSignFullInFixedMonth(monthSignRecord, month));
// 全月是否全部签到 false
System.out.printf("签到前【%s】%n", Integer.toBinaryString(monthSignRecord));
// 签到前【1111111111111111111111111111000】
int signTemp = signInFixedDay(monthSignRecord, getPosition(30));
signTemp = signInFixedDay(signTemp, getPosition(31));
System.out.printf("签到后【%s】%n", Integer.toBinaryString(signTemp));
// 签到后【1111111111111111111111111111011】
System.out.printf("全月是否全部签到 %b %n", isSignFullInFixedMonth(signTemp, month));
// 全月是否全部签到 false
System.out.printf("批量签到前【%s】%n", Integer.toBinaryString(monthSignRecord));
// 批量签到前【1111111111111111111111111111000】
int signBatch = batchSign(monthSignRecord, Arrays.asList(29, 30, 31));
System.out.printf("批量签到后【%s】%n", Integer.toBinaryString(signBatch));
// 批量签到后【1111111111111111111111111111111】
System.out.printf("全月是否全部签到 %b %n", isSignFullInFixedMonth(signBatch, month));
// 全月是否全部签到 true
}
}
2、数据库使用
2.1、场景用例
查询所有支持快递物流的商家（物流方式包括 快递 上门 地铁）
2.1.1、传统的方式
1、数据库使用逗号分隔字符串，通过
find_in_set进行查询2、快递：1、快递+上门：3、快递 + 上门 + 地铁 ： 7，通过 select * from ^ in (1, 3, 7 ……)
2.1.2、位图方式
2.2、存储方式
左边第一位永远为
0，可以使用varchar()存储
CREATE TABLE `test`
(
`id` bigint unsigned NOT NULL AUTO_INCREMENT COMMENT '主键',
`status` varchar(32) NOT NULL COMMENT '产品状态 字典表 productstatus',
`update_user` bigint unsigned DEFAULT '0' COMMENT '更新人',
PRIMARY KEY (`id`) USING BTREE
) COMMENT ='测试表';
insert into test
(`status`,
`create_name`,
`update_user`)
values (1, 2, 3, '0101', 4, 5, 7, 9);
select LPAD(t.status & 0110, 4, '0') as '与运算' from test t;
# 0100
select LPAD(t.status | 0110, 4, '0') as '或运算' from test t;
# 0111
select LPAD(t.status ^ 0110, 4, '0') as '异或运算' from test t;
# 0011
3、BigMap 简单样例
3.1、样例
public class BitMap {
/**
* 用 byte 数组存储数据
*/
private byte[] bits;
/**
* 指定 bitMap的长度
*/
private int bitSize;
/**
* bitmap构造器
*
* @param bitSize bitSize
*/
public BitMap(int bitSize) {
this.bitSize = (bitSize >> 3) + 1;
//1byte 能存储8个数据，那么要存储 bitSize的长度需要多少个bit呢，bitSize/8+1,右移3位相当于除以8
bits = new byte[(bitSize >> 3) + 1];
}
/**
* 在bitmap中插入数字
*
* @param num
*/
public void add(int num) {
// num/8得到byte[]的index
int arrayIndex = num >> 3;
// num%8得到在byte[index]的位置
int position = num & 0x07;
//将1左移position后，那个位置自然就是1，然后和以前的数据做|，这样，那个位置就替换成1了。
bits[arrayIndex] |= 1 << position;
}
/**
* 判断bitmap中是否包含某数字
*
* @param num
* @return
*/
public boolean contain(int num) {
// num/8得到byte[]的index
int arrayIndex = num >> 3;
// num%8得到在byte[index]的位置
int position = num & 0x07;
//将1左移position后，那个位置自然就是1，然后和以前的数据做&，判断是否为0即可
return (bits[arrayIndex] & (1 << position)) != 0;
}
/**
* 清除bitmap中的某个数字
*
* @param num
*/
public void clear(int num) {
// num/8得到byte[]的index
int arrayIndex = num >> 3;
// num%8得到在byte[index]的位置
int position = num & 0x07;
//将1左移position后，那个位置自然就是1，然后对取反，再与当前值做&，即可清除当前的位置了.
bits[arrayIndex] &= ~(1 << position);
}
/**
* 打印底层bit存储
*
* @param bitMap
*/
public static void printBit(BitMap bitMap) {
int index = bitMap.bitSize & 0x07;
for (int j = 0; j < index; j++) {
System.out.print("byte[" + j + "] 的底层存储：");
byte num = bitMap.bits[j];
for (int i = 7; i >= 0; i--) {
System.out.print((num & (1 << i)) == 0 ? "0" : "1");
}
System.out.println();
}
}
/**
* 输出数组元素，也可以使用Arrays的toString方法
*
* @param arr
*/
private static void printArray(int[] arr) {
System.out.print("数组元素：");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
4、总结
4.1、BitMap 的特点
1、针对海量数据的存储，可以极大的节约存储成本！当需要存储一些很大，且无序，不重复的整数集合，那使用Bitmap的存储成本是非常低的。
2、 因为其天然去重的属性，对于需要去重存储的数据很友好！因为bitmap 每个值都只对应唯一的一个位置，不能存储两个值，所以 Bitmap 结构天然适合做去重操作。
3、 同样因为其下标的存在，可以快速定位数据！比如想判断数字 ` 99999 是否存在于该 bitmap中，若是使用传统的集合型存储，那就要逐个遍历每个元素进行判断，时间复杂度为 O(N)。而由于采用 Bitmap存储，只要查看对应的下标数的值是0还是1即可，时间复杂度为 O(1)。所以使用 bitmap可以非常方便快速的查询某个数据是否在bitmap`中。
4、 还有因为其类集合的特性，对于一些集合的交并集等操作也可以支持！比如想查询[1,2,3]与[3,4,5] 两个集合的交集，用传统方式取交集就要两层循环遍历。而 Bitmap实现的底层原理，就是把 01110000 和 00011100 进行与操作就行了。而计算机做与、或、非、异或等等操作是非常快的。
4.2、缺点
虽然bitmap有诸多好处，但是正所谓人无完人，它也存在很多缺陷。
1、 只能存储正整数而不能是其他的类型；
2、不适合存储稀疏的集合，简单理解，一个集合存放了两个数[1,99999999]，那用bitmap存储的话就很不划算，这也与它本来节约存储的优点也背离了；
3、不适用于存储重复的数据。
4.3、BitMap的优化
既然
bitmap的优点如此突出，那应该如何去优化它存在的一些局限呢？
1、 针对存储非正整数的类型，如字符串类型的，可以考虑将字符串类型的数据利用类似hash的方法，映射成整数的形式来使用bitmap，但是这个方法会有hash冲突的问题，解决这个可以优化hash方法，采用多重hash来解决，但是根据经验，这个效果都不太好，通常的做法就是针对字符串建立映射表的方式。
2、针对bitmap的优化最核心的还是对于其存储成本的优化，毕竟大数据领域里面，大多数时候数据都是稀疏数据，而我们又经常需要使用到 bitmap 的特长，比如去重等属性，所以存在一些进一步的优化，比较知名的有WAH、EWAH、RoaringBitmap等，其中性能最好并且应用最为广泛的当属RoaringBitmap
