定义

    通过一个bit数组来存储特定数据的一种数据结构；由于bit是数据的最小单位，所以这种数据结构往往是非常节省存储空间
    用每个位上的0和1来表示1条信息，8个位为1个字节(1B),1024个字节为1KB,1024KB是1M;也就是说1M就有8388608个位
    位运算符来操作计算机底层的位，位运算的执行效率远远高于加、减、乘、除、取模等运算指令
    可以用1个bit来表示2种状态，易可以进行拓展，2bit=4种、3bit=8种等等

    • 位运算符
      & 按位与
      | 按位或
      ^ 按位异或 取余 ？？？
      ～ 取反
      << 左移 乘以2的n次方
      >> 右移 除以2的n次方
      反转二进制位
    • 大小端字节序
    • 实现
      底层：操作的一个个位
      • 数据映射
        使用BitMap的时候，都需要将原始数据（比如用户）映射到BitMap里的位置；这种映射一般可以采用外部数据（比如在数据库里保存用户到BitMap位置的映射），或者采用固定的规则（比如计算用户名的hash code）
        • 外部数据
          通常是在数据库里边给用户分配一个数值型的用户ID，而用户ID的生成规则采用自增量的方式来产生
          采用自增量的另外一个好处是，系统用户数少的时候，BitMap需要的位数也少；当用户量增长时，BitMap的位数跟着增长即可；
        • hash
          布隆过滤器Bloom filter
      • Go Uint64最多也只能每次表示64个二进制位
    • 优点
      因为0和1只能表示非是即否的信息，使用它仅能在一些数据量较大，又只关心是与否的场景下使用使用
      • 节省存储空间
        vs HashSet、HashMap
      • 提供非常快的计算效率
      • 位运算便利——交集并集
    • 优化
      在一个大的bitmap中，存储稀疏的数据
      • BitMap压缩
        • 基于RLE（Run Length Encoding）
        • BBC
        • WAH（http://code.google.com/p/compressedbitset/）
        • EWAH(http://code.google.com/p/javaewah/)
          Apache Hive
          • Google的EWAHCompressedBitmap
            Bitmap存储在long数组中，每个元素称为word（64位）
            1、初始时空的bitmap为unsigned long bitmap[4]，即只有4个word，且word0不存数据信息body而算head，word1、word2、word3存具体数据
            2、动态扩容
            3、Running Length Word（存储跨度） 和 Literal word（存储数据）
            4、推荐增序添加元素，否则需要分裂——影响性能
    • 操作
      • 插入
        1、左移n位，
        2、再原bitmap做或运算
      • 删除
        1、左移n位——表示删除元素
        2、对删除元素取反
        3、与原数按位与
      • 查找
        1、左移n位
        2、按位与
    • 应用
      • 海量数据统计神器
        十万客户端心跳状态记录（添加记录——按位或）
        百万用户在线状态统计（统计1个个数？？？）
        千万消费者数据去重
      • 日活、月活、留存、漏斗分析、多维分析等是如何做到秒级响应
      • 大量数据快速排序
        1、先用bitmap表示
        2、遍历
        • 优点
          1、时间复杂度O(n)
          2、运算效率高，不需要进行比较和移位
          3、占用内存少
        • 缺点
          1、所有的数据不能重复。即不可对重复的数据进行排序和查找。
          2、只有当数据比较密集时才有优势
      • 海量数据快速去重
        20亿个整数中找出不重复的整数的个数，内存不足以容纳这20亿个整数。
        首先，根据“内存空间不足以容纳这05亿个整数”我们可以快速的联想到Bit-map。下边关键的问题就是怎么设计我们的Bit-map来表示这20亿个数字的状态了。其实这个问题很简单，一个数字的状态只有三种，分别为不存在，只有一个，有重复。因此，我们只需要2bits就可以对一个数字的状态进行存储了，假设我们设定一个数字不存在为00，存在一次01，存在两次及其以上为11。那我们大概需要存储空间2G左右。
        接下来的任务就是把这20亿个数字放进去（存储），如果对应的状态位为00，则将其变为01，表示存在一次；如果对应的状态位为01，则将其变为11，表示已经有一个了，即出现多次；如果为11，则对应的状态位保持不变，仍表示出现多次。
        最后，统计状态位为01的个数，就得到了不重复的数字个数，时间复杂度为O(n)。
      • 海量数据快速查找