腾讯一面：基于Redis分布式BitMap的应用

在实际开发中常常遇到如下需求：判断当前元素是否存在于已知的集合中，将已知集合中的元素维护一个HashSet，使用时只需耗时O(1)的时间复杂度便可判断出结果，Java内部或者Redis均提供相应的数据结构。使用此种方式除了占用内存空间外，几乎没有其它缺点。

当数据量达到亿级别时，内存空间的占用显著表现出来，BitMap便是解决此类问题的一种途径。

Redis BitMap能够存储的数据范围为[0,2^32-1]，超过IntegerMAX_VALUE上界值。

为了简化讨论，假设讨论的集合元素的范围为[0,IntegerMAX_VALUE]，可以是其中的任何一个数。

使用HashSet数据结构占用内存空间仅与集合中的元素数量（N）相关。当集合中元素数量为N时，所需的内存空间大概为N4/1024/1024MB，1亿条数据约占内存空间381MB。

基于Redis的BitMap所占用的空间大小不与集合中元素数量相关，与集合中元素的最大值直接相关，因此BitMap所占用的内存空间范围为[N / 8 / 1024 / 1024,IntegerMAX_VALUE / 8 / 1024 / 1024]。

这里给出了一组测试参考数据

当集合中数据增长到10亿条时，使用BItMap最大占用内存约为255MB，而使用HashSet增长到38GB。

使用Redis命令行可直接 *** 作BitMap，将offset位置的值标注为1，则表示当前数据存在。默认情况下未标注的位置值为0。

这里提供一个SpringBoot生态的RedisUtils工具类，内部封装 *** 作Redis BitMap的工具方法。

上述工具类的依赖如下，如果找不到Jar包，请直接使用Maven原始仓库源，阿里云尚未同步完成。

BitMap的存储与取值时间复杂度为O(1)，根据数值可直接映射下标。

BitMap占用内存空间复杂度为O(n)，与集合中元素的最大值正相关，不是集合中元素的数量。

缓存穿透是指当前请求的数据在缓存中不存在，需要访问数据库获取数据（数据库中也不存在请求的数据）。缓存穿透给数据库带来了压力，恶意缓存穿透甚至能造成数据库宕机。

使用BitMap动态维护一个集合，当访问数据库前，先查询数据的主键是否存在集合中，以此作为是否访问数据库的依据。

BitMap新增数据或者移除数据属于轻量级 *** 作，检查 *** 作的准确度依赖于动态集合维护的闭环的完整性。比如向数据库增加数据时需要向BitMap中添加数据，从数据库中删除数据需要从BitMap中移除数据。如果要求严格的检查可靠性，则可以单独维护一个分布式定时任务，定期更新BitMap数据。

布隆过滤器与BitMap有相似的应用场景，但也有一定的区别。给定一个数，BitMap能准确知道是否存在于已知集合中；布隆过滤器能准确判断是否不在集合中，却不能肯定存在于集合中。

BitMap增加或者移除数据时间复杂度为O(1)，方便快捷。布隆过滤器新建容易，剔除数据 *** 作比较繁琐。

在一些需要精确判断的场景，优先选择BitMap，比如判断手机号是否已经注册。

Redis BitMap不是一种新的数据结构，是利用字符串类型做的一层封装，看起来像一种新型数据结构。BitMap不像一种技术，更像是算法，在时间复杂度和空间复杂度之间寻找平衡点。

BitMap其它应用场景比如签到打卡，统计在线人数等等。

String、Hash、List、Set和Zset。

等同于java中的， Map<String,String> string 是redis里面的最基本的数据类型，一个key对应一个value。

应用场景 ：String是最常用的一种数据类型，普通的key/value存储都可以归为此类，如用户信息，登录信息和配置信息等；

实现方式 ：String在redis内部存储默认就是一个字符串，被redisObject所引用，当遇到incr、decr等 *** 作（自增自减等原子 *** 作）时会转成数值型进行计算，此时redisObject的encoding字段为int。

Redis虽然是用C语言写的，但却没有直接用C语言的字符串，而是自己实现了一套字符串。目的就是为了提升速度，提升性能。 Redis构建了一个叫做简单动态字符串（Simple Dynamic String），简称SDS。

Redis的字符串也会遵守C语言的字符串的实现规则，即 最后一个字符为空字符。然而这个空字符不会被计算在len里头。

Redis动态扩展步骤：

Redis字符串的性能优势

常用命令 ：set/get/decr/incr/mget等，具体如下；

ps：计数器（字符串的内容为整数的时候可以使用），如 set number 1。

补充：

等同于java中的： Map<String,Map<String,String>> ，redis的hash是一个string类型的field和value的映射表， 特别适合存储对象。 在redis中，hash因为是一个集合，所以有两层。第一层是key：hash集合value，第二层是hashkey：string value。所以判断是否采用hash的时候可以参照有两层key的设计来做参考。并且注意的是， 设置过期时间只能在第一层的key上面设置。

