Redis作为内存中的数据结构存储系统,它可以用作数据库、缓存和消息中间件。它的value支持多种类型的数据结构,基本数据结构包含:
字符串(strings)
、散列(hashes)
、列表(lists)
、集合(sets)
、有序集合(sorted sets)
五种。这五种数据结构在我们工作中经常使用到,面试过程中经常被问到,因此熟练掌握这5种基本数据结构的使用和应用场景是Redis知识最基础也是最重要的部分。
字符串是Redis最简单的储存类型,它存储的值可以是字符串、整数或者浮点数,对整个字符串或者字符串的其中一部分执行操作;对整数或者浮点数执行
自增(increment)
或者自减(decrement
)操作。
Redis的字符串是一个由字节组成的序列,跟java里面的ArrayList有点类似,采用预分配冗余空间的方式来减少内存的频繁分配,如图中所示,内部为当前字符串实际分配的空间 capacity 一般要高于实际字符串长度 len。当字符串长度小于 1M 时,扩容都是加倍现有的空间,如果超过 1M,扩容时一次只会多扩 1M 的空间。需要注意的是字符串最大长度为 512M。
字符串类型在工作中使用广泛,主要用于缓存数据
,提高查询性能。比如存储登录用户信息、电商中存储商品信息、可以做计数器(想知道什么时候封锁一个IP地址(访问超过几次))等等。
操作指令
set key value: 添加一条String类型数据 get key: 获取一条String类型数据 mset key1 value1 key2 value2: 添加多条String类型数据 mget key1 key2: 获取多条String类型数据 incr key: 自增(+1) incrby key step: 按照步长(step)自增 decr key: 自减(-1) decrby key step: 按照步长(step)递减
实操
# 插入字符串 >set username zhangsan "OK" # 获取字符串 >get username "zhangsan" # 插入多个字符串 >mset age 18 address bj "OK" # 获取多个字符串 >mget username age 1) "zhangsan" 2) "18" # 自增 >incr num "1" >incr num "2" # 自减 >decr num "1" # 指定步长自增 >incrby num 2 "3" >incrby num 2 "5" # 指定步长自减 >decrby num 3 "2" # 删除 >del num "1"
散列相当于Java中的HashMap,内部是无序字典。实现原理跟HashMap一致。一个哈希表有多个节点,每个节点保存一个键值对。
与Java中的HashMap不同的是,rehash 的方式不一样,因为 Java 的 HashMap 在字典很大时,rehash 是个耗时的操作,需要一次性全部 rehash。Redis 为了高性能,不能堵塞服务,所以采用了渐进式 rehash 策略。
渐进式 rehash 会在 rehash 的同时,保留新旧两个 hash 结构,查询时会同时查询两个 hash 结构,然后在后续的定时任务中以及 hash 操作指令中,循序渐进地将旧 hash 的内容一点点迁移到新的 hash 结构中。当搬迁完成了,就会使用新的hash结构取而代之。
当 hash 移除了最后一个元素之后,该数据结构自动被删除,内存被回收。
Hash也可以同于对象存储,比如存储用户信息,与字符串不一样的是,字符串是需要将对象进行序列化(比如json序列化)之后才能保存,而Hash则可以讲用户对象的每个字段单独存储,这样就能节省序列化和反序列的时间。如下:
此外还可以保存用户的购买记录,比如key为用户id,field为商品id,value为商品数量。同样还可以用于购物车数据的存储,比如key为用户id,field为商品id,value为购买数量等等。
操作指令
# 设置属性 hset keyname field1 value1 field2 value2 # 获取某个属性值 hget keyname field # 获取所有属性值 hgetall keyname # 删除某个属性 hdel keyname field # 获取属性个数 hlen keyname # 按照步长自增某个属性(该属性必须是数字) hincrby keyname field step
实操
# 插入 hash 数据 >hset userInfo username zhangsan age 18 address bj "3" # 获取 hash 单条 field 数据 >hget userInfo username "zhangsan" >hget userInfo age "18" # 获取 hash 多个 field 数据 >hmget userInfo username age 1) "zhangsan" 2) "18" # 获取 hash 所有 field 数据 >hgetall userInfo 1) "username" 2) "zhangsan" 3) "age" 4) "18" 5) "address" 6) "bj" # 获取 hash 的 field 个数 >hlen userInfo "3" # 自增 hash 的某个 field >hincrby userInfo age 2 "20" >hincrby userInfo age 2 "22" # 删除 hash 的某个 field >hdel userInfo age "1" # 删除 hash 所有数据 >del userInfo "1"
Redis中的lists相当于Java中的LinkedList,实现原理是一个双向链表(其底层是一个快速列表),即可以支持反向查找和遍历,更方便操作。插入和删除操作非常快,时间复杂度为 O(1),但是索引定位很慢,时间复杂度为 O(n)。
删除
lists的应用场景非常多,可以利用它轻松实现热销榜;可以实现工作队列(利用lists的push操作,将任务存在lists中,然后工作线程再用pop操作将任务取出进行执行 );可以实现最新列表,比如最新评论等。
操作指令
# 左进 lpush key value1 value2 value3... # 左出 lpop key # 右进 rpush key value1 value2 value3... # 右出 rpop key # 从左往右读取 start和end是下标 lrange key start end
实操
# 从 list 左边依次插入 >lpush student zhangsan lisi wangwu "3" # 从 list 右边插入 >rpush student tianqi "4" # 从 list 左边弹出一个 >lpop liangshan "wangwu" # 从 list 右边弹出一个 >rpop liangshan "tianqi" # 获取 list 下标 0 ~ 1 的数据(左闭右闭) >lrange liangshan 0 1 1) "lisi" 2) "zhangsan"
注意:blpop 阻塞版获取
为什么要阻塞版本的pop呢,主要是为了避免轮询。举个简单的例子如果我们用list来实现一个工作队列。执行任务的thread可以调用阻塞版本的pop去获取任务这样就可以避免轮询去检查是否有任务存在。当任务来时候工作线程可以立即返回,也可以避免轮询带来的延迟。
集合类似Java中的
HashSet
,内部实现是一个 value永远为null的HashMap,实际就是通过计算hash的方式来快速排重的,这也是set能提供判断一个成员是否在集合内的原因。
redis的sets类型是使用哈希表构造的,因此复杂度是O(1),它支持集合内的增删改查,并且支持多个集
合间的交集、并集、差集操作。可以利用这些集合操作,解决程序开发过程当中很多数据集合间的问题。比如计算网站独立ip,用户画像中的用户标签,共同好友等功能
操作指令
# 添加内容 sadd key value1 value2 # 查询key里所有的值 smembers key # 移除key里面的某个value srem key value # 随机移除某个value spop key # 返回两个set的并集 sunion key1 key2 # 返回key1踢出交集的那部分(差集) sdiff key1 key2 # 跟siffer相反,返回交集 sinter key1 key2
实操
# 插入多条数据并去重 >sadd nums 1 2 3 "3" # 插入多条数据并去重 >sadd nums 1 2 3 "0" # 获取所有数据 >smembers nums 1) "1" 2) "2" 3) "3" # 删除一条数据,返回的 1 表示删除了一条 >srem nums 2 "1" # 弹出一条数据,返回的 1 表示弹出的数据值为 1 >spop nums "1" # 插入多条数据并去重 >sadd nums1 1 2 3 "3" >sadd nums2 2 3 4 "3" # 交集 >sinter nums1 nums2 1) "2" 2) "3" # 差集 >sdiff nums1 nums2 1) "1" # 并集 >sunion nums1 nums2 1) "1" 2) "2" 3) "3" 4) "4"
sorted sets是Redis类似于 SortedSet 和 HashMap 的结合体,一方面它是一个 set,保证了内部 value 的唯一性,另一方面它可以给每个 value 赋予一个 score,代表这个 value 的排序权重。内部使用HashMap和跳跃表(SkipList)来保证数据的存储和有序,HashMap里放的是成员到score的映射,而跳跃表里存放的是所有的成员,排序依据是HashMap里存的score,使用跳跃表的结构可以获得比较高的查找效率,并且在实现上比较简单。sorted sets中最后一个 value 被移除后,数据结构自动删除,内存被回收。
sorted sets内部的排序功能是通过「跳跃列表」数据结构来实现的,它的结构非常特殊,也比较复杂。因为 zset 要支持随机的插入和删除,所以它不好使用数组来表示。我们先看一个普通的链表结构。
我们需要这个链表按照 score 值进行排序。这意味着当有新元素需要插入时,要定位到特定位置的插入点,这样才可以继续保证链表是有序的。通常我们会通过二分查找来找到插入点,但是二分查找的对象必须是数组,只有数组才可以支持快速位置定位,链表做不到,那该怎么办?
想想一个创业公司,刚开始只有几个人,团队成员之间人人平等,都是联合创始人。随着公司的成长,人数渐渐变多,团队沟通成本随之增加。这时候就会引入组长制,对团队进行划分。每个团队会有一个组长。开会的时候分团队进行,多个组长之间还会有自己的会议安排。公司规模进一步扩展,需要再增加一个层级 —— 部门,每个部门会从组长列表中推选出一个代表来作为部长。部长们之间还会有自己的高层会议安排。
跳跃列表就是类似于这种层级制,最下面一层所有的元素都会串起来。然后每隔几个元素挑选出一个代表来,再将这几个代表使用另外一级指针串起来。然后在这些代表里再挑出二级代表,再串起来。最终就形成了金字塔结构。
想想你老家在世界地图中的位置:亚洲–>中国->安徽省->蚌埠市->固镇县->刘集镇->xxx村->xxxx号,也是这样一个类似的结构。
「跳跃列表」之所以「跳跃」,是因为内部的元素可能「身兼数职」,比如上图中间的这个元素,同时处于 L0、L1 和 L2 层,可以快速在不同层次之间进行「跳跃」。
定位插入点时,先在顶层进行定位,然后下潜到下一级定位,一直下潜到最底层找到合适的位置,将新元素插进去。你也许会问,那新插入的元素如何才有机会「身兼数职」呢?
跳跃列表采取一个随机策略来决定新元素可以兼职到第几层。
首先 L0 层肯定是 100% 了,L1 层只有 50% 的概率,L2 层只有 25% 的概率,L3 层只有 12.5% 的概率,一直随机到最顶层 L31 层。绝大多数元素都过不了几层,只有极少数元素可以深入到顶层。列表中的元素越多,能够深入的层次就越深,能进入到顶层的概率就会越大。
主要应用于根据某个权重进行排序的队列的场景,比如游戏积分排行榜,设置优先级的任务列表,学生成绩表等。
操作指令
# 添加元素 zadd key score value [score value...] # 获取集合的值并按照score从小到大排列, 最小的是最上面 zrange key start end # 返回有序集 key 中,所有 score 值介于 min 和 max 之间(包括等于 min 或 max )的成员。有序集成员按 score 值递增(从小到大)次序排列, 最小的是最上面 zrangeByScore key score_min score_max # 删除 zrem key value # 获取key的集合有多少元素 zcard key # 统计分数从小到大有多少元素 (闭区间) zcount key score_min score_max # 获取value所在位置(从小到大排序,最小的是0) zrank key value # 获取value所在的位置(从大到小排列, 最大的是0) zrevrank key value
实操
# 插入多条数据和分数并去重及排序 >zadd rank 66 zhangsan 88 lisi 77 wangwu 99 zhaoliu "4" # 插入多条数据及分数并去重及排序 >zadd rank 66 zhangsan 88 lisi 77 wangwu 99 zhaoliu "0" # 获取下标 0 ~ 3 的数据(左闭右闭) >zrange rank 0 3 1) "zhangsan" 2) "wangwu" 3) "lisi" 4) "zhaoliu" # 获取分数在 77 ~ 99 之间的数据(左闭右闭) >zrangeByScore rank 77 99 1) "wangwu" 2) "lisi" 3) "zhaoliu" # 删除一条数据 >zrem rank zhaoliu "1" # 查询元素的个数 >zcard rank "3" # 统计分数在 77 ~ 88 之间的数据(左闭右闭) >zcount rank 77 88 "2" # 获取指定元素的下标 >zrank rank zhangsan "0" # 获取指定元素的下标并反转 >zrevrank rank zhangsan "2"
下面这些图来自我的好兄弟
老王
赞助,一个技术很强的全栈专家。