簡單動態(tài)字符串（simple dynamic string）SDS

Redis 沒有直接使用C語言傳統(tǒng)的字符串表示，而是自己構建了一種名為簡單動態(tài)字符串（simple dynamic string SDS）的抽象類型，并將SDS用作Redis 的默認字符串表示：

10.143.128.165:6379> SET msg "hello world"
OK

設置一個key= msg，value = hello world 的新鍵值對，

鍵（key）是一個字符串對象，對象的底層實現(xiàn)是一個保存著字符串“msg” 的SDS；

值（value）也是一個字符串對象，對象的底層實現(xiàn)是一個保存著字符串“hello world” 的SDS

SDS除了用來保存字符串以外，SDS還被用作緩沖區(qū)（buffer）AOF模塊中的 AOF緩沖區(qū)。

SDS 的定義

Redis 中定義動態(tài)字符串的結(jié)構：

/*  
 * 保存字符串對象的結(jié)構  
 */  
struct sdshdr {       
    int len;// buf 中已占用空間的長度      
    int free;// buf 中剩余可用空間的長度    
    char buf[];// 數(shù)據(jù)空間  
};

1、len 變量，用于記錄buf 中已經(jīng)使用的空間長度（這里指出Redis 的長度為5）

2、free 變量，用于記錄buf 中還空余的空間（ 初次分配空間，一般沒有空余，在對字符串修改的時候，會有剩余空間出現(xiàn)）

3、buf 字符數(shù)組，用于記錄我們的字符串（記錄Redis）

SDS 與 C 字符串的區(qū)別

1 獲取字符串長度（SDS O（1）/C 字符串 O(n)）

傳統(tǒng)的C 字符串 使用長度為N+1 的字符串數(shù)組來表示長度為N 的字符串，所以為了獲取一個長度為C字符串的長度，必須遍歷整個字符串。

SDS 的數(shù)據(jù)結(jié)構中，有專門用于保存字符串長度的變量，可以通過獲取len 屬性的值，直接知道字符串長度。

2 杜絕緩沖區(qū)溢出

C 字符串 不記錄字符串長度，除了獲取的時候復雜度高以外，還容易導致緩沖區(qū)溢出。

假設程序中有兩個在內(nèi)存中緊鄰著的 字符串 s1 和 s2，其中s1 保存了字符串“redis”，二s2 則保存了字符串“MongoDb”：

如果我們現(xiàn)在將s1 的內(nèi)容修改為 redis cluster，但是又忘了重新為s1 分配足夠的空間，這時候就會出現(xiàn)以下問題：

原本s2 中的內(nèi)容已經(jīng)被S1的內(nèi)容給占領了，s2 現(xiàn)在為 cluster，而不是“Mongodb”。

當需要對一個SDS 進行修改的時候，redis 會在執(zhí)行拼接操作之前，預先檢查給定SDS 空間是否足夠，如果不夠，會先拓展SDS 的空間，然后再執(zhí)行拼接操作：

3 減少修改字符串時帶來的內(nèi)存重分配次數(shù)

C語言字符串在進行字符串的擴充和收縮的時候，都會面臨著內(nèi)存空間的重新分配問題。

1. 字符串拼接會產(chǎn)生字符串的內(nèi)存空間的擴充，在拼接的過程中，原來的字符串的大小很可能小于拼接后的字符串的大小，那么這樣的話，就會導致一旦忘記申請分配空間，就會導致內(nèi)存的溢出。

2. 字符串在進行收縮的時候，內(nèi)存空間會相應的收縮，而如果在進行字符串的切割的時候，沒有對內(nèi)存的空間進行一個重新分配，那么這部分多出來的空間就成為了內(nèi)存泄露。

我們需要對下面的SDS進行拓展，則需要進行空間的拓展，這時候redis 會將SDS的長度修改為13字節(jié)，并且將未使用空間同樣修改為1字節(jié)

因為在上一次修改字符串的時候已經(jīng)拓展了空間，再次進行修改字符串的時候會發(fā)現(xiàn)空間足夠使用，因此無須進行空間拓展

通過這種預分配策略，SDS將連續(xù)增長N次字符串所需的內(nèi)存重分配次數(shù)從必定N次降低為最多N次

4 惰性空間釋放

SDS 的free 屬性，是用于記錄空余空間的。除了在拓展字符串的時候會使用到free 來進行記錄空余空間以外，在對字符串進行收縮的時候，也可以使用free 屬性來進行記錄剩余空間，避免下次對字符串進行再次修改的時候，需要對字符串的空間進行拓展。

SDS 提供了相應的API，可以在有需要的時候，自行釋放SDS 的空余空間。

通過惰性空間釋放，SDS 避免了縮短字符串時所需的內(nèi)存重分配操作，并未將來可能有的增長操作提供了優(yōu)化

5 二進制安全

C 字符串中的字符必須符合某種編碼，并且除了字符串的末尾之外，字符串里面不能包含空字符，否則最先被程序讀入的空字符將被誤認為是字符串結(jié)尾，這些限制使得C字符串只能保存文本數(shù)據(jù)，而不能保存想圖片，音頻，視頻，壓縮文件這樣的二進制數(shù)據(jù)。

