一、使用的场景

日常业务中需要大量存储一些重复的字符串，例如每日签到用户、朋友圈点赞的好友、计算每日登录用户等。字符串无论长短不仅会浪费大量的存储资源，而且读取查询也耗时耗资源，那有没有一种存储方式对这一类场景进行优化呢。

二、什么原理

1、Bitmap如何解决这个问题

拿每日签到用户的场景举例，首先对用户id进行编号(offset)。

图1.png

这样我们只需要每天创建一个只存储位的数组，比如2023-12-8日只有zhangsan和zhaoliu进行了登录，我们只需要一个4位的字节数组来进行存储：

图2.png
这样就达到了减少存储的目的。

2、压缩Bitmap是如何做到压缩的

然而现实的场景中，存储的数据并不是连续的，而是稀疏的，而且创建Bitmap的时候，长度必须是最大的offset的长度，例如我们有64个用户，那么创建的位数组就是64位。
假如我们有1万个用户，但今天只有编号9999的用户登录了系统，那我们还是创建一个1万个Byte的数组，反而增加了内存的消耗。
为了更容易理解这个问题，我们还是以64位Bitmap为例，也就是最大支持存储64个用户，当我们只存储63时：

图3.png

先创建了长度为64位的数组，只在63这个位置上的存储是有意义的，其他位置都是0，那这种情况是不是可以进行优化呢？
我们把数组拆分成2组，1到32的用户存储到第1组，把33到64的用户存储到第二组。这个时候我们发现第一组的数组里全是0，那第一组是不是可以不创建？这样我们就用一个32位大小的数组存储了64位的数据。
接下来更进一步，把64位的数组拆成每16个一组，那么我们只需要创建最后一个分组的数组，也就是16位的数组来达到进一步压缩的目的。
第4组

图4.png 未命名流程图.jpg

三、怎么模拟实现

代码来简单的模拟实现压缩Bitmap

1、先创建一个类累存储单个的Bitmap

public class ArrayContainer {
    public char[] values;

    public ArrayContainer(int initialCapacity) {
        this.values = new char[initialCapacity];
    }
}

2、实现压缩Bitmap的逻辑

public class CompressedBitmap {
    public static final char Y = 1;
    public static final char N = 0;
    public static final int ARRAY_CONTAINER_SIZE = 16;

    ArrayContainer[] containers;

    public CompressedBitmap(long initialCapacity) {
        int containersSize = (int)(initialCapacity / ARRAY_CONTAINER_SIZE);
        this.containers = new ArrayContainer[containersSize];
    }

    public void add(long offset){
        int shardIndex = getShardIndex(offset);
        ArrayContainer container = containers[shardIndex];
        if(container == null){
            container = new ArrayContainer(ARRAY_CONTAINER_SIZE);
        }

        int shardOffset = getShardOffset(offset);
        container.values[shardOffset] = Y;
        containers[shardIndex] = container;
    }

    public int get(long offset){
        int shardIndex = getShardIndex(offset);
        ArrayContainer container = containers[shardIndex];
        if(container == null){
            return N;
        }

        int shardOffset = getShardOffset(offset);
        if(Y == container.values[shardOffset]){
            return Y;
        }
        return N;
    }

    public int getShardIndex(long offset){
        return (int)((offset - 1) / ARRAY_CONTAINER_SIZE);
    }

    public int getShardOffset(long offset){
        return (int)(offset % ARRAY_CONTAINER_SIZE);
    }

    public static void main(String[] args) {
        System.out.println(2 / ARRAY_CONTAINER_SIZE);
    }
}

3、测试使用

public static void main(String[] args) {
        CompressedBitmap bitmap = new CompressedBitmap(64);
        bitmap.add(63);
        System.out.println(bitmap.get(63));
        System.out.println(bitmap.get(64));
        System.out.println(bitmap.get(2));
 }

四、Redis实现压缩Bitmap存储

Redis本身是支持Bitmap存储的，但是压缩的Bitmap是不支持的。根据上面的原理，同样可以把一个大的Bitmap转成一个个小的Bitmap来达到压缩的目的。

1、包装实体保存压缩位图的信息

