[置頂] Redis源碼閱讀筆記（3）-- 字典dict

2024-07-21 02:52:50

字體：大中小

來源：轉載

供稿：網友

字典是Redis的一種非常重要的底層數據結構，其應用非常廣泛。Redis的數據庫就是使用字典作為底層實現的，對數據庫的增刪查改也都構建在對字典的操作之上；字典也是hash鍵的底層實現之一，當一個哈希鍵包含的鍵值對比較多時，或者鍵值對中的元素都是比較長的字符串時，redis就會使用字典作為底層實現；此外，redis還使用dict和skiplist共同維護一個sorted set。

dict本質上是為了解決算法中的查找問題（Searching），一般查找問題的解法分為兩個大類：一個是基于各種平衡樹，一個是基于哈希表。我們平常使用的各種Map或dictionary，大都是基于哈希表實現的。在不要求數據有序存儲，且能保持較低的哈希值沖突概率的前提下，基于哈希表的查找性能能做到非常高效，接近O(1)，而且實現簡單。

數據結構

我們先來看看dict的數據結構，有四部分組成：dict、dictht、dictType和dictEntry–與字典有關的源代碼都在dict.c/dict.h中。

哈希表–dictht

typedef struct dictht { // 哈希表數組 dictEntry **table; // 哈希表大小 unsigned long size; // 哈希表大小掩碼，用于計算索引值 // 總是等于 size - 1 unsigned long sizemask; // 該哈希表已有節點的數量 unsigned long used;} dictht;

其中，table屬性是一個數組，數組中的每一個元素都是一個指向哈希表節點的指針，而每一個哈希表節點都保存著一個鍵值對。

哈希表節點–dictEntry

typedef struct dictEntry { void *key; // 鍵 union { void *val; uint64_t u64; int64_t s64; } v; // 值 // 指向下個哈希表節點，形成鏈表 struct dictEntry *next;} dictEntry;

哈希表節點使用dictEntry結構表示，每一個dictEntry結構都保存著一個鍵值對。其中需要注意的是，next屬性是指向另外一個哈希表節點的指針，通過這樣一個指針，可以將索引值相同的鍵值對連接在一起，以此解決鍵沖突的問題。

字典–dict

typedef struct dict { dictType *type; void *PRivdata; // 私有數據，由調用者在創建dict的時候傳進來 dictht ht[2]; long rehashidx; int iterators; // 當前正在使用的迭代器數量，暫不討論，忽略} dict;

其中，a、type是一個指向dictType結構的指針，保存一些用于操作特定類型鍵值對的函數；b、ht[2]，一個字典結構包括兩個哈希表，只有在重哈希的過程中，ht[0]和ht[1]才都有效。而在平常情況下，只有ht[0]有效，ht[1]里面沒有任何數據；c、rehashidx屬性，當前重哈希索引，如果rehashidx = -1，表示當前沒有在重哈希過程中；否則，表示當前正在進行重哈希，且它的值記錄當前需要rehash的索引值

字典類型特定函數–dictType

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;

來一張普通狀態下（沒有rehash）的字典結構圖，幫助大家理解這里寫圖片描述圖一

hash算法

將一個新的鍵值對添加到字典里面時，我們需要先計算這個鍵值對構成的哈希表節點在哈希表數組中的位置（即索引值），程序先根據鍵計算出哈希值和索引值，再根據索引值，將鍵值對構成的哈希表節點放到哈希表數組相應的索引上。 hash值和索引值得計算方法：使用字典設置的hash函數，計算key的哈希值

//計算hash值hash = dict->type->hashFunction(key) //使用哈希表的sizemask屬性和哈希值，計算索引值//根據情況的不同，ht[x]可能為ht[0]或者ht[1]index = hash & d->ht[x].sizemask;

每個key先經過hashFunction計算得到一個哈希值，然后計算(哈希值 & sizemask)得到在table上的位置。相當于計算取余(哈希值 % size)（當size不為0時）。

鍵沖突

當兩個或以上數量的鍵分配到哈希表數組的同一個索引上時，我們稱這些鍵發生了沖突。Redis中的hash表使用鏈地址法來解決鍵沖突的問題，每一個哈希表節點都有一個next指針，被分配到同一索引的多個哈希表節點使用next指針構成一條單向鏈表，這樣便解決了鍵沖突的問題。因為dictEntry節點組成的鏈表沒有指向鏈表末尾的指針，所以為了速度考慮，總是將新節點添加到鏈表的表頭位置，排在其他已有節點之前。

圖二：一個包含兩個鍵值對的哈希表 圖三：使用鏈地址法解決k1和k2鍵沖突

rehash算法

rehash指的是重新計算鍵的hash值和索引值，然后將鍵值對放到ht[1]哈希表指定的位置上。首先指出一個概念：哈希表的負載因子-load_factor load_factor = ht[0].used / ht[0].size 在操作哈希表的過程中，表中的鍵值對會增多或者減少。我們知道hash表采用鏈地址法解決鍵沖突的問題，那么當鍵值對增多時，勢必會造成沖突鏈表越來越長，導致hash表查詢效率的下降，這樣就需要對hash表進行擴容；另外，當hash表的鍵值對過少時，就需要對hash表收縮以節省內存。擴容和收縮操作就需要通過rehash實現。 Redis對hash表執行rehash的步驟如下： 1）為字典的ht[1]哈希表分配內存空間，大小取決于要執行的操作和ht[0]哈希表中鍵值對的數量（即ht[0].used屬性的值）；

若負載因子大于5時，執行的是擴容操作，ht[1]哈希表的大小為第一個大于等于ht[0].used*2的2的n次方；負載因子小于0.1時，執行的收縮操作，ht[1]哈希表的大小為第一個大于等于ht[0].used的2的n次方；

2）將保存在ht[0]中的所有鍵值對rehash到hr[1]上面； 3）當ht[0]包含的多有鍵值對全部都遷移至ht[1]之后（ht[0]變為空表），釋放ht[0]，并將ht[1]置為ht[0]、在ht[1]新創建一個空白的哈希表，為下一次rehash做準備； rehash算法源碼：

//執行 N 步漸進式 rehash 。//返回 1 表示仍有鍵需要從 0 號哈希表移動到 1 號哈希表，// 返回 0 則表示所有鍵都已經遷移完畢。//注意，每步 rehash 都是以一個哈希表索引（桶）作為單位的，一個桶里可能會有多個節點，被 rehash 的桶里的所有節點都會被移動到新哈希表。int dictRehash(dict *d, int n) { // 只可以在 rehash 進行中時執行 if (!dictIsRehashing(d)) return 0; // 進行 N 步遷移 // T = O(N) while(n--) { dictEntry *de, *nextde; // 如果 0 號哈希表為空，那么表示 rehash 執行完畢 // T = O(1) if (d->ht[0].used == 0) { // 釋放 0 號哈希表 zfree(d->ht[0].table); // 將原來的 1 號哈希表設置為新的 0 號哈希表 d->ht[0] = d->ht[1]; // 重置舊的 1 號哈希表 _dictReset(&d->ht[1]); // 關閉 rehash 標識 d->rehashidx = -1; // 返回 0 ，向調用者表示 rehash 已經完成 return 0; } // 確保 rehashidx 沒有越界 assert(d->ht[0].size > (unsigned)d->rehashidx); // 略過數組中為空的索引，找到下一個非空索引 while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++; // 指向該索引的鏈表表頭節點 de = d->ht[0].table[d->rehashidx]; // 將鏈表中的所有節點遷移到新哈希表 // T = O(1) while(de) { unsigned int h; // 保存下個節點的指針 nextde = de->next; /* Get the index in the new hash table */ // 計算新哈希表的哈希值，以及節點插入的索引位置 h = dictHashKey(d, de->key) & d->ht[1].sizemask; // 插入節點到新哈希表 de->next = d->ht[1].table[h]; d->ht[1].table[h] = de; // 更新計數器 d->ht[0].used--; d->ht[1].used++; // 繼續處理下個節點 de = nextde; } // 將剛遷移完的哈希表索引的指針設為空 d->ht[0].table[d->rehashidx] = NULL; // 更新 rehash 索引 d->rehashidx++; } return 1;}

Redis中rehash的操作不是一次完成，而是漸進式完成，每次只移動若干個索引下的鍵值對到新表（在ht[0]中采用rehashidx參數來記錄當前需要rehash的索引值）。為此，Redis提供了兩種漸進式的操作來進行rehash。 1）按索引值，每一次只移動一個索引值下面的鍵值對到行的hash表中；

// 在執行節點增刪改查操作時，如果符合rehash條件就會觸發一次rehash操作，每次執行一步static void _dictRehashStep(dict *d) { if (d->iterators == 0) dictRehash(d,1);}

2）按照時間，每次執行一段固定的時間

// 獲取當前的時間戳（以毫秒為單位）long long timeInMilliseconds(void) { struct timeval tv; gettimeofday(&tv,NULL); return (((long long)tv.tv_sec)*1000)+(tv.tv_usec/1000);}// rehash操作每次執行ms時間就退出int dictRehashMilliseconds(dict *d, int ms) { long long start = timeInMilliseconds(); int rehashes = 0; while(dictRehash(d,100)) { // 每次執行100步 rehashes += 100; if (timeInMilliseconds()-start > ms) break; // 如果時間超過ms就退出 } return rehashes;}

rehash算法就講到這里，接下去要分析的大家應該可以想到，對了，就是字典的創建、插入、查找和刪除。

dict的操作

字典的創建–dictCreate()

//創建一個新的字典dict *dictCreate(dictType *type,void *privDataPtr){ dict *d = zmalloc(sizeof(*d)); _dictInit(d,type,privDataPtr); return d;}//初始化hash表int _dictInit(dict *d, dictType *type,void *privDataPtr){ // 初始化兩個哈希表的各項屬性值 // 但暫時還不分配內存給哈希表數組 _dictReset(&d->ht[0]); _dictReset(&d->ht[1]); // 設置類型特定函數 d->type = type; // 設置私有數據 d->privdata = privDataPtr; // 設置哈希表 rehash 狀態 d->rehashidx = -1; // 設置字典的安全迭代器數量 d->iterators = 0; return DICT_OK;}//重置（或初始化）給定哈希表的各項屬性值static void _dictReset(dictht *ht){ ht->table = NULL; ht->size = 0; ht->sizemask = 0; ht->used = 0;}

字典的查找–dictFind()

字典中包含鍵 key 的節點，找到返回節點，找不到返回 NULL， T = O(1)

dictEntry *dictFind(dict *d, const void *key){ dictEntry *he; unsigned int h, idx, table; // 字典（的哈希表）為空 if (d->ht[0].size == 0) return NULL; // 如果條件允許的話，進行單步 rehash if (dictIsRehashing(d)) _dictRehashStep(d); // 計算鍵的哈希值 h = dictHashKey(d, key); // 在字典的哈希表中查找這個鍵，T = O(1) for (table = 0; table <= 1; table++) { // 計算索引值 idx = h & d->ht[table].sizemask; // 遍歷給定索引上的鏈表的所有節點，查找 key he = d->ht[table].table[idx]; // T = O(1) while(he) { if (dictCompareKeys(d, key, he->key)) return he; he = he->next; } // 如果程序遍歷完 0 號哈希表，仍然沒找到指定的鍵的節點 // 那么程序會檢查字典是否在進行 rehash ， // 然后才決定是直接返回 NULL ，還是繼續查找 1 號哈希表 if (!dictIsRehashing(d)) return NULL; } // 進行到這里時，說明兩個哈希表都沒找到 return NULL;}

dict的插入–dictAdd()和dictReplace()

dictAdd()插入新的一對key和value，如果key已經存在，則插入失敗。 dictReplace()也是插入一對key和value，不過在key存在的時候，它會更新value。添加鍵值對時，還需要考慮的是字典是否在rehash：

如果此時沒有進行rehash操作，直接計算出索引添加到ht[0]中如果此刻正在進行rehash操作，則根據ht[1]的參數計算出索引值，添加到ht[1]中//嘗試將給定鍵值對添加到字典中//只有給定鍵 key 不存在于字典時，添加操作才會成功//添加成功返回 DICT_OK ，失敗返回 DICT_ERR//最壞 T = O(N) ，平均 O(1) int dictAdd(dict *d, void *key, void *val){ // 嘗試添加鍵到字典，并返回包含了這個鍵的新哈希節點，T = O(N) dictEntry *entry = dictAddRaw(d,key); // 鍵已存在，添加失敗 if (!entry) return DICT_ERR; // 鍵不存在，設置節點的值，T = O(1) dictSetVal(d, entry, val); // 添加成功 return DICT_OK;}/* * 如果鍵已經在字典存在，那么返回 NULL * 如果鍵不存在，那么程序創建新的哈希節點， * 將節點和鍵關聯，并插入到字典，然后返回節點本身。 * T = O(N) */ dictEntry *dictAddRaw(dict *d, void *key){ int index; dictEntry *entry; dictht *ht; // 如果條件允許的話，進行單步 rehash，T = O(1) if (dictIsRehashing(d)) _dictRehashStep(d); // 計算鍵在哈希表中的索引值 // 如果值為 -1 ，那么表示鍵已經存在，T = O(N) if ((index = _dictKeyIndex(d, key)) == -1) return NULL; // 如果字典正在 rehash ，那么將新鍵添加到 1 號哈希表 // 否則，將新鍵添加到 0 號哈希表 ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0]; // 為新節點分配空間 entry = zmalloc(sizeof(*entry)); // 將新節點插入到鏈表表頭 entry->next = ht->table[index]; ht->table[index] = entry; // 更新哈希表已使用節點數量 ht->used++; // 設置新節點的鍵 // T = O(1) dictSetKey(d, entry, key); return entry;}/* * 將給定的鍵值對添加到字典中，如果鍵已經存在，那么刪除舊有的鍵值對。 * 如果鍵值對為全新添加，那么返回 1 。 * 如果鍵值對是通過對原有的鍵值對更新得來的，那么返回 0 。 * T = O(N) */ int dictReplace(dict *d, void *key, void *val){ dictEntry *entry, auxentry; // 嘗試直接將鍵值對添加到字典 // 如果鍵 key 不存在的話，添加會成功，T = O(N) if (dictAdd(d, key, val) == DICT_OK) return 1; // 運行到這里，說明鍵 key 已經存在，那么找出包含這個 key 的節點T = O(1) entry = dictFind(d, key); // 先保存原有的值的指針 auxentry = *entry; // 然后設置新的值，T = O(1) dictSetVal(d, entry, val); // 然后釋放舊值，T = O(1) dictFreeVal(d, &auxentry); return 0;}//_dictKeyIndex()：在dict中尋找插入位置，如果不在rehash過程中，它只查找ht[0]；否則查找ht[0]和ht[1]；//_dictKeyIndex()可能觸發dict內存擴展--_dictExpandIfNeeded()，詳見dict.c中源碼）。static int _dictKeyIndex(dict *d, const void *key){ unsigned int h, idx, table; dictEntry *he; // 單步 rehash if (_dictExpandIfNeeded(d) == DICT_ERR) return -1; // 計算 key 的哈希值 h = dictHashKey(d, key); for (table = 0; table <= 1; table++) { // 計算索引值 idx = h & d->ht[table].sizemask; // 查找 key 是否存在 he = d->ht[table].table[idx]; while(he) { if (dictCompareKeys(d, key, he->key)) return -1; he = he->next; } // 如果運行到這里時，說明 0 號哈希表中所有節點都不包含 key // 如果這時 rehahs 正在進行，那么繼續對 1 號哈希表進行 rehash if (!dictIsRehashing(d)) break; } // 返回索引值 return idx;}