数据结构之链表

上次写了SDS的内容，很荣幸上了CSDN热榜，距离今天已经过了好久了，因为最近在看一些其他的东西，加上工作有点忙，所以就停止了，这次主要写下链表和字典。

链表定义

链表在redis中使用也是比较多的，比如key对应的元素比较多或者元素包含字符串比较长、发布与订阅、监视器等都会用到链表。
每个链表节点使用一个adlist.h/listNode结构表示，如下：

typedef struct listNode {
	// 前置节点
	typedef listNode *prev;
	// 后置节点
	typedef listNode *next;
	// 节点的值
	void *value;
} listNode 
// 这里其实不用多解释的，双端链表嘛，有前驱节点和有后继节点，next指向下一个节点指针，pre指向前一个节点指针

最经典的比如使用list类型时，l/rpush元素，使用llen获取元素个数等这些操作，在一开始接触时，就想获取元素个数应该不是通过遍历O(n)复杂度来获取长度吧？其实还有使用adlist.h/list来持有的链表，如下：

typedef struct list {
	// 表头节点
	listNode *head;
	// 表尾节点
	listNode *tail;
	// 链表长度
	unsigned long len;
	// 节点值复制函数
	void *(*dup)(void *ptr);
	// 节点值释放函数
	void *(*free)(void *ptr);
	// 节点值对比函数
	int (*match)(void *ptr,void *key);
} list;

以上的dup、free、match是实现多态链表所需的类型特定函数，所以可以保存不同类型的值：

• dup函数用于复制链表节点所保存的值
• free函数用于释放链表节点所保存的值
• match函数用于对比链表节点所保存的值和另一个输入值是否相等
  一个list结构和三个listNode结构如下：
  
  通过上面方式实现redis链表就有了如下特性：
• 双端：节点都有pre和next，获取前驱和后继节点复杂度O(1)
• 链表无环：表头的前驱结点以及表尾的后继节点都指向null
• 获取表头和表尾节点复杂度O(1)
• 获取链表长度复杂度O(1)
• void *指针保存节点值，通过list结构的dup、free、match三属性为节点值设置类型特定函数，所以链表可以用于保存不同类型的值。

数据结构之字典

字典嘛，我首先会想到的就是map这种东西，其实就是一个key和value的映射，在字典里，每个键都是唯一的，可以根据键来进行查找、删除、更新操作等。这种字典在java中很多数据结构使用，但是redis构建了自己的字典。

字典使用

比如如下代码块set一个值，就会将键值对<name,dtxld>保存在字典里，除了数据库，字典还是哈希键的实现之一，当哈希键键值对比较多或者键值对中元素都是比较长的字符串时，就会使用字典作为其实现。

set name dtxld // 简单的string类型

下面主要是由字典来进行的一些延伸：字典的数据结构如下：

typedef struct dict {
	// 类型特定函数
	dictType *type;
	// 私有数据
	void *privdata;
	// hash表(这里可以对比下hashMap)
	dicht ht[2];
	// rehash索引，rehash不进行时，值为-1
	int rehashidx;
} dict 

上面的参数其实都好理解，对于我这个新手来说主要陌生的就是type、privdata、ht，下面分析下：
type属性指向了dictType结构的指针，每个dictType保存了一簇用于操作特定类型键值对的函数，redis为用途不同的字典设置不同的类型特定函数(可以参考下双端链表)，privdata属性保存了需要传给类型特定函数的可选参数，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 *ke2);
	// 销毁键的函数
	void (*keyDestructor)(void *privdata, void *key);
	// 销毁值的函数
	void (*valDestructor)(void *privdata, void *obj);
} dictType 

接着看下ht，塔是包含了两个项的数组，数组中的每一项都是dictht哈希表，一般情况，只使用ht[0]，ht[1]只是对ht[0]进行rehash时使用，dictht结构如下dict.h/dictht：

typedef struct dictht {
	// 哈希表数组
	dictEntry **table;
	// 哈希表大小
	unsigned long size;
	// 总是等于size - 1，用于计算哈希索引值
	unsigned long sizeMask;
	// 该哈希表已有节点数量
	unsigned long used;
} dictht

table属性是数组，数组里每个元素指向dictEntry，dictEntry结构如下dict.h/dictEntry：

