HashMap实现原理分析(7)

}

##Redis Redis 是一个高效的 key-value 缓存系统，也可以理解为基于键值对的数据库。它对哈希表的设计有非常多值得学习的地方，在不影响源代码逻辑的前提下我会尽可能简化，突出重点。

数据结构
在 Redis 中，字典是一个 dict 类型的结构体，定义在 src/dict.h 中:

typedef struct dict {
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;
这里的 dictht 是用于存储数据的结构体。注意到我们定义了一个长度为 2 的数组，它是为了解决扩容时速度较慢而引入的，其原理后面会详细介绍，rehashidx 也是在扩容时需要用到。先看一下 dictht 的定义:

typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long used;
} dictht;
可见结构体中有一个二维数组 table，元素类型是 dictEntry，对应着存储的一个键值对:

typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;
从 next 指针以及二维数组可以看出，Redis 的哈希表采用拉链法解决冲突。

添加元素
向字典中添加键值对的底层实现如下:

dictEntry *dictAddRaw(dict *d, void *key) {
int index;
dictEntry *entry;
dictht *ht;

if (dictIsRehashing(d)) _dictRehashStep(d); if ((index = _dictKeyIndex(d, key)) == -1) return NULL; ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0]; entry = zmalloc(sizeof(*entry)); entry->next = ht->table[index]; ht->table[index] = entry; ht->used++; dictSetKey(d, entry, key); return entry;

}
dictIsRehashing 函数用来判断哈希表是否正在重新哈希。所谓的重新哈希是指在扩容时，原来的键值对需要改变位置。为了优化重哈希的体验，Redis 每次只会移动一个箱子中的内容，下一节会做详细解释。

仔细阅读指针操作部分就会发现，新插入的键值对会放在箱子中链表的头部，而不是在尾部继续插入。这个细节上的改动至少带来两个好处:

找到链表尾部的时间复杂度是 O(n)，或者需要使用额外的内存地址来保存链表尾部的位置。头插法可以节省插入耗时。
对于一个数据库系统来说，最新插入的数据往往更有可能频繁的被获取。头插法可以节省查找耗时。
增量式扩容
所谓的增量式扩容是指，当需要重哈希时，每次只迁移一个箱子里的链表，这样扩容时不会出现性能的大幅度下降。

为了标记哈希表正处于扩容阶段，我们在 dict 结构体中使用 rehashidx 来表示当前正在迁移哪个箱子里的数据。由于在结构体中实际上有两个哈希表，如果添加新的键值对时哈希表正在扩容，我们首先从第一个哈希表中迁移一个箱子的数据到第二个哈希表中，然后键值对会被插入到第二个哈希表中。

在上面给出的 dictAddRaw 方法的实现中，有两句代码: