目录前言1. 简单动态字符串1.1 SDS的定义1.2 空间预分配与惰性空间释放1.3 SDS的api2. 链表2.1 链表与节点的定义2.2 链表的API3. 字典3.1 哈希表与哈希节点3.2 字典3.3 哈希算法3.4 解决键冲突3
参考资料:《Redis设计与实现 第二版》;
本篇笔记按照书里的脉络,将知识点分为四个部分。其中第一部分数据结构与对象分为上中下篇,上篇包括:SDS、链表和字典;中篇包括跳跃表、整数集合和压缩列表;下篇为对象;
sds.h/sdshdr
结构:struct sdshdr {
//记录buf数组中已使用字节数量
//等于SDS所保存字符串长度
int len;
//记录buf数组中未使用字节数量
int free;
//字节数组,保存字符串
char buf[];
}
);
)free
,SDS实现空间预分配和惰性空间释放:
函数 | 作用 | 时间复杂度 |
---|---|---|
sdsnew | 创建一个包含给定C字符串的SDS | O(N),N为给定C字符串的长度 |
sdsempty | 创建一个不包含任何内容的空SDS | O(1) |
sdsfree | 释放给定的SDS | O(N),N为被释放SDS的长度 |
sdslen | 返回SDS的已使用空间字节数 | O(1),通过读取SDS的len属性获得 |
sdsavail | 返回SDS的未使用空间字节数 | O(1),通过读取free属性获得 |
sdsdup | 创建一个给定SDS的副本(copy) | O(N),N为给定SDS的长度 |
sdsclear | 清空SDS保存的字符串内容 | O(1),因为惰性空间释放策略 |
sdscat | 将给定C字符串拼接到SDS字符串的末尾 | O(N),N为被拼接字符串的长度 |
sdscatsds | 将给定SDS字符串拼接到另一个SDS字符串的末尾 | O(N),N为被拼接SDS字符串的长度 |
sdscpy | 将给定的C字符串复制到SDS里面,覆盖原有字符串 | O(N),N为被复制的C字符串长度 |
sdsgrowzero | 用空字符串将SDS扩展至给定长度 | O(N),N为扩展新增的字节数 |
sdsrange | 保留SDS给定区间内的数据,不在区间内的数据会被覆盖或清除 | O(N),N为扩展新增的字节数 |
sdstrim | 接受一个SDS和一个C字符串作为参数,从SDS中移除所有在C字符串出现过的字符 | O(N2),N为给定C字符串的长度 |
sdscmp | 对比两个SDS字符串是否相同 | O(N),N为两个SDS中较短的那个SDS的长度 |
链表节点的定义与实现在adlist.h/listnode
结构里;
typedef struct listNode {
//前置节点
struct listNode *prev;
//后置节点
struct listNode *next;
//节点的值
void *value;
} listNode;
链表的定义在adlist.h/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);
} list;
函数 | 作用 | 时间复杂度 |
---|---|---|
listSetDupMethod | 将给定的函数设置为链表的节点值复制函数 | O(1),复制函数可以通过链表的dup属性直接获得 |
listGetDupMethod | 返回链表当前正在使用的节点值复制函数 | O(1) |
listSetFreeMethod | 将给定的函数设置为链表的节点值释放函数 | O(1),释放函数可以通过链表的free属性直接获得 |
listGetFree | 返回链表当前正在使用的节点值释放函数 | O(1) |
listSetMatchMethod | 将给定的函数设置为链表的节点值对比函数 | O(1),对比函数可以通过链表的match属性直接获得 |
listGetMatchMethod | 返回链表当前正在使用的节点值对比函数 | O(1) |
listLength | 返回链表的长度 | O(1),链表长度可以通过链表的len属性直接获得 |
listFirst | 返回链表的表头节点 | O(1),表头节点可以通过链表的head属性直接获得 |
listLast | 返回链表的表尾节点 | O(1),表尾节点可以通过链表的tail属性直接获得 |
listPrevNode | 返回给定节点的前置节点 | O(1),前置节点可以通过节点的prev属性直接获得 |
listNextNode | 返回给定节点的后置节点 | O(1),前置节点可以通过节点的next属性直接获得 |
listNodeValue | 返回给定节点的目前正在保存的值 | O(1),节点值可以通过节点的value属性直接获得 |
listCreate | 创建一个不包含任何节点的新链表 | O(1) |
listAddNodeHead | 将一个包含给定值的新节点添加到给定链表的表头 | O(1) |
listAddNodeTail | 将一个包含给定值的新节点添加到给定链表的表尾 | O(1) |
listInsertNode | 将一个包含给定值的新节点添加到给定节点的之前或之后 | O(1) |
listSearchKey | 查找并返回链表中包含给定值的节点 | O(N),N为链表长度 |
listIndex | 返回链表在给定索引上的节点 | O(N),N为链表长度 |
listDelNode | 从链表中删除给定节点 | O(N),N为链表长度 |
listRotate | 将链表的表尾节点弹出,然后将被弹出的节点插入到链表的表头,成为新的表头节点 | O(1) |
listDup | 复制一个给定链表的副本 | O(N),N为链表长度 |
listRelease | 释放给定链表,以及链表中的所有节点 | O(N),N为链表长度 |
字典所使用的哈希表的定义,在dict.h/dictht
结构中:
typedef struct dictht {
//哈希表数组
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩码,用于计算索引值
//总是等于size-1
unsigned long sizemask;
//该哈希表已有节点的数量
unsigned long used;
} dictht;
table
是一个数组,数组的每个元素都是指向dict.h/dictEntry
结构的指针;哈希表节点的定义,在dict.h/dictEntry
结构;
typedef struct dictEntry {
//键
void *key;
//值
uNIOn{
void *val;
uint64_t u64;
int64_t s64;
} v;
//指向下个哈希表节点,形成链表
struct dictEntry *next;
} dictEntry;
字典的定义,在dict.h/dict
结构:
typedef struct dict {
//类型特定函数
dictType *type;
//私有数据
void *privdata;
//哈希表
dictht ht[2];
//rehash 索引
//当 rehash 不在进行时,值为-1
int trehashidx;
} dict;
Redis计算哈希值与索引值的方法:
# 使用字典设置哈希函数,计算key的哈希值
hash = dict -> type -> hashFunction(key)
# 使用哈希表的sizemask属性和哈希值,计算索引值
# 根据情况不同,ht[x]可以是ht[0]或者ht[1]
index = hash & dict -> ht[x].sizemask
当字典被用作数据库底层实现,或哈希键底层实现时,Redis使用MurmurHash2
算法计算键的哈希值;
dictEntry
哈希节点里有个next属性,可以用其将索引值相同的节点连成链表;
ht[1]
分配空间,若扩展,则ht[1].size
为第一个大于等于ht[0].used*2
的 2n。若收缩,则ht[1].size
为第一个大于等于ht[0].used
的 2n;ht[0]
中的所有键值对rehash到ht[1]
上;ht[0]
,将ht[1]
设置为ht[0]
,创建一个空白哈希表ht[1]
;load_factor = ht[0].used / ht[0].size
;BGSAVE
和BGREWRITEAOF
命令,并且负载因子大于等于1;BGSAVE
和BGREWRITEAOF
命令,并且负载因子大于等于5;
ht[1]
分配空间;rehashidx
设置为0,表示rehash正式开始;rehashidx++
;ht[0]
中的所有键值对rehash到ht[1]
后,rehashidx
设置为 -1;ht[0]
,再查ht[1]
;ht[1]
新增,保证ht[0]
只减不增;函数 | 作用 | 时间复杂度 |
---|---|---|
dictCreate | 创建一个新字典 | O(1) |
dictAdd | 将给定的键值对添加到字典里 | O(1) |
dictReplace | 将给定键值对添加到字典里,如果键已存在,则会用新值替换旧值 | O(1) |
dictFetchValue | 返回给定键的值 | O(1) |
dictGetRandomKey | 从字典中随机返回一个键值对 | O(1) |
dictDelete | 从字典中删除给定键所对应的键值对 | O(1) |
dictRelease | 释放字典,以及字典包含的键值对 | O(N),N为字典包含的键值对数量 |
--结束END--
本文标题: Redis | 第一部分:数据结构与对象 上篇《Redis设计与实现》
本文链接: https://www.lsjlt.com/news/8926.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-05-15
2024-05-15
2024-05-15
2024-05-15
2024-05-15
2024-05-15
2024-05-15
2024-05-15
2024-05-15
2024-05-15
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0