位图

发表于 本文字数： 578 阅读时长 ≈ 2 分钟

位图是由多个二进制位组成的数组，数组中的每个二进制位都有与之对应的偏移量（也称索引），用户通过这些偏移量可以对位图中指定的一个或多个二进制位进行操作。

基本命令

SETBIT

根据偏移值设置对应下标，返回修改前的值。

位图按照字节进行扩展，将未设置的二进制位设置为 0。

偏移量只能为正数，值只能是 [0 | 1]

1
2
3
4
5
6
-- 设置 bitmap 中下标为 0、2、4、6 的值设置为 1
-- 1010101
SETBIT bitmap 0 1
SETBIT bitmap 2 1
SETBIT bitmap 4 1
SETBIT bitmap 6 1

时间复杂度：O(1)

GETBIT

获取偏移的值，偏移在范围外返回 0.

1
2
3
4
-- 1
GETBIT bitmap 6
-- 0
GETBIT bitmap 5

时间复杂度：O(1)

BITCOUNT

统计位图值为 1 的二进制数量。

1
2
3
4
-- 4
BITCOUNT bitmap
-- 返回第一字节-第二字节中值为 1 的元素个数
BITCOUNT bitmap 0 1

时间复杂度：O(n)

BITPOS

查找位图中第一个指定值的元素下标

1
2
3
4
5
6
7
8
9
10
11
SETBIT bitmap 0 0
SETBIT bitmap 2 1
SETBIT bitmap 4 1
SETBIT bitmap 6 1
BITCOUNT bitmap 0 0
-- 0
BITPOS bitmap 0
-- 2
BITPOS bitmap 1
-- 返回第二字节中值为 1 的元素个数
BITCOUNT bitmap 1 1

时间复杂度：O(n)

BITOP

对位图进行与、或、非和异或的计算。

对于长度不同的位图，会用 0 补全。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
-- bm1 01
SETBIT bm1 0 0
SETBIT bm1 1 1
-- bm2 10
SETBIT bm2 0 1
SETBIT bm2 1 0

-- 00
BITOP AND and bm1 bm2
-- 0
BITCOUNT and
-- 00
BITOP OR or bm1 bm2
-- 2
BITCOUNT or
-- 10
BITOP NOT not bm1
-- 7。这里由于是对字节进行操作的
BITCOUNT not
-- 11
BITOP XOR xor bm1 bm2
-- 2
BITCOUNT xor

时间复杂度：O(n)

BITFIELD

用来对位图中的任意区域存储整数值，并进行计算。

1
2
-- 设置 uint8-bitmap 位图的第一个元素为 u8 类型值为 123
BITFIELD uint8-bitmap SET u8 0 123

时间复杂度：O(n)

总结

  • Redis 的位图是由多个二进制位组成的数组，通过偏移量对位图中一位或多位进行操作；
  • BITCOUNT 命令接受的是字节索引范围，而不是二进制位索引范围；
  • 因为位图是使用字符串实现的，所以字符串命令也可以用于处理位图命令。但必须先转换；