HikariTish

1. 压缩列表（Ziplist）/ 紧凑列表（Listpack）#

当 Hash 存储的元素数量较少，且每个元素的值较小时，Redis 会使用压缩列表（在 Redis 7.0 之后被替换为 Listpack）作为底层实现。

• 原理：压缩列表是一块连续的内存空间，类似于数组，但它没有严格的索引，而是将键值对紧凑地顺序存储。键（Field）和值（Value）交替排列在一起。
• 优势：极大地节省了内存空间。因为数据是连续存储的，减少了内存碎片，也避免了哈希表带来的额外指针开销。
• 劣势：由于是连续内存，当修改数据或数据量变大时，可能会引发连锁更新（Cascade Update），导致性能下降。查找操作是顺序遍历，时间复杂度为 $O(N)$。

2. 哈希表（Hash Table）#

当 Hash 中的数据量增大，或者存入了较大的字符串时，Redis 会将底层结构切换为真正的哈希表（类似于 Java 中的 HashMap 或 Go 中的 map）。

• 原理：使用数组和链表（解决哈希冲突）来实现。通过计算键的哈希值，将其映射到数组的特定位置。
• 优势：查找、更新操作的时间复杂度降低为 $O(1)$（平均情况下）。即使数据量很大，也能保持极高的查询效率。
• 劣势：相比压缩列表，哈希表需要维护大量的指针，并且存在空闲槽位，因此会占用更多的内存空间。

3. 两种结构的切换条件#

Redis 内部有两个配置参数决定了何时从压缩列表切换到哈希表：

⚠️ 关键点：只要满足以上任意一个条件，Redis 就会执行转换操作，且这个转换是单向的——一旦转为哈希表，通常不会再转回压缩列表。

1. 示例一：使用压缩列表存储小对象#

假设我们在 Redis 中存储一个简单的用户信息：HSET user:1001 name "Alice" age 25。由于数据量小，底层将使用压缩列表。

① 分配连续内存：Redis 会在内存中分配一块连续的空间用于存储这个 Hash。

② 顺序写入键值对：Field 和 Value 交替。按顺序写入：先写入 "name"，紧接着写入 "Alice"；然后写入 "age"，紧接着写入 "25"。

③ 读取数据过程：$O(N)$ 遍历查找。如果我们要执行 HGET user:1001 age，Redis 会从头部开始顺序遍历这个连续内存，先看到 "name"，跳过它的值，找到 "age"，然后读取并返回其后面的值 "25"。

2. 示例二：切换为哈希表存储长文本#

现在，我们给这个用户添加一段很长的个人简介（超过 64 字节）：HSET user:1001 bio "这是一段非常非常长的个人简介，超过了默认的限制..."。

① 触发阈值：超过 hash-max-ziplist-value。Redis 发现即将存入的 Value 长度超过了 64 字节的限制。

② 结构转换：从 Ziplist 到 Hash Table。Redis 停止使用压缩列表，申请一个新的哈希表结构。将原来压缩列表中的 "name"、"Alice"、"age"、"25" 逐个计算哈希值，放入新的哈希表中。

③ 存入新数据：$O(1)$ 存储。计算新字段 "bio" 的哈希值，将其和它的长文本值放入哈希表中对应的槽位。后续的查询将全部通过哈希表进行，达到 $O(1)$ 的速度。

1. 如何解决哈希冲突？（链地址法）#

当 Redis 内部决定使用真正的哈希表（Hash Table）来存储数据时，它的底层结构是一个名为 dict（字典）的 C 语言结构。当不同的 Key 计算出相同的哈希值，被映射到哈希表数组的同一个索引（桶槽）时，就会发生哈希冲突。

Redis 解决冲突的方式是使用最经典的 链地址法（Separate Chaining）。

• 原理：哈希表数组中的每一个元素（桶）其实是一个指向链表节点的指针。如果发生冲突，Redis 会将新来的键值对组装成一个链表节点，然后挂在这个槽位所在的链表上。
• 头插法（$O(1)$ 性能）：Redis 采用的是 “头插法”。也就是说，新发生冲突的节点会被直接插入到链表的最头部，而不是尾部。

