DataStructure-如何通过Bitmap实现亿级数据统计

如何通过Bitmap实现亿级数据统计

问题：给你10亿条u_id，去重后存储。并且，实现O(1)时间复杂度下的查询，添加，删除操作。

（做Line网测时，遇到了类似问题。。。当时就留下了不学无术的泪。。。）

题目分析

说到去重，第一反应一定是HashSet吧。那么用HashSet考虑一下。

10亿u_id，用int来表示，需要40亿字节，因为int类型所占的空间是4字节。换算一下，就是4GB内存。。。

如果只给512MB的内存（网测时的题目要求），那就说明这种做法是完全离谱的了。

解决思路

尽管每个uid都用了int类型的数来保存，但也没必要在记录时，也用int类型。

一个int是4个字节，32位。如果假设就存{1，3，5，7} 4个数字，就需要128位的空间。

然而，实际上这4个数字中，最大的值用二进制表示就是0111，4位足矣。存储4个数字用16位，就足够存储。

从128 到 16，这就是这道题的核心解决思路 —— 压缩数据！

当然方法并不是去掉数字开头的0，以上的说法只是说明，常规方法造成的空间浪费有多大。

如果我们直接用Bit来记录一个数据的存在与否，那么10亿条数据，就算最大的数据就是INT_MAX，我们不得不开辟一共2的32次方的Bit，所占用的空间最大就是0.5GB，恰好就能满512MB的内存要求。

这种用一个Bit来记录数据的方式就叫做 Bitmap

手撕Bitmap

要用一个Bit代表一个数据，显然不存在bit数组，以java为例，使用byte[] 数组来实现Bitmap即可。

设计要点

• byte数组的容量需要有这一堆数据中的最大值确定，或者直接用INT_MAX作为最大值。容量应为maxvalue / 8 + 1
• 在增删查方法中，定义两个重要索引： index | position
  • index : 表示byte数组中的索引
  • position ：表示该byte元素的第几位。
• 得到这两个索引后，就可以确定代表该num 的bit位。之后，就是3种位运算。
• 添加数据，就是让该bit变为1。用或运算。
• 查询数据，就是看该bit是否为1，用与运算。
• 删除数据，就是让该bit变为0，用异或运算。

具体实现如下：

//Bitmap类
class Bitmap{
    private byte[] bits;//实际存储数据的容器
    private int maxVal;//最大值
    private int capacity;//容量
    
    public Bitmap(int maxVal){
        this.maxVal = maxVal;
        this.capacity = (maxval/8) + 1;
        bits[] = new byte[capacity];
    }
    
    public void add (int num) {
        int index = num/8;
        int position = num % 8;
        
        byte temp = 1 << position;
        
        bits[index] = bits[index] | temp;
    }
    
    public boolean contains (int num) {
        int index = num / 8;
        int position = num % 8;
        
        byte temp = 1 << position;
        
        return (bits[index] & temp) == temp;
    }
    
    public void remove (int num) {
		int index = num / 8;
        int postion = num % 8;
        
        byte temp = 1 << position;
        
        bits[index] = bit[index] ^ temp;
    }
    
    
}