一. 概述 字典又稱符號表(symbol table),關聯數組(associative array), 映射(map)，是一種用於保存鍵值對(key-value pair)的抽象數據結構。在字典中，一個key和一個value進行關聯稱為鍵值對。在字典中每個鍵都是唯一的，程式可以在字典中根據鍵查找關 ...
一. 概述
字典又稱符號表(symbol table),關聯數組(associative array), 映射(map)，是一種用於保存鍵值對(key-value pair)的抽象數據結構。在字典中，一個key和一個value進行關聯稱為鍵值對。在字典中每個鍵都是唯一的，程式可以在字典中根據鍵查找關聯的值，或通過鍵更新刪除值等操作。在C語言中並沒有內置這種數據結構，因此Redis構建了自己的字典實現。在Redis中應用廣泛， 對資料庫的增，刪，查，改 都是構建在對字典的操作之上的。
-- 例1 127.0.0.1:6379> set msg "hello world" OK 127.0.0.1:6379> get msg "hello world"
在例1中資料庫創建一個鍵為"msg",值為"hello world"的鍵值對，這個鍵值對就是保存在資料庫的字典裡面。字典還是哈希鍵的底層實現之一，當哈希鍵包含的鍵值對比較多，或者鍵值對中的元素都是比較長的字元串時，Redis就會使用字典作為哈希鍵的底層實現。
-- 例2: website是一個包含3個鍵值對的哈希鍵(也叫哈希表)，哈希鍵(key)為 website，哈希鍵的節點鍵是:資料庫名字，哈希鍵的節點值是:網址 127.0.0.1:6379> hmset website redis "Redis.io" mariadb "mariadb.org" mongodb "mongodb.org" OK 127.0.0.1:6379> hlen website (integer) 3 127.0.0.1:6379> hgetall website 1) "redis" 2) "Redis.io" 3) "mariadb" 4) "mariadb.org" 5) "mongodb" 6) "mongodb.org"
在例2中,website哈希鍵的底層實現就是一個字典。字典中包含了3個鍵值對。字典除了用來實現資料庫和哈希鍵之處，Redis在後續學習中會看到各種不同應用。
二. 字典的實現
一個哈希(鍵)表裡面可以有多個哈希節點(key-vlaue), 每個哈希節點保存了字典的一個鍵值對。下麵三個小節將分別介紹Redis的哈希表，哈希表節點，以及字典的實現。
2.1 哈希表定義
typedef struct dictht { //哈希表數組，C語言中，*號是為了表明該變數為指針，有幾個* 號就相當於是幾級指針，這裡是二級指針，理解為指向指針的指針 dictEntry **table; //哈希表大小 unsigned long size; //哈希表大小掩碼，用於計算索引值 unsigned long sizemask; //該哈希已有節點的數量 unsigned long used; }dictht;
上面table屬性是一個數組，數組中的每個元素都是一個指向dict.h/dictEntry結構的指針，每個dictEntry結構保存著一個鍵值對，size屬性記錄了哈希表的大小，也是table數組的大小，而used屬性則記錄哈希表目前已有節點(鍵值對)的數量。sizemask屬性的值總是等於 size-1(從0開始)，這個屬性和哈希值一起決定一個鍵應該被放到table數組的哪個索引上面。
例如：上面例2中，哈希表叫website, 對應一個dictht 結構，鍵值對table數組值是[3], 哈希表size值是3，索引值sizemask值是2，已有節點數量used值是3。
2.2 哈希表節點定義 (鍵值對)
//哈希表節點定義dictEntry結構表示，每個dictEntry結構都保存著一個鍵值對。 typedef struct dictEntry { //鍵 void *key; //值 union{ void *val; uint64_tu64; int64_ts64; }v; // 指向下個哈希表節點，形成鏈表 struct dictEntry *next; }dictEntry;
上面dictEntry 結構中，key屬性保存著鍵值中的鍵，而v屬性則保存著鍵值對中的值，其中鍵值(v屬性)可以是一個指針，或uint64_t整數，或int64_t整數。 next屬性是指向另一個哈希表節點的指針，這個指針可以將多個哈希值相同的鍵值對連接在一起，解決鍵衝突問題。
下圖通過next指針，將兩個索引值相同(索引是2)的鍵k1和k0連接在一起。
2.3 字典定義
// Redis中的字典由dict.h/dict結構表示 typedef struct dict { //類型特定函數 void *type; //私有數據 void *privdata; //哈希表 dictht ht[2]; // rehash 索引 int trehashidx; }dict;
type屬性和privdata屬性是針對不同類型的鍵值對，為創建多態字典而設置的，type屬性是一個指向dictType結構的指針，每個dictType用於操作特定類型鍵值對的函數，Redis會為用途不同的字典設置不同的類型特定函數。 而privdata屬性則保存了需要傳給給那些類型特定函數的可選參數。
typedef struct dictType { //計算哈希值的函數 unsigned int (*hashFunction) (const void *key); //複製鍵的函數 void *(*keyDup) (void *privdata,const void *key); //複製值的函數 void *(*keyDup) (void *privdata,const void *obj); //複製值的函數 void *(*keyCompare) (void *privdata,const void *key1, const void *key2); //銷毀鍵的函數 void (*keyDestructor) (void *privdata, void *key); //銷毀值的函數 void (*keyDestructor) (void *privdata, void *obj); }dictType;View Code
ht屬性是一個包含兩個項的數組，數組中的每個項都是一個dictht哈希表， 一般情況下，字典只使用ht[0] 哈希表, ht[1]哈希表只會對ht[0] 哈希表進行rehash時使用。另一個和rehash有關的屬性是rehashidx,它記錄了rehash目前的進度，如果目前沒有進行rehash，值為-1。下麵圖是一個沒有進行rehash的字典。
rehash是指漸進式的哈希，一張表是舊表，一張表是新表，當hashtable的大小需要動態改變的時候，舊表中的元素就往新開闢的新表中遷移，當下一次變動大小，當前的新表又變成了舊表，以此達到資源的復用和效率的提升。
