2023-06-15：说一说Redis的Key和Value的数据结构组织？

2023-06-15：说一说Redis的Key和Value的数据结构组织?

答案2023-06-15：

全局哈希表

Redis使用哈希表作为保存键值对的数据结构，通过哈希函数将Key映射为哈希表中的一个索引位置，使得Key-Value可以在O(1)时间复杂度内被快速访问。在Redis中，哈希表是由多个哈希桶（也称为槽位/数组元素）组成的，每个哈希桶可以存放多个Key-Value值，同一个哈希桶中的多个键值对可以通过Key进行快速查找。

image.png

在Redis中，哈希表由多个哈希桶组成，每个哈希桶中保存着一个链表，链表中每个节点都是一个键值对，其中键key和值value都是指针类型，指向实际的键和值数据。这样一来，即使值是一个集合，也可以通过value指针指向的地址在内存中获取到实际的集合值。因为这个哈希表保存了所有的键值对，所以，也可以把它称为全局哈希表。

哈希表的最大优势在于可以以O(1)的时间复杂度快速查找键值对。通过哈希函数将键映射为一个索引位置，就可以快速访问所在的哈希桶，从而访问相应的entry元素，获取键值对数据。

当写入大量数据到Redis中时，有时会发现操作突然变慢。这很可能是由哈希表的冲突问题和rehash操作可能带来的阻塞引起。由于哈希表为每个键计算哈希值，将其映射到不同的桶中。然而，不同的键可能具有相同的哈希值，这就是哈希表冲突的存在。

随着向哈希表中写入更多数据，哈希冲突是一个不可避免的问题。当两个键计算出的哈希值映射到同一个桶中时，就会发生哈希冲突。Redis使用链表或跳表解决哈希冲突，将具有相同哈希值的键值对存储在同一个桶中的链表或跳表中。虽然这种方法可以在一定程度上有效解决冲突问题，但当链表或跳表过长时，读写性能会逐渐降低。因此，适当调整哈希表的大小，或使用跳表代替链表，可以提高哈希表的性能和可靠性。

image.png

Redis解决哈希冲突采用链式哈希，即将哈希表中哈希值相同的键值对用链表连接起来存储在同一个桶中，这样的设计称为“开链法”。开链法可以有效地避免哈希冲突，同时适用于哈希桶数量确定或变化不频繁的场景。

具体来说，链式哈希使用指针将多个元素连接在一起，形成链表。当哈希表中存在多个哈希值相同的键值对时，这些键值对可以通过指针顺序访问。由于实现简单且常用，链式哈希常用于解决哈希表冲突，被广泛应用于数据结构中，是一种重要且实用的数据存储方式。