共计 3259 个字符，预计需要花费 9 分钟才能阅读完成。
概念
哈希表：也叫散列表，是根据关键码值 (Key value) 而直接进行访问的数据结构也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
哈希函数：哈希表中元素是由哈希函数确定的。将数据元素的关键字 K 作为自变量，通过一定的函数关系（称为哈希函数）
哈希冲突：计算关键码获取的位置可能会重复，就就是冲突。如何解决冲突 Redis 中使用了链址法
字典实现
哈希表
typedef struct dictht{
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈小标大小掩码，用于计算 下面一小节的如何计算位置可以看到具体的意义。
unsigned long sizemask;
// 哈希表已有节点的数量
unsigned long used;
}
table：是一个数组，数组的每个元素都是一个指向 dict.h/dictEntry 结构的指针；(结构下面可见)
size：记录哈希表的大小，即 table 数组的大小，且一定是 2 的幂；
used：记录哈希表中已有结点的数量；
sizemask：用于对哈希过的键进行映射，索引到 table 的下标中，且值永远等于 size-1。具体映射方法很简单，就是对 哈希值 和 sizemask 进行位与操作，由于 size 一定是 2 的幂，所以 sizemask=size-1，自然它的二进制表示的每一个位 (bit) 都是 1，等同于下文提到的取模；
哈希表节点
typedef struct dictEntry{
// 键
void *key
// 值
union{
void *val;
uint64_t u64;
int64_t s64;
}v;
// 只想下一个哈希表节点，形成链表
struct dictEntry *next;
}dictEntry;
key：是键值对中的键；
v：是键值对中的值，它是一个联合类型，方便存储各种结构；
next：是链表指针，指向下一个哈希表节点，他将多个哈希值相同的键值对串联在一起，用于解决键冲突；如图所示，两个 dictEntry 的 key 分别是 k0 和 k1，通过某种哈希算法计算出来的哈希值和 sizemask 进行位与运算后都等于 3，所以都被放在了 table 数组的 3 号槽中，并且用 next 指针串联起来。
redis 中的字典
typedef struct dict{
//
dictType *type
//
void *privdata;
//
dictht ht[2]
//
int trehashidx;
}dict;
type：是一个指向 dict.h/dictType 结构的指针，保存了一系列用于操作特定类型键值对的函数；
ht：是两个哈希表，一般情况下，只使用 ht[0]，只有当哈希表的键值对数量超过负载 (元素过多) 时，才会将键值对迁移到 ht[1]
trehashidx：由于哈希表键值对有可能很多很多，所以 rehash 不是瞬间完成的，需要按部就班，那么 rehashidx 就记录了当前 rehash 的进度，当 rehash 完毕后，将 rehashidx 置为 -1；
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;
Rehash
其实没有想象中的那么复杂，随着字典操作的不断执行，哈希表保存的键值对会不断增多（或者减少），为了让哈希表的负载因子维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，需要对哈希表大小进行扩展或者收缩。
扩展与收缩的条件
负载因子：load_factor=ht[0].used/ht[0].size 当前使用过的节点数除以哈希大小。当以下条件满足任意一个时，程序就会对哈希表进行扩展操作
服务器目前没有执行 bgsave 或 bgrewriteaof 命令，并且哈希表的负载因子 >=1
服务器目前正在执行 bgsave 或 bgrewriteaof 命令，并且哈希表的负载因子 >=5
当负载因子的值小于 0.1 时，程序就会对哈希表进行收缩操作
Rehash 操作步骤
哈希表的扩容：
为字典 ht[1]分配空间，大小为第一个大于等于 ht[0].used * 2 的 2 的幂；比如：ht[0].used 当前的值为 4，4 * 2 = 8，而 8（2^3）恰好是第一个大于等于 4 的 2 的 n 次方，所以程序会将 ht[1] 哈希表的大小设置为 8。
将保存在 ht[0] 上的键值对 rehash 到 ht[1] 上，rehash 就是重新计算哈希值和索引，并且重新插入到 ht[1] 中，插入一个删除一个
当 ht[0] 包含的所有键值对全部 rehash 到 ht[1] 上后，释放 ht[0] 的控件，将 ht[1] 设置为 ht[0]，并且在 ht[1] 上新创件一个空的哈希表，为下一次 rehash 做准备；
哈希表的收缩：同样是为 ht[1] 分配空间，大小等于 max(ht[0].used, DICT_HT_INITIAL_SIZE )，然后和扩展做同样的处理即可。
渐进式 rehash
扩展或者收缩哈希表的时候，需要将 ht[0] 里面所有的键值对 rehash 到 ht[1] 里，当键值对数量非常多的时候，这个操作如果在一帧内完成，大量的计算很可能导致服务器宕机，所以不能一次性完成，需要渐进式的完成。渐进式 Rehash 的操作步骤：
为 ht[1] 分配指定空间，让字典同时持有 ht[0] 和 ht[1] 两个哈希表。
将 rehashidx 设置为 0，表示正式开始 rehash。
在进行 rehash 期间，每次对字典执行 增、删、改、查操作时，程序除了执行指定的操作外，还会将 哈希表 ht[0].table 中下标为 rehashidx 位置上的所有的键值对 全部迁移到 ht[1].table 上，完成后 rehashidx 自增。这一步就是 rehash 的关键一步。为了防止 ht[0] 是个稀疏表（遍历很久遇到的都是 NULL），从而导致函数阻塞时间太长，这里引入了一个“最大空格访问数”，也即代码中的 enmty_visits，初始值为 n*10。当遇到 NULL 的数量超过这个初始值直接返回。
最后，当 ht[0].used 变为 0 时，代表所有的键值对都已经从 ht[0] 迁移到 ht[1] 了，释放 ht[0].table，并且将 ht[0] 设置为 ht[1]，rehashidx 标记为 -1 代表 rehash 结束。
心中的疑问
如何计算位置
其实哈希表、字典、map，我们并不陌生但是我对这个位置如何计算出的一直是一知半解。也查了一些资料下面整合一下。如果我们有一个长度为 4 的哈希表，有 4 个数字要放入（6，7，9，12）那很简单只要对 4 个数字用 4 取模就可以。结果为：[12,9,6,7]。我们知道取模操作的效率是很低的，那么我们可以用位运算来代替。解决方案为：把哈希表的长度 L 设置为 2 的幂（L = 2^n），那么 L-1 的二进制表示就是 n 个 1，任何值 x 对 L 取模等同于和(L-1) 进行位与（C 语言中的 &）运算。
如何解决冲突
那么问题来了如果数字是（6，7，9，11）如果用 4 取模 [nil,9,6,7 11] 这样就会出现 7 11 对 4 取模结果都为 3 发生了冲突。这就是所谓的哈希键冲突，那么如何解决这样的冲突有很多解决方法，开放地址法、再散列法、链地址法等等。redis 中使用的是链址法，在对象中保存下一个值得地址。接下来继续上面的算法。其实这就是 redis 哈希表结构中 sizemask 字段的意义，就是用来保存 L - 1 这个数字直接用于计算。
