【Redis基本數據結構】字典實現

來自： https://segmentfault.com/a/1190000004850844

字典, 又稱為符號表 關聯數組或者映射,是一種保存鍵值對的抽象數據結構.字典作為一種常用數據結構被內置在許多程序語言中,由于 C 語言沒有內置這種數據結構, Redis 構建了自己的字典實現.

字典在 Redis 中的應用相當廣泛, 比如 Redis 的數據庫就是使用字典作為底層實現的, 對數據庫的 增刪改查操作也是構建在對字典的操作之上的.

除了用作數據庫之外, 字典還是哈希鍵的底層之一, 當一個哈希鍵包含的鍵值對較多,歐哲鍵值對中的元素都是比較長的字符串時, Redis 就會使用字典作為哈希鍵的底層實現.

字典的實現

哈希表

Redis 字典所使用的哈希表由 dict.h/dictht 結構定義:

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

• table 屬性是一個數組, 數組中每個元素都是一個指向 dictEntry 結構的指針, 每個 dictEntry 結構保存著一個鍵值對.

• size 屬性記錄了哈希表的大小,也就是 table 數組的大小

• sizemask 屬性和哈希值一起決定一個鍵應該被放到 table 數組的哪個索引上面

哈希表節點

哈希表節點使用 dictEntry 表示,每個 dictEntry 結構保存著一個鍵值對

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

• 注意這里 v 屬性保存著鍵值對中的值,其中的鍵值可以是指針,或是 uint_64 整數,又或者是 int64_t 整數.

• next 屬性是指向另一個哈希表節點的指針,這個指針將多個哈希值相同的鍵值對連接在一起,以此來解決鍵值沖突(collision)問題.

字典

Redis 中的字典 由 dict.h/dict 結構表示:

typedef struct dict {
    dictType *type;     //類型特定函數
    void *privdata;     //私有數據
    dictht ht[2];       //哈希表
    int rehashdx;      //rehash 索引,當 rehash 不在進行時,值為-1
} dict;

• type 和 privdata 是針對不同類型的鍵值對,為創建多態字典而設置的

  `type`指向一個 `dictType` 結構的指針, 每個` dictType` 結構保存了一簇用于操作特作特定類型鍵值對的函數, Redis 會為用途不同的字典設置不同的類型特定函數.
  
  而` pridata` 則保存了需要傳給那些特定類型函數看可選參數.

• ht 屬性,包含兩個數組,數組的每一項都是一個 dictht 哈希表,一般情況下字典只使用 ht[0] 哈希表, ht[1] 哈希表只會在對哈希表進行 rehash 時使用.

• rehashidex 記錄了 rehash 當前的進度,如果沒有進行 rehash, 值就為-1.

下圖展示了一個普通狀態下的字典(沒有 rehash 進行)

哈希算法

當要將一個新的鍵值對添加到字典里面時,程序會根據鍵計算出哈希值和索引值,然后再根據索引值,將包含新鍵值對的哈希表節點放到哈希表數組的指定索引上.Redis 計算哈希值和索引的方法如下:

hash = dict->type->hashFunction(k);
index = hash & dict->ht[0].sizemask 

假設,要將上圖中鍵值對 k1和v1添加到字典中,使用 hashFunction 計算出 k1 的哈希值為9,那么

index = 9 & 3 = 1;

Redis 使用 MurmurHash2 算法 來計算鍵的哈希值.

解決鍵沖突

當有兩個或兩個以上的鍵被分配到了哈希表數組的同一索引上時,稱這些鍵發生了沖突( collision )

Redis 的哈希表使用鏈地址法來解決沖突,每個哈希表節點都有一個 next 指針,多個哈希表節點可以用 next 指針構成一個單項鏈表,被分配到同一個索引上的多個節點可以用這個對單向鏈表連接起來,這就解決了鍵沖突的問題.

如前面的字典示意圖所示, 鍵 k0 和 k1 的索引值均為1,這里只需用 next 指針將兩個節點連接起來.

,因為 dictEntry 節點組成的鏈表沒有表尾指針,為了 速度考慮,程序總是將新節點調價到鏈表的表頭位置,排在其他已有節點的前面,這樣插入的復雜度為$ O(1)$.

Rehash

隨著操作的不斷進行, 哈希表保存的鍵值對會逐漸地增多或減少,為了讓哈希表的負載因子維持在一個合理的范圍之內,當哈希表保存的鍵值對數量太多或者太少時, 程序需要對哈希表的大小進行相應的擴展或者收縮.這個過程叫做 rehash .

Redis 對字典的哈希表執行 rehash 的步驟如下:

1. 為字典的 ht[1] 哈希表分配空間,空間的大小取決于要執行的操作,以及 ht0] 當前包含的鍵值對數量( used 屬性值):

• 如果執行的是擴展操作,那么 ht[1] 的大小為第一個大于等于 ht0].used*2 的 $2^n$ .

• 如果執行的是收縮操作,那么 ht[1] 的大小為打一個大于等于 ht[0].used 的$2^n$.

1. 將保存在 ht[0] 中所有鍵值對 rehash 到 ht[1] 上面: 任何事指的是重新計算鍵的哈希值和索引值,然后鍵鍵值對放到 ht[1] 哈希表的指定位置.

2. 當 ht[0] 包含的所有鍵值對都遷移到了 ht[1] 之后, 釋放 ht[0] , 再將 ht[1] 設置為 ht[0] ,并在 ht[1] 后面創建一個空白的哈希表.

舉個例子,假設程序要對下圖的 `ht[0] 進行擴展操作

1. ht[0].used 當前值為4 , $2^3$ 恰好是第一個大于等于 4*2 的值,所以 ht[1] 哈希表的大小設置為8,下圖展示了 ht[1] 分配了空間之后字典的樣子.

   ![此處輸入圖片的描述][4]
   

2. 將 ht[0] 包含的四個鍵值對 rehash 到 ht[1], 圖下圖所示:

   ![此處輸入圖片的描述][5]
   

3. 釋放 ht[0], 將 ht[1] 設置為 ht[0]. 再分配一個空哈希表. 哈希表的大小由原來的4 擴展至8.

   ![此處輸入圖片的描述][6]
   

漸進式 rehash

上一節說過, 擴展或收縮哈希表需要將 ht[0] 里的所有鍵值對 rehash 到 ht[1] 中,但是這個 rehash

動作并不是一次性,集中式完成的,而是分多次,漸進式完成的.

這么做的原因是,當哈希表里保存的鍵值對多至百萬甚至億級別時,一次性地全部 rehash 的話,龐大的計算量會對服務器性能造成嚴重影響.

以下是漸進式 rehash 的步驟:

1. 為 ht[1] 分配空間

2. 在字典中維持一個索引計數器變量 rehashidx , 將它的值設置為0,表示 rehash 正式開始

3. 在 rehash 進行期間,每次對字典進行增刪改查時,順帶將 ht[0] 在 rehashidx 索引上的所有鍵值對 rehash 到 ht[1] 中,同時將 rehashidx 加 1.

4. 隨著操作不斷進行,最終在某個時間點上, ht[0] 所有的鍵值對全部 rehash 到 ht[1] 上,這是講 rehashidx 屬性置為 -1,,表示 rehash操作完成.

在漸進式 rehash 執行期間,新添加到字典的鍵值對一律保存到 ht[1] 里,不會對 ht[0] 做添加操作,這一措施保證了 ht[0] 只減不增,并隨著 rehash 進行, 最終編程空表.

漸進式的 rehash 避免了集中式 rehash 帶來 的龐大計算量和內存操作.