JAVA 位图数据结构处理

2018-11-18  本文已影响0人  无极风_amou

        以前在做项目开发过程中,曾遇到过一些布尔型数据需要存取,此类数据的值要么是false,要么是true,但数据量大,比如终端每小时的在线状态记录,用户每日签到记录等,一般采用位图数据结构来存储;
        以用户一年的签到记录为例,签了是true,没签是 false,要记录 365 天。如果使用普通的 key/value数据结构,每个用户要记录 365 个,当用户量很大的时候,存储空间是巨大的。为了解决这个问题,运用了位图这样的数据结构,这样每天的签到记录只占据一个位,365 天就是 365 个位,46 个字节就可以完全容纳下,这就大大节约了存储空间。
        以下就是位图存储的工具类代码

package com.kenny.utils;
/**
 * 
 * @类名: BitStoreUtils
 * @说明: 位图结构数据工具类
 *
 * @author: kenny
 * @Date    2018年11月13日下午7:34:48
 * 修改记录:
 *
 * @see
 */
public class BitStoreUtils {
    /**
     * 最多位数
     */
    final static Integer MAX_LEN = 65536;
    

    /**
     * 创位图数组
     * @param len 位图长度
     * @return
     * @throws Exception 
     */
    public static byte[] createBytes(int len) throws Exception{
        if (len <= 0 || len > MAX_LEN)
            throw new Exception("超出范围"); 
        
        int pos = len%8==0?len/8:len/8+1;
        byte[] bm = new byte[pos];
        return bm;
    }
    
    /**
     * 取得指定位的值 
     * @param bm  位图结构数据
     * @param position  须>0
     * @return  true/false
     */
    public static boolean get(byte[] bm, int position){
        int index = getIndex(position);
        int pos=getBitPos(position);
        
        byte b = bm[index];
        b = (byte)((b >> (7-pos)) & 0x1);
        return b==1?true:false;
    }
    
    /**
     * 设置某位为true
     * @param bm  位图结构数据
     * @param position  位置  >0
     * @param value 设置值 true/false
     */
    public static void set(byte[] bm,int position,boolean value){
        int index = getIndex(position);
        int pos=getBitPos(position);
        
        //转换为8个二进制表示字符串
        String bin = byte2Bin(bm[index]);
        
        //用valve替换原来的值
        StringBuilder sb = new StringBuilder(bin);
        sb.replace(pos,pos+1,value==true?"1":"0");
    
        //二进制转换为byte
        byte nb = bin2Byte(sb.toString());
        //更新
        bm[index]=nb;
    }
    /**
     * 统计全部true的个数
     * @param bm 位图结构数据
     * @return
     */
    public static int countTrue(byte[] bm){
        return countTrue(bm,1,bm.length*8);
    }
    
    /**
     * 统计一定范围内true的个数
     * @param bm  位图结构数据
     * @param from  开始位置  >0
     * @param to  结束位置  >0 && <=总位数
     * @return
     */
    public static int countTrue(byte[] bm,int from,int to){
        int count = 0;
        
        //处理第一个byte
        int i1 = getIndex(from);
        int p1 = getBitPos(from);
        count += countBytes(bm[i1],p1,7);
        //处理中间的n个byte
        int i2 = getIndex(to);
        int p2=getBitPos(to);
        for(int i=i1+1;i<i2;i++){
            count += countBytes(bm[i],0,7);
        }
        //处理最后一个byte
        count += countBytes(bm[i2],0,p2);
        return count;
    }
    
    /**
     * 统计全部false的个数
     * @param bm 位图结构数据
     * @param from  开始位置  >0
     * @param to  结束位置  >0 && <=总位数
     * @return
     */
    public static int countFalse(byte[] bm,int from,int to){
        return to - countTrue(bm,from,to);
    }
    
