Redis使用Hash表作为其底层数据结构来存储键值对。每个Redis数据库都维护着两个哈希表（Hash Table）：ht[0]和ht[1]，其中ht[0]是主要的哈希表，ht[1]是在进行rehash操作时使用的临时表。
Hash表的结构
Redis的哈希表由一个数组和一个链表组成。数组中的每个元素是一个指针，指向哈希冲突时形成的链表。具体结构如下：
-
数组：哈希表的核心部分是一个指针数组，数组中的每个元素都指向一个哈希桶（bucket），每个桶是一个链表的头指针。
-
链表：如果多个键值对映射到相同的哈希桶（即哈希冲突），这些键值对会存储在链表中。每个链表节点存储一个键值对。
哈希冲突问题
哈希冲突是指不同的键经过哈希函数计算后，得到了相同的哈希值（即映射到哈希表中的同一个位置）。在Redis中，哈希冲突通过链地址法解决，即在相同哈希值的情况下，将冲突的键值对存储在一个链表中。
Rehash 操作及其阻塞问题
随着哈希表中的数据增多，哈希冲突的几率增加，导致链表变长，查找操作的时间复杂度由O(1)逐渐退化为O(n)。为了解决这个问题，Redis需要对哈希表进行扩展或缩小，这个过程称为rehash。
Rehash 的过程
-
创建新的哈希表：当需要rehash时，Redis会创建一个新的哈希表
ht[1]，其大小是ht[0]的两倍或一半，取决于当前的负载因子。 -
迁移键值对：将
ht[0]中的所有键值对重新计算哈希值，并移动到ht[1]中。 -
替换旧表：当所有键值对迁移完成后，Redis会释放
ht[0]，并将ht[1]替换为新的ht[0]。
操作阻塞问题
直接进行rehash可能会导致阻塞操作，因为在大规模数据迁移的过程中，Redis需要暂停其他操作，直到迁移完成。这种阻塞对于实时性要求较高的应用是不容忽视的。
渐进式rehash
为了解决rehash过程中可能带来的阻塞问题，Redis采用了渐进式rehash（Incremental Rehashing）的策略。
渐进rehash的实现方式
-
分步执行：Redis不会一次性将所有键值对从
ht[0]迁移到ht[1]。相反，它会在对哈希表进行读写操作时，分步将数据逐步迁移到新的哈希表。每次进行写操作时，Redis会从ht[0]迁移一部分数据到ht[1]。 -
同时维护两个哈希表：在渐进式rehash期间，Redis同时使用
ht[0]和ht[1]。所有的新数据都会插入到ht[1]中，而读取或修改数据时，Redis会首先检查ht[1]，如果没找到，再去ht[0]中查找。 -
rehash索引跟踪：Redis通过一个rehash索引来跟踪迁移进度。每次执行渐进式rehash时，该索引会更新，指向下一个需要迁移的桶。
-
结束rehash：当
ht[0]中的所有键值对都被迁移到ht[1]时，Redis会将ht[1]替换为ht[0]，并清空ht[1]，此时rehash过程结束。
渐进rehash的优势
通过渐进式rehash，Redis将rehash操作分散到多个步骤中，避免了一次性大规模数据迁移带来的阻塞问题。这种方式使得Redis在进行rehash的同时，仍然可以处理其他读写请求，从而保证了高性能和低延迟。
总结来说，Redis通过使用哈希表来存储键值对，并采用链地址法解决哈希冲突。为了避免rehash带来的阻塞问题，Redis使用了渐进式rehash，将数据迁移分步执行，从而提高了系统的响应能力。