Redis数据结构面试题

001什么是布隆过滤器？

布隆过滤器是一个叫“布隆”的人提出的，它本身是一个很长的二进制向量，既然是二进制的向量，那么显而易见的，存放的不是0，就是1。布隆过滤器是一种由位数组和多个哈希函数组成概率数据结构，返回两种结果可能存在和一定不存在。布隆过滤器里的一个元素由多个状态值共同确定。位数组存储状态值，哈希函数计算状态值的位置。
优点：由于存放的不是完整的数据，所以占用的内存很少，而且新增，查询速度够快；
缺点： 随着数据的增加，误判率随之增加；无法做到删除数据；只能判断数据是否一定不存在，而无法判断数据是否一定存在。

002Redis中String常用命令及应用场景。

常用命令:  set,get,decr,incr,mget 等。
含义：String数据结构是简单的Key-Value类型，value不仅可以是String，也可以是数字。
数据结构：内部结构实现上类似于 Java 的 ArrayList，采用预分配冗余空间的方式来减少内存的频繁分配，如图所示：

len 是当前字符串实际长度，capacity 是为字符串分配的可用空间，当字符串长度小于 1M 时，扩容都是加倍现有的空间，如果超过 1M，扩容时一次只会多扩 1M 的空间。字符串最大长度为 512M。
应用场景: 常规计数,微博数，粉丝数等。

003Redis中Hash常用命令及应用场景。

常用命令： hget,hset,hgetall 等。
含义：Redis中的哈希结构就如同Java中的map一样，Hash是一个string类型的field和value的映射表，hash特别适合用于存储对象。
数据结构：Redis Hash通过分桶的方式解决 hash 冲突。它是无序字典。内部实现结构是同样的数组 + 链表二维结构。第一维 hash 的数组位置碰撞时，就会将碰撞的元素使用链表串接起来。第一维是数组，第二维是链表。数组中存储的是第二维链表的第一个元素的指针。

应用场景：存储用户信息，商品信息等等。例如修真院的首页的职业信息，只是简单的信息集合，我们可以直接将它储存到Redis中，在读取的过程中就不用序列化对象，直接操作。

004Redis中List常用命令及应用场景。

常用命令: lpush,rpush,lpop,rpop,lrange等
含义：list就是链表，Redis list的实现为一个双向链表，即可以支持反向查找和遍历，更方便操作，不过带来了部分额外的内存开销。
数据结构：Redis 的列表相当于 Java 语言中的 LinkedList，注意它是链表而不是数组。这意味着 list 的插入和删除操作非常快，时间复杂度为 O(1)，但是索引定位很慢，时间复杂度为 O(n)。
list的特点是:
1)有序
2)可以重复
3)右边进左边出或者左边进右边出，则列表可以充当队列
4)左边进左边出或者右边进右边出，则列表可以充当栈

应用场景：微博的关注列表，粉丝列表，最新消息排行等功能

005Redis中Set常用命令及应用场景。

常用命令：sadd,spop,smembers,sunion 等
含义：set对外提供的功能与list类似，是一个列表的功能，特殊之处在于set是可以自动排重的。 并且set提供了判断某个成员是否在一个set集合内的重要接口，这个也是list所不能提供的。
数据结构:set和字典非常类似，其内部实现就是上述的hashTable的特殊实现，与字典不同的地方有两点：
1)只关注key值，所有的value都是NULL。
2)在新增数据时会进行去重。

场景应用：
1.共同好友、二度好友
2.利用唯一性，可以统计访问网站的所有独立 IP
3.好友推荐的时候，根据 tag 求交集，大于某个 threshold 就可以推荐

006Redis中Sorted Set常用命令及应用场景。

常用命令： zadd,zrange,zrem,zcard等
含义：和set相比，sorted set增加了一个权重参数score，使得集合中的元素能够按score进行有序排列。

数据结构：zset是Redis非常有特色的数据结构，它是基于Set并提供排序的有序集合。其中最为重要的特点就是支持通过score的权重来指定权重。一些排行榜、延迟任务比如指定1小时后执行, 就是使用这个数据结构实现的。

应用场景：在直播系统中，实时排行信息包含直播间在线用户列表，各种礼物排行榜，弹幕消息（可以理解为按消息维度的消息排行榜）等信息，适合使用Redis中的SortedSet结构进行存储。

007Redis的Hash冲突怎么办?

Redis 作为一个K-V的内存数据库，它使用用一张全局的哈希来保存所有的键值对。这张哈希表，有多个哈希桶组成，哈希桶中的entry元素保存了key和value指针，其中*key指向了实际的键，*value指向了实际的值。

所谓的哈希冲突通是指过不同的key，计算出一样的哈希值，导致落在同一个哈希桶中。
Redis为了解决哈希冲突，采用了链式哈希。链式哈希是指同一个哈希桶中，多个元素用一个链表来保存，它们之间依次用指针连接。

因为哈希冲突链上的元素只能通过指针逐一查找再操作，所以当往哈希表插入数据很多，冲突也会越多，冲突链表就会越长，那查询效率就会降低了。为了保持高效，Redis 会对哈希表做rehash操作，也就是增加哈希桶，减少冲突。为了rehash更高效，Redis还默认使用了两个全局哈希表，一个用于当前使用，称为主哈希表，一个用于扩容，称为备用哈希表。

008说说Redis哈希槽的概念？

Redis集群没有使用一致性hash,而是引入了哈希槽的概念，Redis集群有16384个哈希槽，每个key通过CRC16校验后对16384取模来决定放置哪个槽，集群的每个节点负责一部分hash槽。