51工具盒子Redis数据结构-HashTable {#redis%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-hashtable}
在《Reids数据结构》这篇文章中，我们说到了Redis中的
Set和Hash数据类型底层都使用到了hashtable这个数据结构以及Redis的key-value数据库有一个全局哈希表，这里简单说下关于hashtable的结构。
Redis中的hashtable {#redis%E4%B8%AD%E7%9A%84hashtable}
hashtable在Redis中被称为dictionary（字典），是一个数组+链表的结构，正是因为这样hashtable查询数据的时间复杂度是O(1)。简单说就是将key通过Hash函数的计算，就能定位数据在表中的位置，通过索引值就可以直接在数组中获取到数据。既然是哈希表那肯定是有哈希冲突的，在数据逐渐增加的情况下，哈希冲突的可能性也在增加。Redis采用了链式哈希来解决哈希冲突，在不扩容哈希表的前提下，将具有相同哈希值的数据串起来，形成链接起，以便这些数据在表中仍然可以被查询到。（其实就是数组+链表，有点类似Java中的HashMap）。
结构设计 {#%E7%BB%93%E6%9E%84%E8%AE%BE%E8%AE%A1}
简单来说可以理解成Redis有
dictht这么一个结构，这个结构就是一个数组，而数组中的元素则是dictEntry，每个dictEntry元素都有一个指针*next指向哈希冲突的下一个节点形成一个链表。
# dictht数组
# +-----------+
# | dictEntry |
# +-----------+ +-----------+ +-----------+
# | dictEntry |-------->| dictEntry |-------->| ...... |
# +-----------+ +-----------+ +-----------+
# | dictEntry |
# +-----------+
# | dictEntry |
# +-----------+ +-----------+ +-----------+ +-----------+
# | dictEntry |-------->| dictEntry |-------->| dictEntry |-------->| ...... |
# +-----------+ +-----------+ +-----------+ +-----------+
# | dictEntry |
# +-----------+
# | dictEntry |
# +-----------+
在Redis6.0 的源码dict.h第72行中是这样定义dictht的:
/* 这是我们哈希表的结构。每个字典都有两个这样的结构，因为我们实现了增量式重新哈希，用于旧表和新表。*/
typedef struct dictht {
/* 哈希表的数组 */
dictEntry **table;
/* 哈希表的大小 */
unsigned long size;
/* 用来计算索引值的哈希表大小掩码 */
unsigned long sizemask;
/* 已经使用了的节点数量 */
unsigned long used;
} dictht;
从源码dict.h第50行中可以看到这个dictht就是一个数组，里面的元素就是指向dictEntry的指针。dictEntry的结构如下：
typedef struct dictEntry {
/* 键值对中的key */
void *key;
/* 键值对中的value */
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
/* 指向下一个节点 */
struct dictEntry *next;
} dictEntry;
可以看到dictEntry结构里面不仅仅有key 和value 的指针，还有一个指向下一个节点的指针*next，这就是上面说到的用来解决哈希冲突的链式哈希。如果计算出来哈希相同，那么直接在相同的dictEntry里将下一个节点的指针指向冲突的节点就行了。
但是随着数据量的增加，这个链表可能会越来越长，这就会导致查询时间也随着增加，因为链表的遍历时间复杂度是O(N)，那Redis是怎么解决这个问题的呢？在源码dict.h第79行中可以看到还有一个结构体dict，在这个结构里面定义了两个哈希表：
typedef struct dict {
dictType *type;
void *privdata;
/* 两个哈希表，交替使用 */
dictht ht[2];
/* 用来记录字典是否处于rehashing过程中（如果 rehashidx == -1 则表示没有进行 rehashing）*/
long rehashidx;
/* 用来记录当前正在运行的迭代器数量。 */
unsigned long iterators;
} dict;
rehash {#rehash}
为什么Redis在
dict结构要定义两个哈希表呢？
从上面我们知道，随着数据量增加，Redis中的链式哈希中链表长度也会越来越长，这也使得遍历的时间增加，为了解决这个问题，Redis会进行rehash操作，可以理解为给哈希表扩容，这样来减少哈希冲突，也就变向的减少了链表长度。
Redis中rehash的过程可以分为三个步骤：
- 首先给
ht[1]分配空间，一般是当前哈希表ht[0]的两倍。 - 把
ht[0]的数据迁移到ht[1]中。（Redis大部分操作是单线程的，这里Redis采用了渐进式rehash操作。） - 迁移完成后，
ht[0]的空间会被释放，并把ht[1]设置给ht[0]，然后在ht[1]创建一个空白的哈希表，为下次rehash做准备。
渐进式rehash {#%E6%B8%90%E8%BF%9B%E5%BC%8Frehash}
上面Redis在rehash过程中的第2步存在一个问题，那就是Redis大部分操作还是单线程的，这个过程可能会阻塞其他操作，如果是在数据量很大的时候，那可能会花很长时间来完成。所以Redis采用了渐进式rehash操作，简单说就是在每次操作的时候顺便copy到新的哈希表，而且Redis本身也有定时任务来处理。
在这个过程中，Redis中实际同时存在着两个哈希表（ht[0]和ht[1]），所以在这期间对于哈希表的查询操作会在这两张表上进行。比如想要查询一个key，那么Redis会先在ht[0]上查询，如果没有才会到ht[1]上查询。但是这个时候新增的key，也会直接保存到新的哈希表ht[1]中去，而对于ht[0]，不会在添加任何地key上去，这样慢慢地ht[0]就会变成空的哈希表。
rehash触发条件 {#rehash%E8%A7%A6%E5%8F%91%E6%9D%A1%E4%BB%B6}
Redis什么时候才会进行
rehash呢？
扩容 {#%E6%89%A9%E5%AE%B9}
在源码dict.c第958行有这么一个函数_dictExpandIfNeeded：
/* 如果需要，扩展哈希表 */
static int _dictExpandIfNeeded(dict *d){
/* 如果正在rehash那么就直接返回 */
if (dictIsRehashing(d)) return DICT_OK;
/* 如果哈希表为空，则将其扩展到初始大小 */
if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
/* 如果哈希表ht[0]中保存的key个数与哈希表大小的比例已经达到1:1，即保存的节点数已经大于等于哈希表大小，
* 并且当前redis的服务允许执行rehash（此时Redis没有在执行`bgsave`或者`bgrewiteaof`命令的时候）。
* 或者保存的节点数与哈希表大小的比例超过了安全阈值（默认值为5），
* 则将哈希表大小扩容为原来的两倍 */
if ((dict_can_resize == DICT_RESIZE_ENABLE &&
d->ht[0].used >= d->ht[0].size) ||
(dict_can_resize != DICT_RESIZE_FORBID &&
d->ht[0].used / d->ht[0].size > dict_force_resize_ratio)){
return dictExpand(d, d->ht[0].used*2);
}
return DICT_OK;
}
从上面源码中的注释可以看到rehash触发条件主要有两个：
- 当
used>=size（哈希表中已经使用了的节点数量大于等于哈希表的大小）并且此时Redis没有在执行bgsave或者bgrewiteaof命令时，会触发rehash。 - 或者当
used/size>dict_force_resize_ratio（哈希表中已经使用了的节点数量和哈希表的大小的比例超过5）时，不管此时Redis是否在执行bgsave或者bgrewiteaof命令，都会强制进行rehash操作。
缩容 {#%E7%BC%A9%E5%AE%B9}
在数据量增加的时候，Redis会进行
rehash，这个时候是扩容2倍，那么当数据减少的时候呢？
Redis在数据量减少的时候也会进行缩容，以便节约空间。在源码server.c第1700行有databasesCron这么一个函数用来处理Redis数据库中我们需要增量执行的"后台"操作，例如活动键过期、resize、rehash等。这里主要看resize部分：
void databasesCron(void) {
/* 通过随机抽样使键过期。对于Slave服务器来说不需要，因为Master服务器会同步DEL命令。*/
if (server.active_expire_enabled) {
if (iAmMaster()) {
activeExpireCycle(ACTIVE_EXPIRE_CYCLE_SLOW);
} else {
expireSlaveKeys();
}
}
/* 逐步对键进行碎片整理。 */
activeDefragCycle();
/* 在没有BGSAVE或者BGREWRITEAOF执行时，对哈希表进行 rehash */
if (!hasActiveChildProcess()) {
/* 使用全局计数器，这样如果在给定的DB上停止计算，我们就能在下一个定时任务从后续的DB开始*/
static unsigned int resize_db = 0;
static unsigned int rehash_db = 0;
int dbs_per_call = CRON_DBS_PER_CALL;
int j;
/* 不能超过拥有的DB最大数量 */
if (dbs_per_call > server.dbnum) dbs_per_call = server.dbnum;
/* Resize调整大小 */
for (j = 0; j < dbs_per_call; j++) {
tryResizeHashTables(resize_db % server.dbnum);
resize_db++;
}
/* Rehash */
if (server.activerehashing) {
for (j = 0; j < dbs_per_call; j++) {
int work_done = incrementallyRehash(rehash_db);
if (work_done) {
/* 如果已经rehash了一部分，在这里停止并在下一个计划循环中继续进行。*/
break;
} else {
/* 如果这个DB不需要rehash，接着尝试下一个*/
rehash_db++;
rehash_db %= server.dbnum;
}
}
}
}
}
可以看到缩容的时候也会选在没有bgsave或者bgrewiteaof执行的时候。可以看到主要是tryResizeHashTables这个函数在调整大小，这个函数源码在server.c第1436行：
int htNeedsResize(dict *dict) {
long long size, used;
size = dictSlots(dict);
used = dictSize(dict);
return (size > DICT_HT_INITIAL_SIZE &&
(used*100/size < HASHTABLE_MIN_FILL));
}
/* 如果哈希表中已用槽位的百分比达到 HASHTABLE_MIN_FILL，我们会重新调整哈希表的大小，以节省内存 */
void tryResizeHashTables(int dbid) {
if (htNeedsResize(server.db[dbid].dict))
dictResize(server.db[dbid].dict);
if (htNeedsResize(server.db[dbid].expires))
dictResize(server.db[dbid].expires);
}
HASHTABLE_MIN_FILL和DICT_HT_INITIAL_SIZE分别定义在server.h第168行和dict.h第76行中：
/* 每个hashtable的初始大小 */
#define DICT_HT_INITIAL_SIZE 4
/* 哈希表参数 */
#define HASHTABLE_MIN_FILL 10 /* 最小哈希表填充 10% */
可以看到HASHTABLE_MIN_FILL和DICT_HT_INITIAL_SIZE分别是10和4，那么从htNeedsResize就可以得知当哈希表的大小大于初始容量且保存的key数量与哈希表的大小的比例小于0.1的时候需要缩容。
