字典

字典，又稱關(guān)聯(lián)數(shù)組或映射，是一種用于保存鍵值對(duì)的抽象數(shù)據(jù)結(jié)構(gòu)。在字典中，一個(gè)鍵key和一個(gè)值value進(jìn)行關(guān)聯(lián)；字典中的每個(gè)鍵都是獨(dú)一無(wú)二的。

字典的實(shí)現(xiàn)

redis的字典使用哈希表作為底層實(shí)現(xiàn)，一個(gè)哈希表可以有很多節(jié)點(diǎn)，而每個(gè)節(jié)點(diǎn)就保存了字典中的一個(gè)鍵值對(duì)。

哈希表

定義結(jié)構(gòu)如下：

typedef struct dictht {
    //哈希表數(shù)組
    dictEntry **table;
    //哈希表大小
    unsigned long size;
    //哈希表大小掩碼，用于計(jì)算索引值
    unsigned long sizemask
    //該哈希表已有的節(jié)點(diǎn)數(shù)量
    unsigned long used;
}dictht;

結(jié)構(gòu)示意圖如下：

哈希表

哈希表節(jié)點(diǎn)

哈希表節(jié)點(diǎn)使用dictEntry結(jié)構(gòu)表示，每個(gè)節(jié)點(diǎn)都保存著一個(gè)鍵值對(duì)：

typedef struct dictEntry {
    //鍵
    void *key;
    //值,可以是一個(gè)指針，uint64_t整數(shù)，int64_t整數(shù)
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    }v;
    //指向下一個(gè)哈希表節(jié)點(diǎn)，形成鏈表
    struct dictEntry *next;
}dictEntry;

結(jié)構(gòu)圖如下：

哈希表

字典

redis中的字典結(jié)構(gòu)如下：

typedef struct dict {
    //類型特定函數(shù)
    dictType *type;
   //私有數(shù)據(jù)
   void *privdata;
   //哈希表
   dictht ht[2];
   //rehash索引，不進(jìn)行rehash時(shí)，值為-1
   int trehashidx;
}

• [ ] type屬性是一個(gè)指向dictType結(jié)構(gòu)的指針，每個(gè)dictType保存了一組用于操作特定類型鍵值對(duì)的函數(shù)，redis會(huì)為用途不同的字典設(shè)置不同類型特定函數(shù)。
• [ ] privdata屬性，則保存了需要傳遞給那些類型特定函數(shù)的可選參數(shù)。

typedef struct dicType {
    //計(jì)算哈希值得函數(shù)
    unsigned int (*hashFunction) (const void *key);
    //復(fù)制鍵的函數(shù)
    void *(*keyDup) (void * privdata,const void *key);
    //復(fù)制值得函數(shù)
    void *(*valDup) (void *privdata,const void *obj);
    //對(duì)比鍵的函數(shù)
    int (*keyCompare) (void *privdata,const void *key1,const void key2)
    //銷毀鍵的函數(shù)
    int (*keyDestructor) (void *privdata,void *key);
    //銷毀值得函數(shù)
    void (*valDestructor) (void *privdata,void *obj);
}

普通狀態(tài)下的字典如圖所示：

字典結(jié)構(gòu)

ht是包含兩個(gè)項(xiàng)的數(shù)組，每個(gè)項(xiàng)都是一個(gè)哈希表，字典只用ht[0]哈希表，ht[1]哈希表只會(huì)在對(duì)ht[0]哈希表進(jìn)行rehash時(shí)使用。當(dāng)兩個(gè)及以上的鍵值對(duì)分配到了哈希數(shù)組中的同一個(gè)索引上，成為沖突，通過(guò)單鏈表的形式解決

哈希算法

當(dāng)要將一個(gè)新的鍵值對(duì)添加到字典里時(shí)，程序需要先根據(jù)鍵值對(duì)的鍵計(jì)算出哈希值和索引值，然后再根據(jù)索引值，將包含新鍵值對(duì)的哈希表節(jié)點(diǎn)放到哈希表數(shù)組的指定索引上面。

redis使用MurmurHah2算法來(lái)計(jì)算哈希值。

新節(jié)點(diǎn)總是在已有節(jié)點(diǎn)的前邊。

rehash

隨著操作的不斷執(zhí)行，哈希表的鍵值對(duì)會(huì)增加或者減少，為了讓負(fù)載因子維持在合理的范圍內(nèi)，哈希表需要擴(kuò)展或者收縮。

步驟如下：

1. 為字典的ht[1]哈希表分配空間，這個(gè)空間取決于要執(zhí)行的操作，以及ht[0]當(dāng)前包含的鍵值對(duì)數(shù)量。

• 如果是執(zhí)行擴(kuò)展操作，那么ht[1]的大小為：

ht [0].used*2^{n} + 1

• 如果執(zhí)行的是收縮操作，那么ht[1]的大小為：

ht [0].used*2^{n}

2. 將保存在ht[0]中ed所有鍵值對(duì)rehash到ht[1]中，rehash指的是重新計(jì)算哈希值和索引，然后將鍵值對(duì)放到哈希表指定的位置上。
3. 當(dāng)ht[0]遷移完之后，釋放ht[0]，將ht[1]的值設(shè)為ht[0]，并在ht[1]上創(chuàng)建一個(gè)空的哈希表，為下一次rehash做準(zhǔn)備。

漸進(jìn)式rehash

rehash操作不是一次性，集中式的完成，而是分多次漸進(jìn)式的完成的。在rehash期間，每對(duì)字典的添加，刪除，查找或者更新操作時(shí)，都會(huì)進(jìn)行rehash操作；在漸進(jìn)式rehash期間，新添加的鍵值對(duì)一律會(huì)添加到ht[1]中，而不對(duì)ht[0]進(jìn)行操作。

字典api