Redis数据结构—链表与字典的结构
Redis数据结构—链表与字典的结构
大家好，我是白泽。今天我们来聊一聊Redis中的链表与字典的结构
链表
关于链表的基础概念其实你在学习Redis之前一定积累了不少，所以本文将默认你已经掌握了链表相关的基础知识，而Redis的链表其实也就是普通的链表~
因为Redis是使用C语言编写的，因此Redis的数据结构的定义都是使用C语法定义的，你不需要完全理解下方C语言声明结构体的语法，但我认为依靠大家的Java知识也能理解这就像是在Java中定义了一个链表对象
Redis链表节点的结构
typedef struct listNode {
struct listNode *prev; //指向前一个链表节点
struct listNode *next; //指向后一个链表节点
void *value; //当前节点的值(可以按需设定不同数据类型的value)
} listNode;
很明显，当每一个节点内记录了前后两个节点位置之后，链表节点之间就能够彼此前后相连，组成双向通行车道（可以双向遍历）
Redis链表的表示
上面讲解了Redis的链表的节点表示，并由此引申了一下可以借此构建Redis双端链表，而事实上，对于每一个存在的双端链表，Redis使用一个list结构来表示
typedef struct list {
listNode *head; //表头节点
listNode *tail; //表尾节点
unsigned long len; //链表所包含的节点的数量
void *(*dup)(void *ptr); //节点复制函数
void (*free)(void *ptr); //节点释放函数
void (*match)(void *ptr, void *key);//节点值对比函数
} list;
很明显，你看到三个好像是返回值为void的函数，但是看不懂C语法，没关系，传统后端功夫，自然是点到为止
Redis链表用在哪
我不想现在就告诉你，链表被广泛用于实现Redis的各种功能，比如列表键、发布于订阅、慢查询、监视器等（这太空洞了，除了让你听一遍这几个词汇，对你没有任何帮助），等我们后面讲到这几部分的时候，白泽再结合链表和你细说~
字典
和链表一样，Redis所使用的C语言并没有内置字典这种数据结构，因此Redis构建了自己的字典实现。如果你学过数据结构，你会发现Redis的字典事实上就是数据结构中的邻接表，即使没学过，往下看就好啦~
Redis字典结构总览
数组 + 链表 ==> 邻接表，实锤
Redis字典结构分解
还记得吗，上面我们说Redis链表可以用list描述，但是链表存储的数据本质上，是由一系列listNode节点通过前后指针相连存储的；类似的，Redis字典可以用如下dict描述，但是字典存储的数据本质上，是由数组 + 若干链表组合得到的数据结构存储的，字典dict结构如下：
typedef struct dict {
dictType *type; //类型特定函数
void *privdata; //私有数据
dictht ht[2]; //哈希表数组
int trehashidx; //rehash索引，当rehash不在进行时，值为-1
} dict;
现在你只需要关注其中的哈希表数组ht[2]，它的数据类型为dictht，因此也是一种复合的数据结构，如下：
typedef struct dictht {
dictEntry **table; //哈希表数组
unsigned long size; //哈希表大小
unsigned long sizemax; //哈希表大小掩码，用于计算索引值，等于size - 1
unsigned long used; //该哈希表已有节点的数量
} dictht;
哈希表dictht是Redis字典的核心，dictht的四个属性中，size、sizemax、used都是用于描述table属性整体状态。看到这你就明白了，dictht的核心是dictEntry类型的table属性（再次提醒，如果没有C语言的基础，本文中一切你看不懂的语法，包括数据类型，你只需要一眼带过即可，我们的目的是学习Redis的设计思想）
table属性是一个数组，数组中的每个元素都是一个指向dictEntry结构的指针，每个dictEntry结构保存一个键值对，并含有一个指向下一个dictEntry的指针，结构如下：
typedef struct dictEntry {
void *key; //键
union { //值（可以是一个指针，可以是一个uint64_t类型的整数，也可以是一个int64_t类型的整数）
void *val;
uint64_t u64;
int64_t s64;
} v;
struct dictEntry *next;//指向下个哈希表节点，形成链表
} dictEntry;
Redis字典的使用
很抱歉，我不太想将一篇文章的篇幅变得太大，因为阅读大体量的技术文章确实容易令人心生退意，所以本文也点到为止。关于Redis字典的使用部分的知识将在白泽下一篇博客继续讲解，敬请期待~
