普通数据结构
¶SDS(Simple Dynamic String)
¶结构体
struct sdshdr {
int len;
int free;
char buf[];
}
¶和C字符串区别
¶常数复杂度获取字符串长度
¶杜绝缓冲区溢出
¶减少修改字符串的时候需要重新分配内存的次数
¶二进制安全
¶兼容部分C字符串的函数
¶链表
¶结构体
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
}listNode;
typedef struct list {
listNode *head;
listNode *tail;
unsigned long len;
//操作函数指针
void *(*dup)(void *ptr);
void *(free)(void *ptr);
int (*match)(void *ptr, void *key);
}
¶特点
¶双向链表
¶无环
¶同时持有头尾节点指针
¶保存链表长度
¶多态
¶字典
¶结构体
typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
}
-
table属性是一个数组,数组中的每个元素都是一个指向 dict.h/dictEntry 结构的指针,每个 dictEntry 结构的指针。
-
每个 dictEntry 结构保存着一个键值对。
-
size 属性记录了 table 大小。used 记录了 table 目前已有节点(键值对)数量。
-
sizemask 属性的值总是等于 size-1,这个属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引上(和hashmap中算法类似)。
typedef struct dictEntry {
void *key;
union {
void *val;
unit64_tu64;
int64_ts64;
} v;
struct dictEntry *next;
}
- key属性保存着键值对中的键
- 而v属性则保存着键值对中的值,其中键值对的值可以是一个指针,或者是一个uint64_t整数,又或者是一个int64_t整数。
- next属性是指向另一个哈希表节点的指针,这个指针可以将多个哈希值相同的键值对连接在一次,以此来解决键冲突( collision)的问题。
typedef struct dict {
dictType *type;
void *privdata;
}