［Redis源碼閱讀］dict字典的實作

dict是一種用于儲存鍵值對的抽象資料結構，在redis中使用非常廣泛，比如資料庫、哈希結構的底層。

當執行下面這個指令：

以及使用哈希結構，如：

都會使用到dict作為底層資料結構的實作。

先看看字典以及相關資料結構體的定義：

把上面的結構定義串起來，得到下面的字典資料結構：

根據資料結構定義，把關聯圖畫出來後，看代碼的時候就更加清晰。

從圖中也可以看出來，字典的哈希表裡，使用了連結清單解決鍵沖突的情況，稱為鍊式位址法。

當操作越來越多，比如不斷的向哈希表添加元素，此時哈希表需要配置設定了更多的空間，如果接下來的操作是不斷地删除哈希表的元素，那麼哈希表的大小就會發生變化，更重要的是，現在的哈希表不再需要那麼大的空間了，在redis的實作中，為了保證哈希表的負載因子維持在一個合理範圍内，當哈希表儲存的鍵值對太多或者太少時，redis對哈希表大小進行相應的擴充和收縮，稱為rehash（重新散列）。

負載因子 = 哈希表已儲存節點數量 / 哈希表大小

負載因子越大，意味着哈希表越滿，越容易導緻沖突，性能也就越低。是以，一般來說，當負載因子大于某個常數(可能是 1，或者 0.75 等)時，哈希表将自動擴容。

在上面的rehash流程圖裡面，rehash的操作不是一次性就完成了的，而是分多次，漸進式地完成。

原因是，如果需要rehash的鍵值對較多，會對伺服器造成性能影響，漸進式地rehash避免了對伺服器的影響。

漸進式的rehash使用了dict結構體中的rehashidx屬性輔助完成。當漸進式哈希開始時，rehashidx會被設定為0，表示從dictEntry[0]開始進行rehash，每完成一次，就将rehashidx加1。直到ht[0]中的所有節點都被rehash到ht[1]，rehashidx被設定為-1，此時表示rehash結束。

在漸進式rehash期間，所有對字典的操作，包括：添加、查找、更新等等，程式除了執行指定的操作之外，還會順帶将ht[0]哈希表索引的所有鍵值對rehash到ht[1]。比如添加：

使用一個标記值标記某項操作正在執行是程式設計中常用的手段，比如本文提到的rehashidx，多利用此手段可以解決很多問題。

我在github有對Redis源碼更詳細的注解。感興趣的可以圍觀一下，給個star。Redis4.0源碼注解。可以通過commit記錄檢視已添加的注解。

原創文章，文筆有限，才疏學淺，文中若有不正之處，萬望告知。

更多精彩内容，請關注個人公衆号。