位图

1、引言

　　位图是使用位（bit）数组来对数据进行统计，排序和去重，其结构图如下：

　　　　

　　其中位图的索引映射需要存储的值，位图索引所在位置的值表示索引对应的值是否已经存储。

2、接口

 1 public interface ByteMap {
 2 
 3     /* get the value in the index of byte map
 4      * @param index the index in byte map to get 
 5      * @return 1 or 0 base the value in the index of byte map
 6      */
 7     int getByte(int index);
 8     
 9     /* set the value in the index of byte map
10      * @param index the index in byte map to set
11      * @param flag the value setted in the index of byte map
12      */
13     void setByte(int index, int flag);
14     
15     /* set the value in byte map from start to end
16      * @param start the start index in byte map
17      * @param end the end index in byte map
18      * @flag the value setted in byte map from start to end
19      */
20     void setByte(int start, int end, int flag);
21     
22     /*
23      * get the size of byte map
24      */
25     int getSize();
26     
27     /*
28      * set the size of byte map
29      * @param size to be setted
30      */
31     void setSize(int size);
32     
33     /*
34      * count how many 1 in byte map
35      */
36     int countOne();
37     
38     /*
39      * count how many i in byte map from start to end
40      */
41     int countOne(int start, int end);
42     
43     /*
44      * get the sub map of byte map from start to end
45      */
46     ByteMap subMap(int start, int end);
47     
48     /*
49      * flip the value in byte map 
50      */
51     ByteMap not();
52     
53     /*
54      * or operation with another byte map
55      */
56     ByteMap or(ByteMap byteMap);
57     
58     /*
59      * xor operation with another byte map
60      */
61     ByteMap xor(ByteMap byteMap);
62     
63     /*
64      * and operation with another byte map
65      */
66     ByteMap and(ByteMap byteMap);
67     
68     /*
69      * byte map left shift operation
70      */
71     ByteMap leftShift(int shiftStep);
72     
73     /*
74      * byte map right shift operation
75      */
76     ByteMap rightShift(int shiftStep);
77 }

 3、实现

　　定义静态byte数组常量，用于快速检验位图上索引对应的值：

 1 private static final byte[] BYTE_VALUE = {
 2         0x0001,
 3         0x0002,
 4         0x0004,
 5         0x0008,
 6         0x0010,
 7         0x0020,
 8         0x0040,
 9         -0x0080
10 };

声明字段：

1 private int size;
2 private byte b;
3 private byte[] biteMap;

其中size为位图的大小；当位图的size小于等于8时，使用b，否则使用biteMap

构造函数：

 1 public ByteMapImpl() {
 2     this(8);
 3 }
 4     
 5 public ByteMapImpl(int size) {
 6     if(size <= 0) {
 7         throw new IllegalArgumentException("ByteMap size value should be positive");
 8     }
 9     this.size = size;
10     if(size <= 8) {
11         this.b = 0;
12     }else {
13         int len = (size >> 3) + ((size & 7) > 0 ? 1 : 0);
14         this.biteMap = new byte[len];
15     }
16 }

 其中位图的索引从0开始的

位图最重要的两个接口是：

 1 public int getByte(int index) {
 2     if(index < 0 || index >= this.size) {
 3         throw new IllegalArgumentException("index out of bit map");
 4     }
 5     byte unit = (this.size <= 8) ? this.b : this.biteMap[index >> 3];
 6     int result = 0;
 7     result = unit & BYTE_VALUE[index & 7];
 8     return result == 0 ? 0 : 1;
 9 }
10     
11 public void setByte(int index, int flag) {
12     if(index < 0 || index >= this.size) {
13         throw new IllegalArgumentException("index out of bit map");
14     }
15     if(flag != 0 && flag != 1) {
16         throw new IllegalArgumentException("illegal flag argument, must be 1 or 0");
17     }
18         
19     if(flag == this.getByte(index)) {
20         return;
21     }
22     int offSet = index & 7;
23     if(this.size <= 8) {
24         if(flag == 1) {
25             this.b = (byte) (this.b | BYTE_VALUE[offSet]);
26         }else {
27             this.b = (byte) (this.b & (~BYTE_VALUE[offSet]));
28         }
29             
30     }else {
31         int unitIndex = index >> 3;
32         byte unit = this.biteMap[unitIndex];
33         if(flag == 1) {
34             this.biteMap[unitIndex] = (byte) (unit | BYTE_VALUE[offSet]);
35         }else {
36             this.biteMap[unitIndex] = (byte) (unit & (~BYTE_VALUE[offSet]));
37         }
38     }
39 }

通过位操作与，或以及移位实现以上两个接口

