简单动态字符串（simple dynamic string）SDS

Redis 没有直接使用C语言传统的字符串表示，而是自己构建了一种名为简单动态字符串（simple dynamic string SDS）的抽象类型，并将SDS用作Redis 的默认字符串表示：

10.143.128.165:6379> SET msg "hello world"OK

设置一个key= msg，value = hello world 的新键值对，

键（key）是一个字符串对象，对象的底层实现是一个保存着字符串“msg” 的SDS；

值（value）也是一个字符串对象，对象的底层实现是一个保存着字符串“hello world” 的SDS

SDS除了用来保存字符串以外，SDS还被用作缓冲区（buffer）AOF模块中的AOF缓冲区。

SDS 的定义

Redis 中定义动态字符串的结构：

  struct sdshdr {           int len;// buf 中已占用空间的长度          int free;// buf 中剩余可用空间的长度        char buf[];// 数据空间  };

len 变量，用于记录buf 中已经使用的空间长度（这里指出Redis 的长度为5）

free 变量，用于记录buf 中还空余的空间（初次分配空间，一般没有空余，在对字符串修改的时候，会有剩余空间出现）

buf 字符数组，用于记录我们的字符串（记录Redis）

SDS 与 C 字符串的区别

1 获取字符串长度（SDS O（1）/C 字符串 O(n)）

传统的C 字符串 使用长度为N+1 的字符串数组来表示长度为N 的字符串，所以为了获取一个长度为C字符串的长度，必须遍历整个字符串。

SDS 的数据结构中，有专门用于保存字符串长度的变量，可以通过获取len 属性的值，直接知道字符串长度。

2 杜绝缓冲区溢出

C 字符串 不记录字符串长度，除了获取的时候复杂度高以外，还容易导致缓冲区溢出。

假设程序中有两个在内存中紧邻着的 字符串 s1 和 s2，其中s1 保存了字符串“redis”，二s2 则保存了字符串“MongoDb”：

如果我们现在将s1 的内容修改为redis cluster，但是又忘了重新为s1 分配足够的空间，这时候就会出现以下问题：

原本s2 中的内容已经被S1的内容给占领了，s2 现在为 cluster，而不是“mongoDB”。

当需要对一个SDS 进行修改的时候，redis 会在执行拼接操作之前，预先检查给定SDS 空间是否足够，如果不够，会先拓展SDS 的空间，然后再执行拼接操作：

3 减少修改字符串时带来的内存重分配次数

C语言字符串在进行字符串的扩充和收缩的时候，都会面临着内存空间的重新分配问题。

字符串拼接会产生字符串的内存空间的扩充，在拼接的过程中，原来的字符串的大小很可能小于拼接后的字符串的大小，那么这样的话，就会导致一旦忘记申请分配空间，就会导致内存的溢出。

字符串在进行收缩的时候，内存空间会相应的收缩，而如果在进行字符串的切割的时候，没有对内存的空间进行一个重新分配，那么这部分多出来的空间就成为了内存泄露。

我们需要对下面的SDS进行拓展，则需要进行空间的拓展，这时候redis 会将SDS的长度修改为13字节，并且将未使用空间同样修改为1字节

因为在上一次修改字符串的时候已经拓展了空间，再次进行修改字符串的时候会发现空间足够使用，因此无须进行空间拓展

通过这种预分配策略，SDS将连续增长N次字符串所需的内存重分配次数从必定N次降低为最多N次

4 惰性空间释放

SDS 的free 属性，是用于记录空余空间的。除了在拓展字符串的时候会使用到free 来进行记录空余空间以外，在对字符串进行收缩的时候，也可以使用free 属性来进行记录剩余空间，避免下次对字符串进行再次修改的时候，需要对字符串的空间进行拓展。

SDS 提供了相应的API，可以在有需要的时候，自行释放SDS 的空余空间。

通过惰性空间释放，SDS 避免了缩短字符串时所需的内存重分配操作，并未将来可能有的增长操作提供了优化

5 二进制安全

C 字符串中的字符必须符合某种编码，并且除了字符串的末尾之外，字符串里面不能包含空字符，否则最先被程序读入的空字符将被误认为是字符串结尾，这些限制使得C字符串只能保存文本数据，而不能保存想图片，音频，视频，压缩文件这样的二进制数据。

Redis 不是靠空字符来判断字符串的结束的，而是通过len这个属性。

6 兼容部分C字符串函数

虽然SDS 的API 都是二进制安全的，但一样遵循C字符串以空字符串结尾的惯例。

========================================================================

链表

链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度。

Redis 中 列表键的底层实现之一就是链表。当一个列表键包含了数量较多的元素，又或者列表中包含的元素都是比较长的字符串时，Redis 就会使用链表作为列表键的底层实现。

每个链表节点使用一个 listnode结构表示：

typedef struct listNode{      struct listNode *prev;      struct listNode * next;      void * value;  }

多个链表节点组成的双端链表：

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);//节点值对比函数}

链表的特性

• 双端：链表节点带有prev 和next 指针，获取某个节点的前置节点和后置节点的时间复杂度都是O（N）
• 无环：表头节点的 prev 指针和表尾节点的next 都指向NULL，对立案表的访问时以NULL为截止
• 表头和表尾：因为链表带有head指针和tail 指针，获取链表头结点和尾节点的时间复杂度为O(1)
• 长度计数器：链表中存有记录链表长度的属性 len
• 多态：链表节点使用 void* 指针来保存节点值，并且可以通过list 结构的dup 、 free、 match三个属性为节点值设置类型特定函数。

========================================================================

字典

字典，又称为符号表（symbol table）、关联数组（associative array）或映射（map），是一种用于保存键值对的抽象数据结构。　

在字典中，一个键（key）可以和一个值（value）进行关联，字典中的每个键都是独一无二的。在C语言中，并没有这种数据结构，但是Redis 中构建了自己的字典实现。

10.143.128.165:6379> SET msg "hello world"OK

字典的定义

1 哈希表

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

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

一个空的字典的结构图如下：

在结构中存有指向dictEntry 数组的指针，而我们用来存储数据的空间就是 dictEntry

 2. 哈希表节点（ dictEntry ）

typeof struct dictEntry{   void *key; //键   uNIOn{   //值      void *val;      uint64_tu64;      int64_ts64;   }   struct dictEntry *next;}

在数据结构中，key 是唯一的，但是存入里面的key 并不是直接的字符串，而是一个hash 值，通过hash 算法，将字符串转换成对应的hash 值，然后在dictEntry 中找到对应的位置。

如果出现hash 值相同的情况，Redis 采用了链地址法：

当k1 和k0 的hash 值相同时，将k1中的next 指向k0 形成一个链表。

3 字典

typedef struct dict {      dictType *type;  // 类型特定函数        void *privedata; // 私有数据       dictht  ht[2];  // 哈希表      in trehashidx; // rehash 索引}

type 属性 和privdata 属性是针对不同类型的键值对，为创建多态字典而设置的。

ht 属性是一个包含两个项（两个哈希表）的数组

普通状态下的字典：

解决哈希冲突

在插入一条新的数据时，会进行哈希值的计算，如果出现了hash值相同的情况，Redis 中采用了连地址法（separate chaining）来解决键冲突。每个哈希表节点都有一个next 指针，多个哈希表节点可以使用next 构成一个单向链表，被分配到同一个索引上的多个节点可以使用这个单向链表连接起来解决hash值冲突的问题。

 现在要插入k2，通过hash 算法计算到k2 的hash 值为2，即需要将k2 插入到dictEntry[2]中：