Redis 数据结构-字典源码分析---Java技术大杂烩

本文首发于个人公众号 Java 技术大杂烩，欢迎关注

前言

字典这种数据结构并不是 Redis 那几种基本数据结构，但是 hash ， sets 和 sorted sets 这几种数据结构在底层都是使用字典来实现的（并不仅仅是字典），现在看下它的实现原理。

结构

Redis 字典的结构和 Java 中的 HashMap 有点类似，都是存放键值对，在底层都是使用数组加链表（称为一个哈希表）的形式来实现的，但与 HashMap 不同的是，在 Redis 中，它由两个哈希表组成，它的结构大致如下图所示：

由上图可以看到，它使用两个 hashtable ，姑且称之为 0 号哈希表和 1 号哈希表，每次只会使用 0 号哈希表，那么 1 号哈希表有什么用呢？当哈希表的键值对很多或很少的话，就需要对哈希表进行扩展或缩小，比如哈希表中数组的大小默认为 4 ，如果哈希表中键值对很多，则数组中每项的链表就会很长，而链表查找速度很很慢，不像数组那样根据索引定位，所以为了让哈希表的负载因子（load factor）维持在一个合理的范围内，就需要对哈希表进行扩展或缩小，称为 rehash。

结构定义

接下来看下上述结构图的定义，

首先看下字典结构的定义：