    /**
     * 首个为true 位置
     * @param bm
     * @return
     */
    public static int firstTrue(byte[] bm){
        int position = 0;
        boolean found = false;
        for(int i=0;i<bm.length;i++){
            byte b=bm[i];
            byte bits[] = new byte[8];
            for (int j = 7; j >= 0; j--) { 
                bits[j] = (byte)(b & 1);
                b = (byte) (b >> 1);
            }
            for (int k = 0; k <= 7; k++) {
                if (bits[k] == 1){
                    found = true;
                    break;
                }else{
                    position++;
                }
                
            }
            if (found)
              break;
        }
        return found?position+1:0;
    }
       /**
     * 计算每一个byte中1的个数
     * @param b
     * @param fromIndex
     * @param toIndex
     * @return
     */
    private static int countBytes(byte b,int fromIndex, int toIndex) {
        int count = 0;
        for (int i = 7; i >= 0; i--) {  
            //当前位等于1且在开始和结束 的范围内,则计数  
            if (i >= fromIndex && i <= toIndex && (byte)(b & 1) == 1){
                count++;
            }
            b = (byte) (b >> 1);  
        } 
        return count;  
    }
    
    /**
     * 取得字符 的8位二进制字符串
     * 如2,返回 00000010
     * @param b
     * @return
     */
    private static String byte2Bin(byte b) {  
        String result = "" 
                + (byte) ((b >> 7) & 0x1) + (byte) ((b >> 6) & 0x1)  
                + (byte) ((b >> 5) & 0x1) + (byte) ((b >> 4) & 0x1)  
                + (byte) ((b >> 3) & 0x1) + (byte) ((b >> 2) & 0x1)  
                + (byte) ((b >> 1) & 0x1) + (byte) ((b >> 0) & 0x1);
        return result;
    }
    /**
     * 二进制字符转byte
     * @param bin
     * @return
     */
    private static byte bin2Byte(String bin) { 
        int result, len; 
        if (null == bin) {
            return 0; 
        } 
        len = bin.length(); 
        if (len == 8){
            //第一位是0表示正数否则负数
            result = Integer.parseInt(bin, 2);
            result = bin.charAt(0) == '0'?result:result - 256;
        }else if (len == 4){
            result = Integer.parseInt(bin, 2);
        }else
            result = 0;
        return (byte) result; 
    } 
    

    /**
     * 根据位置取得第几byte (数组下标由0开始)
     * 如22则为1,24则为2
     * @param position
     * @return
     */
    private static int getIndex(Integer position){
        return position%8==0?position/8-1:position/8;
    }
    /**
     * 根据位置取得byte中第几位 (数组下标由0开始)
     * @param position
     * @return
     */
    private static Integer getBitPos(Integer position){
        //没有余数,则位于前一个字符的第7位
        return position%8==0?7:position%8-1;
    }
}

测试:

package com.kenny.utils;

public class Test {
    public static void main(String[] args) throws InterruptedException {
        byte[] b;
        try {
            b = BitStoreUtils.createBytes(365);
            System.out.println(String.format("第  %s 日签到前=%s",5,BitStoreUtils.get(b,5)));
            System.out.println(String.format("第  %s 日签到前=%s",17,BitStoreUtils.get(b,17)));
            BitStoreUtils.set(b,5,true);
            BitStoreUtils.set(b,17,true);
            System.out.println(String.format("第  %s 日签到后=%s",5,BitStoreUtils.get(b,5)));
            System.out.println(String.format("第  %s 日签到后=%s",17,BitStoreUtils.get(b,17)));
            System.out.println(String.format("签到总次数=%s",BitStoreUtils.countTrue(b)));
            System.out.println(String.format("前 %s 日签到次数=%s",10,BitStoreUtils.countTrue(b,1,10)));
            System.out.println(String.format("前 %s 日签到次数=%s",20,BitStoreUtils.countTrue(b,1,20)));
            System.out.println(String.format("前 %s 日未签到次数=%s",10,BitStoreUtils.countFalse(b,1,10)));
            System.out.println(String.format("前 %s 日未签到次数=%s",20,BitStoreUtils.countFalse(b,1,20)));
            System.out.println(String.format("首次签到是第 %s 日",BitStoreUtils.firstTrue(b)));    
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

测试结果:

第  5 日签到前=false
第  17 日签到前=false
第  5 日签到后=true
第  17 日签到后=true
签到总次数=2
前 10 日签到次数=1
前 20 日签到次数=2
前 10 日未签到次数=9
前 20 日未签到次数=18
首次签到是第 5 日
上一篇下一篇

猜你喜欢

热点阅读