【数据结构】bitmap-ag真人游戏

一、bitmap介绍

bitmap，即位图，使用每个位表示某种状态，适合处理整型的海量数据。本质上是哈希表的一种应用实现，原理也很简单，给定一个int整型数据，将该int整数映射到对应的位上，并将该位由0改为1。例如：

// 存在一个int整型数组
int[] arr = new int[]{6,2,7,14,3};

arr数组中最大值为14，考虑位的下标从0开始，需要长度为15的bit，因此每个bit代表着0~14的整数，如图所示：

很显然，使用 bitmap 存储这个数组只使用了使用15bit，而使用 hashset 或 hashmap 的话，一个数组元素会存储为一个int，而一个int占4个byte，即4*8=32bit，这里有5个数组元素则需要5*32=160bit，这样的话，使用 bitmap 存储一个元素则可以节省32倍的内存空间。因此，bitmap 的优势就不言而喻了。

俗话说，结构决定功能，bitmap非常适合对整型的海量数据进行查询统计、排序、去重；适合对两个集合做交集、并集运算，但不支持非运算，如果需要进行非运算则需要提供一个全量的bitmap才行。另外，java中的 bitset 集合是对 bitmap 算法相对简单的实现，而谷歌开发的 ewahcompressedbitmap 是一种更为优化的实现，后面再详细分析下。

二、bitmap应用场景

举个很常见的例子，比如我们项目的数据库表中经常会有id列，通过该id列可以映射我们需要统计查询的列，或需要去重的列，比如有一张订单表：

1、查询统计、定位查询，排序，去重

首先，根据order_id建立与其他列的映射关系，order_id其实就是 bitmap，如图：

如果按商家统计今日接单量：

如果按顾客或者送货地址统计接单量，也是类似，这里查询统计接单量是非常实用的。

此外，快速查找一个数据是否在订单集合里也很简单，这里 order_id 的 0~5 中 1~5 对应的位均会被修改为1，如果查找订单0是否存在，判断0对应的位是否为1即可，很明显不存在订单0。而去重的话，bitmap结构决定它具有去重的特性，如果有两个订单3，第一个订单3会将3对应的位修改为1，第二个也会修改为1，最终3对应的位仍然是1。bitmap结构也决定它具有排序特性，这个很好理解。

2、取两个集合的交集，并集等

接着上面的查询统计，如果查询十足便利店被高新区下单的情况，该如何查询呢？这里，就相当于取 十足便利店 和 高新区 的交集了，如图所示：

那如果改为查询 十足便利店 或 高新区下单的情况，该如何查询呢？这里，就相当于取 十足便利店 和 高新区 的并集了，如图所示：

三、bitmap的实现

1、自己动手实现bitmap

代码简单实现如下：

public class bitmap {
    private char[] bytes; // 用字符数组存储元素
    private int nbits; // 指定bitmap长度
    public bitmap(int nbits) {
        this.nbits = nbits;
        this.bytes = new char[nbits / 16   1]; // 一个字符占2个字节，也就是2*8=16bit
    }
    /**
     * 设置int整数对应的位，修改为1
     */
    public void set(int k) {
        if (k > nbits)
            return;
        int byteindex = k / 16;
        int bitindex = k % 16;
        bytes[byteindex] |= (1 << bitindex);
    }
    /**
     * 获取int整数对应的位是否存在，true存在，false不存在
     */
    public boolean get(int k) {
        if (k > nbits)
            return false;
        int byteindex = k / 16;
        int bitindex = k % 16;
        return (bytes[byteindex] & (1 << bitindex)) != 0;
    }
}

测试一下：

@springboottest
class mysporthealthyapplicationtests {
    @test
    void test1() {
        int[] arr = new int[]{6, 2, 7, 14, 3};
        int maxarr = arrays.stream(arr).max().getasint();
        // 指定bitmap长度
        bitmap bitmap = new bitmap(maxarr   1);
        // 数组的整数放进bitmap
        for (int i = 0; i < arr.length; i  ) {
            bitmap.set(arr[i]);
        }
        // 判断哪些值存在
        for (int i = 0; i < maxarr   1; i  ) {
            logger.info(i   ",是否在bitmap内-----》:"   bitmap.get(i));
        }
    }
}

控制台输出结果：

注意：

