字典、哈希表基本数据结构
redis字典使用哈希表作为底层实现，基本结构就是数组+散列
typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 哈希表数组的大小
unsigned long size;
// 掩码，用于计算新加入的元素的index（sizemask值等于size-1）
unsigned ling sizemask;
// 哈希表中已有节点的数量
unsigned long used;
} dictht;
其中，哈希表数组中的每一个节点，与1.8之前的jdk中map很相似，也是链表结构
typedef struct dictEntry {
// 键
void *key
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 指向下个哈希表节点，形成链表
struct dictEntry *next;
} dictEntry;
最终的redis字典内部，由2个哈希表构成。平时只使用其中的一个，当需要扩展或收缩哈希表时，启用第二个，后续详细介绍
redis字典结构如下：
typedef struct dict {
dictType *type
void *privdata;
// 哈希表（实际存储数据），平时使用ht[0]，当需要扩展或收缩哈希表时，将ht[0]的数据rehash到ht[1]，然后释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新建一个空白哈希表，done
dictht ht[2];
// 是否正在执行rehash的标识，不在进行时为-1
int trehashidx;
} dictEntry;
下面介绍一些hash操作常遇到的问题：index选择、index冲突、rehash触发条件、rehash流程
index选择
index选择和jdk类似
- 首先计算出哈希值 hash = dict -> type -> hashFunction(key);
- 再位运算 index = hash & dict -> ht[0].sizemask;
- 注意，这要求ht[0]的大小为2的n次幂，方便hash值被按位与到哈希表的大小里
index冲突
采用链地址方法，冲突的节点被添加在冲突链的头部。不会变成树，就是链
rehash触发条件
哈希表的扩展、收缩会触发rehash，这里和jdk不类似了
扩展条件（满足任意一个即可）：
- 负载因子（已保存节点数量ht[0].used / 哈希表大小ht[0].size） >=1、且服务器目前没有在执行 BGSAVE 或 BGREWRITEAOF
- 负载因子 >=5、且服务器目前在执行 BGSAVE 或 BGREWRITEAOF
收缩条件：
- 负载因子 < 0.1
rehash流程
在rehash发生之前，数据都保存在两个哈希表中的第一个ht[0]中，从这里开始rehash流程：
- 为ht[1]分配空间。
- 如果是扩展，则ht[1]大小为大于等于ht[0].used * 2 的第一个2的n次幂。比如ht[0]大小为16，used为17，则扩展后大小为64
- 如果是收缩，则ht[1]大小为大于等于ht[0].used 的第一个2的n次幂。比如ht[0]大小为128，used为10，则收缩后大小为16
- 将ht[0]的所有键值对rehash到ht[1]，即重新计算哈希、重新计算索引、重新处理冲突
- 释放ht[0]
- 将ht[1]设置为ht[0]，并在ht[1]创建一个新的空白哈希表
渐进式rehash：
当键值对很多时，一次性rehash从ht[0]到ht[1]耗时耗资源很大，redis会分多次完成ht[0]到ht[1]
- 渐进式rehash时，新增操作直接保存到ht[1]，其他入删除、更新、查找等都会先操作ht[0]再操作ht[1]
这里性能影响、如何分批还不是很清楚