DICT數據結構 Dict其實就是一個hash表，但在redis中，已經存在一種叫Hash的數據結構，所以，就把Hash表改名成Dict吧。。。 Dict是Redis進行鍵值處理的靈魂，不管多大的數據量，始終維持O(1)的時間復雜度（排除bucket下鏈表很長的情況） 全局保存的所有key，
DICT數據結構
dict其實就是一個hash表，但在redis中，已經存在一種叫“hash”的數據結構，所以，就把hash表改名成dict吧。。。
dict是redis進行鍵值處理的靈魂，不管多大的數據量，始終維持o(1)的時間復雜度（排除bucket下鏈表很長的情況）
全局保存的所有key，都存在于一個dict中
而且別的數據結構，比如set、hash也可能會用到dict
Dict實現于 dict.h? dict.c 兩個文件中
其類型定義如下圖：
1. dict：表示一個獨立的dict結構，提供給外部使用
1 typedef struct dict { *privdata; rehashidx; iterators; } dict;
2. dictht：表示一個獨立的dict容器，內部使用，外部程序不建議直接操作該結構
1 typedef struct dictht { unsigned unsigned unsigned } dictht;
3. dictEntry：數據結點，香港服務器租用，其實就是一個kv鍵值對，還包含一個next指針
1 typedef struct dictEntry { 2 void *key; 3 void *val; 4 struct dictEntry *next; 5 } dictEntry;
4.?dictType：定義了一組回調函數，進行數據結點的操作
typedef struct dictType { unsigned *(*keyDup)(*(*valDup)((*keyCompare)(*key2); (*keyDestructor)((*valDestructor)(void *privdata, void *obj); //銷毀val } dictType;
?
?
DICT操作
Redis中的dict是一個標準的 “bucket + 開鏈” 的哈希表
并未進行更復雜的處理
包括防止哈希沖突導致開鏈過長的問題，也沒有考慮
如果精心構造一串key來打redis，很容易打死的
所以，企業級應用的同學們，如果你的Redis服務對用戶比較Open，別下個源碼就用了，還是動手改改HashFunction再用吧！
?
Redis用兩個dictht結構，作用是為了能夠漸進地導數據，防止Rehash時阻塞時間太長
這種做法在memcache中就已經用了，不過memcache中是開辟一個線程專門做rehash而已
相比之下，不開線程的處理方式不用鎖，BUG更少一些
?
命名空間?
Redis中的Dict分為兩類：
1. 系統級Dict，具有全局的命名空間，其定義如下：
typedef struct redisDb { dict *dict; dict *expires; dict *blocking_keys; dict *io_keys; dict *watched_keys; id; } redisDb;
2. 應用級Dict，由metadata數據結構自己維護，主要是一些 set、hash結構中的dict
? ? 如下圖：?
Rehash
當滿足以下條件時，會啟動Rehash
1 // 當有效空間使用率 htNeedsResize(dict *dict) { size, used; 5 6 size = dictSlots(dict); 7 used = dictSize(dict); 8 return (size && used && size > DICT_HT_INITIAL_SIZE && 9 (used*100/size REDIS_HT_MINFILL)); 10 }
?
1 // 當有效空間使用率 > 100%時， _dictExpandIfNeeded(dict *d) 4 { 5 … … (d->ht[0].used >= d->ht[0].size && 8 (dict_can_resize || 9 d->ht[0].used/d->ht[0].size > dict_force_resize_ratio)) 10 { 11 return dictExpand(d, ((d->ht[0].size > d->ht[0].used) ? 12 d->ht[0].size : d->ht[0].used)*2); 13 } 14 return DICT_OK; 15 }
?
Rehash啟動后，就要開始進行Rehash操作了
但是，Rehash的代價是很大的，特別是當容量超過千萬級以后，往往會耗費數十秒來進行操作（視機器性能）
所以，Redis采用了漸進式的Rehash，把操作分片，一步步來，總不能阻塞用戶響應吧
根據Dict的類型不同，會采用不同的Rehash策略：
1. 全局性的DICT結構（就是全局命名空間中的key），會周期性的進行rehash，每次進行 1ms
? ? 而且，不受稍后提到的 SafeIterator的干擾，可以一直執行（但是，虛擬主機，不受干擾是一回事，在iterator循環空間中，還是得用Safe模式的，所以，源碼中也會看到大量針對全局dict的SafeIterator，這一點需要理解一下）
? ? 畢竟，全局的，是重要的嘛，擠也要擠出1ms來，用吧！而且還甭想打擾它，別不服氣了
2. 應用級DICT結構（就是用戶自定義的一些DICT），Redis會采取一種 Lazy Rehash 的策略
? ? 所謂 Lazy Rehash，就是用得越多，處理得越快；用得越少，處理得越慢
? ? 什么叫“用”呢？
? ? 很好理解，“增刪查”操作都叫用，源碼里對應：dictAdd、dictGenericDelete、dictFind、dictGetRandomKey操作，都會促發_dictRehashStep函數進行Rehashing
? ? 但別高興太早，每次只觸發一條而已，所以，慢慢來吧~~
? ??
Iterator
由于Dict內部結構的復雜性，虛擬主機，提供一個遍歷所有數據的iterator，是非常必要的
Dict提供兩種Iterator:
1.?dictGetIterator：普通iter，在遍歷時不可對dict做更多操作，否則會引起數據遺漏或重復
2.?dictGetSafeIterator：安全iter，什么操作都能做，安全的，你懂的。
可以參考上圖理解這一點，不再贅述
DictType
dictType 定義了dict的操作行為。Redis預定義了一組dictType，規范各種類型dict的操作
相關代碼如下：
