[TOC] ### **基本原理** ***** #### **什么是字典** `字典`，又稱為`符號表`（symbol table）、`關聯數組`（associative array）或`映射`（map），是一種用于保存鍵值對（key-value pair）的`抽象數據結構` 在字典中，一個鍵（key）可以和一個值（value）進行關聯（或者說將鍵映射為值），這些關聯的鍵和值就稱為鍵值對。 #### **字典底層的實現** Redis的字典使用哈希表作為底層實現，一個哈希表里面可以有多個哈希表節點，而每個哈希表節點就保存了字典中的一個鍵值對。 #### **哈希表** Redis字典所使用的哈希表由dict.h/dictht結構定義： ``` typedef?struct?dictht?{ ????// 哈希表數組 ????dictEntry?**table; ????//?哈希表大小 ????unsigned?long?size; ????// 哈希表大小掩碼，用于計算索引值 ???? // 總是等于size-1 ????unsigned?long?sizemask; ????//?該哈希表已有節點的數量 ????unsigned?long?used; }?dictht; ``` `table`屬性是一個數組，數組中的每個元素都是一個指向dict.h/dictEntry結構的指針，每個dictEntry結構保存著一個鍵值對。 `size`屬性記錄了哈希表的大小，也即是table數組的大小， `used`屬性則記錄了哈希表目前已有節點（鍵值對）的數量。 `sizemask`屬性的值總是等于size-1，這個屬性和哈希值一起決定一個鍵應該被放到table數組的哪個索引上面。 下圖展示了一個大小為4的空哈希表（沒有包含任何鍵值對）：  #### **哈希表節點** 哈希表節點使用dictEntry結構表示，每個dictEntry結構都保存著一個鍵值對： ``` typedef?struct?dictEntry?{ ????//鍵 ????void?*key; ?//值 ????union{ ????????void?*val; ????????uint64_tu64; ????????int64_ts64; ????}?v; ????//指向下個哈希表節點，形成鏈表 ????struct?dictEntry?*next; }?dictEntry; ``` `key`屬性保存著鍵值對中的鍵，而v屬性則保存著鍵值對中的值，其中鍵值對的值可以是一個指針，或者是一個uint64_t整數，又或者是一個int64_t整數。 **next**屬性是指向另一個哈希表節點的指針，這個指針可以將多個哈希值相同的鍵值對連接在一次，以此來`解決鍵沖突`（collision）的問題。 下圖展示了如何通過next指針，將兩個索引值相同的鍵k1和k0連接在一起。  #### **字典的定義** Redis中的字典由dict.h/dict結構表示： ``` typedef?struct?dict?{ ????//類型特定函數 ????dictType*type; ????//私有數據 ????void?*privdata; ?? // 哈希表 ???? dictht?ht[2]; ?? //rehash 索引 ?? // 當rehash 不在進行時，值為-1 ????in?trehashidx;?/*?rehashing?not?in?progress?if?rehashidx?==?-1?*/ }?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?*(*valDup)(void?*privdata,?const?void?*obj); ????//對比鍵的函數 ????int?(*keyCompare)(void?*privdata,?const?void?*key1,?const?void?*key2); ????//? 銷毀鍵的函數 ????void?(*keyDestructor)(void?*privdata,?void?*key); ????// 銷毀值的函數 ????void?(*valDestructor)(void?*privdata,?void?*obj); }?dictType; ``` `ht屬性`是一個包含兩個項的數組，數組中的每個項都是一個dictht哈希表，一般情況下，字典只使用ht\[0\]哈希表，ht\[1\]哈希表只會在對ht\[0\]哈希表進行rehash時使用。 除了ht\[1\]之外，另一個和`rehash`有關的屬性就是`rehashidx`，它記錄了rehash目前的進度，如果目前沒有在進行rehash，那么它的值為-1。 下圖展示了一個普通狀態下（沒有進行rehash）的字典：  ### **哈希算法** ***** 當要將一個新的鍵值對添加到字典里面時，程序需要先根據鍵值對的鍵計算出哈希值和索引值，然后再根據索引值，將包含新鍵值對的哈希表節點放到哈希表數組的指定索引上面。 **哈希算法詳情** 參見：[哈希算法](%E7%AC%AC%E5%9B%9B%E8%8A%82%EF%BC%9A%E5%AD%97%E5%85%B8%E7%9A%84%E5%AE%9E%E7%8E%B0%E4%BA%8C-%E5%93%88%E5%B8%8C%E7%AE%97%E6%B3%95.md) ### **哈希沖突的解決** ***** 當有兩個或以上數量的鍵被分配到了哈希表數組的同一個索引上面時，我們稱這些鍵發生了沖突（collision）。 **字典哈希沖突解決方案** 參見 :[哈希沖突解決方案](%E7%AC%AC%E4%BA%94%E8%8A%82%EF%BC%9A%E5%AD%97%E5%85%B8%E7%9A%84%E5%AE%9E%E7%8E%B0%E4%B8%89-%E8%A7%A3%E5%86%B3%E9%94%AE%E5%86%B2%E7%AA%81.md) ### **rehash的原理** ***** 隨著操作的不斷執行，哈希表保存的鍵值對會逐漸地增多或者減少，為了讓哈希表的負載因子（load factor）維持在一個合理的范圍之內，當哈希表保存的鍵值對數量太多或者太少時，程序需要對哈希表的大小進行相應的擴展或者收縮。 `rehash操作詳情` 參見：[rehash原理](%E7%AC%AC%E5%85%AD%E8%8A%82%EF%BC%9A%E5%AD%97%E5%85%B8%E7%9A%84%E5%AE%9E%E7%8E%B0%E5%9B%9B-rehash%E5%8E%9F%E7%90%86.md)