Redis中字符串与字典如何实现？
本文和大家分享的主要是redis中字符串与字典相关内容，一起来看看吧，希望对大家学习redis有所帮助。
简单动态字符串 （SDS）
内部实现
struct sdshdr {
len int; // 所保存的字符串长度
free int; // 未使用的字节长度
char buf[]; // 字节数组，用于保存字符串
}
c 字符串通常是以空字符 '\\0' 结尾，所以一个 SDS 的长度为： len + free + 1
与 c 字符串的区别
获取字符串长度
． 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;
结构示意图：
redis-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]
扩展的触发条件
1. 在没有执行 BGSAVE 或 BGREWRITEAOF 时，哈希表的负载因子 >= 1
2. 在执行 BGSAVE 或 BGREWRITEAOF 时，哈希表的负载因子 >= 5
负载因子的计算：
load_factor = ht[0].used / ht[0].size
在进行 BGSAVE 或 BGREWRITEAOF 时，提高负载因子是为了避免扩容，避免不必要的内存写入
收缩的触发条件
负载因子 < 0.1
渐进式哈希
在扩容或者收缩时，需要将 ht[0] 全部哈希到 ht[1] , 如果一次性哈希， 当数据足够多时，会存在效率问题。因此 redis 通过逐步哈希的方式，其具体过程如下：
1. 为 ht[1] 分配空间
2. 设置 rehashidx = 0
3. 新添加的数据不再加入到 ht[0] , 而是加入到 ht[1] 中，保证 ht[0] 不会增加数据
4. 将 ht[0]->table[rehashidx] 的数据全部哈希到 ht[1] 中
5. rehashidx++
6. 随着不断的执行， ht[0] 的数据哈希到了 ht[1] , 这是可以 设置 rehashidx = 1 ， 表明 rehash 结束，释放 ht[0] , ht[1] 设置为 ht[0]
在 rehash 的过程中， 删除，查找，更新会同时在 ht[0] , ht[1] 中进行， 但是添加只会在 ht[1] 中。
来源：简书