简述
HashTable，大家听起来是不是很熟悉？Java中也有个HashTable，也是使用数组桶+单链表来实现的，其实大致上和Redis的字典差不多。不过Redis中的字典做了大量优化，今天我们一起来学习下Redis数据结构之字典(HashTable)😀。
字典
大家也知道，Java中的HashTable是利用对key-value结构的key进行hash，获取到的值作为数组桶的下标，按照下标找到数组桶的位置，然后判断是否为空，为空则插入，不为空（遇到了冲突）则插入链表中。当然，如果数据太多，超过了一定阈值，则HashTable或进行扩容处理。Redis中的字典也一样，有着类似Java中的HashTable操作，而且还有更好的性能。现在我们一起看看Redis中的字典实现。
Redis字典
我们首先看看几个重要的结构体：
- dict
字典结构体。代码如下：
typedef struct dict {
// 指向dictType结构体的指针。类型特定函数，用于操作特定类型键值对的函数，具体在下面的dictType结构体中可以看到
dictType *type;
// 私有数据，保存了需要传给那些类型特定函数的可选参数。
void *privdata;
// 两个哈希表，一个用于存数据，另一个rehash的时候扩展内存、复制数据时候使用。具体存数据地方
dictht ht[2];
// rehash用到，-1代表不进行rehash，具体下面分析
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
// 当前进行的迭代数量
unsigned long iterators; /* number of iterators currently running */
} dict;
type是一个指向dictType结构体的指针，每个dictType用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同的类型特定函数。ht代表了两个哈希表，哈希表的结构是dictht。ht[0]是保存数据，h[1]当进行rehash的时候使用。
- dictType
字典类型结构体。每个dictType用于操作特定类型键值对的函数。
typedef struct dictType {
//计算哈希值的函数
uint64_t (*hashFunction)(const void *key);
//复制键的函数
void *(*keyDup)(void *privdata, const void *key);
//复制值的函数
void *(*valDup)(void *privdata, const void *obj);
//对比键的函数
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
//销毁键的函数
void (*keyDestructor)(void *privdata, void *key);
//销毁值的函数
void (*valDestructor)(void *privdata, void *obj);
//是否允许分配内存
int (*expandAllowed)(size_t moreMem, double usedRatio);
} dictType;
- dictht
HashTable，数组+单链表结构。
/* This is our hash table structure. Every dictionary has two of this as we
* implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
//哈希表数组
dictEntry **table;
//哈希表数组大小
unsigned long size;
//用来计算hash值，获取数组桶下标
unsigned long sizemask;
//哈希表总使用数，即键值对个数
unsigned long used;
} dictht;
table是一个数组，里面存放的是指向dictEntry的指针。size是记录了哈希表数组的大小，used记录的是已有节点的数量。sizemark用来计算哈希值，定位数组桶使用。
- dictEntry
节点信息，包含键值对和下一个节点的指针。
typedef struct dictEntry {
//键，sds类型
void *key;
//联合体，导致值可以多用途，可以存储指针或存储整数或浮点数。必定可以存储上面类型之前，通过不同的引用，告诉编译器如何解释对应的内存块。
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
//下一个节点指针
struct dictEntry *next;
} dictEntry;
dictEntry中保存了最多三个指针，键指针key，值val如果不是uint64_t整数，或int64_t整数的话，也是一个指针。还有一个指针next是指向另外一个dictEntry的指针，用于将多个hash相同的键值对连在一起，解决冲突的问题。
以上是Redis字典中几个重要的结构体，具体再dict.h中可以看到。
字典整体结构图
上面总结了字典中重要的数据结构，下面我们画图来看看他们之间的联系。如下图所示：
我们这里添加了三个key-value，当key经过hash计算后得到hash值为0，则放在table[0]上；计算到hash值为3的有两个，则他们放在table[3]上，使用next指针将两个节点连接起来。Redis中使用的是头插法，所以新的节点总是插入到链表的头部，排在已有节点的前面。
rehash
什么是rehash？rehash就是字面上是重新hash。rehash其实就是增加现有的哈希数组桶数量，让逐渐增多的键值对能够在更多的数组桶上分布，减少单个桶中元素个数，从而减少了链表长度，也减少了哈希冲突。
我们在回顾下dict，其中dictht用了两个哈希表，ht[0]和ht[1]。当一开始插入数据的时候，默认会使用ht[0]，ht[1]还未被分配空间。当数据越来越多的时候，如果进行了rehash，ht[1]就体现了作用：扩容备用。
rehash流程
- 分配两倍的空间给ht[1]。
- 把ht[0]中的数据重新计算hash值，并且复制插入到ht[1]中。
- 释放ht[0]的空间。
过程很简单，其实就是扩容-复制-释放空间。但是数据量特别大，一次性把ht[0]的数据复制迁移到ht[1]中，会造成Redis线程阻塞，无法服务请他请求。所以，Redis为了解决此问题，采用了渐进式rehash。
渐进式rehash
什么是渐进式rehash？其实就是第二部中，我们没有直接把所有数据都复制迁移到ht[1]，而是当Redis处理客户端请求的时候，从ht[0]中第一个索引位置开始，顺带把这个索引位置上的所有键值对都复制迁移到ht[1]中。跟着处理下一个请求，再把ht[0]中的下一个索引位置键值对复制迁移到ht[1]中。如此循环执行，最终会把所有的键值对都复制迁移到了ht[1]。
这里说明下，如果此时客户端来的请求是读取，那么会先在ht[0]中读，读不到再到ht[1]中读；如果客户端来的请求是插入，则只会到ht[1]中插入。
渐进式rehash流程如下图所示：
Redis运用了渐进式rehash，巧妙地把一次性大量数据的操作，分摊到了多次请求中协助处理，避免了耗时操作，保证了客户端能够快速访问数据。
对于String类型来说，找到哈希桶的位置就能直接进行增删改查了，所以哈希表的增删改查时间复杂度都是O(1)。不过对于其他类型，比如ziplist，skiplist等集合类型的值的数据结构，复杂度增加，时间复杂度也会上升。
set中的值为HashTable数据结构
因为set中如果保存的值含有字符串，或者超过一定阈值的时候，值的数据结构为HashTable，所以我看了下是怎么存的。结果发现，存值的时候，值会以sds类型存，并且使用dictEntry的key指针指向值的，value指针为NULL。
int setTypeAdd(robj *subject, sds value) {
long long llval;
if (subject->encoding == OBJ_ENCODING_HT) {
dict *ht = subject->ptr;
dictEntry *de = dictAddRaw(ht,value,NULL);
if (de) {
dictSetKey(ht,de,sdsdup(value));
dictSetVal(ht,de,NULL);
return 1;
}
}
// 忽略
return 0;
}
总结
今天介绍了Redis中HashTable许多内容，包括了哈希表如果解决冲突，字典中结构中的变量含义，字典的整体结构，Redis的渐进式rehash和set中的值为HashTable数据结构时是如何存储的。
字典是Redis的底层数据结构，Redis每个键和值都是保存在了全局哈希表结构中，值中的数据结构其实不止SDS，也包括了ziplist、skiplist、intset和hashtable。
评论区