redis 原理（未完）

1.动态字符串

   sds结构：内有三个字段，len,free与buf[],前两者市记录存储字符串的长度与未使用的长度。后者则是用来储存字符串。

   structsdshdr{

          intlen; //字符串长度不包含最后的空字符\0（C的为n+1）

          intfree;//空间的预留可以避免与C一样频繁分配内存

          charbuf[];//最后以/0结尾

   }

   结构体中定义长度，可以避免需要获取长度时遍历整个字符串。同时可以根据len决定长度，避免特殊空字符串（\0）造成的错误识别。

   虽然使用长度作为定义，但是还是会多分配一个字节保存空字符串。这是为了兼容C，从而兼容相关头文件。

2.链表

   链表结构：内置三个字段*prev ,*next,*value.

   typedefstruct listNode{

          structlistNode *prev;

          structlistNode *next;

          void*value;

   }listNode;

   list链表：

   typedefstruct list{

          listNode*head;//头节点

          listNode*tail;//尾节点

          unsignedlong len;//链表长度

          void*(*dup)(void *ptr);//节点复制函数

          void(*free)(void *pre);//节点释放函数

          int(*match)(void *pre,void *key);//节点对比函数

   }list;

3.字典

   在字典中，一个键key对应一个值value.且每一个键都是唯一的。

  3.1字典实现-哈希表

image

   Typedefstruct dictht{

          dictEntry**table;//哈希数组

          unsignedlong size;//哈希大小

          unsignedlong sizemask;//哈希大小掩码 用于计算索引 值为size-1

          unsignedlong used;//已有节点数

   }dictht;

   哈希数组节点表示：

    Typedef struct dictEntry{

          Void*key;

          Union{

                 Void*val;      

                 Unit64_tu64;

                 Int64_ts64;

          }v;//解决不同类型的字段。

          StructdictEntry *next;//指向哈希值相同的哈希表节点，将相同哈希值的节点串连起

//来，解决键冲突问题。

   }dictEnry;