数据结构
凡是Hash字典，首先得有一个数组，这个数组是用来存储<Key, Value>对中的Value。
<Key, Value>对中的Key，是用来计算Value在数组中的下标位置。
一般的做法是，将Key通过特定的Hash算法得到一个整数值，然后将这个整数值与数组长度求余，计算的结果就是这个Value在数组中的位置。
然而当出现Hash冲突，也就是不同的Key得到相同的Hash值的时候，不同的Value将会保存到数组中的同一个位置。那么这个时候数组中就不能单纯的只存储Value了，就要将数组中的元素链表化，变成如下图所示：
数组中的每个元素，不仅要保存Value，还需要保存Key，以及指向下一个节点的指针。
所以当出现Hash冲突的时候，不同的<Key, Value>对都分配到了同一个数组下标位置，这时候这些不同的<Key, Value>对组成了一个链表，这个数组下标下存储的是一个链表。
Redis中的Hash字典，原理上是类似的，只是在上面包装了一下，加了一些特有的工程信息。
主要包含三部分：字典，Hash表，Hash表节点
Hash表
typedef struct dictht {
dictEntry **table; //指针数组，用于存储键值对
unsigned long size; //table数组的大小
unsigned long sizemask; //掩码 = size - 1
unsigned long used; //table数组中已存元素个数
} dictht
这里的sizemask的用途是，某个<Kev, Value>对的数组下标值 = Hash(Key) & sizemask。其计算结果等同于Hash(Key)%size，但是因为是位运算，计算效率要比求余运算快得多。
Hash表节点
Hash表中的元素是用dictEntry来封装的。
typedef struct dictEntry{
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry
简单点理解就是，dictEntry里面包含了key, value，以及指向下一个dictEntry的next指针。
字典
对hash表进行一层封装，把一些特殊的操作封装到字典里面，比如计算hash值，rehash等。
typedef struct dict{
dictType *type; //dictType里面封装了这个字典需要的一些特殊的操作，比如计算key的hash值
void *privatedata; //传给dictType里面那些操作所需的参数数据
dictht ht[2]; //两个hash表，大部分情况下只使用ht[0]，在扩容的情况下需要用到另外一个
long rehashidx; //rehash的进度，也就是记录目前ht[0]这个table里面哪个数组下标正在rehash
unsigned long iterators; //当前运行的迭代器数
} dict;
所以Redis Hash字典的整个结构图如下：
- 当往Hash字典中加入<Key, Value>对时，首先在Dict的type中根据Key计算出Hash值；
- 然后获取dictht[0].sizemask，通过Hash(key)&dictht[0].sizemask，得到这个<Key, Value>对在dictht[0].table数组中的位置。
- 将传入的<Key, Value>封装成一个新的dictEntry存入计算出来的位置。
扩容和缩容
当持续往字典里面添加<Key, Value>对后，字典空间慢慢会不够，这个时候就需要扩容。
- 申请一块新空间，大小为原来的两倍，并且往上取2的N次方。比如原来字典里面的数组长度是3，扩容的时候要申请大小为8的空间，因为3的两倍是6，6不是2的N次方，所以往上到8;
- 将字典的rehashidx设置为0. 并将ht[1]指向这块扩容后的新空间， ht[1]的size, sizemask， used都相应的更新；
- 所有的插入操作都rehash到ht[1]。查找，删除，更新则兼顾ht[0]和ht[1];
- 最后把ht[0]里面老的元素都rehash到ht[1]，rehashidx设置为正在rehash的ht[0]里面元素的下标值；
- 删除ht[0]里面的元素，对调ht[0]和ht[1]，将rehashidx设置为-1；
缩容也是类似的流程。
