Redis底层是采用哈希加链表实现的，了解Redis内部数据结构，对学习Redis有很大的帮助。
先来看几个关键词
dictEntry：表示一个key-value节点。
dictht：表示一个dict哈希表，里面有一个数组，数组里面的每个元素都是指向dictEntry的指针。
dict：表示redis的字典结构，里面有2个哈希表，一个用来存储键值对，一个用来rehash。
dictType：保存了一些用于操作特定类型键值对的函数
附上源码：
dictEntry
typedef struct dictEntry { void *key; //key void*表示任意类型指针 union { //联合体中对于数字类型提供了专门的类型优化 void *val; uint64_t u64; int64_t s64; } v; struct dictEntry *next; //next指针 } dictEntry;dictht
typedef struct dictht { dictEntry **table; //数组指针，每个元素都是一个指向dictEntry的指针 unsigned long size; //表示这个dictht已经分配空间的大小，大小总是2^n unsigned long sizemask; //sizemask = size - 1; 是用来求hash值的掩码，为2^n-1 unsigned long used; //目前已有的元素数量 } dictht;dict
typedef struct dict { dictType *type; //type中定义了对于Hash表的操作函数，比如Hash函数，key比较函数等 void *privdata; //privdata是可以传递给dict的私有数据 dictht ht[2]; //每一个dict都包含两个dictht，一个用于rehash int rehashidx; //表示此时是否在进行rehash操作 int iterators; //迭代器 } dict;dictType
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阶段，即ht[1]是空的
当哈希表的冲突率过高时链表会很长，这时查询效率就会变低，所以有必要进行哈希表扩展，而如果哈希表存放的键值对很少的时候把size设的很大，又会浪费内存，这时就有必要进行哈希表收缩。这里扩展和收缩的过程，其实就是rehash的过程
将ht[0]上的Key重新按照Hash函数计算Hash值，存到ht[1]的过程
步骤如下：
1. 为dict的哈希表ht[1]分配空间，分配的空间大小取决于操作类型和当前键值对数量ht[0].used
(1)如果是扩展操作，ht[1]的大小为第一个大于等于的整数
(2)如果是收缩操作，ht[1]的大小为第一个大于等于的整数
2. 重新计算ht[0]中所有键的哈希值和索引值，将相应的键值对迁移到ht[1]的指定位置中去，需要注意的是，这个过程是渐进式完成的，不然如果字典很大的话全部迁移完需要一定的时间，这段时间内Redis服务器就不可用了哟
3. 当ht[0]的所有键值对都迁移到ht[1]中去后（此时ht[0]会变成空表），把ht[1]设置为ht[0]，并重新在ht[1]上新建一个空表，为下次rehash做准备
渐进式rehash：
从性能的角度出发考虑，一次性rehash操作，在键太多的情况下，会造成长时间的阻塞，因此提出渐进式rehash，即多次进行rehash操作，一步步最终将所有的键完成rehash。
步骤如下：
1. 为ht[1]分配空间，此时字典同时持有ht[0]和ht[1]
2. 将rehashidx设为0，表示rehash正式开始
3. 在rehash期间，每次对字典执行任意操作时，程序除了执行对应操作之外，还会顺带将ht[0]在rehashidx索引上的所有键值对rehash到ht[1]，操作完后将rehashidx的值加一
4. 在rehash期间，对字典进行ht[0].size次操作之后，rehashidx的值会增加到ht[0].size，此时ht[0]的所有键值对都已经迁移到ht[1]了，程序会将rehashidx重新置为-1，以此表示rehash完成
这里需要注意的是，在rehash的过程中，ht[0]和ht[1]可能同时存在键值对，因此在执行查询操作的时候两个哈希表都得查，而如果是执行插入键值对操作，则直接在ht[1]上操作就行。
最后说下Redis在什么条件下会对哈希表进行扩展或收缩：
1. 服务器当前没有在执行BGSAVE或BGREWRITEAOF命令且哈希表的负载因子大于等于1时进行扩展操作
2. 服务器正在执行BGSAVE或BGREWRITEAOF命令且哈希表的负载因子大于等于5时进行扩展操作
（这里负载因子的计算公式为：负载因子=哈希表当前保存节点数/哈希表大小，而之所以在服务器进行BGSAVE或BGREWRITEAOF的时候负载因子比较大才进行扩展操作是因为此时Redis会创建子进程，而大多数操作系统采取了写时复制的技术来优化子进程使用效率，不适合在这种时候会做大规模的数据迁移活动，说白了就是为了节约内存和提升效率）
3. 当前负载因子小于0.1时进行收缩操作
