Bitmap的原理和应用

面试中经常会问到类似问题，看上去很简单，就是一个排序而已，但是你好好想想大部分排序算法都需要把数据放到内存里面操作，这10亿个数字得占用多少内存？好吧，你可以使用外部排序算法，在磁盘上完成排序！当然这些传统算法肯定是可以解决的，不过这里有一个更好的方案，采用bitmap排序，介绍如下：

bitmap是什么？ 大家都知道在计算机中一个字节(byte) = 8位(bit), 这里的bit就是位，数据的最小表示单位，map一般是表示地图或者映射，加一起叫作位图？貌似不太形象

简单回顾一下二进制的一些知识：

1byte = 8bit

一个bit有2种状态，0 或者 1

所以1个byte可以表示0000 0000 -> 1111 1111, 也就是十进制的 0 到 255

其中十进制和二进制对应关系如下：

0 ---------> 0000 0000
 1 ---------> 0000 0001
 2 ---------> 0000 0010
 3 ---------> 0000 0011
 4 ---------> 0000 0100
 5 ---------> 0000 0101
 6 ---------> 0000 0110
 7 ---------> 0000 0111
 8 ---------> 0000 1000
 9 ---------> 0000 1001
10 ---------> 0000 1010
11 ---------> 0000 1011
12 ---------> 0000 1100
13 ---------> 0000 1101
14 ---------> 0000 1110
15 ---------> 0000 1111
.......................
.......................
255...........1111 1111

在大部分编程语言里面，int类型一般的都是占4个byte，也是32位，甭管你这个数字是1 或者是 21亿你都得占32位，所以如果你现在有10亿数字需要存放在内存里面，需要多少内存呢？

1000000000 * 4 / 1024 / 1024 = 3800MB，大概需要3800MB内存，这里计算出的数值只适合C，在PHP里面，一个整型变量占用的实际空间远远大于4byte，是好几倍！

为了解决这个问题，bitmap采用了一种映射机制，举个例子，假如有 1，3, 7，2, 5 这5个数字需要存放，正常情况下你需要5*4=20byte，但bitmap只需要1byte，它是咋做到呢？

假设下面是1byte，首先将所有位置为0：

0 0 0 0 0 0 0

从第一个0开始数数，把对应数字的位置置为1，比如说第一个1那就是第2个位置置为1，第二个3就是把第4个位置置为1，依此论推…

1 => 0 1 0 0 0 0 0 0
3 => 0 0 0 1 0 0 0 0
7 => 0 0 0 0 0 0 0 1
2 => 0 0 1 0 0 0 0 0
5 => 0 0 0 0 0 1 0 0

叠加起来最终的串就是：

0 1 1 1 0 1 0 1

其实最终的数字和二进制没有什么关系，纯粹是数数，这个串就可以代表最大到7的数字，然后我们就开始数数，从0开始：

比如第1个位置是1，那就记个1
比如第2个位置是1，那就记个2
比如第3个位置是1，那就记个3
比如第5个位置是1，那就记个5
比如第7个位置是1，那就记个7

结果就是 1 2 3 5 7，不仅仅排序了，而且还去重了！如果按照这种转换机制，1个int类型，32位的话，可以表示0-31之间的数字！

如果你们要表示最大1万的数，那就需要1万个位的串，但是编程语言并没有这样的数据类型，但是可以用数组去模拟

举个例子：一个整型是32位，也就说我们大概需要314个数组元素来表示这个串

数组第1个元素 00 – 31

数组第2个元素 32 – 63

数组第3个元素 64 – 95

数组第4个元素 96 – 127

… …

提到这个算法的好处，最大的好处就是节省内存，节省了好几十倍，适合处理大量数据，除了快速排序，还可以做快速去重，快速查询是否存在，还有一个比较好听的应用 Bloom Filter(布隆过滤器):

Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到{1,…,m}的范围中。对任意一个元素x，第i个哈希函数映射的位置hi(x)就会被置为1（1≤i≤k）。注：如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。 Bloom Filter 在判断y是否属于这个集合时，对y应用k次哈希函数，若所有hi(y)的位置都是1（1≤i≤k），就认为y是集合中的元素，否则就认为y不是集合中的元素。

代码

下面是这个算法的一些演示代码：

<?php

namespace App\bitmap;

