Bitmap为什么那么快？

57 阅读 0 评论 38 点赞

我是靠谱客的博主懦弱黄蜂，最近开发中收集的这篇文章主要介绍Bitmap为什么那么快？，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一、Bitmap是个啥？

二、Bitmap有什么优缺？

三、Bitmap有啥应用场景？

一、Bitmap是个啥？

Bitmap实际上就是String类型的，你可以在Redis里面Help一下可以看到String是有类似bitop、bitpos等位操作。

Redis中的String类型最大支持512M，因此最多可以支持512*1024*1024*8=2^32bit（比特），具体的bitmap是用于操作每个bit的值（只有1和0），如果你曾经用过IBM大型机或者学过汇编语言的话应该不会陌生。

既然知道Bitmap是什么啦，那怎么创建或初始化呢？也很简单。String的话我们用Set，类似的Bitmap我们用Setbit。

语法：setbit key offset value （当然这个value只能是0或1）

范例：setbit mybitmap 10 1 (这里意思是创建key为mybitmap的bitmap，然后把offset为10的那个bit置为1

二、Bitmap有什么优缺？

优缺点吧，网上一搜一大堆，我这里也重复一下（算是方便自己以后翻查）

优点	1、因为是基于bit的操作，所以适合大数据量的快速查询及去重； 2、至于说节省空间，毕竟是以bit的形式存储状态，那绝对是要比使用字符格式存储在数据库中要来得多；
缺点	1、如果数据是比较稀疏的，例如我们使用用户ID的哈希值作为bitmap的偏移量且用户数量不多的话，从数据致密度来说还是挺浪费空间；（但是好像有很多专门的压缩算法，如RLE） 2、注意偏移量的数据碰撞问题，还是上面的例子，特别是要哈希函数带来的数据碰撞问题；

基于曾经学过C和数字电路，这里着重展开一下为什么计算速度快，关键还是在于移位运算和其本身算法。

移位运算：

还记得大学时候学数字电路吗？应该有讲过，移位计算在计算机里面是很高效的运算方法（幸好大学里学的数字电路没有完全给回老师，哈哈）。

举个简单例子：1<<2 , 这里代表00000001向左位移两位变成00000100等于4，实际效果等于四则运算1* 2^2=4，因此它们是等效的。这些移位指令中，左移一位相当于乘以2，右移一位相当于除以2。与乘除法相比，移位操作是是单机器周期指令（即一次操作只需一个CPU周期时间），乘除法则需要多个CPU周期时间，如果涉及浮点运算则更甚（当然不同CPU架构有着不同的指令集也会导致一定的差异）。

另外，也跟寻址方式有关系。在ARM架构，这种移位操作（如ASL/ASR/LSL/LSR）是基于寄存器寻址。这里通俗的解释一下，就好像一个人要掏个手机出来，你说从口袋还是从背包里掏出来哪个更快？其中，寄存器就好像口袋，内存就好像背包，这里大家就知道为什么了吧。

算法复杂度：

另外，Bitmap的常规操作setbit、getbit等算法的时间复杂度都是O(1)；bitpos、bitcount、bitop等则是O(N)（具体参考官网： https://redis.io/commands/bitop）。怎么理解？就是说无论输入数据增大多少倍，前两种算法运行所需要的时间都不变，后三种是跟数据量大小成线性正比例。我这里展示一下getbit的源码并简单介绍一下它的逻辑（有兴趣的朋友可以直接在github上找）。

从源码可以看出，无论你输入的offset增加多少倍，它还是得通过两步（1、除以8计算位于第几个byte；2、于操作计算位于该byte数组上第几个bit），因此的算法计算说话的时间是不变的，因此是O(1)。

三、Bitmap有啥应用场景？

你理解一下Bitmap是什么？首先，它有一条key（我这里称它为某个主题），它的value就是bitmap，然后bitmap是通过每一个bit位去存储或反映在该主题下的该bit位所代表的元素的状态.。基于这样的理解，那我们日常还是有很多场景可以套用Bitmap的，例如日月活统计、点赞统计等常规功能网上一搜一大堆，这里不打算展开。我觉得主要有以下两种分类。