本文共 4838 字，大约阅读时间需要 16 分钟。
SDS （Simple Dynamic String）是 Redis 最基础的数据结构。直译过来就是”简单的动态字符串“。Redis 自己实现了一个动态的字符串，而不是直接使用了 C 语言中的字符串。
sds 的数据结构：
struct sdshdr { // buf 中已占用空间的长度 int len; // buf 中剩余可用空间的长度 int free; // 数据空间 char buf[];}; 所以一个 SDS 的就如下图：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-t2YCOSKC-1573627290412)(media/15663750838907/15663751675407.jpg)]
所以我们看到，sds 包含3个参数。buf 的长度 len，buf 的剩余长度，以及buf。为什么这么设计呢？
可以直接获取字符串长度。
C 语言中，获取字符串的长度需要用指针遍历字符串，时间复杂度为 O(n)，而 SDS 的长度，直接从len 获取复杂度为 O(1)。杜绝缓冲区溢出。
由于C 语言不记录字符串长度，如果增加一个字符传的长度，如果没有注意就可能溢出，覆盖了紧挨着这个字符的数据。对于SDS 而言增加字符串长度需要验证 free的长度，如果free 不够就会扩容整个 buf，防止溢出。减少修改字符串长度时造成的内存再次分配。
redis 作为高性能的内存数据库，需要较高的相应速度。字符串也很大概率的频繁修改。 SDS 通过未使用空间这个参数，将字符串的长度和底层buf的长度之间的额关系解除了。buf的长度也不是字符串的长度。基于这个分设计 SDS 实现了空间的预分配和惰性释放。二进制安全。
C 语言中的字符串是以 ”\0“ 作为字符串的结束标记。而 SDS 是使用 len 的长度来标记字符串的结束。所以SDS 可以存储字符串之外的任意二进制流。因为有可能有的二进制流在流中就包含了”\0“造成字符串提前结束。也就是说 SDS 不依赖 “\0” 作为结束的依据。兼容C语言
SDS 按照惯例使用 ”\0“ 作为结尾的管理。部分普通C 语言的字符串 API 也可以使用。C语言中并没有链表这个数据结构所以 Redis 自己实现了一个。Redis 中的链表是：
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; 链表的结构比较简单，数据结构如下：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pwkSNd6w-1573627290413)(media/15663750838907/15663752964435.jpg)]总结一下性质：
字典数据结构极其类似 java 中的 Hashmap。
Redis的字典由三个基础的数据结构组成。最底层的单位是哈希表节点。结构如下：
typedef struct dictEntry { // 键 void *key; // 值 union { void *val; uint64_t u64; int64_t s64; } v; // 指向下个哈希表节点，形成链表 struct dictEntry *next;} dictEntry; 实际上哈希表节点就是一个单项列表的节点。保存了一下下一个节点的指针。 key 就是节点的键，v是这个节点的值。这个 v 既可以是一个指针，也可以是一个 uint64_t或者 int64_t 整数。*next 指向下一个节点。
通过一个哈希表的数组把各个节点链接起来：
typedef struct dictht { // 哈希表数组 dictEntry **table; // 哈希表大小 unsigned long size; // 哈希表大小掩码，用于计算索引值 // 总是等于 size - 1 unsigned long sizemask; // 该哈希表已有节点的数量 unsigned long used;} dictht; 通过图示我们观察：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FVEBYd5O-1573627290413)(media/15663750838907/15663753610286.jpg)]
实际上，如果对java 的基本数据结构了解的同学就会发现，这个数据结构和 java 中的 HashMap 是很类似的，就是数组加链表的结构。
字典的数据结构：
typedef struct dict { // 类型特定函数 dictType *type; // 私有数据 void *privdata; // 哈希表 dictht ht[2]; // rehash 索引 // 当 rehash 不在进行时，值为 -1 int rehashidx; /* rehashing not in progress if rehashidx == -1 */ // 目前正在运行的安全迭代器的数量 int iterators; /* number of iterators currently running */} dict; 其中的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 *key2); // 销毁键的函数 void (*keyDestructor)(void *privdata, void *key); // 销毁值的函数 void (*valDestructor)(void *privdata, void *obj);} dictType; 字典的数据结构如下图：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PI20viEC-1573627290414)(media/15663750838907/15663754115428.jpg)]这里我们可以看到一个dict 拥有两个 dictht。一般来说只使用 ht[0],当扩容的时候发生了rehash的时候，ht[1]才会被使用。
当我们观察或者研究一个hash结构的时候偶我们首先要考虑的这个 dict 如何插入一个数据？
我们梳理一下插入数据的逻辑。
计算Key 的 hash 值。找到 hash 映射到 table 数组的位置。
如果数据已经有一个 key 存在了。那就意味着发生了 hash 碰撞。新加入的节点，就会作为链表的一个节点接到之前节点的 next 指针上。
如果 key 发生了多次碰撞，造成链表的长度越来越长。会使得字典的查询速度下降。为了维持正常的负载。Redis 会对 字典进行 rehash 操作。来增加 table 数组的长度。所以我们要着重了解一下 Redis 的 rehash。步骤如下：
渐进式的 rehash 。
其实如果字典的 key 数量很大，达到千万级以上，rehash 就会是一个相对较长的时间。所以为了字典能够在 rehash 的时候能够继续提供服务。Redis 提供了一个渐进式的 rehash 实现
rehash的步骤如下：
转载地址：http://hzorb.baihongyu.com/