简单动态字符串 （SDS）
内部实现
struct sdshdr {
len int; // 所保存的字符串长度
free int; // 未使用的字节长度
char buf[]; // 字节数组，用于保存字符串
}
c 字符串通常是以空字符 '\0' 结尾，所以一个 SDS 的长度为： len + free + 1
与 c 字符串的区别
| 类型 | c 字符串 | SDS |
|---|---|---|
| 获取字符串长度 | O(N) | O(1) |
| 是非 API 安全 | 存在缓冲区溢出风险 | API 安全，无缓冲区溢出 |
| 是否二进制安全 | 非二进制安全 | 二进制安全 |
| 修改字符串导致内存分配 | 每次重新分配 | N 次修改最多 N 次分配 |
| 是否兼容 <string.h> 标准库 | 完全兼容 | 部分兼容 |
获取字符串长度
- c 字符串获取长度是逐个读取字符计算长度，时间复杂度为: O(N)
- SDS 是通过
len来获取字符串长度，时间复杂度为: O(1)
API 安全
- c 字符串不会检查内存空间是否足够，当拼接字符串时，有可能会出现缓冲区溢出问题
- SDS 则会根据
free来判断空间是否足够，如果内存空间不足，则会申请内存空间，因此不会有缓冲区溢出问题
二进制安全
- c 字符串是根据空字符
\0来判断字符串是否结束，因此字符串中间不能有空字符， 只能用来保存文本内容，无法保存二进制数据 - SDS 是通过
len来判断字符串是否结束，因此既可以保存文本内容，又可以保存二进制数据
内存分配
- c 字符串每次修改内容时都需要进行重新的内存分配
- SDS 则是根据
free判断空间是否足够，如果不足，重新内配， 并且当修改后的len< 1M 时， 额外多分配len的长度， 此时free=len； 当缩短 SDS 字符串内容时， 并不会立即释放空间, 而是通过将free变大，记录剩余空间，以减少之后的再分配。（通过惰性释放避免内存浪费问题）
字典
内部实现
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;
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;
/* This is our hash table structure. Every dictionary has two of this as we
* implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
int iterators; /* number of iterators currently running */
} dict;
结构示意图：
原理讲解
字段
ht 字段
ht 是一个两个项的数组，其中 ht[0] 用于存放哈希表，ht[1] 在哈希重排时使用
rehashidx 字段
当 rehashidx == -1 时，表示当前不是在 rehash, 用于表示在进行 rehash 操作时，进行到了哪一步。
如何操作数据
假设现在需要添加一个数据 <k, v>, 先需要计算哈希值:
hash = dict->type->hashFunction(k);
然后根据 sizemask 求出索引值:
index = hash & dict->ht[x]->sizemask;
// x 表示实际存放哈希表的索引， 一般为 0 ，当在进行 rehash 时为 1
这样就可以将 <k, v> 存储在 dict->ht[x]->table[index] 中， 如果 table[index] 中已经有数据， 则新添加的数据放在链表表头. (这是因为 table[index] 中的链表时一个单链表，没有指向链表尾部的指针，添加到表头更快)
rehash 过程
当哈希表保存的数据太多或太少时，需要对哈希表进行相应的扩容或者收缩。
如果进行扩容操作，那么 ht[1] 的大小为第一个不小于 ht[0].used * 2 的 2^n (n 为正整数)， 如: used = 5, ht[0].used * 2 = 10 < 2^4 = 16, 所以 ht[1] 的大小为：16 ·
然后就可以将 ht[0] 的数据哈希到 ht[1] 中， 当 ht[0] 中的数据全部哈希到 ht[1] 后， 释放 ht[0], 将 ht[1] 变 ht[0]
扩展的触发条件
- 在没有执行
BGSAVE或BGREWRITEAOF时，哈希表的负载因子>= 1 - 在执行
BGSAVE或BGREWRITEAOF时，哈希表的负载因子>= 5
负载因子的计算：
load_factor = ht[0].used / ht[0].size
在进行
BGSAVE或BGREWRITEAOF时，提高负载因子是为了避免扩容，避免不必要的内存写入
收缩的触发条件
负载因子 < 0.1
渐进式哈希
在扩容或者收缩时，需要将 ht[0] 全部哈希到 ht[1], 如果一次性哈希， 当数据足够多时，会存在效率问题。因此 redis 通过逐步哈希的方式，其具体过程如下：
- 为
ht[1]分配空间 - 设置
rehashidx = 0 - 新添加的数据不再加入到
ht[0], 而是加入到ht[1]中，保证ht[0]不会增加数据 - 将
ht[0]->table[rehashidx]的数据全部哈希到ht[1]中 rehashidx++- 随着不断的执行，
ht[0]的数据哈希到了ht[1], 这是可以 设置rehashidx = 1， 表明rehash结束，释放ht[0],ht[1]设置为ht[0]
在 rehash 的过程中， 删除，查找，更新会同时在 ht[0], ht[1] 中进行， 但是添加只会在 ht[1] 中。
