字典又称散列表，是用来存储键值（key-value）对的一种数据结构，在很多高级语言中都有实现，如Java的Map。但是C语言没有这种数据结构，Redis是K-V型数据库，整个数据库是用字典来存储的，对Redis 数据库进行任何增、删、改、查操作，实际就是对字典中的数据进行增、删、改、查操作。
1、数据结构
Java中的HashMap就是典型的字典，这里以JDK1.7的HashMap（只用链表处理哈希冲突）为例：
- 对键key进行哈希，获取hash值再通过取余等操作得到索引值，通过索引在数组找到对应元素，如果没有找到元素，说明这个key在字典中不存在，如果找到元素，执行第2步。
- 字典中的元素同时存储着键key、值value和发生哈希冲突的元素next，将元素的key和要查找的key进行比较，如果相等则将值value取出，如果不相等，则继续查找next元素的，直到next元素指向NULL，则说明该key在字典中不存在。
在Redis中，字典实现主要依靠于：字典、Hash表和Hash表节点。字典中有两个Hash表，每个Hash表存储若干Hash表节点，每个Hash表节点存储着键值对K-V。
1.1、Hash表
//该结构体一共占用4*8=32字节
typedef struct dictht {
// 指针数组 里面的指针元素指向Hash表节点
dictEntry **table;
// table的长度，该长度初始值为4，哈希表的容量会翻倍扩容，即8，16,32……
unsigned long size;
/* 掩码，上面的size-1，这样获得的数字在二进制下为11,111,1111……每一位都为1，方便按位与操作，
这样：索引值=Hash&sizemask。这样得出结果和Hash%size相等，且按位与操作远比取余快得多。
*/
unsigned long sizemask;
// table数组已存储元素个数 包括Hash冲突的链表
unsigned long used;
} dictht;
1.2、Hash表节点
Hash表中的dictEntry **table中每个指针，就是指向Hash表节点：
// 该结构体一共占用3*8=24字节
typedef struct dictEntry {
// 键
void *key;
//共用体表示值 根据不同场景使用不同字段
union {
// 当用于存储整个Redis所有键值对时，使用val表示值
void *val;
uint64_t u64;
// 当用于记录键的过期时间时，使用s64表示过期时间
int64_t s64;
double d;
} v;
// 指向Hash冲突的元素
struct dictEntry *next;
} dictEntry;
1.3 字典
// 该结构体一共占用4*8+2*32=96字节
typedef struct dict {
// 函数指针 每个字典都有对应的操作
dictType *type;
// 字典独有字段 配合上面的函数指针进行操作
void *privdata;
// 两个Hash表 在Hash扩容缩小时，需要再哈希rehash，这时需要两个哈希表，一般只会使用ht[0]一个哈希表
dictht ht[2];
// rehash的标识 默认为-1，表示该字典未进行rehash。进行rehash时，该值表示rehash到了那个索引
long rehashidx;
/* 当前运行的迭代器数，当有安全迭代器绑定到该字典时，迭代数+1，暂停rehash操作，迭代结束-1。
普通的迭代器不会影响该数值*/
unsigned long iterators;
} dict;
type字段指向dictType结构体，内部一共六个函数指针：
typedef struct dictType {
// 字典使用的Hash函数
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);
} dictType;
2、基本操作
主要也是增删改查操作。
2.1、初始化字典
首先在服务器redis-server启动时，需要一个空字典用于存储整个Redis的键值对：
static dict *dictCreate(dictType *type, void *privDataPtr) {
// 申请96个字节内存生成一个空字典
dict *ht = malloc(sizeof(*ht));
// 结构体初始化赋值
_dictInit(ht,type,privDataPtr);
return ht;
}
以下字典初始化赋值操作：
int _dictInit(dict *d, dictType *type,void *privDataPtr){
/*将一个早已初始化的哈希表重新赋值
static void _dictReset(dict *ht) {
ht->table = NULL;
ht->size = 0;
ht->sizemask = 0;
ht->used = 0;
}
*/
_dictReset(&d->ht[0]);
_dictReset(&d->ht[1]);
d->type = type;
d->privdata = privDataPtr;
d->rehashidx = -1;
d->iterators = 0;
return DICT_OK;
}
2.2、添加元素
当我们使用redis的客户端，执行set key value的时候，就是在向数据库字典里面尝试添加一对键值对，此时redis服务端会判断key是否存在，如果存在则修改value，否则就新增key和value。
void setKey(redisDb *db, robj *key, robj *val) {
// 如果没有找到key，就新增
if (lookupKeyWrite(db,key) == NULL) {
dbAdd(db,key,val);
} else {
// 找到了key，即修改
dbOverwrite(db,key,val);
}
incrRefCount(val);
removeExpire(db,key);
signalModifiedKey(db,key);
}
2.2.1 查找key
robj *lookupKeyWrite(redisDb *db, robj *key) {
// 先检查key是否过期
expireIfNeeded(db,key);
// 查找key
return lookupKey(db,key,LOOKUP_NONE);
}
robj *lookupKey(redisDb *db, robj *key, int flags) {
// 真正查找key的函数
dictEntry *de = dictFind(db->dict,key->ptr);
if (de) {
robj *val = dictGetVal(de);
if (server.rdb_child_pid == -1 &&
server.aof_child_pid == -1 &&
!(flags & LOOKUP_NOTOUCH))
{
if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
updateLFU(val);
} else {
val->lru = LRU_CLOCK();
}
}
return val;
} else {
return NULL;
}
}
static dictEntry *dictFind(dict *ht, const void *key) {
dictEntry *he;
unsigned int h;
// 哈希表长度为0 不用查找 肯定没有key 直接返回NULL
if (ht->size == 0) return NULL;
// 取得该key对应的索引
h = dictHashKey(ht, key) & ht->sizemask;
// 根据索引拿到哈希表节点
he = ht->table[h];
// 当取得的哈希表节点不为NULL时
while(he) {
// 比较两个键是否相同
if (dictCompareHashKeys(ht, key, he->key))
return he;
// 如果不同 继续往后查找next节点
he = he->next;
}
return NULL;
}
2.2.2 、添加键值对
当客户端输入的key为新key时，添加键值对。
void dbAdd(redisDb *db, robj *key, robj *val) {
// 赋值key字符串
sds copy = sdsdup(key->ptr);
// 真正的添加函数
int retval = dictAdd(db->dict, copy, val);
……
}
// 新增键值对
int dictAdd(dict *d, void *key, void *val)
{
// 首先添加键，若字典已存在该键返回NULL，否则添加至新节点并返回新节点
dictEntry *entry = dictAddRaw(d,key,NULL);
// 键存在 则返回错误 因为新增操作的key应该是不存在于字典中的
if (!entry) return DICT_ERR;
// 往节点中添加值
dictSetVal(d, entry, val);
return DICT_OK;
}
// dictAddRaw函数 添加键并返回新的节点
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
long index;
dictEntry *entry;
dictht *ht;
// 判断字典是否在处于再哈希状态 是则执行一次再哈希
if (dictIsRehashing(d)) _dictRehashStep(d);
// _dictKeyIndex函数找到键返回-1，把原节点存至existing，否则返回新节点索引，也可能会触发哈希表的扩容
if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
return NULL;
// 如果字典处于再哈希状态，那么去ht[1]，否则还是使用ht[0]
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;
}
// 根据键查找哈希表索引的_dictKeyIndex函数
static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing)
{
unsigned long idx, table;
dictEntry *he;
if (existing) *existing = NULL;
// 判断是否需要扩容
if (_dictExpandIfNeeded(d) == DICT_ERR)
return -1;
for (table = 0; table <= 1; table++) {
// 通过哈希值和掩码获取索引
idx = hash & d->ht[table].sizemask;
// 根据索引获取哈希表节点指针
he = d->ht[table].table[idx];
// 如果节点存在继续判断
while(he) {
// 判断找到的key和新key或者两个key的哈希值是否相等，
if (key==he->key || dictCompareKeys(d, key, he->key)) {
// 如果相等，说明新插入的key已存在吗，返回-1，否则继续往下比较next
if (existing) *existing = he;
return -1;
}
he = he->next;
}
// 如果未进行rehash，那么不需要查找ht[1]，直接返回NULL
if (!dictIsRehashing(d)) break;
}
return idx;
}
2.2.3、字典的扩容
当添加新键的时候，可能会触发扩容：
int dictExpand(dict *d, unsigned long size)
{
// 如果字典处于再哈希状态，或者ht[0]已使用长度大于size，直接返回错误
if (dictIsRehashing(d) || d->ht[0].used > size)
return DICT_ERR;
// 新的哈希表
dictht n;
// 计算新哈希表的长度，必须为2的整数次幂，如果是从0扩容，默认长度为4，否则长度会翻倍
unsigned long realsize = _dictNextPower(size);
// 如果新哈希表的长度和原表长度一样 则返回错误
if (realsize == d->ht[0].size) return DICT_ERR;
// 分配一个新的哈希表 并初始化各字段
n.size = realsize;
n.sizemask = realsize-1;
n.table = zcalloc(realsize*sizeof(dictEntry*));
n.used = 0;
// 如果是第一次扩容，即从0到默认的4，那么直接将ht[0]指向新哈希表
if (d->ht[0].table == NULL) {
d->ht[0] = n;
return DICT_OK;
}
// 将ht[1]指向新哈希表，并设置rehashidx = 0，表示需要再哈希
d->ht[1] = n;
d->rehashidx = 0;
return DICT_OK;
}
扩容后需要注意，字典的size和sizemask发生了变化，由于key的索引是通过Hash值和掩码按位与得到的，所以扩容后需要重新计算索引，这一过程就是rehash。
2.3.4、 rehash
准确来说，只要哈希表的容量发生了变化，那么都需要rehash。Redis的rehash主要分为三步：
- 为ht[1] 申请空间，当扩容时容量为ht[0]的2倍，当容量利用率不足10%时，将容量缩小为最接近当前已用容量的2的整数次幂，也就是说不论扩容缩容，都要保证哈希表容量的大小一定要是2的整数次幂。申请完空间后，将字典中的rehashidx改为0，表示开始rehash。
- 调用dictRehash函数，重新计算ht[0]中每个键的Hash值与索引值，然后依次添加到ht[1]中并删除原键值对。字典中的字段rehashidx改为ht[0]当前正在进行rehash操作的节点的索引值。
- rehash操作完成后，清空ht[0]，然后调换ht[0]和ht[1]，这样ht[0]就是新的完整的哈希表，最后把rehashidx字段改回-1，表示当前没有rehash操作。
Redis作为一款高性能的单进程数据库，需要提供快速的存取服务，当数据库中的键值对数量达到很高的数量级时，直接进行rehash会十分耗费时间，会导致严重的服务不可用。Redis对此做出了自己的优化，具体操作如下：
在执行正删改查操作之前，判断字典是否在rehash，如果在进行则调用dictRehashStep函数进行rehash，每次调用只会对1个节点操作1次。当服务空闲时，若字典也需rehash操作，那么会调用incrementallyRehash函数批量进行rehash操作，每次对100个节点操作，耗时1毫秒。所以，整个rehash操作被分配到多次操作中，对于客户端来说几乎无感知。
2.3、查找元素
命令：get key
根据客户端给出的键查找值。
dictEntry *dictFind(dict *d, const void *key)
{
dictEntry *he;
uint64_t h, idx, table;
// 如果整个字典还是空的，直接返回NULL
if (d->ht[0].used + d->ht[1].used == 0) return NULL;
// 如果字典需要rehash，那么执行1次rehash
if (dictIsRehashing(d)) _dictRehashStep(d);
// 计算出key的Hash值
h = dictHashKey(d, key);
// 遍历两个哈希表
for (table = 0; table <= 1; table++) {
// Hash值按位与掩码，得到索引
idx = h & d->ht[table].sizemask;
// 根据索引得到哈希表节点
he = d->ht[table].table[idx];
// 如果哈希表节点存在
while(he) {
// 比较两个key的值和其哈希值，只要其中一个相等就返回哈希表节点
if (key==he->key || dictCompareKeys(d, key, he->key))
return he;
// 继续查找next节点
he = he->next;
}
// 如果未进行rehash，那么不需要查找ht[1]，直接返回NULL
if (!dictIsRehashing(d)) return NULL;
}
return NULL;
}
2.4、修改元素
修改和新增是同一个函数setKey(redisDb *db, robj *key, robj *val)的不同分支,主要函数为dbOverwrite：
void dbOverwrite(redisDb *db, robj *key, robj *val) {
// 根据键查找节点
dictEntry *de = dictFind(db->dict,key->ptr);
// 找不到节点就停止更新操作
serverAssertWithInfo(NULL,key,de != NULL);
dictEntry auxentry = *de;
// 获取原val值
robj *old = dictGetVal(de);
if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
val->lru = old->lru;
}
// 将新的val设置到节点中
dictSetVal(db->dict, de, val);
// 服务是否配置了异步执行删除操作
if (server.lazyfree_lazy_server_del) {
// 异步释放原val的内存
freeObjAsync(old);
dictSetVal(db->dict, &auxentry, NULL);
}
// 释放原val的内存
dictFreeVal(db->dict, &auxentry);
}
2.5、删除元素
int dictDelete(dict *ht, const void *key) {
return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR;
}
static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
uint64_t h, idx;
dictEntry *he, *prevHe;
int table;
if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL;
if (dictIsRehashing(d)) _dictRehashStep(d);
h = dictHashKey(d, key);
// 根据key查找节点
for (table = 0; table <= 1; table++) {
idx = h & d->ht[table].sizemask;
he = d->ht[table].table[idx];
prevHe = NULL;
// 如果节点存在则进行删除
while(he) {
// 通过比较后，删除节点，释放内存，调整链表结构
if (key==he->key || dictCompareKeys(d, key, he->key)) {
// 根据要删除的元素位置，调整链表
if (prevHe)
prevHe->next = he->next;
else
d->ht[table].table[idx] = he->next;
if (!nofree) {
dictFreeKey(d, he);
dictFreeVal(d, he);
zfree(he);
}
// 将已使用节点数减一
d->ht[table].used--;
return he;
}
prevHe = he;
he = he->next;
}
if (!dictIsRehashing(d)) break;
}
return NULL;
}
注意，删除可能会触发缩容操作，缩容其实调用的是扩容使用的dictExpand(dict *d, unsigned long size)函数，只不过将size变小了。
3、字典的遍历
举例Redis两种遍历的命令：keys和hscan。前者会一次性遍历整个数据库；而后者每次执行只取部分数据，分多次遍历。
3.1、迭代器遍历
迭代器（iterator）有时又称光标（cursor）是程序设计的软件设计模式，可在容器对象（container，例如链表或数组）上遍访的接口，设计人员无需关心容器对象的内存分配的实现细节。
在Redis字典的迭代过程中，如果出现rehash操作，由于数据会先拷贝到另一个哈希表中，那么可能导致同一条数据被多次遍历，想要明白Redis如何解决这个问题，还需要看一下迭代器的实现。
// 整个结构体大小为：5*8+2*4=48字节
typedef struct dictIterator {
// 迭代的字典
dict *d;
// 迭代到的哈希表索引
long index;
// table指当前正在迭代的哈希表ht[0]或ht[1]，safe表示是否为安全迭代器
int table, safe;
// 当前哈希表节点和接下来的哈希表节点
dictEntry *entry, *nextEntry;
// 字典的指纹，当字典发生变化时该值也会发生变化
long long fingerprint;
} dictIterator;
Redis是单进程单线程模式，所以如果执行遍历命令时不修改数据，就不会触发rehash，迭代器根据safe字段分为两种：0表示普通迭代器，1表示安全迭代器。普通迭代器只进行遍历，而安全迭代器遍历数据的同时还可以删除数据。
3.1.1、 普通迭代器
普通迭代器会对字典指纹字段fingerprint，做严格的校验以确保迭代过程中字典结构没有发生变化，读取出的数据也不会重复。
-
使用dictGetIterator函数初始化一个普通迭代器：
dictIterator *dictGetIterator(dict *d) { dictIterator *iter = zmalloc(sizeof(*iter)); iter->d = d; iter->table = 0; iter->index = -1; // safe = 0表示这是一个普通迭代器 iter->safe = 0; iter->entry = NULL; iter->nextEntry = NULL; return iter; } -
循环调用dictNext函数遍历哈希表节点：
dictEntry *dictNext(dictIterator *iter) { while (1) { // 迭代器entry节点为NULL 取当前哈希表 if (iter->entry == NULL) { dictht *ht = &iter->d->ht[iter->table]; // 当还迭代索引为-1且迭代的哈希表为ht[0]，即第一次开始迭代时 if (iter->index == -1 && iter->table == 0) { // 如果是安全迭代器，则将字典的iterators字段+1，这样字典会暂停rehash if (iter->safe) iter->d->iterators++; // 如果是普通迭代器，则计算字典的指纹并赋值给fingerprint字段 else iter->fingerprint = dictFingerprint(iter->d); } // 迭代索引+1 iter->index++; // 判断当前哈希表是否迭代到最后 if (iter->index >= (long) ht->size) { /* 字典正在rehash且迭代的是ht[0]，那么开始迭代ht[1]并将迭代索引置为0，否则说明 整个字典迭代完毕，结束循环*/ if (dictIsRehashing(iter->d) && iter->table == 0) { iter->table++; iter->index = 0; ht = &iter->d->ht[1]; } else { break; } } // 根据索引取出节点 iter->entry = ht->table[iter->index]; } else { // 如果entry不为NULL，那么取出单链表的下一个节点 iter->entry = iter->nextEntry; } // 如果entry不为NULL，nextEntry指向单链表下一个节点，返回当前节点 if (iter->entry) { iter->nextEntry = iter->entry->next; return iter->entry; } } return NULL; } -
利用dictNext函数遍历完，释放迭代器：
void dictReleaseIterator(dictIterator *iter) { // 如果迭代器索引不为-1或者迭代器的table不为0 if (!(iter->index == -1 && iter->table == 0)) { // 如果是安全迭代器，就将字典的iterators字段-1，这样可以继续进行rehash if (iter->safe) iter->d->iterators--; else /*对于普通迭代器，重新计算字典指纹并与第一次迭代时计算的字典指纹比较。 如果两个指纹相等，即字典在迭代过程中发生了其它操作，就输出异常并退出程序。*/ assert(iter->fingerprint == dictFingerprint(iter->d)); } zfree(iter); }
3.1.2、安全迭代器
安全迭代器的原理和普通迭代器类似，在普通迭代器中已经介绍过，是通过限制字典的rehash操作保证数据的准确。rehash的相关函数如：
static void _dictRehashStep(dict *d) {
// 只有当前绑定的迭代器为普通迭代器才进行rehash
if (d->iterators == 0) dictRehash(d,1);
}
所以当字典被安全迭代器遍历时，并不会进行rehash。
3.2、间断遍历
迭代器是完全遍历，当数据量很大时，耗时较长，导致短时间内Redis不可用。Redis另外提供了一个scan操作，即间断遍历。字典的间断遍历由dictScan函数实现：
/*d：迭代的字典 v：迭代开始的游标，即哈希表数组的索引 fn：函数指针，每个遍历到的哈希表节点都要用这个函数处理
bucketfn：函数指针，整理碎片时使用 private：回调函数fn所需的参数*/
unsigned long dictScan(dict *d,
unsigned long v,
dictScanFunction *fn,
dictScanBucketFunction* bucketfn,
void *privdata)
{
dictht *t0, *t1;
const dictEntry *de, *next;
unsigned long m0, m1;
if (dictSize(d) == 0) return 0;
if (!dictIsRehashing(d)) {
t0 = &(d->ht[0]);
m0 = t0->sizemask;
/* Emit entries at cursor */
if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
de = t0->table[v & m0];
while (de) {
next = de->next;
fn(privdata, de);
de = next;
}
/* Set unmasked bits so incrementing the reversed cursor
* operates on the masked bits */
v |= ~m0;
/* Increment the reverse cursor */
v = rev(v);
v++;
v = rev(v);
} else {
t0 = &d->ht[0];
t1 = &d->ht[1];
/* Make sure t0 is the smaller and t1 is the bigger table */
if (t0->size > t1->size) {
t0 = &d->ht[1];
t1 = &d->ht[0];
}
m0 = t0->sizemask;
m1 = t1->sizemask;
/* Emit entries at cursor */
if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
de = t0->table[v & m0];
while (de) {
next = de->next;
fn(privdata, de);
de = next;
}
/* Iterate over indices in larger table that are the expansion
* of the index pointed to by the cursor in the smaller table */
do {
/* Emit entries at cursor */
if (bucketfn) bucketfn(privdata, &t1->table[v & m1]);
de = t1->table[v & m1];
while (de) {
next = de->next;
fn(privdata, de);
de = next;
}
/* Increment the reverse cursor not covered by the smaller mask.*/
v |= ~m1;
v = rev(v);
v++;
v = rev(v);
/* Continue while bits covered by mask difference is non-zero */
} while (v & (m0 ^ m1));
}
return v;
}