public class CompressedBitInfo implements Serializable {

    /**
     * 真实offset
     */
    private long sourceOffset;
    /**
     * 分桶的编号
     */
    private long bucketIndex;
    /**
     * 桶内的offset
     */
    private long bucketOffset;

    public long getSourceOffset() {
        return sourceOffset;
    }

    public void setSourceOffset(long sourceOffset) {
        this.sourceOffset = sourceOffset;
    }

    public long getBucketIndex() {
        return bucketIndex;
    }

    public void setBucketIndex(long bucketIndex) {
        this.bucketIndex = bucketIndex;
    }

    public long getBucketOffset() {
        return bucketOffset;
    }

    public void setBucketOffset(long bucketOffset) {
        this.bucketOffset = bucketOffset;
    }

    @Override
    public String toString() {
        return "CompressedBitInfo{" + "sourceOffset=" + sourceOffset + ", bucketIndex=" + bucketIndex + ", bucketOffset=" + bucketOffset + '}';
    }
}

2、工具类计算每个小桶的Bitmap

public class CompressedBitTookit {
    public static final long DEFAULT_BUCKET_SIZE = 65536L;

    public static CompressedBitInfo getBitInfo(long sourceOffset, long bucketSize) {
        CompressedBitInfo bucketInfo = new CompressedBitInfo();
        bucketInfo.setSourceOffset(sourceOffset);
        long bucketIndex = sourceOffset / bucketSize;
        long bucketOffset = sourceOffset % bucketSize;
        bucketInfo.setBucketIndex(bucketIndex);
        bucketInfo.setBucketOffset(bucketOffset);
        return bucketInfo;
    }
    public static CompressedBitInfo getBitInfo(long sourceOffset) {
        CompressedBitInfo bucketInfo = getBitInfo(sourceOffset, DEFAULT_BUCKET_SIZE);
        return bucketInfo;
    }

    public static long getSourceOffset(long bucketIndex, long bucketSize, long bucketOffset) {
        return bucketIndex * bucketSize + bucketOffset;
    }
    public static long getSourceOffset(long bucketIndex,  long bucketOffset) {
        return getSourceOffset(bucketIndex, DEFAULT_BUCKET_SIZE, bucketOffset);
    }

3、读写Bitmap

public void setCompressedBit(String key, long offset, boolean value, int expireSeconds) {
        CompressedBitInfo bitInfo = CompressedBitTookit.getBitInfo(offset);
        String bitKey = getBitKey(key, bitInfo.getBucketIndex());
        redis.setBit(bitKey, bitInfo.getBucketOffset(),value);
        redis.expire(bitKey, expireSeconds);
    }

    
    public void setCompressedBit(String key, long offset, boolean value) {
        CompressedBitInfo bitInfo = CompressedBitTookit.getBitInfo(offset);
        String bitKey = getBitKey(key, bitInfo.getBucketIndex());
        redis.setBit(bitKey, bitInfo.getBucketOffset(),value);
    }

    
    public void setCompressedBit(String key, long offset) {
        this.setCompressedBit(key, offset, true);
    }


    
    public void remCompressedBit(String key, long offset) {
        this.setCompressedBit(key, offset, false);
    }

    
    public Boolean getCompressedBit(String key, long offset) {
        CompressedBitInfo bitInfo = CompressedBitTookit.getBitInfo(offset);
        String bitKey = getBitKey(key, bitInfo.getBucketIndex());
        log.debug("getCompressedBit with key:{}, offset:{}",bitKey, bitInfo.getBucketOffset());
        return redis.getBit(bitKey, bitInfo.getBucketOffset());
    }

    
    public void deleteAllCompressedBit(String key, long maxOffset) {
        CompressedBitInfo bitInfo = CompressedBitTookit.getBitInfo(maxOffset);
        for (int i = 0; i < bitInfo.getBucketIndex(); i++) {
            String bitKey = getBitKey(key, i);
            redis.expire(bitKey, 0);
        }
    }

    private String getBitKey(String key, long bucketIndex) {
        return new StringBuffer(key).append("_").append(bucketIndex).toString();
    }