位示图算法实现大数据的存储

时间：2023-01-08 16:43:04

          今天在看排序算法的时候，看到了用位示图法实现的，上面说可以大大减少内存的使用，尤其针对大数据的存储，数据量非常大的的时候，他的优点就比较明显了，因为他存储数据值依靠1个位来表示。具体是怎么回事呢，继续往下看。位图法，位图法，当然和位相关，下面我给出一组数组int[]{1, 3, 5,8}，也许在普通的我们的编程中，我们肯定是存放在一个32位整形的数组中，1个32位整数，4个字节，4个数字总共16个字节，而如果用位图法，表示，可以用一个这么一个位字符串表示：

10101001

1出现的位置就是代表数字的值，第1，3,5,8个位置的值为1，就代表了这些数字的存在，这样一算只需要8位，也就是1个字节，比刚刚那个整整省了15个字节。可见这个算法的效率十分之高，但是又一个难题摆在面前了，如何存储和读取这样的形式中的数值无疑将是这个算法的最难点。

        首先是数据的存入过程，将整形数字存入相应的位，并把相应的位置的数字标记为1，就代表完成任务了，第一步，我们当然得先声明一个用来存放数值的数组:

//声明了整形数组，最大的存放的数字的值可以到3 * 32
private static int[] bitmap = new int[3];
我在这里定义了3个单位的数组，每个数组值含32位，也就是说，是3个32位0排成一起，那最大表示的值就是96了。这个很好理解吧。为了容易懂，把操作改小了容易懂。接下来就是我们要传入值进行位设置操作了，主要分为以下步骤:

1.算出是在哪个一个数组下标的范围内，除以32去商

2.知道了哪个下标了，算出在此下标的偏移位置，再取余32操作

3.根据偏移量，折算出此时的二进制形式值，就是一直左移到那个位置上

4.最后进行或运算，把那个位置的值变为1，操作结束

附上代码:

/**
 * 传入的数字，用来存储在位图中
 * @param number
 */
public static void setBitmapNumber(int number){
int index = number / 32;
int pos = number % 32;
int flag = 1;

//如果刚好整除
if(pos == 0){
//算上个整数位的
pos = 32;
index--;
}

for(int j=0; j<pos-1; j++){
//左移pos个位置，用于后面的位运算
flag = flag << 1;
}

//找到此数组的位置，进行或运算，把此位置的0变为1
bitmap[index] = bitmap[index] | flag; 
System.out.println(MessageFormat.format("第{0}下标，第{1}位，值为{2}", index, pos, bitmap[index]));
}
我在这里的测试例子的输出结果，输入的数字为： 

int[] initArray = new int[]{15, 31, 75};
for (int i = 0; i < initArray.length; i++) {
setBitmapNumber(initArray[i]);
}
输出为： 

第0下标，第15位，值为16,384
第0下标，第31位，值为1,073,758,208
第2下标，第11位，值为1,024
第0下标的意思是这个1的位置在bitmap[0]中，

75因为已经过了2给32，所以在bitmap[2]中，第11位置，十进制的值就为2的10次方，就是1024了。

0000000000000010000000000000001
0000000000000000000000000000000
0000000000100000000000000000000
上面就是此操作的存储结果。 
/**
 * 整数表示成二进制位的形式
 * @param number
 */
public static void setIntToBit(int number){
int flag = 1;
for(int j=0; j<31; j++){
if((number & flag) == 1){
//说明最右边一位为1
System.out.print(1);
}else{
System.out.print(0);
}
number = number >> 1;
}

System.out.print("\n");
}
我写了这个方法，转化了一下。就是不断右移，输出，循环操作。
      当然了，有存入必然有取出的过程，思路主要如下:

1.遍历biamap[]整形数组，从0下标到最后一个小标

2.在每个下标中，再执行32位的逐位扫描，判断有无设置1的存在

