redis设计与实现

字典

哈希表dict.h/dictht 结构

哈希节点dictEntry 结构

字典 dict.h/dict 结构

dictType 结构

哈希算法

# 使用字典设置的哈希函数，计算键 key 的哈希值hash = dict->type->hashFunction(key);# 使用哈希表的 sizemask 属性和哈希值，计算出索引值# 根据情况不同， ht[x] 可以是 ht[0] 或者 ht[1]index = hash & dict->ht[x].sizemask;

跳跃表

redis.h/zskiplistNode 结构

zskiplist 结构

redis设计与实现

动态字符串

sds.h/sdshdr 结构

与C语言字符串相比优势

常数复杂度获取字符串长度

杜绝缓冲区溢出

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

空间预分配

惰性空间释放

链表

adlist.h/listNode

adlist.h/list

特性

双端

无环

带表头指针和表尾指针

带链表长度计数器

多态

整数集合

每个 intset.h/intset 结构表示一个整数集合