class Bitmap
{
const MAX = 10000;
const SHIFT = 5;
const MASK = 0x1F;
const DIGITS = 32;

private $bits = [];

public function __construct()
{
$len = 1 + self::MAX / self::DIGITS;
for ($i = 0; $i < $len; $i++) {
$this->bits[$i] = 0;
}
}

public function set(int $n)
{
$this->bits[$n >> self::SHIFT] |= (1 << ($n & self::MASK));
}

public function clear(int $n)
{
$this->bits[$n >> self::SHIFT] &= (~(1 << ($n & self::MASK)));
}

public function test(int $n)
{
return $this->bits[$n >> self::SHIFT] & (1 << ($n & self::MASK));
}
}

$bitmap = new Bitmap();

for ($i = 0; $i < Bitmap::MAX; $i++) {
$bitmap->clear($i);
}

$exampleData = [1, 23, 34, 5454, 677, 834, 123, 355, 6784, 2345, 98, 9782, 432, 2342, 872, 732, 2334];
foreach ($exampleData as $item) {
$bitmap->set($item);
}

for ($i = 1; $i <= Bitmap::MAX; $i++) {
if ($bitmap->test($i)) {
printf("%d ", $i);
}
}

此算法的实现是参考一个C语言版本的，简单解析一下：

第一步，是初始化一个数组，这个数组的长度是根据最大的元素的值来的，比如说你要存一个最大10000的数，由于每个元素最多32位，所以需要大概314个数组。

第二步，初始化数组中的每个元素，把每个位都置成0，在PHP里面其实不需要，但是C里面是必须的，使用了clear这个函数。

SHIFT 是表示位移的位数，之所以是5是因为2的5次方是32，简单的说 $n >> self::SHIFT 这个操作是为了找到当前元素在哪个数组！

MASK 是表示掩码，0x1F是 十进制的31，1 << ($n & self::MASK) 这个操作是计算出当前元素在对应数组里面位置！

举个例子，当前元素是100，按照算法，是在第3个数组里面，下标为4的位置，大家仔细推敲一下，结果确实是这样！只不过这里运用了不少位操作，所以理解起来可能会麻烦一点。

REDIS bitmap相关应用

自己造轮子太累，redis提供了类似的命令，最大可以存放2的32次方，即21亿多的数字，主要有以下几个：SETBIT， GETBIT， BITCOUNT， BITOP， BITPOS，BITFIELD，

主要用来做活跃用户在线状态、活跃用户统计、用户签到等场景，特别适合大量用户，几千万上亿级别，当然你用传统数据库也能做，但是redis做起来更简单，更节省空间！

下面举一个用户签到的功能设计案例：

很多App都有一个签到功能，比如说连续签到7天或者30天给一些奖励，需求十分简单！

作为后端，我们需要提供一个签到接口，然后记录用户签到的信息，比如用户uid，签到时间！

如果使用传统关系型数据库，我们可能需要建一张签到表，大概有id、uid、createdTime等几个字段，当用户签到的时候新增一条记录就行！这种做法肯定是没问题的，但是如果网站每天有千万用户签到，那么这张表每天都会有千万条记录产生，数据的存储是问题！分库分表必不可少！

假如使用redis的bit操作，我们可以使用setbit，SETBIT key offset value 对指定的key的value的指定偏移(offset)的位置1或0, 其中key我们可以设置为当天的年月日，offset是用户uid（这里暂时只考虑uid是纯数字的情况）,value的话1表示已签到。比如说用户uid位12500的用户在20190501签到了，我们可以执行SETBIT 20190501 12500 1,其它用户依此论推！

如果我们需要查询用户某天是否签到，只需要使用GETBIT 20190501 12500，返回1表示已签到，0未签到。

如果需要查询某天有多少人签到，可以使用BITCOUNT 20190501。

如果要统计连续7天签到的总人数的话可以使用bitop命令，比如bitop AND 7_dasy_sign 20190501 20190502 20190503 ... 20190507。

理论上讲，setbit的大小在0到2的32次方（最大使用512M内存）之间，即0~4294967296之间，也就说最多可以存储42亿用户的签到情况。和数据库相比，这种方式查询的效率非常高，并不会因为数据大而变慢，而且比较节省内存，操作上也不是太复杂