3.如果有1的存在，此时的偏移量+下标*32，就是之前下标的总位数，就是最终的值了

代码如下:

/**
 * 获取位图中所存放的数字
 */
private static void getBitmapNumber(){
int temp = 0;
//在单个数字中的位偏移量
int offset = 1;
int flag = 1;

for(int i=0; i<bitmap.length; i++){
temp = bitmap[i];

for(int j=0; j<31; j++){
if((temp & flag) == 1){
//说明最右边一位为1
System.out.println(MessageFormat.format("第{0}下标，第{1}位，值为{2}", i, offset, 32 * i + offset));
}

temp = temp >> 1;
offset++;
}
//重置偏移量为1
offset = 1;
}
}
测试代码输出的结果: 

第0下标，第15位，值为15
第0下标，第31位，值为31
第2下标，第11位，值为75
里面涉及了比较多的位运算，大家可以自己先运行一下，他到底是怎么算的。看起来操作都已经成功了嘛，但是，我在调试程序的时候发现了一个问题，每当我用32的整数倍的值去算的时候，就会失败，首先存入就会失败，没错，就是越界的问题，后来想了想总共32位，在java里没有无符号整形的说法，所以肯定有1位要作为符号位，所以只能表示到31的位置，32位就会出错，不信的话，可以把我的代码拷贝运行，看一下结果。我这个只是一个小小Demo类型的测试，当数据量非常大的时候，你可以用几个M的字节，去存放海量的数据，肯定比每个传统存储形式要高效很多，而且位运算的执行效率比普通的加减乘除也来的直接。再一次见证了算法的魅力了吧。最后贴出完整程序供大家学习： 

package BitmapStore;

import java.text.MessageFormat;

/**
 * 位示图法存储数据，面对大数据的时候可以减少内存的使用
 * @author lyq
 *
 */
public class Client {
//声明了整形数组，最大的存放的数字的值可以到3 * 32
private static int[] bitmap = new int[3];

public static void main(String[] agrs){
//int[] initArray = new int[]{2, 15, 33, 75, 178, 1000};
int[] initArray = new int[]{15, 31, 75};
for (int i = 0; i < initArray.length; i++) {
setBitmapNumber(initArray[i]);
}

for (int i = 0; i < initArray.length; i++) {
setIntToBit(bitmap[i]);
} 

getBitmapNumber();
}

/**
 * 传入的数字，用来存储在位图中
 * @param number
 */
public static void setBitmapNumber(int number){
int index = number / 32;
int pos = number % 32;
int flag = 1;

//如果刚好整除
if(pos == 0){
//算上个整数位的
pos = 32;
index--;
}

for(int j=0; j<pos-1; j++){
//左移pos个位置，用于后面的位运算
flag = flag << 1;
}

//找到此数组的位置，进行或运算，把此位置的0变为1
bitmap[index] = bitmap[index] | flag; 
System.out.println(MessageFormat.format("第{0}下标，第{1}位，值为{2}", index, pos, bitmap[index]));
}

/**
 * 获取位图中所存放的数字
 */
private static void getBitmapNumber(){
int temp = 0;
//在单个数字中的位偏移量
int offset = 1;
int flag = 1;

for(int i=0; i<bitmap.length; i++){
temp = bitmap[i];

for(int j=0; j<31; j++){
if((temp & flag) == 1){
//说明最右边一位为1
System.out.println(MessageFormat.format("第{0}下标，第{1}位，值为{2}", i, offset, 32 * i + offset));
}

temp = temp >> 1;
offset++;
}
//重置偏移量为1
offset = 1;
}
}

/**
 * 整数表示成二进制位的形式
 * @param number
 */
public static void setIntToBit(int number){
int flag = 1;
for(int j=0; j<31; j++){
if((number & flag) == 1){
//说明最右边一位为1
System.out.print(1);
}else{
System.out.print(0);
}
number = number >> 1;
}

System.out.print("\n");
}

}


标签：

相关文章