Dict數據結構

一、Redis字典的核心組件

Redis字典由三部分構成：

1. dictht（哈希表）：存儲桶數組與元數據
2. dictEntry（哈希節點）：存儲鍵值對
3. dict（字典主體）：包含雙哈希表（用于漸進式重哈希）和類型函數

---

二、哈希表結構 dictht（Dict HashTable）

typedef struct dictht {dictEntry **table;        // 桶數組指針unsigned long size;       // 哈希表總槽位數（桶大小）unsigned long sizemask;   // 掩碼（size-1）unsigned long used;       // entry的數量
} dictht;

字段詳解：

1. dictEntry **table

   • 核心存儲結構：指向指針數組(entry數組)的指針
   • 數組元素為dictEntry*類型（鏈表頭指針）

2. size

   • 哈希表的大小（總是2^n）
   • 通過_dictNextPower函數動態擴容（如4→8→16）

3. sizemask

   • 核心優化設計：值為size-1
   • 作用：替代取模運算?index = hash & sizemask

4. used

   • 當前有效節點數量（非空桶計數）
   • 縮容條件：used/size < 0.1

這里的 used即標識entry數量的字段可能比哈希表大小字段更大,因為可能計算出同樣的hash值,所以value就放在同一個位置

---

三、哈希節點 dictEntry

typedef struct dictEntry {void *key;          // 鍵指針union {             // 聯合值域（節約內存）void *val;      // 通用值指針uint64_t u64;   // 無符號64位整數int64_t s64;    // 有符號64位整數double d;       // 雙精度浮點} v;struct dictEntry *next;  // 沖突鏈表指針
} dictEntry;

字段詳解：

1. void *key

   • 鍵的指針（支持任意數據類型）
   • 實際存儲類型取決于Redis對象系統（SDS/INET等）
   • 通過dictType中的哈希函數計算索引

2. 值聯合體?v

   • 創新設計：共用內存空間（每次只用一種類型）
   • val：通用對象指針（如RedisObject）
   • u64/s64：直接存儲整數（避免內存碎片）
   • d：直接存儲浮點數（如ZSET的score）
   • 典型內存優化：8字節空間覆蓋所有類型

3. struct dictEntry *next

   • 沖突解決方案：單向鏈表
   • 頭插法添加新節點（O(1)復雜度）
   • 鏈表長度>64觸發樹化（在rehash時轉換）
     

Dict添加鍵值對過程

步驟1：計算哈希值與索引

// 示例：添加鍵值對 k1:v1
hash = dict->type->hashFunction(k1);  // 計算鍵k1的SipHash值
index = hash & dict->ht[0].sizemask;  // 圖中sizemask=3

---

步驟2：解決哈希沖突

1. 創建新entry：

   entry = zmalloc(sizeof(dictEntry));
   entry->key = k1;
   entry->v.val = v1;
   

2. 頭插法鏈入：

   entry->next = dict->ht[0].table[index]; 
   // 原table[1]指向k2節點，新entry指向k2
   

---

步驟3：更新哈希表狀態

dict->ht[0].table[index] = entry;  // 桶指針指向新插入的entry
dict->ht[0].used++;                // used計數+1（used從1→2）

Dict數據結構中,默認使用Dict中的第一個哈希表作為數據的存儲,圖片中

• ht[0]被初始化為一個dictht結構體（table數組大小為4，存儲兩個鍵值對k1:v1和k2:v2）。
• ht[1]為null，所有字段（table、size等）為空或0，表明當前未進行rehash。

Dict的擴容

每次擴容時都是擴容都是擴容到2**n,并且是第一個大于等于used+1的2**n

條件一：LoadFactor ≥ 1 且無后臺進程運行

if (d->ht[0].used >= d->ht[0].size && dict_can_resize)  // 等效于"LoadFactor≥1"

• 設計目的
  平衡內存效率和性能：當平均每個桶至少存儲一個元素時（LoadFactor=1），沖突概率顯著增加。此時擴容可降低沖突率，但需考慮系統負載。

• 后臺進程限制原因
  保護持久化操作：

  1. 執行BGSAVE或BGREWRITEAOF時，Redis使用寫時復制（Copy-on-Write）?機制
  2. 若此時擴容（分配新哈希表），會觸發大量內存頁復制
  3. 可能耗盡內存或造成性能抖動（圖示代碼注釋明確提到此保護邏輯）

---

條件二：LoadFactor > 5

// dict_force_resize_ratio 在源碼中定義為5
if (d->ht[0].used/d->ht[0].size > dict_force_resize_ratio)  

