redis-6.2.4
首先定义字典的数据结构
跟hashpMap里面类似，一般是由数组和链表组成。
dictht
typedef struct dictht {
//entry类型的数组，保存指向entry的指针
dictEntry **table;
//哈希表的大小
unsigned long size;
//哈希表掩码，总等于size-1，二进制运算 12%8 ->1100&111=100=4
unsigned long sizemask;
//enrty的个数
unsigned long used;
} dictht;dict
typedef struct dict {
//dict类型，里面由不同的hash函数
dictType *type;
//私有数据
void *privdata;
//两个哈希表，一个是当前数据，一个备胎，留着rehash用的
dictht ht[2];
//rehash的进度，-1表示未进行
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
//rehash是否暂停
int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;dictEntry
typedef struct dictEntry {
void *key;//键
//制定了不同类型的值
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;//值
//指向下一个节点
struct dictEntry *next;
} dictEntry;链表的初始化逻辑
dict *dictCreate(dictType *type,
void *privDataPtr)
{
//给dict分配一个空间
dict *d = zmalloc(sizeof(*d));
_dictInit(d,type,privDataPtr);
return d;
}
具体的初始化
int _dictInit(dict *d, dictType *type,
void *privDataPtr)
{
//这里保存的是两个hash表
//一个指向但钱的数据
_dictReset(&d->ht[0]);
//另一个一般为空，用于rehash的时候使用
_dictReset(&d->ht[1]);
d->type = type;
d->privdata = privDataPtr;
//rehash的进度，这里-1表示未进行
d->rehashidx = -1;
//rehash是否暂停，1是暂停，0是继续
d->pauserehash = 0;
return DICT_OK;
}rehash
int dictResize(dict *d)
{
unsigned long minimal;
if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;
//如果使用的还超过呢，就不先扩容了
minimal = d->ht[0].used;
//DICT_HT_INITIAL_SIZE值为4
if (minimal < DICT_HT_INITIAL_SIZE)
minimal = DICT_HT_INITIAL_SIZE;
//不然就扩容，
return dictExpand(d, minimal);
}dictExpandIfNeeded
static int _dictExpandIfNeeded(dict *ht);_dictExpandIfNeeded
static int _dictExpandIfNeeded(dict *d)
{
//如果正在hash过程当中，就返回DICT_OK
if (dictIsRehashing(d)) return DICT_OK;
//hash表要是空的就返回初始化大小4
if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
//如果负载因子达到1以上了并且再满足下面两个条件之一
if (d->ht[0].used >= d->ht[0].size &&
//当前没有进行bgrewrite等操作，也就是可以扩容
//或者比例超过5 dict_force_resize_ratio了，那他也会扩容dictExpand
(dict_can_resize ||
d->ht[0].used/d->ht[0].size > dict_force_resize_ratio) &&
dictTypeExpandAllowed(d))
{
//孔融大小used+1,底层对扩容大小坐判断，最终是找一个大于等于userd+1的2的n次幂。有点类似操作系统连续内存管理的伙伴算法
return dictExpand(d, d->ht[0].used + 1);
}
return DICT_OK;
}dictTypeExpandAllowed
过考虑当前的装载因子和可能的内存需求，来决定是否允许字典扩容，以优化其性能和内存使用。
expandAllowed函数的返回值随后被作为dictTypeExpandAllowed函数的返回值返回。这个返回值决定了是否允许字典进行扩展。如果expandAllowed返回1，表示允许扩展；如果返回0，则不允许
static int dictTypeExpandAllowed(dict *d) {
//返回null指没有特定的扩展条件，1表示可以扩展
if (d->type->expandAllowed == NULL) return 1;
return d->type->expandAllowed(
//这里是用来计算给定数值的下一个幂的值，如输入9结果为16
_dictNextPower(d->ht[0].used + 1) * sizeof(dictEntry*),//能计算出扩展之后大致的内存大小
//表示当前装在因子
(double)d->ht[0].used / d->ht[0].size);
}dictExpand
int dictExpand(dict *d, unsigned long size) {
return _dictExpand(d, size, NULL);
}_dictExpand
d: 指向需要扩展或初始化的dict结构体的指针。size: 请求的哈希表大小。malloc_failed: 一个指向整数的指针，用于指示内存分配是否失败。
int _dictExpand(dict *d, unsigned long size, int* malloc_failed)
{
//处理内存分配失败的预备步骤
//如果malloc_failed不是NULL，则将其所指向的值初始化为0，表示内存分配尚未失败。
if (malloc_failed) *malloc_failed = 0;
//如果字典正在进行重新哈希（即正在扩展中）或当前使用的元素数量已经超过了请求的大小，函数将返回DICT_ERR，表示不执行扩展
if (dictIsRehashing(d) || d->ht[0].used > size)
return DICT_ERR;
//创建一个新的hash表
dictht n; /* the new hash table */
//确定一下新得扩容大小，这里就是之前介绍得函数。
unsigned long realsize = _dictNextPower(size);
//如果计算出来的hash表大小还和之前一样，那就算了吧，返回错误
if (realsize == d->ht[0].size) return DICT_ERR;
//分配新的大小
n.size = realsize;
//之前提到过的掩码
n.sizemask = realsize-1;
if (malloc_failed) {
n.table = ztrycalloc(realsize*sizeof(dictEntry*));
//判断一下分配的内存空间大小是否成功，如果能分配的话就不为null了
*malloc_failed = n.table == NULL;
if (*malloc_failed)
//分配不成功则返回错误
return DICT_ERR;
} else
n.table = zcalloc(realsize*sizeof(dictEntry*));
//将n的使用节点指向0
n.used = 0;
//如果原始哈希表 d->ht[0] 中的 table 指针为 NULL，这表示字典尚未进行过初始化，即字典为空。
if (d->ht[0].table == NULL) {
//将新创建的哈希表 n 赋值给原始哈希表 d->ht[0]，以便开始接受键值对。
d->ht[0] = n;
//函数返回 DICT_OK，表示字典扩容成功。
return DICT_OK;
}
/* Prepare a second hash table for incremental rehashing */
//将新准备好的n赋值给ht[1]
d->ht[1] = n;
//改变标识准备扩容
d->rehashidx = 0;
return DICT_OK;
}
不管是扩容还是收缩，必定会创建新的哈希表，（把创建的哈希表赋值给那个空闲的hash表，再从旧的导入空闲的里面。）导致哈希表的size和sizemask变化，而key的查询与sizemask有关。因此必须对哈希表中的每一个key重新计算索引，插入新的哈希表，这个过程称为rehash。过程是这样的：
计算新hash表的realeSize，值取决于当前要做的是扩容还是收缩：
如果是扩容，则新size为第一个大于等于dict.ht[0].used + 1的2^n
如果是收缩，则新size为第一个大于等于dict.ht[0].used的2^n （不得小于4）
按照新的realeSize申请内存空间，创建dictht，并赋值给dict.ht[1]
设置dict.rehashidx = 0，标示开始rehash
将dict.ht[0]中的每一个dictEntry都rehash到dict.ht[1]
将dict.ht[1]赋值给dict.ht[0]，给dict.ht[1]初始化为空哈希表，释放原来的dict.ht[0]的内存
将rehashidx赋值为-1，代表rehash结束
在rehash过程中，新增操作，则直接写入ht[1]，查询、修改和删除则会在dict.ht[0]和dict.ht[1]依次查找并执行。这样可以确保ht[0]的数据只减不增，随着rehash最终为空
dictRehash
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[0].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(d->ht[0].size > (unsigned long)d->rehashidx);
//检测索引为 rehashidx 的桶是否为空。如果为空，则继续递增 rehashidx 直到找到一个非空桶。
while(d->ht[0].table[d->rehashidx] == NULL) {
//用rehashid来记录已经完成迁移节点的链表下标
d->rehashidx++;
if (--empty_visits == 0) return 1;
}
//原hash位置的桶
de = d->ht[0].table[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;
//通过掩码来确定在新的表结构中的位置,做位运算
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;
}
//原位置桶置空，处理下一个桶
d->ht[0].table[d->rehashidx] = NULL;
d->rehashidx++;
}
//节点移动完成
if (d->ht[0].used == 0) {
//释放ht[0]
zfree(d->ht[0].table);
//将ht[1]赋值给ht[0]
d->ht[0] = d->ht[1];
//把ht清理了回复初始空状态
_dictReset(&d->ht[1]);
//hash过程结束
d->rehashidx = -1;
return 0;
}
//1代表着还没hash完成
return 1;
}为了防止大数据的数据迁移中的rehash时间比较长，所以我们分段进行rehash，并用rehashid来记录已经迁移完成的节点链表下标。并且在做删，改，查的过程当中，数据要么在t1里要么再t0里并且由于数据是迁移的并不会重复，因此需要两边都要查询。
但是新增操作不需要去查询在哪里，只需要在扩容的t1里就好。确保t0数据只剪不增加。
结束之后rehashid赋值为-1.
