Redis底层之字典

Redis底层之字典

字典，是一种用于保存键值对（key-value pair）的数据结构。

举个例子，我们向redis中写入：

msg就是键，“hello world”就是值，他们是一对键值对。

而许多这样的键值对组合在一起就成了哈希表。

Redis的字典就是使用哈希表作为底层实现，一个哈希表中存放多个哈希表节点（每个节点保存一个键值对）。

Redis字典使用的hash表结构如下：

table是一个数组，数组中的每一个元素都是指向一个dict.h/dictEntry结构，每个dict.h/dictEntry保存一个键值对。

size记录哈希表（即table数组）的大小，used属性记录哈希表目前已经有的节点的数量。sizemask的值总是等于size-1，这个值会和键的hash值一起决定这个键对应的键值对该存放在什么位置。

key保存键值对中的键，v保存这键值对中的值，键值对的值可以是一个指针，或者是一个uint64_t整数，或者是int64_t整数。

next属性指向另一个哈希表节点，这个指针将多个哈希值相同的键值对连接在一起，以此来解决键的冲突。

如下图就是将冲突的键值对用next指针相连：

Redis中的字典由dict.h/dict结构表示：

ht属性是一个包含两个项的数组，数组中的每个项都是一个dictht哈希表，一般只是用ht[0]，只有在对ht[0]进行rehash时才会使用ht[1]。rehashidx等于-1时表示目前没有进行rehash。

随着操作的不断执行，哈希表保存的键值对会越来越多，如果冲突变多，导致链表变长，查询变慢，所以需要对哈希表进行扩容。有扩容就有收缩，当哈希表剩余空间太多时，就会缩小哈希表的空间。

扩容时会先为ht[1]申请足够的空间：

然后将ht[0]中的每一个键值对重新进行hash计算在ht[1]中找到对应的位置。

渐进式rehash

我们知道rehash是一个耗时比较长的过程（键值对数量可能非常大），如果在这个过程中有新的操作需要向哈希表中添加新的键值对，我们不会将它添加到ht[0]，而是直接加到ht[1]。

下面看一下哈希表渐进式rehahs的步骤：

渐进式rehash的好处在于不需要将庞大的工作量在同一时间完成，避免了集中式rehash的庞大计算量。

在进行渐进式rehash执行期间的哈希表操作会在ht[0] ht[1]两个表中操作。

比如要查找一个键，会先在ht[0]中找，没有的话再到ht[1]中找。

总结：