前言

我们对 Redis 的深刻印象就是"快"，它在接收到一个键值对操作指令后在微妙内完成操作。 为什么它能这么快，一方面它是在内存中进行操作，内存访问本身速度快，另一方面是它有高效的数据结构。键值对是按一定的数据结构存储，操作键值对就是对数据结构增删改查，高效的数据结构是 Redis 快速处理数据的基础。

底层数据结构

底层数据结构 Redis 的底层数据结构有六种，简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组，String 的底层实现是简单动态字符串，List、Hash、Set 和 SortedSet 都有两种底层实现结构，这四种类型被称为集合类型，特点是一个 key 对应一个集合数据

键和值的数据结构是什么

Redis 用一个哈希表保存所有键值对，实现 key-value 快速访问。

一个哈希表就是一个数组，数组每个元素叫哈希桶，每个哈希桶保存键值对数据。然而哈希桶中的元素不是 value 本身，而是指向 value 的指针，即 value 存储的内存地址。

全局哈希表

如图，这个哈希表保存了所有键值对，哈希桶中的 entry 元素保存key 和value 指针，哈希表能在 O(1) 时间复杂度快速查找键值对，所以我们只需要计算 key 的哈希值就能找到对应的哈希桶位置，进而找到对应的 entry 元素。不同类型的 value 都能被找到，不论是 String、List、Set、Hash。

这种查找方式只需要进行一次哈希计算，不论数据规模多少，然而，在 Redis 中写入大量数据后，操作有时候会变慢，因为出现了哈希表的冲突以及 rehash 带来的操作阻塞。

哈希冲突

当哈希表中数据增加，新增的数据 key 哈希计算出的哈希值和老数据 key 的哈希值会在同一个哈希桶中，也就是说多个 key 对应同一个哈希桶。

链式哈希

Redis 中，同一个哈希桶中多个元素用一个链表保存，它们之间用指针连接，这就是链式哈希。

如图所示，entry1、entry2 和 entry3 都保存在哈希桶 3 中，导致哈希冲突。entry1 增加个next 指针指向 entry2，entry2 增加next 指针指向 entry3，不论哈希桶 3 元素有多少个，都可以通过指针连接起来，形成一个链表，叫做哈希冲突链。

链式哈希会产生一个问题，随着哈希表数据越来越多，哈希冲突越来越多，单个哈希桶链表上数据越来越多，查找时间复杂度退化到 O(n)，查找耗时增加，效率降低。

rehash

为解决这个问题，Redis 会对哈希表做 rehash 操作。rehash 也就是增加现有的哈希桶数量，让逐渐增多的 entry 元素能在更多的桶之间分散保存，减少单个桶中的元素数量，从而减少单个桶中的冲突。

Redis 使用两个全局哈希表：哈希表 1 和哈希表 2，最开始新增数据默认存到哈希表 1，哈希表 2 没有被分配空间，当数据增加，Redis 开始执行 Rehash 操作：

  1. 给哈希表 2 分配更大空间，可以是当前哈希表 1 大小的两倍
  2. 把哈希表 1 的数据重新映射并拷贝到哈希表 2
  3. 释放哈希表 1 空间

rehash 后，从哈希表 1 切换到哈希表 2，哈希表 2 空间更多，哈希冲突更少，原来哈希表 1 留做下次 rehash 扩容备用，按同样的步骤把哈希表 2 的数据迁移到哈希表 1。

在第二步涉及大量数据拷贝，如果一次性把哈希表 1 迁移完，耗时很长，会造成线程阻塞，无法处理其他请求，Redis 是怎么处理这个问题呢？它采用渐进式 rehash

渐进式 rehash

在第二步中，Redis 正常处理客户端请求，每处理一个请求，从哪哈希表 1 的第一个索引位置开始，把这个位置上的所有 entry 拷贝到哈希表 2 中。处理下一个请求时，把下一个索引位置的 entry 做同样操作。

渐进式 rehash 把一次性大量拷贝的开销，分摊到了多次处理请求的过程中，避免了耗时操作，保证了数据的快速访问。

总结

今天我们学习了全局哈希表，哈希冲突和链式哈希，rehash 等，哈希表是 Redis 中一种非常重要的数据结构，掌握它对学习 Redis 有非常重要的作用。