typedef struct dict { dictType *type; //字典类型 void *privdata; //私有数据 dictht ht[2]; // 哈希表，有两个，实现渐进式rehash long rehashidx; // rehash 索引，当不进行rehash的时候，值为-1 unsigned long iterators; // 当前正在运行的迭代器的数量 } dict;

其中，dictht ht[2] 对应的是上图中的ht[0]和[1]。

之后，看下哈希表的定义：

/* * 哈希表 */ typedef struct dictht { // 哈希表数组 dictEntry **table; // 哈希表大小 unsigned long size; unsigned long sizemask; // 该哈希表已有节点的数量 unsigned long used; } dictht;

对应的上图中的哈希表数组，数组中的每一项是链表，链表节点使用 dictEntry 表示，接下来看下 dictEntry 的定义：

//哈希表节点 typedef struct dictEntry { // 键 void *key; // 值 union { void *val; uint64_t u64; int64_t s64; double d; } v; // 指向下个哈希表节点，形成链表 struct dictEntry *next; } dictEntry;

以上的定义就表示的字典的数据结构，上述的定义代码是在 dict.h 文件中，该文件中，除了上述代码外，还有一些其他的API定义，如迭代器等。

接下来看下字典的操作，如添加元素，删除元素，查找元素，rehash 等，这个操作代码主要是在 dict.c 文件中

字典操作

首先看下几个公共的方法；

_dictInit : 初始化哈希表int _dictInit(dict *d, dictType *type, void *privDataPtr) { // 初始化两个哈希表的各项属性值 // 但暂时还不分配内存给哈希表数组 _dictReset(&d->ht[0]); _dictReset(&d->ht[1]); d->type = type; // 设置类型 d->privdata = privDataPtr; // 设置私有数据 d->rehashidx = -1; // 设置 rehash的状态，表示不正在rehash d->iterators = 0; // 设置安全迭代器数量 return DICT_OK; }_dictKeyIndex: 根据 key 来获取添加的这个键值对应该存放在哈希表中的索引。//如果 key 已经存在于哈希表，那么返回 -1 //如果字典正在进行 rehash ，那么总是返回 1 号哈希表的索引。因为在字典进行 rehash 时，新节点总是插入到 1 号哈希表。 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; // 遍历 0 号哈希表和 1 号哈希表 for (table = 0; table <= 1; table++) { // 获取哈希表中的每一项 idx = hash & d->ht[table].sizemask; //获取每一项的链表 he = d->ht[table].table[idx]; // 遍历链表 while(he) { // 如果key 存在，则放回 -1 if (key==he->key || dictCompareKeys(d, key, he->key)) { if (existing) *existing = he; return -1; } he = he->next; } // 如果哈希表没有正在进行rehash操作，则表示只有 0 号哈希表中有数据，就不要在 1 号哈希表中进行查找 // 否则的话，就还需要遍历 1 号哈希表进行查找 if (!dictIsRehashing(d)) break; } // 返回索引 return idx; }_dictExpandIfNeeded : 哈希表是否需要扩展static int _dictExpandIfNeeded(dict *d) { // 如果正在进行 rehash，则表示正在进行扩展，直接返回 OK if (dictIsRehashing(d)) return DICT_OK; // 如果 0 号哈希表为空，则需要对哈希表进行初始化，初始化哈希表数组的大小为DICT_HT_INITIAL_SIZE // #define DICT_HT_INITIAL_SIZE 4 // 可以看到，哈希表数组的初始大小为 4 if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE); // 以下两个条件之一为真时，对字典进行扩展 // 1）字典已使用节点数和字典大小之间的比率接近 1：1 并且 dict_can_resize 为真 // 2）已使用节点数和字典大小之间的比率超过 dict_force_resize_ratio // static unsigned int dict_force_resize_ratio = 5; if (d->ht[0].used >= d->ht[0].size && (dict_can_resize || d->ht[0].used/d->ht[0].size > dict_force_resize_ratio)) { // 新哈希表的大小至少是目前已使用节点数的两倍 return dictExpand(d, d->ht[0].used*2); } return DICT_OK; }

上述代码中，如果哈希表为空，即是第一次添加元素的时候，需要初始化哈希表，哈希表的大小为 4 ，如下所示：

还有一种情况是，如果哈希表的已有的节点和哈希表的大小的比例超过阈值 dict_force_resize_ratio 即 5 的时候，需要对哈希表进行扩展，

扩展的哈希表大小为已使用节点的2倍，如果哈希表的大小为 4 ，已使用节点数量为24， 则 24/4 > 5 ，就需要对哈希表进行扩展，此时哈希表的大小为 24*2 = 48。

dictExpand : 扩展哈希表的过程// 扩展或创建一个新的哈希表 int dictExpand(dict *d, unsigned long size) { // 如正在进行 rehash，表示已经进行扩展，返回扩展失败 // 如果扩展的大小比已有节点还要小，则扩展失败 if (dictIsRehashing(d) || d->ht[0].used > size) return DICT_ERR; dictht n; /* the new hash table */ // 新的哈希表的大小，为 2 的 size 次方 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 号哈希表为空，表示这是一次初始化：将新哈希表赋给 0 号哈希表。 if (d->ht[0].table == NULL) { d->ht[0] = n; return DICT_OK; } // 如果 0 号哈希表非空，那么这是一次 rehash ：程序将新哈希表设置为 1 号哈希表， // 并将字典的 rehash 标识打开，让程序可以开始对字典进行 rehash d->ht[1] = n; d->rehashidx = 0; return DICT_OK; }rehash

接下来看下字典的 rehash，字典为什么需要 rehash，随着操作的不断执行， 哈希表保存的键值对会逐渐地增多或者减少， 如果保存的键值很多，哈希表较小，则哈希表中每一项的链表就会很长，而链表的查找速度较慢，所以为了让哈希表的负载因子（load factor）维持在一个合理的范围之内， 当哈希表保存的键值对数量太多或者太少时， 程序需要对哈希表的大小进行相应的扩展或者收缩。而在 Redis 的字典扩展或缩小的过程中，是一个渐进式的过程，为什么不是一次性进行操作，而是渐进式的方式？因为如果字典较大，在扩展的时候，需要重新申请空间，再把旧字典的值 copy 到新的字典中取，这是一个 O(n) 的操作，很费时，所有，采用的是渐进式的方式，在字典进行扩展的过程中，还可以进行其他的操作，如添加，查找等。rehash 的过程就是根据 0 号哈希表的已有节点来计算需要扩展的大小，根据该大小创建 1 号哈希表，再把 0 号哈希表的数据慢慢移动到 1 号哈希表上，rehash 指的是重新计算键的哈希值和索引值， 然后将键值对放置到 ht[1] 哈希表的指定位置上。当移到完成后，再把 1 号哈希表赋给 0 号哈希表，之后清空 1 号哈希表，为下次 rehash 做准备。

接下来从代码层面看下 rehash 的过程：

// 执行 N 步渐进式 rehash // 返回 1 表示仍有键需要从 0 号哈希表移动到 1 号哈希表， // 返回 0 则表示所有键都已经迁移完毕。 // 注意：rehash的时候，都是以桶（链表）为单位的，一个桶里面可能有多个节点， int dictRehash(dict *d, int n) { int empty_visits = n*10; /* Max number of empty buckets to visit. */ // 如果rehash已经完毕，则返回0 if (!dictIsRehashing(d)) return 0; while(n-- && d->ht[0].used != 0) { dictEntry *de, *nextde; assert(d->ht[0].size > (unsigned long)d->rehashidx); while(d->ht[0].table[d->rehashidx] == NULL) { d->rehashidx++; if (--empty_visits == 0) return 1; } // 取出hash表中的每个桶 de = d->ht[0].table[d->rehashidx]; // 循环把该桶中所有的键移动到新的hash表中，桶中的节点以链表的形式存放 while(de) { uint64_t h; nextde = de->next; // 在新的哈希表中获取要存放元素的索引 h = dictHashKey(d, de->key) & d->ht[1].sizemask; // 移动元素 de->next = d->ht[1].table[h]; d->ht[1].table[h] = de; d->ht[0].used--; d->ht[1].used++; de = nextde; // 下一个节点 } // 该桶中的所有key都转移成功后，置为null， d->ht[0].table[d->rehashidx] = NULL; // 获取下一个桶 d->rehashidx++; } // 当0号哈希表中所有的键都移到1号表后， if (d->ht[0].used == 0) { zfree(d->ht[0].table); // 重置 0 号哈希表 d->ht[0] = d->ht[1]; // 把 1 号哈希表的指针赋值给 0 号表 _dictReset(&d->ht[1]); // 重置1号哈希表，为下一次rehash做准备 d->rehashidx = -1; // rehash完成 return 0; // rehash完成 } return 1; }dictAdd: 向字典中添加元素int dictAdd(dict *d, void *key, void *val) { // 键添加到字典，并返回包含了这个键的新哈希节点 dictEntry *entry = dictAddRaw(d,key,NULL); // 如果键存在，添加失败 if (!entry) return DICT_ERR; // 如果键不存在，则设置值 dictSetVal(d, entry, val); return DICT_OK; } //将键插入到字典中，如果键已经存在，则返回null，否则的话，以该键创建新的哈希节点，插入到字典中并返回 dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing) { long index; dictEntry *entry; dictht *ht; //进行 rehash if (dictIsRehashing(d)) _dictRehashStep(d); // 在哈希表中获取新元素存放的索引，如果元素已存在，则返回null if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1) return NULL; //如果正在进行rehash，则直接把新元素插入到 1 号哈希表中，否则的话，将新元素插入到 0 号哈希表中 ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0]; // 分配空间 entry = zmalloc(sizeof(*entry)); // 把新节点插入到对应的索引中 entry->next = ht->table[index]; ht->table[index] = entry; //哈希表中已使用节点加1 ht->used++; // 设置新节点的键 dictSetKey(d, entry, key); // 返回新创建的节点 return entry; }

如下图所示：

dictDelete : 删除节点// 删除成功，返回 OK ， 如果找不到对应的键，则删除失败 int dictDelete(dict *ht, const void *key) { return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR; } // 查找并删除包含给定键的节点 // 参数 nofree 决定是否调用键和值的释放函数, 0 表示调用，1 表示不调用 static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) { uint64_t h, idx; dictEntry *he, *prevHe; int table; // 0 号哈希表和 1 号哈希表中使用节点的数量都为0，表示哈希表为空 if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL; if (dictIsRehashing(d)) _dictRehashStep(d); //计算key的哈希值 h = dictHashKey(d, key); //两个哈希表，表示需要在两个哈希表中查找 for (table = 0; table <= 1; table++) { //计算索引值 idx = h & d->ht[table].sizemask; //指向该索引上的链表 he = d->ht[table].table[idx]; // 当前节点的上一个节点 prevHe = NULL; //遍历该链表上的所有节点 while(he) { // 找到要删除的key 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); } //使用节点减1 d->ht[table].used--; //返回删除的节点 return he; } // 把当前节点设置为前一个节点 prevHe = he; //查找下一个节点 he = he->next; } // 如果字典不正在进行 rehash，表示只有 0 号哈希表中有数据，不需要在 1 号哈希表中进行查找 // 否则，如果 rehash 正在进行，则还需要在 1 号哈希表中进行查找删除 if (!dictIsRehashing(d)) break; } return NULL; /* not found */ }

删除节点的过程如下：

if (prevHe) // 如果要删除的节点的前一个节点不为空，则删除该节点 prevHe->next = he->next; else // 如果要删除的节点是第一个节点，则直接把该节点的下一个节点设置为该链表的头节点 d->ht[table].table[idx] = he->next;

前一个节点不为空：prevHe->next = he->next

要删除的是第一个节点：d->ht[table].table[idx] = he->next

dictFetchValue : 查找对应键的值，//返回对应键的值 void *dictFetchValue(dict *d, const void *key) { dictEntry *he; he = dictFind(d,key); return he ? dictGetVal(he) : NULL; } //查找key对应的节点 dictEntry *dictFind(dict *d, const void *key) { dictEntry *he; uint64_t h, idx, table; //哈希表为空 if (d->ht[0].used + d->ht[1].used == 0) return NULL; /* dict is empty */ // 正在rehash if (dictIsRehashing(d)) _dictRehashStep(d); // 计算键的哈希值 h = dictHashKey(d, key); //在 0 号哈希表和 1 号哈希表中查找 for (table = 0; table <= 1; table++) { // 索引值 idx = h & d->ht[table].sizemask; // 索引值对应的链表 he = d->ht[table].table[idx]; // 遍历链表 while(he) { // 找到就返回 if (key==he->key || dictCompareKeys(d, key, he->key)) return he; he = he->next; } // 如果正在进行rehash，1号哈希表中可能也有数据，则需要再在1号哈希表中进行查找， // 如果rehash完毕了，表示只有0号哈希表中有数据，就不需要在1号哈希表中查找了，直接返回null if (!dictIsRehashing(d)) return NULL; } return NULL; }命令操作字典

接下来看下 hash， sets 和 sorted sets 命令是如何操作字典的。

hash 操作字典添加操作：// hash 底层存放数据不仅仅是字典这种数据结构，还有压缩列表等结构 int hashTypeSet(robj *o, sds field, sds value, int flags) { int update = 0; if (o->encoding == OBJ_ENCODING_ZIPLIST) { ........................ // 如果该对象的编码方式是字典的方式，则需要在字典中添加该键值对 } else if (o->encoding == OBJ_ENCODING_HT) { dictEntry *de = dictFind(o->ptr,field); // 如果已存在，则更新 if (de) { sdsfree(dictGetVal(de)); if (flags & HASH_SET_TAKE_VALUE) { dictGetVal(de) = value; value = NULL; } else { dictGetVal(de) = sdsdup(value); } update = 1; } else { sds f,v; if (flags & HASH_SET_TAKE_FIELD) { f = field; field = NULL; } else { f = sdsdup(field); } if (flags & HASH_SET_TAKE_VALUE) { v = value; value = NULL; } else { v = sdsdup(value); } // 向字典中添加元素 dictAdd(o->ptr,f,v); } } ...................... return update; }

查找操作：

sds hashTypeGetFromHashTable(robj *o, sds field) { dictEntry *de; // 编码格式为哈希表 serverAssert(o->encoding == OBJ_ENCODING_HT); // 在哈希表中查找 de = dictFind(o->ptr, field); if (de == NULL) return NULL; // 返回对应的值 return dictGetVal(de); }

删除操作：

int hashTypeDelete(robj *o, sds field) { int deleted = 0; if (o->encoding == OBJ_ENCODING_ZIPLIST) { ...................... // 编码方式为哈希表 } else if (o->encoding == OBJ_ENCODING_HT) { // 从哈希表中删除元素 if (dictDelete((dict*)o->ptr, field) == C_OK) { deleted = 1; if (htNeedsResize(o->ptr)) dictResize(o->ptr); } } else { serverPanic("Unknown hash encoding"); } return deleted; }sets 操作字典

添加操作:

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; } } else if (subject->encoding == OBJ_ENCODING_INTSET) { .................... } else { serverPanic("Unknown set encoding"); } return 0; }

删除操作：

int setTypeRemove(robj *setobj, sds value) { long long llval; // 编码方式为哈希表 if (setobj->encoding == OBJ_ENCODING_HT) { // 在哈希表中删除元素 if (dictDelete(setobj->ptr,value) == DICT_OK) { if (htNeedsResize(setobj->ptr)) dictResize(setobj->ptr); return 1; } } else if (setobj->encoding == OBJ_ENCODING_INTSET) { .............. } else { serverPanic("Unknown set encoding"); } return 0; }

以上就是 Redis 中字典的实现原理

---来自腾讯云社区的---Java技术大杂烩