剩下的接口基于以上实现的：

  1 public void setByte(int start, int end, int flag) {
  2     for(int i = start ; i <= end; ++i) {
  3         this.setByte(i, flag);
  4     }
  5 }
  6     
  7 public int getSize() {
  8     return size;
  9 }
 10 
 11 public void setSize(int size) {
 12     this.size = size;
 13 }
 14     
 15 public int countOne() {
 16     return this.countOne(0, this.size - 1);
 17 }
 18     
 19 public int countOne(int start, int end) {
 20     int count = 0;
 21     for(int i = start; i <= end; i++) {
 22         count += this.getByte(i);
 23     }
 24     return count;
 25 }
 26     
 27 public ByteMap subMap(int start, int end) {
 28     ByteMap byteMap = new ByteMapImpl(end - start + 1);
 29     for(int i = start; i <= end; ++i) {
 30         if(this.getByte(i) != 0) {
 31             byteMap.setByte(i - start, 1);
 32         }
 33     }
 34     return byteMap;
 35 }
 36     
 37 public  ByteMap not() {
 38     ByteMap byteMap = new ByteMapImpl(this.size);
 39     for(int i = 0; i < this.size; ++i) {
 40         int flag = (this.getByte(i) == 0) ? 1 : 0;
 41         byteMap.setByte(i, flag);
 42     }
 43     return byteMap;
 44 }
 45     
 46 public ByteMap or(ByteMap byteMap) {
 47     int s1 = this.size;
 48     int s2 = byteMap.getSize();
 49     int orSize = s1 > s2 ? s1 : s2;
 50     ByteMap orMap = new ByteMapImpl(orSize);
 51     int i = 0;
 52     while(i < s1 && i < s2) {
 53         if(this.getByte(i) != 0 || byteMap.getByte(i) != 0) {
 54             orMap.setByte(i, 1);
 55         }
 56         ++i;
 57     }
 58     while(i < s1) {
 59         if(this.getByte(i) != 0) {
 60             orMap.setByte(i, 1);
 61         }
 62         ++i;
 63     }
 64     while(i < s2) {
 65         if(byteMap.getByte(i) != 0) {
 66             orMap.setByte(i, 1);
 67         }
 68         ++i;
 69     }
 70     return orMap;
 71 }
 72     
 73 public ByteMap xor(ByteMap byteMap) {
 74     int s1 = this.size;
 75     int s2 = byteMap.getSize();
 76     int xorSize = s1 > s2 ? s1 : s2;
 77     ByteMap xorMap = new ByteMapImpl(xorSize);
 78     int i = 0;
 79     while(i < s1 && i < s2) {
 80         if(this.getByte(i) !=  byteMap.getByte(i)) {
 81             xorMap.setByte(i, 1);
 82         }
 83         ++i;
 84     }
 85     while(i < s1) {
 86         if(this.getByte(i) != 0) {
 87             xorMap.setByte(i, 1);
 88         }
 89         ++i;
 90     }
 91     while(i < s2) {
 92         if(byteMap.getByte(i) != 0) {
 93             xorMap.setByte(i, 1);
 94         }
 95         ++i;
 96     }
 97     return xorMap;
 98 }
 99     
100 public ByteMap and(ByteMap byteMap) {
101     int s1 = this.size;
102     int s2 = byteMap.getSize();
103     int orSize = s1 > s2 ? s1 : s2;
104     ByteMap andMap = new ByteMapImpl(orSize);
105     int i = 0;
106     while(i < s1 && i < s2) {
107         if(this.getByte(i) != 0 && byteMap.getByte(i) != 0) {
108             andMap.setByte(i, 1);
109         }
110         ++i;
111     }
112     return andMap;
113 }
114     
115 public ByteMap leftShift(int shiftStep) {
116     ByteMap shiftMap = new ByteMapImpl(this.size);
117     if(this.countOne() > 0 && shiftStep < this.size) {
118         if(shiftStep < 0) {
119             return this.rightShift((0 - shiftStep));
120         }else {
121             for(int i = shiftStep; i < this.size; ++i) {
122                 if(this.getByte(i) != 0) {
123                     shiftMap.setByte(i - shiftStep, 1);
124                 }
125             }
126         }
127     }
128     return shiftMap;
129 }
130     
131 public ByteMap rightShift(int shiftStep) {
132     ByteMap shiftMap = new ByteMapImpl(this.size);
133     if(this.countOne() > 0 && shiftStep < this.size) {
134         if(shiftStep < 0) {
135             return this.leftShift((0 - shiftStep));
136         }else {
137             for(int i = this.size - shiftStep - 1; i >= 0; --i) {
138                 if(this.getByte(i) != 0) {
139                     shiftMap.setByte(i + shiftStep, 1);
140                 }
141             }
142         }
143     }
144     return shiftMap;
145 }

4、测试

