​ 整数集合（intset）是用于保存整数值的集合抽象数据结构，可以保存的类型为 int16_t、int32_t、int64_t的整数值，并且保证了集合不会出现重复的元素值。

整数集合的实现

​ 每个 intset.h/intset 结构表示一个整数集合：

1
2
3
4
5
6
7
8
9
10

typedef struct intset {
	//编码方式
	uint32_t encoding;

	//集合包含的元素数量
	uint32_t length;

	//保存元素的数组
	int8_t contents[];
} intset;

contents 数组是整数集合的底层实现：整数集合的每个元素都是 contents数组的一个数组项（item），各个项在数组中按值的大小从小到大有序的排列，并且数组中不包含任何重复项。

length 属性记录了整数集合包含的元素数量，也即是 contents数组的长度。

涉及的算法如下：

mismatch&next_permutation(prev_permutation、is_permutation)&copy&unique&rotate&move

准备工作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

struct Msg {
	int index;
	int msg;
};
//用于打印显式
void PrintVec(vector<Msg>::iterator iter_begin, vector<Msg>::iterator iter_end) {
	for (auto iter = iter_begin; iter != iter_end; iter++) {
		if (iter != iter_begin) {
			cout << "--";
		}
		cout << iter->index << ":" << iter->msg;
	}
	cout << endl << endl;
}
//打印INT数组
void PrintVecInt(vector<int>::iterator iter_begin, vector<int>::iterator iter_end) {
	for (auto iter = iter_begin; iter != iter_end; iter++) {
		if (iter != iter_begin) {
			cout << "--";
		}
		cout << *iter;
	}
	cout << endl << endl;
}

生成数据（所有的排序针对index，msg只是为了标识稳定与否）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

vector<Msg> v_msg;
//vector<Msg> v_msg_sec;
Msg temp_msg;
int count = 10; 
srand((int)time(0));
for (int i = 0; i < count; i++) {
	temp_msg.index = rand() % 100;
	temp_msg.msg = i;
	v_msg.push_back(temp_msg);
	//if (rand() % 2 == 0 && i != 0) {
	//	temp_msg.index = rand() % 100;
	//	temp_msg.msg = i;
	//	v_msg_sec.push_back(temp_msg);
	//}
}

• mismatch

Redis跳跃表的实现。

用到的两个结构体redis.h/zskiplistNode和redis.h/zskiplist两个结构定义，其中zskiplistNode结构表示跳跃表节点，而zskiplist结构则是用于保存跳跃表节点的相关信息，具体的以下有讲解。

一个跳跃表的例子

其中图片最左边的是zskiplist结构,包含以下属性：

• header 指向跳跃表的表头节点。

• tail 指向跳跃表的表尾节点。

• level 记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。

• length 记录跳跃表的长度，也就是跳跃表目前包含节点的数量（表头节点不包含在内）。

Redis的字典使用哈希表 作为底层实现，一个哈希表里面可以有多个哈希表节点，而每一个哈希表节点保存了一个键值对。

1. 哈希表

   Redis字典所使用的哈希表在dict.h/dictht结构定义。

   1 2 3 4 5 6 7 8 9 10 11

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

各个属性介绍都在注释里，这里值得注意的是sizemask属性的值总是等于size-1,这个属性值和哈希值一起决定一个键值对应该被放在table的哪个索引上。
以下为一个大小为4的空哈希表（没有任何键值对）：

Redis的链表结构解析

1. 链表节点定义

   链表节点结构adlist.h/listNode

   1 2 3 4 5 6 7 8 9

   typedef struct listNode { //前置节点 struct listNode *prev; //后置节点 struct listNode *next; //节点的值 void *value; }listNode;

由于有prev和next，多个listNode可以组成双端链表结构。

2. list定义