Redis數據結構—鏈表與字典的結構
Redis數據結構—鏈表與字典的結構
大家好，我是白澤。今天我們來聊一聊Redis中的鏈表與字典的結構
鏈表
關於鏈表的基礎概念其實你在學習Redis之前一定積累了不少，所以本文將默認你已經掌握了鏈表相關的基礎知識，而Redis的鏈表其實也就是普通的鏈表~
因為Redis是使用C語言編寫的，因此Redis的數據結構的定義都是使用C語法定義的，你不需要完全理解下方C語言聲明結構體的語法，但我認為依靠大家的Java知識也能理解這就像是在Java中定義了一個鏈表對象
Redis鏈表節點的結構
typedef struct listNode {
struct listNode *prev; //指向前一個鏈表節點
struct listNode *next; //指向後一個鏈表節點
void *value; //當前節點的值(可以按需設定不同數據類型的value)
} listNode;
很明顯，當每一個節點內記錄了前後兩個節點位置之後，鏈表節點之間就能夠彼此前後相連，組成雙向通行車道（可以雙向遍歷）
Redis鏈表的表示
上面講解了Redis的鏈表的節點表示，並由此引申了一下可以藉此構建Redis雙端鏈表，而事實上，對於每一個存在的雙端鏈表，Redis使用一個list結構來表示
typedef struct list {
listNode *head; //表頭節點
listNode *tail; //表尾節點
unsigned long len; //鏈表所包含的節點的數量
void *(*dup)(void *ptr); //節點複製函數
void (*free)(void *ptr); //節點釋放函數
void (*match)(void *ptr, void *key);//節點值對比函數
} list;
很明顯，你看到三個好像是返回值為void的函數，但是看不懂C語法，沒關係，傳統後端功夫，自然是點到為止
Redis鏈表用在哪
我不想現在就告訴你，鏈表被廣泛用於實現Redis的各種功能，比如列表鍵、發佈於訂閱、慢查詢、監視器等（這太空洞了，除了讓你聽一遍這幾個辭彙，對你沒有任何幫助），等我們後面講到這幾部分的時候，白澤再結合鏈表和你細說~
字典
和鏈表一樣，Redis所使用的C語言並沒有內置字典這種數據結構，因此Redis構建了自己的字典實現。如果你學過數據結構，你會發現Redis的字典事實上就是數據結構中的鄰接表，即使沒學過，往下看就好啦~
Redis字典結構總覽
數組 + 鏈表 ==> 鄰接表，實錘
Redis字典結構分解
還記得嗎，上面我們說Redis鏈表可以用list描述，但是鏈表存儲的數據本質上，是由一系列listNode節點通過前後指針相連存儲的；類似的，Redis字典可以用如下dict描述，但是字典存儲的數據本質上，是由數組 + 若干鏈表組合得到的數據結構存儲的，字典dict結構如下：
typedef struct dict {
dictType *type; //類型特定函數
void *privdata; //私有數據
dictht ht[2]; //哈希表數組
int trehashidx; //rehash索引，當rehash不在進行時，值為-1
} dict;
現在你只需要關注其中的哈希表數組ht[2]，它的數據類型為dictht，因此也是一種複合的數據結構，如下：
typedef struct dictht {
dictEntry **table; //哈希表數組
unsigned long size; //哈希表大小
unsigned long sizemax; //哈希表大小掩碼，用於計算索引值，等於size - 1
unsigned long used; //該哈希表已有節點的數量
} dictht;
哈希表dictht是Redis字典的核心，dictht的四個屬性中，size、sizemax、used都是用於描述table屬性整體狀態。看到這你就明白了，dictht的核心是dictEntry類型的table屬性（再次提醒，如果沒有C語言的基礎，本文中一切你看不懂的語法，包括數據類型，你只需要一眼帶過即可，我們的目的是學習Redis的設計思想）
table屬性是一個數組，數組中的每個元素都是一個指向dictEntry結構的指針，每個dictEntry結構保存一個鍵值對，並含有一個指向下一個dictEntry的指針，結構如下：
typedef struct dictEntry {
void *key; //鍵
union { //值（可以是一個指針，可以是一個uint64_t類型的整數，也可以是一個int64_t類型的整數）
void *val;
uint64_t u64;
int64_t s64;
} v;
struct dictEntry *next;//指向下個哈希表節點，形成鏈表
} dictEntry;
Redis字典的使用
很抱歉，我不太想將一篇文章的篇幅變得太大，因為閱讀大體量的技術文章確實容易令人心生退意，所以本文也點到為止。關於Redis字典的使用部分的知識將在白澤下一篇部落格繼續講解，敬請期待~
