【Redis 笔记】（2）Redis中的数据结构
接着上一篇文章Redis 系统学习（1）redis实现消息队列的内容，继续深入学习redis
redis中的五种数据结构
Redis有五种基础数据结构，分别为：string（字符串）、list（列表）、hash（字典）、set（集合）和zset（有序集合）。
下面再对应分析一下Redis源代码。了解一下相关的类型的实现，学习一下Redis 是如何做到内存使用的极致的。
在server.h文件中，给出了RedisObject的结构体定义，我们一起来看看。
typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:LRU_BITS; // LRU_BITS为24
int refcount;
void *ptr;
} robj;
其中，ptr指向对象中实际存放的值，这里不需要过多解释，针对其他四个结构体参数，
Redis的对象有五种类型，分别是string、hash、list、set和zset，type属性就是用来标识着五种数据类型。type占用4个bit位，其取值和类型对应如下：
#define OBJ_STRING 0
#define OBJ_LIST 1
#define OBJ_SET 2
#define OBJ_ZSET 3
#define OBJ_HASH 4
String 字符串
string是Redis中最简单的数据结构，它的内部表示就是一个字符数组。Redis所有的数据结构都以唯一的key字符串作为名称，然后通过这个唯一的key值来获取相应的value数据。不同类型的数据结构的差异就在于value的结构不一样。
Redis没有使用C语言的字符串结构，而是自己设计了一个简单的动态字符串结构sds。它的特点是：可动态扩展内存、二进制安全和与传统的C语言字符串类型兼容。
对比C语言和SDS中的字符串
对比：
SDS 来说， 程序只要访问 SDS 的 len 属性， 就可以立即知道 SDS 的长度为 5字节。Redis 将获取字符串长度所需的复杂度从 O(N) 降低到了 O(1) ， 这确保了获取字符串长度的工作不会成为 Redis 的性能瓶颈。
下面来看看对应的源代码，至于如何阅读源代码，参考如何阅读 Redis 源码？
我这里是基于redis-5.0.8 源代码进行分析。
sds.h
//sds是二进制安全的，它可以存储任意二进制数据，不能像C语言字符串那样以‘\0’来标识字符串结束，因此它必然存在一个长度字段
typedef char *sds;
/* Note: sdshdr5 is never used, we just access the flags byte directly.
* However is here to document the layout of type 5 SDS strings. */
//为了满足不同长度的字符串可以使用不同大小的Header，从而节省内存。sds结构一共有五种Header定义
/*
在这里解释一下attribute ((packed))的用意：加上此字段是为了让编译器以紧凑模式来分配内存。如果没有这个字段，
编译器会按照struct中的字段进行内存对齐，这样的话就不能保证header和sds的数据部分紧紧的相邻了，
也不能按照固定的偏移来获取flags字段。
*/
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* used */
uint8_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len; /* used */
uint16_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len; /* used */
uint32_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len; /* used */
uint64_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
sds.c创建函数
Redis在创建sds时，会为其申请一段连续的内存空间，其中包含sds的header和数据部分buf[]
sds sdsnewlen(const void *init, size_t initlen) {
void *sh;
sds s;
char type = sdsReqType(initlen);
/* Empty strings are usually created in order to append. Use type 8
* since type 5 is not good at this. */
if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
// 得到sds的header的大小
int hdrlen = sdsHdrSize(type);
unsigned char *fp; /* flags pointer. */
// s_malloc等同于zmalloc，+1代表字符串结束符
sh = s_malloc(hdrlen+initlen+1);
if (init==SDS_NOINIT)
init = NULL;
else if (!init)
memset(sh, 0, hdrlen+initlen+1);
if (sh == NULL) return NULL;
// s为数据部分的起始指针
s = (char*)sh+hdrlen;
fp = ((unsigned char*)s)-1;// 得到flags的指针
// 根据字符串类型来设定header中的字段
switch(type) {
case SDS_TYPE_5: {
*fp = type | (initlen << SDS_TYPE_BITS);
break;
}
case SDS_TYPE_8: {
SDS_HDR_VAR(8,s);
sh->len = initlen;// 设定字符串长度
sh->alloc = initlen;// 设定字符串的最大容量
*fp = type;
break;
}
case SDS_TYPE_16: {
SDS_HDR_VAR(16,s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
case SDS_TYPE_32: {
SDS_HDR_VAR(32,s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
case SDS_TYPE_64: {
SDS_HDR_VAR(64,s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
}
if (initlen && init)
memcpy(s, init, initlen); // 拷贝数据部分
s[initlen] = '\0';// 与C字符串兼容
return s; // 返回创建的sds字符串指针
}
sds.c动态调整函数
sds最重要的性能就是动态调整，Redis提供了扩展sds容量的函数。
// 在原有的字符串中取得更大的空间，并返回扩展空间后的字符串
sds sdsMakeRoomFor(sds s, size_t addlen) {
void *sh, *newsh;
size_t avail = sdsavail(s);// 获取sds的剩余空间
size_t len, newlen;
char type, oldtype = s[-1] & SDS_TYPE_MASK;
int hdrlen;
/* Return ASAP if there is enough space left. */
if (avail >= addlen) return s;
len = sdslen(s);
sh = (char*)s-sdsHdrSize(oldtype);
newlen = (len+addlen);
// sds规定：如果扩展后的字符串总长度小于1M则新字符串长度为扩展后的两倍
// 如果大于1M，则新的总长度为扩展后的总长度加上1M
// 这样做的目的是减少Redis内存分配的次数，同时尽量节省空间
if (newlen < SDS_MAX_PREALLOC) // SDS_MAX_PREALLOC = 1024*1024
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
// 根据sds的长度来调整类型
type = sdsReqType(newlen);
/* Don't use type 5: the user is appending to the string and type 5 is
* not able to remember empty space, so sdsMakeRoomFor() must be called
* at every appending operation. */
if (type == SDS_TYPE_5) type = SDS_TYPE_8;
hdrlen = sdsHdrSize(type);
if (oldtype==type) {
// 如果与原类型相同，直接调用realloc函数扩充内存
newsh = s_realloc(sh, hdrlen+newlen+1);
if (newsh == NULL) return NULL;
s = (char*)newsh+hdrlen;
} else {
/* Since the header size changes, need to move the string forward,
* and can't use realloc */
// 如果类型调整了，header的大小就需要调整
// 这时就需要移动buf[]部分，所以不能使用realloc
newsh = s_malloc(hdrlen+newlen+1);
if (newsh == NULL) return NULL;
memcpy((char*)newsh+hdrlen, s, len+1);
s_free(sh);
s = (char*)newsh+hdrlen;// 更新s
s[-1] = type;// 设定新的flags参数
sdssetlen(s, len);// 更新len
}
sdssetalloc(s, newlen);// 更新sds的容量
return s;
}
sds.c字符串追加
/* Append the specified binary-safe string pointed by 't' of 'len' bytes to the
* end of the specified sds string 's'.
*
* After the call, the passed sds string is no longer valid and all the
* references must be substituted with the new pointer returned by the call. */
sds sdscatlen(sds s, const void *t, size_t len) {
// 获取原字符串的长度
size_t curlen = sdslen(s);
// 按需调整空间，如果容量不够容纳追加的内容，就会重新分配字节数组并复制原字符串的内容到新数组中
s = sdsMakeRoomFor(s,len);
if (s == NULL) return NULL; // 内存不足
memcpy(s+curlen, t, len); // 追加目标字符串到字节数组中
sdssetlen(s, curlen+len);// 设置追加后的长度
s[curlen+len] = '\0';// 让字符串以 \0 结尾，便于调试打印
return s;
}
sds的二进制安全
C 字符串中的字符必须符合某种编码（比如 ASCII）， 并且除了字符串的末尾之外， 字符串里面不能包含空字符， 否则最先被程序读入的空字符将被误认为是字符串结尾 —— 这些限制使得 C 字符串只能保存文本数据， 而不能保存像图片、音频、视频、压缩文件这样的二进制数据。为了确保 Redis 可以适用于各种不同的使用场景， SDS 的 API 都是二进制安全的（binary-safe）： 所有 SDS API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组里的数据， 程序不会对其中的数据做任何限制、过滤、或者假设 —— 数据在写入时是什么样的， 它被读取时就是什么样。
这也是我们将 SDS 的 buf 属性称为字节数组的原因 —— Redis 不是用这个数组来保存字符， 而是用它来保存一系列二进制数据。
list(列表)
Redis的列表相当于Java中的LinkedList，注意它是链表而不是数组。这意味着list的插入和删除操作非常快，时间复杂度为O(1),但是索引定位很慢，时间复杂度为O(n)。列表中每个元素都使用了双向指针顺序，是为双向链表。
Redis的列表结构常用于做异步队列使用。将需要延后处理的任务结构体序列化成字符串，塞入Redis的列表，另一个线程从列表中轮询数据进行处理。
其实看源代码，我们会发现这种数据类型对应两种实现方法，一种是压缩列表（ziplist.c），另一种是双向循环链表（adlist.c）。
adlist.c 双端链表
Redis 的这种双向链表的实现方式，非常值得借鉴。它额外定义一个 list 结构体，来组织链表的首、尾指针，还有长度等信息。这样，在使用的时候就会非常方便。参考adlist.c和adlist.h
除了实现列表类型以外， 双端链表还被很多 Redis 内部模块所应用：
- 事务模块使用双端链表依序保存输入的命令；
- 服务器模块使用双端链表来保存多个客户端；
- 订阅/发送模块使用双端链表来保存订阅模式的多个客户端；
- 事件模块使用双端链表来保存时间事件（time event）；
下面来看看对应的源代码：
还是先看看头文件 adlist.h
/*
* A generic doubly linked list implementation
*/
#ifndef __ADLIST_H__
#define __ADLIST_H__
/* Node, List, and Iterator are the only data structures used currently. */
// 链表节点定义
typedef struct listNode {
struct listNode *prev;// 指向前一个节点
struct listNode *next;// 指向后一个节点
void *value;
} listNode;
typedef struct listIter {
listNode *next;// 指向下一个节点
int direction;// 方向参数，正序和逆序
} listIter;
typedef struct list {
listNode *head;// 指向链表头节点
listNode *tail;// 指向链表尾节点
void *(*dup)(void *ptr);// 自定义节点值复制函数
void (*free)(void *ptr);// 自定义节点值释放函数
int (*match)(void *ptr, void *key);// 自定义节点值匹配函数
unsigned long len;// 链表长度
} list;
list *listCreate(void);
void listRelease(list *list);
void listEmpty(list *list);
list *listAddNodeHead(list *list, void *value);
list *listAddNodeTail(list *list, void *value);
list *listInsertNode(list *list, listNode *old_node, void *value, int after);
void listDelNode(list *list, listNode *node);
listIter *listGetIterator(list *list, int direction);
listNode *listNext(listIter *iter);
void listReleaseIterator(listIter *iter);
list *listDup(list *orig);
listNode *listSearchKey(list *list, void *key);
listNode *listIndex(list *list, long index);
void listRewind(list *list, listIter *li);
void listRewindTail(list *list, listIter *li);
void listRotate(list *list);
void listJoin(list *l, list *o);
/* Directions for iterators */
#define AL_START_HEAD 0
#define AL_START_TAIL 1
#endif /* __ADLIST_H__ */
再来接着看看adlist.c里的双端链表部分操作：
list *listCreate(void)
{
struct list *list;// 定义一个链表指针
if ((list = zmalloc(sizeof(*list))) == NULL)// 申请内存
return NULL;
list->head = list->tail = NULL;// 空链表的头指针和尾指针均为空
list->len = 0; // 设定长度
list->dup = NULL;// 自定义复制函数初始化
list->free = NULL;// 自定义释放函数初始化
list->match = NULL;// 自定义匹配函数初始化
return list;
}
/* Add a new node to the list, to head, containing the specified 'value'
* pointer as value.
*
* On error, NULL is returned and no operation is performed (i.e. the
* list remains unaltered).
* On success the 'list' pointer you pass to the function is returned. */
// 该函数向list的头部插入一个节点
list *listAddNodeHead(list *list, void *value)
{
listNode *node;
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
node->value = value;
if (list->len == 0) { // 如果链表为空
list->head = list->tail = node;
node->prev = node->next = NULL;
} else { // 如果链表非空
node->prev = NULL;
node->next = list->head;
list->head->prev = node;
list->head = node;
}
list->len++; // 长度+1
return list;
}
/* Add a new node to the list, to tail, containing the specified 'value'
* pointer as value.
*
* On error, NULL is returned and no operation is performed (i.e. the
* list remains unaltered).
* On success the 'list' pointer you pass to the function is returned. */
// 该函数可以在list的尾部添加一个节点
list *listAddNodeTail(list *list, void *value)
{
listNode *node;
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
node->value = value;
if (list->len == 0) { // 如果链表为空
list->head = list->tail = node;
node->prev = node->next = NULL;
} else { // 如果链表非空
node->prev = list->tail;
node->next = NULL;
list->tail->next = node;
list->tail = node;
}
list->len++;
return list;
}
// 向任意位置插入节点
// 其中，old_node为插入位置
// value为插入节点的值
// after为0时表示插在old_node前面，为1时表示插在old_node后面
list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
listNode *node;
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
node->value = value;
if (after) { // 向后插入
node->prev = old_node;
node->next = old_node->next;
// 如果old_node为尾节点的话需要改变tail
if (list->tail == old_node) {
list->tail = node;
}
} else {
// 向前插入
node->next = old_node;
node->prev = old_node->prev;
// 如果old_node为头节点的话需要改变head
if (list->head == old_node) {
list->head = node;
}
}
if (node->prev != NULL) {
node->prev->next = node;
}
if (node->next != NULL) {
node->next->prev = node;
}
list->len++;
return list;
}
/* Remove the specified node from the specified list.
* It's up to the caller to free the private value of the node.
*
* This function can't fail. */
void listDelNode(list *list, listNode *node)
{
if (node->prev) // 删除节点不为头节点
node->prev->next = node->next;
else // 删除节点为头节点需要改变head的指向
list->head = node->next;
if (node->next) // 删除节点不为尾节点
// 删除节点为尾节点需要改变tail的指向
node->next->prev = node->prev;
else
list->tail = node->prev;
if (list->free) list->free(node->value);// 释放节点值
zfree(node);// 释放节点
list->len--;
}
/* Returns a list iterator 'iter'. After the initialization every
* call to listNext() will return the next element of the list.
*
* This function can't fail. */
listIter *listGetIterator(list *list, int direction)
{
listIter *iter;// 声明迭代器
if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
// 根据迭代方向来初始化iter
if (direction == AL_START_HEAD)
iter->next = list->head;
else
iter->next = list->tail;
iter->direction = direction;
return iter;
}
/* Duplicate the whole list. On out of memory NULL is returned.
* On success a copy of the original list is returned.
*
* The 'Dup' method set with listSetDupMethod() function is used
* to copy the node value. Otherwise the same pointer value of
* the original node is used as value of the copied node.
*
* The original list both on success or error is never modified. */
//链表复制函数
list *listDup(list *orig)
{
list *copy;
listIter iter;
listNode *node;
if ((copy = listCreate()) == NULL)
return NULL;
// 复制节点值操作函数
copy->dup = orig->dup;
copy->free = orig->free;
copy->match = orig->match;
// 重置迭代器
listRewind(orig, &iter);
while((node = listNext(&iter)) != NULL) {
void *value;
// 复制节点
// 如果定义了dup函数，则按照dup函数来复制节点值
if (copy->dup) {
value = copy->dup(node->value);
if (value == NULL) {
listRelease(copy);
return NULL;
}
} else // 如果没有则直接赋值
value = node->value;
// 依次向尾部添加节点
if (listAddNodeTail(copy, value) == NULL) {
listRelease(copy);
return NULL;
}
}
return copy;
}
/* Search the list for a node matching a given key.
* The match is performed using the 'match' method
* set with listSetMatchMethod(). If no 'match' method
* is set, the 'value' pointer of every node is directly
* compared with the 'key' pointer.
*
* On success the first matching node pointer is returned
* (search starts from head). If no matching node exists
* NULL is returned. */
listNode *listSearchKey(list *list, void *key)
{
listIter iter;
listNode *node;
listRewind(list, &iter);
while((node = listNext(&iter)) != NULL) {
if (list->match) {// 如果定义了match匹配函数，则利用该函数进行节点匹配
if (list->match(node->value, key)) {
return node;
}
} else {// 如果没有定义match，则直接比较节点值
if (key == node->value) {// 找到该节点
return node;
}
}
}
return NULL;
}
/* Return the element at the specified zero-based index
* where 0 is the head, 1 is the element next to head
* and so on. Negative integers are used in order to count
* from the tail, -1 is the last element, -2 the penultimate
* and so on. If the index is out of range NULL is returned. */
//根据序号来查找节点
listNode *listIndex(list *list, long index) {
listNode *n;
if (index < 0) { // 序号为负，则倒序查找
index = (-index)-1;
n = list->tail;
while(index-- && n) n = n->prev;
} else { // 正序查找
n = list->head;
while(index-- && n) n = n->next;
}
return n;
}
/* Rotate the list removing the tail node and inserting it to the head. */
void listRotate(list *list) {
listNode *tail = list->tail;
if (listLength(list) <= 1) return;
/* Detach current tail */
// 取出表尾指针
list->tail = tail->prev;
list->tail->next = NULL;
/* Move it as head */
// 将其移动到表头并成为新的表头指针
list->head->prev = tail;
tail->prev = NULL;
tail->next = list->head;
list->head = tail;
}
ziplist.c压缩列表
当列表中存储的数据量比较小的时候，列表就可以采用压缩列表的方式实现。具体需要同时满足下面两个条件：
列表中保存的单个数据（有可能是字符串类型的）小于 64 字节；
列表中数据个数少于 512 个。
它并不是基础数据结构，而是 Redis 自己设计的一种数据存储结构。它有点儿类似数组，通过一片连续的内存空间，来存储数据。不过，它跟数组不同的一点是，它允许存储的数据大小不同。
压缩列表这种存储结构，一方面比较节省内存，另一方面可以支持不同类型数据的存储。而且，因为数据存储在一片连续的内存空间，通过键来获取值为列表类型的数据，读取的效率也非常高。
通过源代码我们可以发现，ziplist可以用来存放字符串或者整数，其存储数据的特点是：比较小的整数或比较短的字符串。Redis的列表建，哈希键，有序集合的底层实现都用到了ziplist。
这一块相关的源代码注释，还在整理中，后面整理后发出来：
目前可以参考： 压缩列表
hash(字典)
Redis里的字典相当于Java中的HashMap，它是无序的，内部存储了很多键值对，实现结构上与HashMap也是一样的，都是“数组+链表”二维结构。而存放的位置是根据key的hashCode来计算的，若两个key计算出来的在数组的同一位，则在这个下标下使用链表串接起来。
Redis中的hash只能存字符串，而且它们rehash的方式也不一样。因为HashMap在字典很大时，rehash是很耗时的，需要一次性全部rehash。Redis为了追求高性能，不能堵塞服务，采用了渐进式rehash策略。
渐进式rehash的时候，不会一次全部rehash，而是将旧hash里的内容慢慢迁移（迁移后旧的里面就没有了）到新的hash结构中，在彻底迁移完之前，查询时会同时查询两个hash结构。当迁移完成后，就会用新的hash结构，旧的数据结构被自动删除。注意，hash结构的存储消耗要高于单个字符串。
Redis中的字典采用哈希表作为底层实现，在Redis源码文件中，字典的实现代码在dict.c和dict.h文件中。
// 计算哈希值
h = dictHashKey(d, key);
// 调用哈希算法计算哈希值
#define dictHashKey(d, key) (d)->type->hashFunction(key)
计算出哈希值之后，需要计算其索引。Redis采用下列算式来计算索引值
// 举例：h为5，哈希表的大小初始化为4，sizemask则为size-1，
// 于是h&sizemask = 2，
// 所以该键值对就存放在索引为2的位置
idx = h & d->ht[table].sizemask;
一个字典结构
字典类型也有两种实现方式。一种是我们刚刚讲到的压缩列表，另一种是散列表。
只有当存储的数据量比较小的情况下，Redis 才使用压缩列表来实现字典类型。具体需要满足两个条件：
字典中保存的键和值的大小都要小于 64 字节；
字典中键值对的个数要小于 512 个。
当不能同时满足上面两个条件的时候，Redis 就使用散列表来实现字典类型。Redis 使用MurmurHash2这种运行速度快、随机性好的哈希算法作为哈希函数。对于哈希冲突问题，Redis 使用链表法（separate chaining）来解决。除此之外，Redis 还支持散列表的动态扩容、缩容。
源代码整理后发上来。
解决hash 冲突
使用链表法解决hash冲突
set（集合）
Redis中的set和list都是字符串序列，非常相似，不同于set是用hash来实现值的唯一性，无序的，不可重复的。它的内部实现相当于一个特殊的字典，字典中所有的value都是一个值NULL。
这种数据类型也有两种实现方法，一种是基于有序数组，另一种是基于散列表。
当要存储的数据，同时满足下面这样两个条件的时候，Redis 就采用有序数组，来实现集合这种数据类型。
存储的数据都是整数；
存储的数据元素个数不超过 512 个。
当不能同时满足这两个条件的时候，Redis 就使用散列表来存储集合中的数据。
zset（有序集合）
zset是Redis提供的最有特色的数据结构，也是面试中最常出现的角色。它是ziplist和skiplist（跳跃列表）的结合体，一方面它是一个set，保证了值的唯一性，另一方面它可以给每个值赋予一个score，代表着这个值的排序权重。当存储元素的数量小于128个，所有member的长度都小于64字节，就会使用ziplist。
下面来看看skiplist（跳跃列表）：
跳跃表是一种有序的数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问的目的。跳跃表在插入、删除和查找操作上的平均复杂度为O（logN），最坏为O（N），可以和红黑树相媲美，但是在实现起来，比红黑树简单很多。
容器型数据结构的通用规则
我们没有在推入元素之前创建空的 list，或者在 list 没有元素时删除它。在 list 为空时删除 key，并在用户试图添加元素（比如通过 LPUSH）而键不存在时创建空 list，是 Redis 的职责。
这不光适用于 lists，还适用于所有包括多个元素的 Redis 数据类型 – Sets, Sorted Sets 和 Hashes。
基本上，我们可以用三条规则来概括它的行为：
当我们向一个聚合数据类型中添加元素时，如果目标键不存在，就在添加元素前创建空的聚合数据类型。
当我们从聚合数据类型中移除元素时，如果值仍然是空的，键自动被销毁。
对一个空的 key 调用一个只读的命令，比如 LLEN （返回 list 的长度），或者一个删除元素的命令，将总是产生同样的结果。该结果和对一个空的聚合类型做同个操作的结果是一样的。
总结
redis的数据结构由多种数据结构来实现，主要是出于时间和空间的考虑，当数据量小的时候通过数组下标访问最快、占用内存最小，而压缩列表只是数组的升级版；
因为数组需要占用连续的内存空间，所以当数据量大的时候，就需要使用链表了，同时为了保证速度又需要和数组结合，也就有了散列表。
参考文章
Redis 数据结构的源码分析，参考：
Redis 数据结构-字符串源码分析：https://my.oschina.net/mengyuankan/blog/1926320
Redis 数据结构-字典源码分析： https://my.oschina.net/mengyuankan/blog/1929593
https://zcheng.ren/sourcecodeanalysis/theannotatedredissourcesds/
https://redissrc.readthedocs.io/en/latest/index.html
未完待续......
