链表
因为Redis的实现采用C语言，而C语言没有链表，所以Redis构建了自己的链表实现
应用场景
链表键
发布与订阅、慢查询、监视器等
Redis服务器本身使用链表来保存多个客户端的状态信息
使用链表来构建客户端输出输出缓冲区
链表和链表结点的实现
每个链接节点使用一个listNode结构体
struct listNode * prev;
前置节点
struct listNode * next;
后置节点
使用list来持有链表，操作起来更方便
unsigned long len;
链表节点数量
void *(*dup) (void * ptr)
节点复制函数
void (*free)(* void ptr)
节点释放函数
int (*match)(void *ptr, void * key);
节点值对比函数
多态
链表节点使用void *指针来保存节点的值，并且可以通过list结构的dup\free\match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值
链表和链表节点的API
listSetDupMethod
将给定的函数设置为链表节点复制函数
listGetDupMethod
返回链表当前正在使用的节点复制函数
free和match同上
lsitNodeValue
返回给定节点目前正在保存的值
listCreate
创建一个不包含任何节点的新链表
listAddNodeHead
将一个包含给定值的新节点添加到给定链表的表头
listAddNodeTail
将一个包含给定值的新节点添加到给定链表的表尾
listInsertNode
将一个包含给定值的新节点添加到给定节点的之前或之后
listSearchKey
查找并返回链表中包含给定值的节点
listDelRotate
将链表的表尾节点弹出，然后将被弹出的新疆棉插入到链表的表头，成为新的表头节点
listRelease
释放给定链表，以及链表中的所有节点
字典(符号表、关联数组或者映射(map))
C语言并没有内置字典所以Redis构建了自己的字典实现
Redis的数据库就是使用字典作为底层实现的，对数据上的增、删、改、查操作也是构建在字典的操作之上的<br>
字典也是哈希键的底层实现之一：当一个哈希键包含的键值对比较多，又或者键值对中的元素都是比较长的字符串时
哈希算法
将一个新的键值对添加到字典里面时，程序需要先根据键值对计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈表结点放到哈希表数组的指定索引上面
计算方法：
# 使用字典设置的哈希函数，计算键 key 的哈希值<br>hash = dict->type->hashFunction(key);<br><br># 使用哈希表的 sizemask 属性和哈希值，计算出索引值<br># 根据情况不同， ht[x] 可以是 ht[0] 或者 ht[1]<br>index = hash & dict->ht[x].sizemask;
当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis使用MurmurHash2算法来计算键的哈希值。MurmurHash算法的优点在于：即使输入的键是有规律的，算法仍然能给出一个很好的随机分布性，并且算法的计算速度也非常快
Redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表结点，而每个哈希表结点就保存了字典里的一个键值对
哈希表
dict.h/dictht定义了字典所使用的哈希表
typedef struct dictht {<br> // 哈希表数组<br> dictEntry **table;<br><br> // 哈希表大小<br> unsigned long size;<br><br> // 哈希表大小掩码，用于计算索引值<br> // 总是等于 size - 1<br> unsigned long sizemask;<br><br> // 该哈希表已有节点的数量<br> unsigned long used;<br><br>} dictht;
table属性是一个数组，数组中的每个元素都是一个指向dict.h/dictEntry结构的指针，每个dictEntry结构保存着一个车键值对
sizemask属性的值总是等于size-1，这个属性和哈希值一起决定一个键值对应该被放到table数组的哪个索引上面
哈希节点
哈希节点使用dictEntry结构表示，每个dictEntry结构保存着一个键值对
typedef struct dictEntry {<br> // 键<br> void *key;<br><br> // 值<br> union {<br> void *val;<br> uint64_t u64;<br> int64_t s64;<br> } v;<br><br> // 指向下个哈希表节点，形成链表<br> struct dictEntry *next;<br>} dictEntry;
next属性是指向另一个哈希表节点，这个指针可以将多个哈希值相同的键值对连接在一起，以此来解决键冲突的问题
通过next指针将索引值相同的键k1和k0连接在一起
字典
字典有dict.h/dict结构表示
typedef struct dict {<br> // 类型特定函数<br> dictType *type;<br><br> // 私有数据<br> void *privdata;<br><br> // 哈希表<br> dictht ht[2];<br><br> // rehash 索引<br> // 当 rehash 不在进行时，值为 -1<br> int rehashidx; /* rehashing not in progress if rehashidx == -1 */<br>} dict;
type属性和privdata属性是针对不同类型的键值对，为创建多态字典而设置的
type属性是一个指向dictType结构的指针，每个dictType结构保存了一簇用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同的类型特定的函数
privdata属性则保存了需要传给那些类型特定函数的可选参数
dictType结构
typedef struct dictType {<br> // 计算哈希值的函数<br> unsigned int (*hashFunction)(const void *key);<br><br> // 复制键的函数<br> void *(*keyDup)(void *privdata, const void *key);<br><br> // 复制值的函数<br> void *(*valDup)(void *privdata, const void *obj);<br><br> // 对比键的函数<br> int (*keyCompare)(void *privdata, const void *key1, const void *key2);<br><br> // 销毁键的函数<br> void (*keyDestructor)(void *privdata, void *key);<br><br> // 销毁值的函数<br> void (*valDestructor)(void *privdata, void *obj);<br>} dictType;
ht属性是一个包含两个项的数组，数组中的每个项都是一个dictht哈希表，一般情况下，字典只是使用ht[0]哈希表，ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用
rehashidx记录了了rehash目前的进度，如果目前没变在进行rehash，那么它的值为-1
解决键冲突
使用链地址法来解决键冲突：每个哈希表节点都有一个next指针，多个哈希表节点可以用net指针构成一个单向链表
rehash
背景：
随着操作不断执行，哈希表保存的键值对会逐渐增多或减少，为了让哈希表的负载因子维持在一个合理的范围内，程序需要对哈希表的大小进行相应的扩展或收缩
rehash(重新散列)
为字典的ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量
如果执行的是扩展操作，那么ht[1]的大小为第一个大于等于ht[0].used * 2的2^n
如果执行的是收缩操作，那么ht[1]的大小为第一个大于等于ht[0].used的2^n
将保存在ht[0]中的所有键值对rehash到ht[1]上面：rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上
当ht[0]包含的所有键值对都迁移到了ht[1]之后(ht[0]变为空表)，释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新建一个空白哈希表，为下一次rehash做准备
哈希表的扩展和收缩
扩展时机
服务器目前没有执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1
服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5
收缩时机
当哈希表的负载因子小于0.1时，程序自动开始对哈希表执行收缩操作
负载因子 = 哈希表已保存节点数量 / 哈希表大小
根据 BGSAVE 命令或 BGREWRITEAOF 命令是否正在执行， 服务器执行扩展操作所需的负载因子并不相同， 这是因为在执行 BGSAVE 命令或 BGREWRITEAOF 命令的过程中， Redis 需要创建当前服务器进程的子进程， 而大多数操作系统都采用写时复制（copy-on-write）技术来优化子进程的使用效率， 所以在子进程存在期间， 服务器会提高执行扩展操作所需的负载因子， 从而尽可能地避免在子进程存在期间进行哈希表扩展操作， 这可以避免不必要的内存写入操作， 最大限度地节约内存。
渐进式rehash
扩展或收缩哈希表需要将ht[0]里面的所有键值对rehash到ht[1]里面，但是这个rehash动作并不是一次性、集中式地完成的，而是分多次、渐进式地完成的
背景：如果ht[0]中的见键值对数量庞大，一次性将这些键值对全部rehash到ht[1]，庞大的计算两可能导致服务器在一段时间内停止服务。为了避免rehash对服务器性能造成影响，服务器不是一次性将ht[0]里面exe键值对全部rehash到ht[1]中，而是分多次，渐进式地进行rehash
步骤：
为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表
为字典维持一个索引计数气遍历rehashidx，并将它的值设置为0，表示rehash工作正式开始
在rehash进行期间，每次对自检执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的键值对rehash到ht[1]，当rehash工作完成之后，程序将rehashidx属性的值增一
随着字典操作的不断进行，最终在某个时间点上，ht[0]的所有键值对都会被rehash到ht[1]，这时程序将rehashidx设置为-1，表示rehash操作已完成
渐进式rehash执行期间的哈希表操作
在渐进式rehash期间，字典的删除、查找、更新等操作都是在两张表上进行的
要在字典里面查找一个键，程序首先在ht[0]里面进行查找，如果没有找到，就会继续到ht[1]里面查找
新添加一个键值对一律会被保存到ht[1]里面，而ht[0]则不再进行任何添加操作
字典API
dictReplace
将给定的剑指对添加到字典里面，如果键已经存在，那么用新的值取代原来的值
dictGetRandomKey
从字典里面随机返回一个键值对
dictDelete
从字典中删除给定键所对应的键值对
dictRelease
释放给定字典，以及字典中包含的所有键值对
