字典(dict)简介
字典，又称为符号表（symbol table）、关联数组（associative array ）或映射（map）, 是一种用于保存键值对（key-value pair）的抽象数据结构。
字典通常作为一种数据结构类型很多高级语言中实现，但是 redis 使用的 c 语言并没有这种数据结构，因此 redis 构建了自己的字典实现。
哈希表节点 dict.h/dictEntry
typedef struct dictEntry { // 键 void *key; // 值 union { void *val; uint64_t u64; int64_t s64; double d; } v; // 指向下一个 hash 节点 struct dictEntry *next; /* Next entry in the same hash bucket. */ void *metadata[]; /* An arbitrary number of bytes (starting at a * pointer-aligned address) of size as returned * by dictType's dictEntryMetadataBytes(). */ } dictEntry; // dict 相关的操作函数，以函数指针的方式存在。 typedef struct dictType { // 计算哈希值函数 unsigned int (*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;
字典结构由 dict.h/dict 结构表示
// 字典 typedef struct dict { dictEntry **table; //类型特定函数 dictType *type; unsigned long size; //hash 表的大小 unsigned long sizemask; // mask 计算索引值 unsigned long used; // 表示已经使用的个数 void *privdata; } dict; typedef struct dictIterator { dict *ht; int index; dictEntry *entry, *nextEntry; } dictIterator;
梳理一下结构, 普通状态下（没有 rehash）的字典。
重点解释
- dict 中的 size 每次都是 <= 2^s 进行分配
/* Our hash table capability is a power of two */ static unsigned long _dictNextPower(unsigned long size) { unsigned long i = DICT_HT_INITIAL_SIZE; if (size >= LONG_MAX) return LONG_MAX; while(1) { if (i >= size) return i; i *= 2; }
- dict 中的 rehashidex = -1|# 标记是否进行 rehash, 默认 -1 表示未进行， # 表示当前 dt[0] 中第 # 个 tb 实例
等于 -1:
#define dictIsRehashing(d) ((d)->rehashidx != -1)
不等于 -1:
int dictRehash(dict *d, int n) { int empty_visits = n*10; /* Max number of empty buckets to visit. */ if (!dictIsRehashing(d)) return 0; while(n-- && d->ht_used[0] != 0) { dictEntry *de, *nextde; /* Note that rehashidx can't overflow as we are sure there are more * elements because ht[0].used != 0 */ assert(DICTHT_SIZE(d->ht_size_exp[0]) > (unsigned long)d->rehashidx); while(d->ht_table[0][d->rehashidx] == NULL) { d->rehashidx++; if (--empty_visits == 0) return 1; } de = d->ht_table[0][d->rehashidx]; /* Move all the keys in this bucket from the old to the new hash HT */ while(de) { uint64_t h; nextde = de->next; /* Get the index in the new hash table */ h = dictHashKey(d, de->key) & DICTHT_SIZE_MASK(d->ht_size_exp[1]); de->next = d->ht_table[1][h]; d->ht_table[1][h] = de; d->ht_used[0]--; d->ht_used[1]++; de = nextde; } d->ht_table[0][d->rehashidx] = NULL; d->rehashidx++; }
- dict 中的 sizemark 用于计算当前 key 位于那个 dictEntry, 其大小等于 size -1.
idx = hash & DICTHT_SIZE_MASK(d->ht_size_exp[table]);使用 & 运算比 % 性能更高。
- dict 第一次是初始化只会启用 ht_table[0], ht_table[1] 在这个那个 dict 充当临时存储的作用