应用场景 ：我们要存储一个用户信息对象数据，其中包括用户ID、用户姓名、年龄和生日，通过用户ID我们希望获取该用户的姓名或者年龄或者生日；

实现方式 ：Redis的Hash实际是内部存储的Value为一个HashMap，并提供了直接存取这个Map成员的接口。如，Key是用户ID, value是一个Map。 这个Map的key是成员的属性名，value是属性值 。这样对数据的修改和存取都可以直接通过其内部Map的Key(Redis里称内部Map的key为field), 也就是通过 key(用户ID) + field(属性标签) 就可以 *** 作对应属性数据。 当前HashMap的实现有两种方式 ：当HashMap的成员比较少时Redis为了节省内存会采用类似一维数组的方式来紧凑存储，而不会采用真正的HashMap结构，这时对应的value的redisObject的encoding为zipmap，当成员数量增大时会自动转成真正的HashMap,此时redisObject的encoding字段为int。

常用命令 ：hget/hset/hgetall等，具体如下：

等同于java中的 Map<String,List<String>> ，list 底层是一个链表，在redis中，插入list中的值，只需要找到list的key即可，而不需要像hash一样插入两层的key。 list是一种有序的、可重复的集合。

应用场景 ：Redis list的应用场景非常多，也是Redis最重要的数据结构之一，比如twitter的关注列表，粉丝列表等都可以用Redis的list结构来实现；

实现方式 ：Redis list的实现为一个 双向链表 ，即可以支持反向查找和遍历，更方便 *** 作，不过带来了部分额外的内存开销，Redis内部的很多实现，包括 发送缓冲队列 等也都是用的这个数据结构。

常用命令 ：lpush/rpush/lpop/rpop/lrange等，具体如下：

性能总结 :

它是一个字符串链表，left、right都可以插入添加。

等同于java中的 Map<String,Set<String>> ，Set 是一种无序的，不能重复的集合。并且在redis中，只有一个key它的底层由hashTable实现的，天生去重。

应用场景 ：Redis set对外提供的功能与list类似是一个列表的功能，特殊之处在于set是可以自动去重的，当你需要存储一个列表数据，又不希望出现重复数据时，set是一个很好的选择，并且 set提供了判断某个成员是否在一个set集合内的重要接口 ，这个也是list所不能提供的；如保存一些标签的名字。标签的名字不可以重复，顺序是可以无序的。

实现方式 ：set 的内部实现是一个 value永远为null的HashMap，实际就是通过计算hash的方式来快速排重的，这也是set能提供判断一个成员是否在集合内的原因。

常用命令 ：sadd/spop/smembers/sunion等，具体如下：

ZSet(Sorted Set：有序集合) 每个元素都会关联一个double类型的分数score，分数允许重复，集合元素按照score排序（ 当score相同的时候，会按照被插入的键的字典顺序进行排序 ），还可以通过 score 的范围来获取元素的列表。

应用场景 ：Redis sorted set的使用场景与set类似，区别是set不是自动有序的，而sorted set可以 通过用户额外提供一个优先级(score)的参数来为成员排序，并且是插入有序的，即自动排序。 当你需要一个有序的并且不重复的集合列表，那么可以选择sorted set数据结构，比如twitter 的public timeline可以以发表时间作为score来存储，这样获取时就是自动按时间排好序的。

底层实现 ： zset 是 Redis 提供的一个非常特别的数据结构，常用作排行榜等功能，以用户 id 为 value ，关注时间或者分数作为 score 进行排序。实现机制分别是 zipList 和 skipList 。规则如下：

zipList：满足以下两个条件

skipList：不满足以上两个条件时使用跳表、组合了hash和skipList

为什么用skiplist不用平衡树？

主要从内存占用、对范围查找的支持和实现难易程度这三方面总结的原因。

拓展：mysql为什么不用跳表？

常用命令 ：zadd/zrange/zrem/zcard等；

官网地址： >

格式 setbit key bitoffset bitValue

定义在字符串类型上的面向位的 *** 作集合

实际使用场景：

1 统计日活 或者 换一种说法，app签到功能

连续签到 功能， 连续的key ，然后bitoffset 做一个按位与的 *** 作

key 是时间 bitoffset 是userId bitvalue 1或者0 ，代表是否登录

redis中字符串限制最大为512M，所以位图中最大可容纳2^32(42亿)个不同的位。

2 视频、文章等等的已读或未读状态

几个人已读

以上就是关于腾讯一面：基于Redis分布式BitMap的应用全部的内容，包括:腾讯一面：基于Redis分布式BitMap的应用、Redis --- 八种数据类型（基本命令）、redis的bitmap等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！