• 設計目的
  緊急避險機制：
  當哈希沖突極度嚴重時（平均每個桶鏈長超過5），即使有后臺進程運行也強制擴容，避免查詢性能雪崩（鏈表遍歷從O(1)退化為O(n)）。

• 臨界值選擇依據

  1. 經驗值：桶鏈超過5個節點，查找效率明顯下降（實測性能衰減曲線）
  2. 內存容忍上限：5倍空間浪費是可承受極限（例：16個桶存80個元素）

Dict的收縮

收縮大小為第一個大于等于used的2**n,此時的size遠比used大,之所以是大于等于要保證實際

當刪除元素后，Redis 會調用?htNeedsResize(dict)?檢查是否滿足收縮條件：

size = dictSlots(dict);   // 哈希表總槽位數
used = dictSize(dict);    // 已使用槽位數（鍵值對數量）
if (size > DICT_HT_INITIAL_SIZE && (used * 100 / size < HASHTABLE_MIN_FILL)) {  // 默認HASHTABLE_MIN_FILL=10return 1;  // 需要收縮
}

條件解讀：

1. 哈希表大小超過初始值（DICT_HT_INITIAL_SIZE，默認為4）
2. 負載因子 < 10%（即已用槽位數不足總槽位的10%）
3. 特殊保護：若?used < 4，強制按4計算，避免過度收縮

---

?收縮執行流程

1.?調用入口

刪除元素后觸發檢查：

// t_hash.c
if (dictDelete(dict, field) == C_OK) {if (htNeedsResize(o->ptr)) dictResize(o->ptr);  // 滿足條件則執行收縮
}

2.?計算目標大小

// dictResize() 邏輯
minimal = dict->ht[0].used;  // 當前實際元素數量
if (minimal < DICT_HT_INITIAL_SIZE)minimal = DICT_HT_INITIAL_SIZE;  // 最小收縮到初始大小
return dictExpand(dict, minimal);

可以看到這里不論是收縮還是擴容最后都調用了dictExpand方法 下面是該源碼

int dictExpand(dict *d, unsigned long size) {return _dictExpand(d, size, NULL);
}/* * 擴展或收縮字典的哈希表* * @param d: 目標字典指針* @param size: 期望的新哈希表大小* @param malloc_failed: 內存分配失敗標志（輸出參數）* @return: 操作狀態（DICT_OK 或 DICT_ERR）*/
int _dictExpand(dict *d, unsigned long size, int* malloc_failed) {// 初始化內存分配失敗標志if (malloc_failed) *malloc_failed = 0;/* * 有效性檢查：* 1. 如果字典正在 rehash 中，禁止擴展* 2. 如果當前元素數量大于目標大小，禁止收縮,這里的size就是目標擴容大小*/if (dictIsRehashing(d) || d->ht[0].used > size)return DICT_ERR;dictht n; /* 新哈希表 */// 計算新的size（調整為大于等于size的最小2的冪）unsigned long realsize = _dictNextPower(size);/* 如果新size與當前size相同，無需操作 */if (realsize == d->ht[0].size) return DICT_ERR;/* 分配新哈希表并初始化所有指針為NULL */n.size = realsize;n.sizemask = realsize-1;  // 掩碼用于快速計算索引/* * 內存分配策略：* - 如果允許內存分配失敗（malloc_failed != NULL），使用嘗試分配* - 否則使用強制分配（失敗會panic）*/if (malloc_failed) {n.table = ztrycalloc(realsize*sizeof(dictEntry*));*malloc_failed = n.table == NULL;  // 設置分配失敗標志if (*malloc_failed)return DICT_ERR;} else {n.table = zcalloc(realsize*sizeof(dictEntry*));}n.used = 0;  // 初始化已用槽位數為0/* * 首次初始化處理（非rehash場景）：* 當ht[0]為空時，直接使用新哈希表作為主表*/if (d->ht[0].table == NULL) {d->ht[0] = n;return DICT_OK;}/* * 準備漸進式rehash：* 1. 將新哈希表放入ht* 2. 設置rehashidx=0標記開始rehash* （圖片中dictResize()最終會調用此邏輯）*/d->ht[1] = n;d->rehashidx = 0;  // 從索引0開始遷移數據return DICT_OK;
}

如圖會更具當前的used來去判斷此時的dictEntry的大小 并且為二的n次方,遷移的時候會將dictEntry從原本的地方一個一個遷移過來,全部遷移完過后ht[0]的table指針會指向新的dictEntry,ht[1]指向null

但是如果說一次性完成的話?如果Dict中包含的數據太多了,可能會導致主線程阻塞 因此DIct的rehash是多次完成的,如果是查詢和修改那么ht[0]的dictEntry和ht[1]的dictEntry都需要去查詢