1 简单动态字符串实现

redis实现了SDS（simple dynamic string）功能，可以在支持C语言的字符串功能的同时，进行进一步的性能和安全性提升来满足数据库的需求。
数据结构如下：

struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* 使用长度*/
    uint64_t alloc; /* 字符串总分配长度 */
    unsigned char flags; /*前3位用于类型表示*/
    char buf[];//字节数组
};

对比传统C语言字符串实现，SDS实现优势所在如下：

接口实现：

//创建包含init字符串的sds
sds sdsnew(const char *init);
//创建空的sds
sds sdsempty(void);
//拷贝一个sds
sds sdsdup(const sds s);
//释放sds
void sdsfree(sds s);
//追加
sds sdscat(sds s, const char *t);
//拷贝
sds sdscpy(sds s, const char *t);
//用空字符扩展到len
sds sdsgrowzero(sds s, size_t len);
//移除字符串出现过的字符
sds sdstrim(sds s, const char *cset);
//比较
int sdscmp(const sds s1, const sds s2);

2 链表实现

链表采用的是常规的双向链表表示方式，链表结点数据结构如下：

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

链表示意图：

链表设计的巧妙之处在于双端链表的设计采用的函数指针的方式，利用初始化注册回调函数的方式实现，链表的拷贝，释放和匹配操作。这样用户可以灵活的根据自身的数据类型进行相应的处理。

typedef struct list {
    listNode *head;							//头结点
    listNode *tail;							//尾结点				
    void *(*dup)(void *ptr);				//复制函数	
    void (*free)(void *ptr);				//释放函数
    int (*match)(void *ptr, void *key);		//匹配函数
    unsigned long len;						//链表元素个数
} list;

实现接口：

#define listSetDupMethod(l,m) ((l)->dup = (m))     //设置复制函数
#define listSetFreeMethod(l,m) ((l)->free = (m))	//设置释放函数
#define listSetMatchMethod(l,m) ((l)->match = (m))	//设置匹配函数
list *listCreate(void);								//创建空链表
void listRelease(list *list);						//重置
void listEmpty(list *list);							//链表清空
list *listAddNodeHead(list *list, void *value);		//头插
list *listAddNodeTail(list *list, void *value);		//尾插
list *listInsertNode(list *list, listNode *old_node, void *value, int after); //固定位置插入
void listDelNode(list *list, listNode *node);		//删除结点
listIter *listGetIterator(list *list, int direction);//获取迭代器
listNode *listNext(listIter *iter);					//获取下一个结点
void listReleaseIterator(listIter *iter);			//释放迭代器
list *listDup(list *orig);							//list复制
listNode *listSearchKey(list *list, void *key);   //返回指定结点
listNode *listIndex(list *list, long index);	  //获取索引结点
void listRewind(list *list, listIter *li);		  //设置正向迭代器
void listRewindTail(list *list, listIter *li);	　//设置反向迭代器
void listRotateTailToHead(list *list);            //删除尾元素加入头部
void listRotateHeadToTail(list *list);			  //删除头元素加入尾部
void listJoin(list *l, list *o);					//追加

3 字典

3.1 数据结构

redis字典底层采用哈希表实现，具体数据结构定义如下：

//哈希表
typedef struct dictht {
	//哈希表数组
    dictEntry **table;
    //哈希表大小
    unsigned long size;
    //哈希表大小掩码
    unsigned long sizemask;
    //哈希表已有结点数量
    unsigned long used;
} dictht;

哈希表示意图：

哈希表结点，具体定义如下所示：

//表元素节点
typedef struct dictEntry {
    void *key;		  //键
    union {
        void *val;    //值
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; //结点下一个哈希表结点
} dictEntry;

哈希表如何解决键冲突问题：
主要是利用哈希表结点将相同键的利用链表串联在一起。

字典结构：

struct dict {
    dictType *type; //字典类型，用于存放字典操作函数

    dictEntry **ht_table[2];  //用于存放字典表结构，两张表ht0，ht1
    unsigned long ht_used[2];//对应哈希表已经占用的元素索引个数

    long rehashidx; //重新散列标志，-1表示无需重新散列，0表示开始散列，依次递增

    /* Keep small vars at end for optimal (minimal) struct padding */
    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
    signed char ht_size_exp[2]; //对应哈希表的元素个数/2
};

//字典类型,字典针对不同类型的操作函数，做到不同类型的多态
typedef struct dictType {
    uint64_t (*hashFunction)(const void *key);//哈希函数
    void *(*keyDup)(dict *d, const void *key);//键复制
    void *(*valDup)(dict *d, const void *obj);//值复制
    int (*keyCompare)(dict *d, const void *key1, const void *key2);//键比较
    void (*keyDestructor)(dict *d, void *key);//键析构
    void (*valDestructor)(dict *d, void *obj);//值析构
    int (*expandAllowed)(size_t moreMem, double usedRatio);
    /* Allow a dictEntry to carry extra caller-defined metadata.  The
     * extra memory is initialized to 0 when a dictEntry is allocated. */
    size_t (*dictEntryMetadataBytes)(dict *d);
} dictType;

3.2 字典添加及哈希算法

在数据添加到字典基本涵盖了字典的核心功能，包括获取字典索引的流程和扩展字典哈希表流程。具体如下图所示。
需要注意的点：

• 扩展字典时机，一般是首次分配和当已使用元素等于表长时；
• 扩展字典大小，一般是used两倍，同时需要修正为2^n；
• 计算索引时，如果是正在rehash，需要计算ht[1]中的索引；
• 字典添加操作，如果正在rehash，需要单步更新一个哈希表元素；

3.3 重新散列（rehash）

重新散列主要目的是由于旧表无法满足要求需要对表进行扩展或者收缩。重新散列原理很简单就是将旧表的元素，按照新表的长度索引进行散列拷贝旧表元素到新表的过程。具体如下图所示：
需要注意点：

• 重新散列过程，这是一个渐进式的过程，并不是一步到位，每次进行增，删，改，查过程如果正在进行散列，将会进行一次单步散列；
• 渐进式散列好处，防止数据库庞大的情况下，重新散列而导致服务器短时间内服务响应的问题；
• rehash索引含义，当散列完成是值是-1，其他情况下是当前正在拷贝的ht[0]表的索引位置；
• rehash某个索引可能对应多个值，需要拷贝整个链表；
• rehash过程，将ht[0]拷贝到ht[1]表,ht[0]表释放，然后ht[1]重新指向ht[0]，最后ht[1]重置指向空。

实现接口：

dict *dictCreate(dictType *type, void *privDataPtr);  	//创建字典
int dictExpand(dict *d, unsigned long size);			//扩展字典
int dictAdd(dict *d, void *key, void *val);				//添加元素
int dictReplace(dict *d, void *key, void *val);			//替换元素
int dictDelete(dict *d, const void *key);				//删除元素
void dictRelease(dict *d);								//释放字典
dictEntry * dictFind(dict *d, const void *key);			//查找元素
void *dictFetchValue(dict *d, const void *key);			//返回键对应值