SDS 链表

时间:2023-11-26 14:11:08

sds定义

struct sdshdr{

int len

int free

char buf[]

}

SDS 链表

SDS 链表

sds和c语言类似,仍然把字符串的末尾加上一个‘、0’,但是不会计入总长度,也就是不会对len造成影响,属于默认的,对使用者来说是透明的

根据这个数据的定义,我们可以判断出sds和c字符串的区别

(1)获取len长度的时间复杂度不一样,一个是O(N),一个是O(1),

(2)杜绝缓冲区的溢出:对于c字符串,由于不会记录长度,所有可以造成溢出,比如我们说的strcat之类的,必须事先由使用者malloc出足够的空间,但是sds在追加的时候,会自动检查长度,如果长度不够的话,会自动扩展空间,类似vector,这样就杜绝了缓冲区溢出的情况

(3)减少了字符穿改变时候重新分配内部的次数,比如我们在c中,如果加长一个字符串或则缩短一个字符串的话,我们都需要重新分配空间但是sds对字符串的修改做了一些优化

sds字符串的冲分配优化

(1)空间预分配:如果增加字符串的时候,我们的空间不够用了,我们会重新分配,如果sds的长度小雨1MB,如果字符串的长度为len的话,我们我们将len=free=len,buf的长度为2×len+1

如果字符串大于1MB,那么我们的free设置为1mb,则buf=len+1mb+1

综上所述,我们可以减少redis字符串增加长度的分配次数

(2惰性空间释放):如果需要缩短字符串的话,我们不会将空间释放,而是将这些记录到free中,这样的话以以后可以使用

二进制安全:

c字符串只能保存文本,但是sds可以保存视频图片之类的二进制数据,不会因为遇到终止符而停止传输,因为sds是通过len的长度判断终止的,不是针对‘\0’

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;s
上面就是链表的定义,
根据定义我们可以总结几个特点
1:双端:自带后置和前置节点,这样或者前后node的时间复杂度就是1,大大的降低了时间复杂度
2:无环:第一个节点的前置和最后一个节点的后置指向的都是NULL,所以他不是一个环
3:带有表头指针和表尾指针(见定义)
4:带len:和sds类似,获得长度的时间复杂度为1
5:多态:节点通过上面三个void×类型的处理节点,复制,释放,对比,可以处理多种类型
typedef struct listNode {

    // 前置节点
struct listNode *prev; // 后置节点
struct listNode *next; // 节点的值
void *value; } listNode;
链表的应用地方很多,比如列表键的底层实现就是链表,
链表的节点数据结构定义就是上面的定义,每一个节点都有一个前置后置指针,