### dict數據結構 dict是一個用于維護key和value映射關系的數據結構，與很多語言中的Map或dictionary類似。Redis的一個database中所有key到value的映射，就是使用一個dict來維護的。dict本質上是為了解決算法中的查找問題(Searching)。 1.一般查找問題的解法分為兩個大類：一個是基于各種平衡樹，一個是基于哈希表，平常使用的各種Map或dictionary，大都是基于哈希表實現的。 2.dict也是一個基于哈希表的算法，跟java中的hashMap類似，用key計算出哈希值，并得到key在哈希表中的位置，再采用拉鏈法解決沖突，并在裝載因子（load factor）超過預定值時自動擴展內存，引發重哈希（rehashing）。 為了能更清楚地展示dict的數據結構定義，用一張結構圖來表示dict(字典)的構成。如下圖：  數據結構代碼 ~~~c #dict字典的數據結構 typedef struct dict{ dictType *type; //直線dictType結構，dictType結構中包含自定義的函數，這些函數使得key和value能夠存儲任何類型的數據 void *privdata; //私有數據，保存著dictType結構中函數的 參數 dictht ht[2]; //兩張哈希表 long rehashidx; //rehash的標記，rehashidx=-1表示沒有進行rehash，rehash時每遷移一個桶就對rehashidx加一 int itreators; //正在迭代的迭代器數量 } #dict結構中ht[0]、ht[1]哈希表的數據結構 typedef struct dictht{ dictEntry[] table; //存放一個數組的地址，數組中存放哈希節點dictEntry的地址 unsingned long size; //哈希表table的大小，出始大小為4 unsingned long sizemask; //用于將hash值映射到table位置的索引，大小為（size-1） unsingned long used; //記錄哈希表已有節點（鍵值對）的數量 } ~~~ 上圖就是Redis的dict(字典)數據結構，一個dict需要注意幾點： （1）dict采用哈希函數對key取哈希值得到在哈希表中的位置(桶的位置)，采用拉鏈法解決hash沖突。 （2）兩張哈希表（ht[2]）：只有在重哈希的過程中，ht[0]和ht[1]才都有效。而在平常情況下，只有ht[0]有效，ht[1]里面沒有任何數據。上圖表示的就是重哈希進行到中間某一步時的情況。 （3）重哈希：跟HashMap一樣當裝載因子（load factor）超過預定值時就會進行rehash。dict進行rehash擴容，將ht[0]上某一個bucket（即一個桶上dictEntry鏈表）上的每一個鏈表移動到擴容后的ht[1]上(每次只移動一個鏈表，即漸進式rehash。原因是為了防止redis長時間的堵塞導致不可用)，觸發rehash的操作有查詢、插入和刪除元素。rehashidx會記錄每次需要移動鏈表bucket桶的位置(后面會詳細講解)。 （4）當 ht[0] 包含的所有鍵值對都遷移到了 ht[1] 之后 （ht[0] 變為空表），釋放 ht[0] ， 將 ht[1] 設置為 ht[0] ， 并在 ht[1] 新創建一個空白哈希表， 為下一次 rehash 做準備