typedef struct dictEntry {
	// 兼
	void *key;
	// 值--可以指针/uint64_t整数/int64_t整数
	union {
		void *val;
		uint64_tu64;
		int64_ts64;
	} v;
	// next指针指向另一个哈希表节点的指针，形成链表--hash冲突，形成链表的时候
	// 使用的头插法，因为链表没有指向表尾的指针，redis毕竟性能优先嘛
	// 也是为了性能
	struct dictEntry *next;
} dictEntry

rehash之前整个字典结构合起来如下：

知道上面的这些东西之后，我首先会去想怎么把一个键值对放进去这个哈希表中，所以redis会有hash算法来计算索引值：

// 计算hash值，字典被用作数据库底层实现或者hash键底层实现，redis使用的Murmurhash算法来计算键的hash值
hash = dict->type->hashFunction(key);
// 计算索引值，为什么是ht[x]因为ht[0]和ht[1]会换的，后面会说
index = hash & dict->ht[x].sizeMask;

rehash

随着业务的变化，键值对太多或者太少，这时肯定会有相应的扩展和收缩的操作，这个操作通过执行rehash(重新散列函数)来完成，主要步骤如下：

• 为字典的ht[1]分配空间(这个在上面画到过，一开始是0)，这个空间的大小会取决于要执行的操作以及ht[0]当前包含的键值对数量，也就是ht[0].used的值
  如果执行的是扩展操作：ht[1]大小是第一个大于等于ht[0].used * 2的2 ^ n(2的n次幂)。
  如果执行的是收缩操作：ht[1]大小是第一个大于等于ht[0].used 的2n。
• 将保存的ht[0]里的元素rehash到ht[1]，rehash就是重新计算hash值和index索引
• 当ht[0]都迁移到ht[1]以后(ht[0变成了空表])，这时释放掉ht[0]，将ht[1]设置成ht[0]，并在ht[1]新创建一个空白哈希表，为下一次rehash做准备

在这里我一开始就联想到了hashMap，就会去想那什么时候去扩展呢？
redis是根据服务器有没有在执行bgsave或者bgrewriteaof来进行扩展，当正在进行时，并且hash表的load_factor(负载因子)大于等于5会去扩展；
当没有进行时，hash表的load_factor(负载因子)大于等于1会去扩展。

// 负载因子 = 哈希表已保存节点数量 / 哈希表的大小
load_factor = ht[0].used / ht[0].size

这里会想到为什么和是否执行bgsave或者bgrewriteaof，他的负载因子不同呢？当然了，redis也是出于避免rehash和他们一同执行，毕竟他们执行时候会去创建子进程，这样可以避免不必要的内存写入，减少内存。
这里当load_factor小于0.1时，会自动进行收缩操作。

这里还有一个问题，既然是rehash，那到底是怎么执行的呢？键值对如果就4、5个，那一会的事情就搞定，如果数量很大，500多万，5亿个呢？一次性rehash完，肯定会导致服务器一段时间停止服务，这估计就完了吧…
所以redis采用的渐进式rehash，什么是渐进式rehash，其实就是分多次进行。具体步骤如下：

• 为ht[1] 分配空间，让字典同时持有ht[0]和ht[1]两个哈希表
• 在字典里维护一个索引计数器变量rehashidx，将它的值设为0，表示rehash工作正式开始
• 在rehash期间，每次对字典进行curd操作时，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，rehash完成之后，程序将其rehashidx值+1
• 随着程序的执行，最终ht[0]上的键值对全部rehash到ht[1]，将rehashidx设置为-1，rehash结束。

当然在字典同时持有ht[0]和ht[1]的时候，并且在rehash期间，ht[0]不在进行任何添加操作，都会添加到ht[1]，这时候你在添加到ht[0]那真是没意义，因为这样可以保证ht[0]只会减少不会增加，随着rehash最后变为空表。当查找一个键的时候，程序会先在ht[0]查找，若没有才会去ht[1]查找。

上面是我对这两个的理解，若有不对欢迎指出评论，顺便给个赞，年后马上金三银四，祝福大家跳槽愉快，薪资翻倍，下一篇跳表、整数集合、压缩列表一起整了，加油吧年轻人！