快捷導航

Redis底層數(shù)據(jù)結(jié)構(gòu)之字典(Dict)的實現(xiàn)

更新時間：2025年06月06日 08:54:35 作者：碼農(nóng)開荒路

本文主要介紹了Redis底層數(shù)據(jù)結(jié)構(gòu)之字典(Dict)的實現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧

Dict基本結(jié)構(gòu)

Dict我們可以想象成目錄，要翻看什么內(nèi)容，直接通過目錄能找到頁數(shù)，翻過去看。如果沒有目錄，我們需要一頁一頁往后翻，這樣時間復雜度就與遍歷的O(n)一樣了，而用了Dict我們就可以在O(1)的時間復雜度內(nèi)快速找到鍵對應(yīng)的值。說到這里，大家會覺得Dict與JAVA中的哈希表功能差不多，其實，Redis的Dict數(shù)據(jù)結(jié)構(gòu)底層實現(xiàn)正是哈希表，不過維護了2個哈希表。Redis實現(xiàn)Dict數(shù)據(jù)結(jié)構(gòu)創(chuàng)建了三個重要的結(jié)構(gòu)體，分別是dict、dictht和dictEntry。下面先給出Dict的整體結(jié)構(gòu)幫助大家更好的理解一下：

dict

typedef struct dict{
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx;
    unsigned long iterators;
} dict;

ht[2]：表示在一個Dict結(jié)構(gòu)中，包含有兩個dictht的結(jié)構(gòu)，也就是我們說的兩張哈希表。
rehashidx：是dict在rehash時的偏移索引，具體如何工作在后邊的rehash過程中會詳細講。

dictht

typedef struct dictht{
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
}dictht

table：指向?qū)嶋Hhash存儲。存儲可以看做是一個數(shù)組，所以是*table表示。（源碼中的**table是一個二級指針，也就是指向dictEntry*的指針）。
size：哈希表的大小。實際就是dictEntry有多少元素空間。
sizemask：哈希表大小的掩碼表示，總是等于size-1.這個屬性和哈希值一起決定一個鍵應(yīng)該被放到table數(shù)組的哪個索引上面，索引計算規(guī)則是index=hash&sizemask，前提是size的大小是二次方冪，這一點與JAVA哈希表底層計算索引是一樣的原理。
used：表示已經(jīng)使用的節(jié)點數(shù)量。通過這個字段可以很方便地查詢到目前dict元素總量。

dictEntry

typedef struct dictEntry{
     void *key;
     union{
          void *val;
          uint64_tu64;
          int64_ts64;
     }v;
     struct dictEntry *next;
}dictEntry

*key：存儲鍵。
v：用來存儲具體的值，可以看到，值可以是一個指針，可以是uint64_t整數(shù)，也可以是int64_t整數(shù)。
*next：用于采用拉鏈法將相同索引的dictEntry串起來，解決哈希沖突問題。（采用的是頭插法，JAVA中JDK8之后采用的是尾插法，留個小問題，為什么JAVA中不延續(xù)使用頭插法？）

Dict的漸進式擴容機制

想必大家有一個疑問，為什么Dict底層要維護兩張哈希表，實際存儲的話使用一張哈希表不就可以了嗎。其實，第二張哈希表的存在是為了給第一張哈希表的擴容提供支持。下面我們來詳細介紹一下Dict中哈希表的漸進式擴容流程和擴容時機。

Dict漸進式擴容流程

首先，當向字典添加新元素時，發(fā)現(xiàn)第一張哈希表ht[0]需要擴容，就會進行rehash操作，為第二張哈希表ht[1]分配空間。ht[1]表的大小為大于等于ht[0]表used值的2倍的2次方冪。舉個例子，如果ht[0]中已經(jīng)使用的節(jié)點數(shù)量為500，那么擴容時ht[1]被分配的空間是1024而不是1000。這么做是為了維護擴容后表的大小始終是2次方冪。

接著，dict的rehashidx由靜默狀態(tài)（-1）變?yōu)殚_始工作狀態(tài)（0）。

最后，遷移ht[0]中的數(shù)據(jù)到ht[1]，也就是將數(shù)據(jù)從舊表中遷移到新表中。在rehash進行期間，每次對dict執(zhí)行增刪改查操作，程序會順帶遷移當前rehashidx在ht[0]上對應(yīng)的數(shù)據(jù)，并更新偏移索引。與此同時，部分情況周期函數(shù)也會進行遷移。如果rehashidx剛好在一個已刪除的空位置上，那么是直接返回還是嘗試往下找？我們來看一下dictRehash函數(shù)的源碼：

//int empty_visits = n*10;//Max number of empty buckets to visit.

while(d->ht[0].table[d->rehashidx] == NULL) {
    d->rehashidx++;
    if (--empty_visits == 0) return 1;
}

可以看到，答案是會繼續(xù)往下去找，但是有個上限是n*10，即最多再找這么多次，n是傳進來的參數(shù)，調(diào)用的時候?qū)嶋H值為1，即最多往后再找10個，這么做是防止因為連續(xù)碰到空位置導致主線程操作被阻塞。

隨著字典操作的不斷執(zhí)行，最終在某個時間點上，ht[0]的所有鍵值對都會被rehash到ht[1]，此時再將ht[1]和ht[0]指針對象互換，同時將rehashidx設(shè)置為-1，表示rehash工作已經(jīng)完成。這個事情也是在rehash函數(shù)做的，每次遷移完一個元素，會檢查是否已經(jīng)完成了整個遷移：

if (d->ht[0].used == 0) {
    zfree(d->ht[0].table);
    d->ht[0] = d->ht[1];
    _dictReset(&d->ht[1]);
    d->rehashidx = -1;
    return 0;
}

總結(jié)一下，漸進式擴容的核心就是刪改查操作時順帶遷移，其中增的操作直接增到新表中。

Dict漸進式擴容時機

Redis提出了一個負載因子的概念（與JAVA中的負載因子不同），用于表示目前Dict的使用情況，是情況良好還是已經(jīng)堵塞不堪。設(shè)負載椅子為F，那么負載因子計算公式為F=ht[0].used/ht[0].size,也就是使用空間大小和總空間大小的比值。Redis會根據(jù)負載因子的情況來進行擴容。

當負載因子的值小于1時，認為dict的使用情況良好，不需要進行擴容。

當負載因子的值大于等于1時，說明此時的dict空間已經(jīng)非常緊張了，新增的數(shù)據(jù)會發(fā)生哈希沖突在鏈表上堆疊。如果此時服務(wù)器沒有執(zhí)行BGSAVE或者BGREWRITEAOF這兩個復制命令，就會立刻進行擴容，反之則不會立刻擴容。

當負載因子的值大于5時，說明此時的dict中哈希沖突已經(jīng)非常嚴重了，哈希表的搜索性能嚴重退化向鏈表。此時不管服務(wù)器是否在執(zhí)行復制命令，都會立刻對哈希表進行擴容操作。

Dict為什么采用漸進式擴容機制？

在JAVA中，哈希表其實也有擴容操作，并且是在單張表上完成的rehash操作。但是對于Redis中的Dict來說，兩者存放的數(shù)據(jù)量不在一個量級上，由于Redis是單線程的，如果對dict中存放的大量數(shù)據(jù)進行一次性rehash，那么耗費的時間會非常久，從而造成主線程的長時間阻塞。為了性能考慮，Dict采用空間換時間的方法，多花費一張表的空間，配合漸進式擴容機制，幾乎完全消除rehash可能造成的主線程阻塞。