Redis學習筆記（三） 字典

Redis的字典使用哈希表作為底層實現，一個哈希表中可以有多個哈希表節點，而每個哈希節點就保存在字典中的一個鍵值對。

redis字典所用的哈希表由disht結構定義。

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

table 屬性是一個數組，數組中的每個元素都是一個指向dictEntry結構的指針，每個dictEntry結構保存著一個鍵值對。其他的屬性不多說。

哈希表節點

哈希表節點使用dictEntry結構標識，每個dictEntry保存一個鍵值對。

typedef struct dictEntry{
    void *key;//鍵
    union{
    void *val;
    uint64_tu64'
    int64_ts64'
    } v;//值
    struct dictEntry *next;//指向下個哈希節點，形成鏈表
} ductEntry;

*next 屬性是指向另一個哈希表節點的指針，這個指針可以將多個哈希值相同的鍵值對連接在一起，解決鍵衝突的問題。所以，每一個哈希索引為一個單向鏈表。

Redis中的字典由dict結構表示：

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

Redis計算哈希值和索引值的方法：

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

解決鍵衝突：

當兩個或兩個一個數量的鍵被分配到了哈希表數組的同一個索引上面時，為我們稱作這些鍵發生衝突。Redis的哈希表使用鏈地址法來解決衝突，每個哈希表節點的next指針構成了一個單向鏈表，以此來解決鍵衝突。

另外由於鏈表沒有指向鏈表結尾的指針，為考慮速度，每次將新加的節點放到鏈表表頭位置（複雜度為O(1)）。

Rehash

隨著哈希表保存的鍵增多或減少，為了讓哈希表的負載因數維持在一個合理的範圍內，程式會對哈希表的小小進行rehash（重新散列）。

    1、為字典表的ht[1]哈希表分配空間，這個哈希表的空間大小取決於要執行的操作以及ht[0]包含的鍵值對數量

        （1）如果執行擴展，ht[1] =第一個>=ht[0].used * 2 的2的n次方冪。

        （2）如果收縮 ht[1] = 第一個>=ht[0].used 的2的n次方冪

    2、h[0] 遷移至h[1]。

    3、清空h[0]，將h[1]設置為h[0]，新建h[1]。

漸進式rehash 

字典表同時使用ht[0],ht[1],ht[0]通過索引計數器分批量的遷移至ht[1]，為解決ht[0]所持有的鍵值對量太大的問題。

不為別的，每天學一點，總會有收穫。

說明：尊重作者知識產權，文中內容參考《Redis設計與實現》，僅在此做學習與大家分享。