实际上海量数据的设置和查询逻辑没有这么简单，甚至会出现一些极端情况，比如有一个整型数组[1,2,50000,80000000000]，元素间隔很大，导致2和50000，以及50000和80000000000之间存在很多空的bit，这些bit很明显占据了很大的空间，我们可以参考jdk中位集的概念，引入 word 有效解决了这类问题，感兴趣的可以去阅读 bitset 集合源码一探究竟。

2、jdk中实现的bitmap —— bitset 集合

下面这段是jdk对bitset集合的描述：

this class implements a vector of bits that grows as needed. each component of the bit set has a boolean value. the bits of a bitset are indexed by nonnegative integers. individual indexed bits can be examined, set, or cleared. one bitset may be used to modify the contents of another bitset through logical and, logical inclusive or, and logical exclusive or operations.
by default, all bits in the set initially have the value false.
every bit set has a current size, which is the number of bits of space currently in use by the bit set. note that the size is related to the implementation of a bit set, so it may change with implementation. the length of a bit set relates to logical length of a bit set and is defined independently of implementation.
unless otherwise noted, passing a null parameter to any of the methods in a bitset will result in a nullpointerexception.
a bitset is not safe for multithreaded use without external synchronization.

总结如下：

• 一个bitset对象可以通过logical and、logical inclusive or、and logical exclusive or操作来修改另一个bitset对象的内容；
• 默认情况下，集合中的所有位的初始值为false。位集的每个组成部分都有一个布尔值，每个位集都有一个当前大小，即该位集当前使用的空间位数，换言之大小与位集的实现有关，因此它可能随实现而改变；
• bitset集合对于多线程使用是不安全的。
• 另外，bitset 可以看作是 word 组成的数组，而一个word 对应一个64位的long类型，需要6个地址位。

做下测试：

@springboottest
class mysporthealthyapplicationtests {
    @test
    void test1() {
        int[] arr = new int[]{1, 7, 50000, 30000000}; //1到3千万
        int maxarr = arrays.stream(arr).max().getasint();
        bitset bitset = new bitset(maxarr   1);
        // 存放数据
        bitset.set(1);
        bitset.set(7);
        bitset.set(50000);
        bitset.set(30000000);
        // 查找
        logger.info("1000是否存在------->"   bitset.get(1000)); //false
        logger.info("7是否存在------->"   bitset.get(7)); //true
        logger.info("50000是否存在------->"   bitset.get(50000)); //true
        logger.info("5000000是否存在------->"   bitset.get(5000000)); //false
        logger.info("30000000是否存在------->"   bitset.get(30000000)); //true
    }
}

3、谷歌实现的bitmap —— ewahcompressedbitmap

对于一个很长的 bitmap 只存储少量的数据，比如只有第50000000的位置为1，那么它之前的空间会造成浪费，所以谷歌的实现对这个空间进行了优化，提供了 ewahcompressedbitmap ，要使用需要先引入依赖：

    com.googlecode.javaewah
    javaewah
    1.1.0

原理：

ewahcompressedbitmap 将整个的二进制数据划分为一个个word，一个word需要64位 ，而一个空的 bitmap 默认拥有 4 个word ，也就是 4*64=256 位，其中 word0 存储 bitmap 的头信息，当我们改变对应位置的bit位的值时 word 会跟着变化。

word又可以分为两种：直接存储数据的lw，存储跨度信息的rlw，ewah有些word存储实际数据，有些word存储数据和数据之间的间隔个数，当节点之间跨度很大时，bitmap不会傻傻把长度扩充到bitmap的最高位那么多，他会由一个节点专门存储两个节点之间的跨度信息，以此达到节省空间的目的。在插入新的数据的时候，如果数据不存放在已有的word当中，ewah还会进行动态扩充或对存储跨度的节点进行分裂。

四、bitmap总结

至此，介绍了bitmap的原理、常用的使用场景，自己动手写一个bitmap，顺便分析了jdk及谷歌对bitmap实现和优化。bitmap不是万能的，如果数据量大到一定程度，如64bit类型的数据，不能用bitmap，2^64bit=2^61byte=2048pb=2eb。bitmap的好处在于空间复杂度不随原始集合内元素的个数增加而增加，而它的坏处也源于这一点 —— 空间复杂度随集合内最大元素增大而线性增大。bitmap对整型的海量数据操作较为合适，而对字符型 或 非整数型的海量数据，则推考虑荐使用布隆过滤器。