1.字典结构
typedef struct dict {
//类型特定函数dictType *type;
//私有数据， 为特定函数传参数void *privdata;
//哈希表 ht[0]正在用的哈希表 ht[1] rehash时会用到dictht ht[2];
//-1时没有进行rehash,否则代表rehash的索引long rehashidx; /* rehashing not in progress if rehashidx == -1 */int iterators; /* number of iterators currently running */
} dict;
2.哈希表
typedef struct dictht {
//哈希节点的数组dictEntry **table;
//大小unsigned long size;
//哈希表的掩码 用于计算索引值(将键值对放在哪个位置)unsigned long sizemask;
//已有节点数量unsigned long used;
} dictht;
3.哈希表节点
typedef struct dictEntry {
//键void *key;
//值union {void *val;uint64_t u64;int64_t s64;double d;} v;
//指向下一个hash节点，防止hash冲突struct dictEntry *next;
} dictEntry;
4. 解决键冲突
什么是哈希冲突： 至少两个键hash后分配到了哈希表数组的同一个索引上
redis使用链表发解决这个问题，当发生冲突时利用节点的next解决问题
5. rehash
当发生rehash时，先为ht[1]分配空间，在进行hash表增删改查时逐渐将ht[0]的键值对移到ht[1]上(配合rehashidx, 记录索引的位置),新增的键值对直接放到ht[1]上，保证ht[0]只减不增. 当ht[0]为空时，释放ht[0],ht[1]置为ht[0]
6.rehash源码
//d 字典 n rehash的数量
int dictRehash(dict *d, int n) {
//最多空桶的数量int empty_visits = n*10; /* Max number of empty buckets to visit. */
//如果没有rehash(判断rehashindex 是否是-1) 函数对出if (!dictIsRehashing(d)) return 0;//while循环 n减减 并且ht[0]还有节点while(n-- && d->ht[0].used != 0) {dictEntry *de, *nextde;/* Note that rehashidx can't overflow as we are sure there are more* elements because ht[0].used != 0 */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;}
//获取节点de = d->ht[0].table[d->rehashidx];/* Move all the keys in this bucket from the old to the new hash HT */while(de) {unsigned int h;
//存储下一个节点，方便while循环nextde = de->next;/* Get the index in the new hash table */
//计算节点在ht[1]中的索引位置h = dictHashKey(d, de->key) & d->ht[1].sizemask;
//节点做为头节点 存储在ht[1]中de->next = d->ht[1].table[h];d->ht[1].table[h] = de;
//修改节点的数量d->ht[0].used--;d->ht[1].used++;de = nextde;}d->ht[0].table[d->rehashidx] = NULL;
//下一个位置d->rehashidx++;}/* Check if we already rehashed the whole table... */
//判断rehash是否结束if (d->ht[0].used == 0) {
//释放ht[0]zfree(d->ht[0].table);
//ht[1]变为ht[0]d->ht[0] = d->ht[1];_dictReset(&d->ht[1]);
//rehash结束d->rehashidx = -1;return 0;}/* More to rehash... */return 1;
}