💡 面试亮点：为什么要用头插法？因为 Redis 想要追求极致的速度。如果是尾插法，每次都需要遍历整个链表找到尾部（时间复杂度 $O(N)$）；而头插法只需要修改指针，时间复杂度永远是 $O(1)$。此外，由于 Redis 是单线程模型，不需要像多线程环境（比如 Java 早期的 HashMap）那样担心头插法引发的并发死链问题。

2. 什么是渐进式 Rehash？（平滑过渡的艺术）#

随着数据的不断写入或删除，哈希表里的元素会越来越多（导致链表过长，查询变慢）或越来越少（导致内存浪费）。这时，Redis 需要对哈希表进行扩容或缩容，这个重新计算哈希值并将节点放入新表的过程就叫 Rehash。

3. 结合 Golang 后端开发的加分项#

如果你在面试中不仅讲清了 Redis 的原理，还能把它和 Go 语言联系起来，这就是绝对的降维打击了：

其实 Go 语言内置的 map 在扩容机制上，和 Redis 的渐进式 Rehash 有着异曲同工之妙。Go 的 map 在触发扩容时，也会分配一个更大的 buckets 数组，但它也不会一次性把旧的 oldbuckets 迁移完，而是采用 渐进式驱逐（Evacuation）。在每次向 map 插入或修改数据时，Go 运行时最多会搬运 2 个 bucket 的数据到新数组中。这两者都是典型的为了避免出现长时间的性能抖动（Latency spike）而采用的平滑过渡策略。

1. 什么是 Listpack？#

Listpack 也是一块连续的内存空间，其核心目的与 Ziplist 完全一样：极致节省内存。它在宏观上的表现和 Ziplist 几乎一致，没有传统的链表指针，对 CPU 缓存极为友好。

它最大的壮举在于：在保持极高内存利用率的同时，从数据结构底层彻底杀死了”连锁更新”的可能性。

2. 它是如何根除”连锁更新”的？#

我们可以回顾一下，Ziplist 发生连锁更新的”罪魁祸首”是：每个节点里存了上一个节点的长度（previous_entry_length）。前一个节点变大，当前节点的这个字段就可能被迫膨胀，进而引发多米诺骨牌效应。

Listpack 的破局思路极其简单粗暴：砍掉这个关联！

在 Listpack 中，节点不再关心上一个节点有多长，它只记录自己的长度。既然我不记录你，你变大变小就跟我毫无关系，连锁更新的导火索自然就被完全掐断了。

3. Listpack 的微观结构#

既然不记录上一个节点的长度，那 Listpack 是怎么实现从后往前倒序遍历的呢？（双向遍历是 List、ZSet 等结构的基本需求）。

这就是 Listpack 节点（Entry）设计的精妙之处。每个 Listpack Entry 包含三个部分：

如何实现反向遍历？

当 Redis 内部的指针停留在某个 Entry 的开头时，如果想找上一个节点，指针只需要往后退一步（减去一点指针偏移量），就能精准读取到上一个节点末尾的 backlen。既然知道了上一个节点的总长度，指针再往回跳跃这个长度的距离，就完美定位到了上一个节点的开头！

这种”把自身长度写在尾部”的设计，既满足了双向遍历的需求，又做到了节点之间的绝对空间解耦。

4. Listpack 在 Redis 中的演进历程#

作为后端开发实习生，如果在面试中能准确说出底层数据结构的版本演替，能向面试官证明你不仅在背”八股文”，而且真正在关注核心技术的生命周期：

📝 总结：Listpack 本质上是一个去除了 previous_entry_length 字段、将自身长度记录在尾部的”升级版 Ziplist”。它在保留了内存连续性的同时，让每次节点更新的时间复杂度严格保持在常量或线性范围内，彻底避免了最坏情况下的性能灾难。