Redis 不是靠空字符來判斷字符串的結(jié)束的，而是通過len這個屬性。

6 兼容部分C字符串函數(shù)

雖然SDS 的API 都是二進制安全的，但一樣遵循C字符串 以空字符串結(jié)尾的慣例。

========================================================================

鏈表

鏈表提供了高效的節(jié)點重排能力，以及順序性的節(jié)點訪問方式，并且可以通過增刪節(jié)點來靈活地調(diào)整鏈表的長度。

Redis 中 列表鍵的底層實現(xiàn)之一就是鏈表。當一個列表鍵包含了數(shù)量較多的元素，又或者列表中包含的元素都是比較長的字符串時，Redis 就會使用鏈表作為列表鍵的底層實現(xiàn)。

每個鏈表節(jié)點使用一個  listNode結(jié)構表示：

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

多個鏈表節(jié)點組成的雙端鏈表：

list：

typedef struct list{   
    listNode  * head;//表頭節(jié)點  
    listNode  * tail;//表尾節(jié)點   
    unsigned long len;//鏈表長度   
    void *(*dup) (void *ptr);//節(jié)點值復制函數(shù) 
    void (*free) (void *ptr);//節(jié)點值釋放函數(shù) 
    int (*match)(void *ptr, void *key);//節(jié)點值對比函數(shù)
}

鏈表的特性

• 雙端：鏈表節(jié)點帶有prev 和next 指針，獲取某個節(jié)點的前置節(jié)點和后置節(jié)點的時間復雜度都是O（N）
• 無環(huán)：表頭節(jié)點的 prev 指針和表尾節(jié)點的next 都指向NULL，對立案表的訪問時以NULL為截止
• 表頭和表尾：因為鏈表帶有head指針和tail 指針，獲取鏈表頭結(jié)點和尾節(jié)點的時間復雜度為O(1)
• 長度計數(shù)器：鏈表中存有記錄鏈表長度的屬性 len
• 多態(tài)：鏈表節(jié)點使用 void* 指針來保存節(jié)點值，并且可以通過list 結(jié)構的dup 、 free、 match三個屬性為節(jié)點值設置類型特定函數(shù)。

========================================================================

字典

字典，又稱為符號表（symbol table）、關聯(lián)數(shù)組（associative array）或映射（map），是一種用于保存鍵值對的抽象數(shù)據(jù)結(jié)構?！?/p>

在字典中，一個鍵（key）可以和一個值（value）進行關聯(lián)，字典中的每個鍵都是獨一無二的。在C語言中，并沒有這種數(shù)據(jù)結(jié)構，但是 Redis 中構建了自己的字典實現(xiàn)。

10.143.128.165:6379> SET msg "hello world"
OK

字典的定義

1 哈希表

Redis 字典所使用的哈希表由 dict.h/dictht 結(jié)構定義：

typedef struct dictht {  
   dictEntry **table; //哈希表數(shù)組  
   unsigned long size;//哈希表大小   
   unsigned long sizemask;//哈希表大小掩碼，用于計算索引值  
   unsigned long used;//該哈希表已有節(jié)點的數(shù)量
}

一個空的字典的結(jié)構圖如下：

在結(jié)構中存有指向dictEntry 數(shù)組的指針，而我們用來存儲數(shù)據(jù)的空間就是 dictEntry

 2. 哈希表節(jié)點（ dictEntry ）

typeof struct dictEntry{
   void *key; //鍵
   union{   //值
      void *val;
      uint64_tu64;
      int64_ts64;
   }
   struct dictEntry *next;
}

在數(shù)據(jù)結(jié)構中，key 是唯一的，但是存入里面的key 并不是直接的字符串，而是一個hash 值，通過hash 算法，將字符串轉(zhuǎn)換成對應的hash 值，然后在dictEntry 中找到對應的位置。

如果出現(xiàn)hash 值相同的情況，Redis 采用了 鏈地址法：

當k1 和k0 的hash 值相同時，將k1中的next 指向k0 形成一個鏈表。

3 字典

typedef struct dict {  
    dictType *type;  // 類型特定函數(shù)    
    void *privedata; // 私有數(shù)據(jù)   
    dictht  ht[2];  // 哈希表  
    in trehashidx; // rehash 索引
}

type 屬性 和privdata 屬性是針對不同類型的鍵值對，為創(chuàng)建多態(tài)字典而設置的。

ht 屬性是一個包含兩個項（兩個哈希表）的數(shù)組

普通狀態(tài)下的字典：

解決哈希沖突

在插入一條新的數(shù)據(jù)時，會進行哈希值的計算，如果出現(xiàn)了hash值相同的情況，Redis 中采用了連地址法（separate chaining）來解決鍵沖突。每個哈希表節(jié)點都有一個next 指針，多個哈希表節(jié)點可以使用next 構成一個單向鏈表，被分配到同一個索引上的多個節(jié)點可以使用這個單向鏈表連接起來解決hash值沖突的問題。

 現(xiàn)在要插入k2，通過hash 算法計算到k2 的hash 值為2，即需要將k2 插入到dictEntry[2]中：