字典是一種用於儲存鍵值對的 抽象資料結構 ，也被稱為查詢表、對映或關聯表。
在字典中，一個 鍵 （key）可以和一個值（value）進行關聯，這些關聯的 鍵 和值就稱之為鍵值對。
抽象資料結構，啥意思？就是可以需要實際的資料結構是實現這個功能。抽象，意味著它這是實現功能的標準，凡是能夠完成這些功能的都可以是其實現。
redis的字典字典作為一種資料結構內建在很多高階程式語言裡面，但是redis是基於C語言進行開發的，所以沒有內建這種資料結構，redis只能構建自己的字典實現。
字典通常可以由兩種底層資料結構組成，分別是線性表（陣列）和hash表。而redis一般是採用hash表的方式進行構建
redis字典為啥不用線性表實現字典基於用線性表實現，如果我這個字典有200個鍵值對，那麼我就開闢一個長度為200的陣列對這些元素進行放置。
基於線性表實現的字典的優缺點很明顯：
1、實現簡單，適用於任意關鍵字型別。
2、平均檢索效率低（線性時間），表長度n比較大時，檢索比較耗時。
雜湊如何實現字典之前寫過一篇文章，關於java中的hashcode解析，有興趣的讀者可以回看下一些經典的hash函式和實現
面試官問我：hashcode 是什麼？和equals是兄弟嗎？
redis字典所使用的 雜湊表 由dict.h/dictht組成
typedef struct dictht { dictEntry **table; //雜湊表陣列 unsigned long size; //雜湊表大小，即雜湊表陣列大小 unsigned long sizemask; //雜湊表大小掩碼，總是等於size-1，主要用於計算索引 unsigned long used; //已使用節點數，即已使用鍵值對數}dictht;可以看到redis聲明瞭一個結構體，裡面由一個雜湊表陣列，雜湊表陣列大小的long值，一個用於計算索引的雜湊表大小掩碼以及已使用的節點數構成。
這個雜湊表陣列，存放的是雜湊節點dicEntry，我們會將key-value鍵值對給它放進去。
typedef struct dictEntry { void *key; //存放key值 union { void *val; //存放value值 uint64_t u64; //uint64_t整數 int64_t s64; //int64_t整數 }v; struct dictEntry *next; //指向下個雜湊表節點，形成連結串列}dictEntry;如圖所示就透過next指標來將兩個索引相同的鍵k1和k0連線在一起。
Redis 中的 字典 由 dict.h/dict 結構表示：
typedef struct dict { // 型別特定函式 dictType *type; // 私有資料 void *privdata; // 雜湊表 dictht ht[2]; // rehash 索引 // 當 rehash 不在進行時，值為 -1 int rehashidx; /* rehashing not in progress if rehashidx == -1 */} dict;可以看到字典裡有一個長度為2的雜湊表陣列，那麼為啥不是三個四個甚至更多呢？感覺雜湊表越多不是效率更快嗎？
其實設定2的原因在於，h[0]用於儲存，h[1]用於當容量不足時進行擴充,更多的雜湊表也用不上，反而可能在擴充時要同步成為效能瓶頸。
字典如何增添一個元素當要將一個新的鍵值對加入到字典中的時候，首先要計算這個key的雜湊值和索引值，然後再根據這個索引值放入字典中h[0]的索引位置
舉個例子， 對於圖 4-4 所示的字典來說， 如果我們要將一個鍵值對 k0 和 v0 新增到字典裡面， 那麼程式會先使用語句：
hash = dict->type->hashFunction(k0);計算機 k0 的雜湊值。
假設計算得出的雜湊值為 8 ， 那麼程式會繼續使用語句：
index = hash & dict->ht[0].sizemask = 8 & 3 = 0;計算出鍵 k0 的索引值 0 ， 這表示包含鍵值對 k0 和 v0 的節點應該被放置到雜湊表陣列的索引 0 位置上， 如圖 所示。
什麼時候會進行擴容按照java中hashmap的說法，當負載因子 loadFactor>0.75 的情況下會進行擴容
在redis中，字典裡的雜湊會根據以下兩種情況進行擴容：
伺服器目前沒有在執行 BGSAVE 命令或者 BGREWRITEAOF 命令， 並且雜湊表的負載因子大於等於 1 ；伺服器目前正在執行 BGSAVE 命令或者 BGREWRITEAOF 命令， 並且雜湊表的負載因子大於等於 5 ；其中雜湊表的負載因子可以透過公式：
# 負載因子 = 雜湊表已儲存節點數量 / 雜湊表大小load_factor = ht[0].used / ht[0].size首先要清楚為什麼rehash的時候要漸進式。
這就好比去參加高考，肯定是初中畢業後讀三年高中，一點點學習高中知識後才可以參加高考，這才可以取得不錯的成績。學習是循序漸進的，hash也要，不然中考完直接去參加高考，這誰頂得住啊。
Rehash操作分為兩種：
擴充套件：當負載因子較大時，應該擴大 dictht::size 以降低平均長度，加快查詢速度。
收縮：當負載因子較小時，應該減小 dictht::size 以減少對記憶體的浪費。
當整體的資料量比較少，如百八十個key-value對儲存的時候，hash的過程肯定耗時不會很多。但是在生產環境下，一個數據庫下key-value值都是有百萬級別的，在進行rehash操作的時候勢必會達到秒級別的運算。所以這個hash的過程不是一次性集中的完成，而是分多次漸進式的完成。
以下是雜湊表漸進式 rehash 的詳細步驟：
為 ht[1] 分配空間， 讓字典同時持有 ht[0] 和 ht[1] 兩個雜湊表。在字典中維持一個索引計數器變數 rehashidx ， 並將它的值設定為 0 ， 表示 rehash 工作正式開始。在 rehash 進行期間， 每次對字典執行新增、刪除、查詢或者更新操作時， 程式除了執行指定的操作以外， 還會順帶將 ht[0] 雜湊表在 rehashidx 索引上的所有鍵值對 rehash 到 ht[1] ， 當 rehash 工作完成之後， 程式將 rehashidx 屬性的值增1。隨著字典操作的不斷執行， 最終在某個時間點上， ht[0] 的所有鍵值對都會被 rehash 至 ht[1] ， 這時程式將 rehashidx 屬性的值設為 -1 ， 表示 rehash 操作已完成。rehash的過程中有資料變化怎麼辦關於字典的操作無非就是四個，增刪改查。
這樣就能保證redis在h[0]上是隻少不多，所有的記錄都會被遷移到h[1]上。
如何解決雜湊碰撞這個問題還是我面試騰訊的時候面試官問我的原題。
一開始我說了兩個思路，一個是無限增大線性表的容量，一個是採用陣列+連結串列的方式。
面試官：對這兩個都是構成hash的方式，但是如果我的兩個鍵值對的hashcode是一樣的呢？
我：那就可以將這個hash演算法設計的複雜化，比如hash裡頭再巢狀一層hash，這樣碰撞的機率就會變小了。
面試官：這種方法其實也是可以的，那還有沒有其他方法呢？
我：....（支支吾吾中）
然後面試就結束了orz
其實還有另一種方法我不知道就是公共溢位區法
建立一個公共溢位區，假設雜湊函式的值域為[0,m-1],則設向量HashTable[0..m-1]為基本表，另外設立儲存空間向量OverTable[0..v]用以儲存發生衝突的記錄。