为了便于测试，重写Object类型的toString方法：

 1 @Override
 2 public String toString() {
 3     StringBuilder sb = new StringBuilder();
 4     if(this.size <= 8) {
 5         for(int i = 0; i < 8; ++i) {
 6             if(i < 7) {
 7                 try {
 8                     sb.append(this.getByte(i) + ",");
 9                 } catch (IllegalArgumentException e) {
10                     sb.append("0,");
11                 }
12             }else {
13                 try {
14                     sb.append(this.getByte(i));
15                 } catch (IllegalArgumentException e) {
16                     sb.append("0");
17                 }
18             }
19         }
20     }else {
21         for(int i = 0; i < this.biteMap.length*8; ++i) {
22             if((i&7) == 0) {
23                 sb.append("\n" + (i>>3) + ":");
24             }else {
25                 sb.append(",");
26             }
27             try {
28                 sb.append(this.getByte(i));
29             } catch (IllegalArgumentException e) {
30                 sb.append("0");
31             }
32         }
33     }
34     return sb.toString();
35 }

测试main函数：

 1 public static void main(String[] args) {
 2     ByteMap byteMap1 = new ByteMapImpl(60);
 3     byteMap1.setByte(3, 5, 1);
 4     System.out.println("byteMap1:" + byteMap1.toString());
 5     System.out.println("byteMap1 count 1:" + byteMap1.countOne());
 6     ByteMap byteMap2 = byteMap1.subMap(1, 11);
 7     System.out.println("byteMap1 sub map:" + byteMap2);
 8     System.out.println("byteMap1 sub map count 1:" + byteMap2.countOne());
 9     System.out.println("or map:" + byteMap1.or(byteMap2));
10     System.out.println("and map:" + byteMap1.and(byteMap2));
11     System.out.println("xor map:" + byteMap1.xor(byteMap2));
12     System.out.println("byteMap1 left shift 3 bit:" + byteMap1.leftShift(3));
13     System.out.println("byteMap1 right shift 3 bite:" + byteMap1.rightShift(3));
14 }

结果：

byteMap1:
0:0,0,0,1,1,1,0,0
1:0,0,0,0,0,0,0,0
2:0,0,0,0,0,0,0,0
3:0,0,0,0,0,0,0,0
4:0,0,0,0,0,0,0,0
5:0,0,0,0,0,0,0,0
6:0,0,0,0,0,0,0,0
7:0,0,0,0,0,0,0,0
byteMap1 count 1:3
byteMap1 sub map:
0:0,0,1,1,1,0,0,0
1:0,0,0,0,0,0,0,0
byteMap1 sub map count one:3
or map:
0:0,0,1,1,1,1,0,0
1:0,0,0,0,0,0,0,0
2:0,0,0,0,0,0,0,0
3:0,0,0,0,0,0,0,0
4:0,0,0,0,0,0,0,0
5:0,0,0,0,0,0,0,0
6:0,0,0,0,0,0,0,0
7:0,0,0,0,0,0,0,0
and map:
0:0,0,0,1,1,0,0,0
1:0,0,0,0,0,0,0,0
2:0,0,0,0,0,0,0,0
3:0,0,0,0,0,0,0,0
4:0,0,0,0,0,0,0,0
5:0,0,0,0,0,0,0,0
6:0,0,0,0,0,0,0,0
7:0,0,0,0,0,0,0,0
xor map:
0:0,0,1,0,0,1,0,0
1:0,0,0,0,0,0,0,0
2:0,0,0,0,0,0,0,0
3:0,0,0,0,0,0,0,0
4:0,0,0,0,0,0,0,0
5:0,0,0,0,0,0,0,0
6:0,0,0,0,0,0,0,0
7:0,0,0,0,0,0,0,0
byteMap1 left shift 3 bit:
0:1,1,1,0,0,0,0,0
1:0,0,0,0,0,0,0,0
2:0,0,0,0,0,0,0,0
3:0,0,0,0,0,0,0,0
4:0,0,0,0,0,0,0,0
5:0,0,0,0,0,0,0,0
6:0,0,0,0,0,0,0,0
7:0,0,0,0,0,0,0,0
byteMap1 right shift 3 bite:
0:0,0,0,0,0,0,1,1
1:1,0,0,0,0,0,0,0
2:0,0,0,0,0,0,0,0
3:0,0,0,0,0,0,0,0
4:0,0,0,0,0,0,0,0
5:0,0,0,0,0,0,0,0
6:0,0,0,0,0,0,0,0
7:0,0,0,0,0,0,0,0

5、总结

　　使用位图适合稠密数据，不然会造成大量空间的浪费

6、思考

　　（1）为什么 BYTE_VALUE[7] = -0x0080；

　　（2）实现的位图是非线程安全的，怎样改进既能保证线程安全，又不会大幅度降低性能；

 

源码参考：https://github.com/pythonerleilei/Search/tree/master/src/seach/data_structure/map