10亿量级数据（long）存储

10亿个整型（长整型）数据的存储，如果按照一般的int类型或者long类型存储的话，那会占据较大的内存空间：
比如使用long类型存储10亿个数据，一个long类型为64位二进制，即8个字节（8B），1024B = 1KB ， 1024KB = 1M ，1024M = 1G ，那么10亿个long类型数据大小为：1000000000*8/1024/1024/1024 = 7.5G（约等于），这样一个数据量的情况下，如果还要对其进行查重的话，那将会非常影响程序的运行速度。

为了缩减空间，我想直接使用二进制来存储数据，0表示某个数据不存在，1表示某个数据存在，那么就需要10亿个0或者1来表示10亿个数据 ， 存储所占的空间便是：1000000000/8/1024/1024 = 120M（约等于），从7.5G变成120M，不仅节省了大量的空间而且查重的话，我只需要判断该数据所对应的二进制位是否为1即可

以上只是理论如此，但实际的空间应该不止120M，不过也肯定比7.5G要小很多。

在JAVA中没有直接用来表示二进制的数据类型，所以我决定还是直接存储long类型的方式来完成上面的设想，一个long类型为64位，其中包括一位符号位，所以实际可用的位数为63位，那么我就需1000000000/63 = 15873016个long类型的数据，这里就需要 1000000000/63*8/1024/1024 = 122M（约等于）的空间。

那么如何才能知道15873016个long类型的数据中，每一个所代表的63位具体数据是什么呢，其实很简单，都已经分好了每63个数据放在一个long类型的二进制中，那给每一个long类型一个索引即可，索引的计算就是具体的数据/63，比如0/63 = 0 ， 1/63 = 0 ， 5/63 = 0 ， 62/63 = 0，也就是说[0,62]区间内的所有整数的索引都是0，[63,125]索引为1 …以此类推，索引存储为int类型，一共有15873016个索引，占据的空间就是：15873016 * 4/1024*1024 = 61M（约等于）

从上面来看，所需要的总空间大小大约为 122 + 61 = 183M ， 没超过500M，就是要500M 空间，那也远比7.5G要小。

具体的java实现如下：

我采用了HashMap来存储全部数据 ， Interger便是我上述 所谓的索引，Long便是每一个数据
注： 全文包括代码实现仅是个人想法记录，以下代码仅适合存储正整数，比如对电话号码的存储和查重，个人通过简单的输入数据存储和查询是否存在的测试都是通过了的，如有我没考虑清楚的地方请指出，或者有更好的实现方式也希望大家能分享给我。

public class BitStorage {

    private  HashMap storageMap = new HashMap<>();//所有数据的存储单元 map

    private int part = 0;//段 ，即存储单元Map的key

    private int offSet = 0;//数据偏移量 ， 在value的数据中的偏移量

    //存储一个数据
    public void addData(Long longData){
        part = (int)(longData / 63);

        offSet = (int)(longData % 63);

        String str = getBVStr(part);//首先在map中获取该数据所在的段即long类型数据的二进制字符串

        int number = offSet - str.length();

        StringBuilder stringBuilder = addZero(str , number);

        stringBuilder.reverse().replace(offSet , offSet +1 , "1");

        storageMap.put(part , convertLong(stringBuilder));

    }

    //判断一个数据是否已经存储
    public boolean isExist(Long l){
        part = (int)(l / 63);

        Long aLong = storageMap.get(part);

        String str = getBVStr(part);

        if(str == "0"){//段不存在，数据一定不存在
            return false;
        }

        offSet = (int)(l % 63);

        int length = str.length();

        if(length - 1 < offSet){//长度小于偏移量，数据一定不存在
            return false;
        }

        if(str.charAt(length-1-offSet) == '1'){//判断具体所对应的二进制位是否为1
            return true;
        }else{
            return false;
        }
    }
    
    //字符串增加长度
    private StringBuilder addZero(String s, int number){
        for(int i = 0 ; i <= number ; i++){
            s = "0" + s;
        }
        return new StringBuilder(s);
    }

    //获取数据的数据的二进制字符串形式,如果存储单元中不存在该段数据，则返回字符串0
    private String getBVStr(int key){
        Long l = storageMap.get(key);
        if(l == null){
            return "0";
        }else{
            return Long.toBinaryString(l);
        }
    }

    //转换成Long类型的数据
    private Long convertLong(StringBuilder stringBuilder){
        int length = stringBuilder.length();
        long l = 0;
        for(int i = 0 ; i < length ; i++){
            if(stringBuilder.charAt(i) == '1'){
                l += (long)Math.pow(2,i);
            }
        }
        return new Long(l);
    }
}