共计 3561 个字符，预计需要花费 9 分钟才能阅读完成。
大家好，我是散步 coding, 最近在整顿 2022 年 Redis 最新面试题, 大家也能够通过我上面的博客地址在线浏览, 明天讲讲第 2 篇 – Redis 数据结构。本文首发于公众号: 散步 coding
2022 年 Redis 最新面试题目录
- Redis 基础知识
- Redis 数据结构
- Redis 事务
- Redis 数据长久化
- Redis 集群
- Redis 淘汰策略
- Redis 分布式锁
- Redis 缓存问题
- 运维和部署
数据结构
- Redis 的数据类型有哪些?
- 说说 Redis 哈希槽的概念？
- Hash 如何实现 O(1) 的查问和设置速度, 以及扩容原理
- 布隆过滤器
Redis 的数据类型有哪些？
呈现概率: ★★★★★
这个在面试的过程呈现的概率特地高了。
<font color=#FF000 >Redis 反对五种罕用的数据类型：string（字符串），hash（哈希），list（列表），set（汇合）及 zsetsorted set：有序汇合 )</font>。
redis 的根本数据结构对应的底层实现如下图所示：
1)、Redis 的字符串是 <font color=#FF000 > 动静字符串 </font>，是能够批改的字符串，内部结构实现上相似于 Java 的 ArrayList，采纳 <font color=#FF000 > 预调配冗余空间 </font> 的形式来缩小内存的频繁调配，如图所示：
len 是以后字符串理论长度，capacity 是为字符串调配的可用空间，当字符串长度小于 1M 时，扩容都是加倍现有的空间，如果超过 1M，扩容时一次只会多扩 1M 的空间。字符串最大长度为 512M。
2)、hash
Redis Hash 通过 <font color=#FF000 > 分桶的形式 </font> 解决 hash 抵触。它是无序字典。外部实现构造是同样的 <font color=#FF000 > 数组 + 链表二维构造 </font>。第一维 hash 的数组地位碰撞时，就会将碰撞的元素应用链表串接起来。第一维是数组，第二维是链表。数组中存储的是第二维链表的第一个元素的指针。
3)、list
Redis 的列表相当于 Java 语言中的 LinkedList，留神 <font color=#FF000 > 它是链表而不是数组 </font>。这意味着 list 的插入和删除操作十分快，工夫复杂度为 O(1)，然而 <font color=#FF000 > 索引定位很慢 </font>，工夫复杂度为 O(n)。
list 的特点是:
- 有序
- 能够反复
- 左边进右边出或者右边进左边出，则列表能够充当队列
- 右边进右边出或者左边进左边出，则列表能够充当栈
4)、set
<font color=#FF000 >set 和字典十分相似 </font>，其外部实现就是上述的 hashTable 的非凡实现，与字典不同的中央有两点：
- 只关注 key 值，所有的 value 都是 NULL。
- 在新增数据时会进行去重。
5)、zsetsorted set
zset 是 Redis 十分有特色的数据结构，它是基于 Set 并提供排序的有序汇合。其中最为重要的特点就是反对通过 score 的权重来指定权重。一些排行榜、提早工作比方指定 1 小时后执行, 就是应用这个数据结构实现的。
6)、 拓展篇
如果你说你还晓得一些其余的几种数据结构比方: HyperLogLog、Geo、Pub/Sub、Redis Module，BloomFilter，RedisSearch，Redis-ML，面试官得眼睛就开始发亮了。
Redis5.0 带来了 Stream 类型。从字面上看是流类型，但其实从性能上看，应该是 Redis 对音讯队列（MQ，Message Queue）的欠缺实现。用过 Redis 做音讯队列的都理解，基于 Reids 的音讯队列实现有很多种，例如：
- PUB/SUB，订阅 / 公布模式
- 基于 List 的 LPUSH+BRPOP 的实现
- 基于 Sorted-Set 的实现
Redis Stream 的构造如图所示，它有一个音讯链表，将所有退出的音讯都串起来，每个音讯都有一个惟一的 ID 和对应的内容。音讯是长久化的，Redis 重启后，内容还在。
Hash 如何实现 O(1) 的查问和设置速度, 以及扩容原理
呈现概率: ★★★★★
<font color=#FF000 >Redis Hash 通过分桶的形式解决 hash 抵触。它是无序字典。外部实现构造是同样的数组 + 链表二维构造 </font>。第一维 hash 的数组地位碰撞时，就会将碰撞的元素应用链表串接起来。第一维是数组，第二维是链表。数组中存储的是第二维链表的第一个元素的指针。
因为是通过数组取模的形式, 能够实现 O(1) 的查问和设置速度。
不过如果概率多时, 链表长度过长时，查问工夫复杂度会升高到 O(n)。这个须要进行扩容了。
<font color=#FF000 > 大字典的扩容 </font> 是十分耗时间的，须要 <font color=#FF000 > 从新申请新的数组 </font>，失常状况下，当 hash 表中元素的个数等于第一维数组的长度时，就会开始扩容，扩容的新数组是原数组大小的 2 倍，而后将旧字典所有链表中的元素从新挂接到新的数组上面，这是一个 O(n) 级别的操作，Redis 应用渐进式 rehash 扩容，分屡次来缓缓的将旧数组中的键值对 rehash 到新数组的操作就称之为渐进式 rehash。渐进式 rehash 能够防止了集中式 rehash 带来的宏大计算量，在渐进式 rehash 过程中，因为还可能会有新的键值对存进来，此时 Redis 的做法是新增加的键值对对立放入 ht[1] 中，这样就确保了 ht[0] 键值对的数量只会缩小，当执行 rehash 操作时须要执行查问操作，此时会先查问 ht[0]，查找不到后果再到 ht[1] 中查问。
说说 Redis 哈希槽的概念？
呈现概率: ★★★
Redis 集群没有应用一致性 hash, 而是引入了哈希槽的概念，<font color=#FF000 >Redis 集群有 16384 个哈希槽 </font>，每个 key 通过 CRC16 校验后对 16384 取模来决定搁置哪个槽，集群的每个节点负责一部分 hash 槽。
布隆过滤器
呈现概率: ★★★
这个在面试中呈现的概率, 次要看面试官的偏好, 不过如果问到，而且你能答复比拟好的，预计是一个比拟好的加分项。
布隆过滤器是 Redis 的高级性能，尽管这种构造的去重率并不齐全准确，但和其余构造一样都有特定的利用场景，比方当解决 <font color=#FF000 > 海量数据时 </font>，就能够应用布隆过滤器实现去重。
一些场景: 百度爬虫零碎每天会面临海量的 URL 数据，咱们心愿它每次只爬取最新的页面，而对于没有更新过的页面则不爬取，因策爬虫零碎必须对曾经抓取过的 URL 去重，否则会重大影响执行效率。然而如果应用一个 set（汇合）去装载这些 URL 地址，那么将造成资源空间的重大节约。
布隆过滤器（Bloom Filter）是一个高空间利用率的概率性数据结构，由二进制向量（即位数组）和一系列随机映射函数（即哈希函数）两局部组成。
布隆过滤器应用 exists() 来判断某个元素是否存在于本身构造中。当布隆过滤器断定某个值存在时，其实这个值只是有可能存在；当它说某个值不存在时，那这个值必定不存在，这个误判概率大概在 1% 左右。
Bloom Filter 的原理
1)、工作流程 - 增加元素
布隆过滤器次要由位数组和一系列 hash 函数形成，其中位数组的初始状态都为 0。
上面对布隆过滤器工作流程做简略形容，如下图所示：
2)、工作流程 - 断定元素是否存在
当咱们须要判断一个元素是否存时，其流程如下：首先对给定元素再次执行哈希计算，失去与增加元素时雷同的位数组地位，判断所得地位是否都为 1，如果其中有一个为 0，那么阐明元素不存在，若都为 1，则阐明元素有可能存在。
3)、为什么是可能“存在”
您可能会问，为什么是有可能存在？其实起因很简略，那些被置为 1 的地位也可能是因为其余元素的操作而扭转的。比方，元素 1 和 元素 2，这两个元素同时将一个地位变为了 1（图 1 所示）。在这种状况下，咱们就不能断定“元素 1”肯定存在，这是布隆过滤器存在误判的根本原因。
Bloom Filter 的毛病
bloom filter<font color=#FF000 > 就义了判断的准确率、删除的便利性 </font>，才做到在工夫和空间上的效率比拟高，是因为
1)、存在误判，可能要查到的元素并没有在容器中，然而 hash 之后失去的 k 个地位上值都是 1。如果 bloom filter 中存储的是黑名单，那么能够通过建设一个白名单来存储可能会误判的元素。
2)、删除数据。一个放入容器的元素映射到 bit 数组的 k 个地位上是 1，删除的时候不能简略的间接置为 0，可能会影响其余元素的判断。能够思考 Counting Bloom Filter
也欢送关注我的公众号: 散步 coding。一起交换, 在 coding 的世界里散步, 回复: redis, 收费获取最新 Redis 面试题 (含答案)。
