国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專(zhuān)欄INFORMATION COLUMN

跟著大彬讀源碼 - Redis 8 - 對(duì)象編碼之字典

kun_jian / 2348人閱讀

摘要:屬性記錄了哈希表目前已有節(jié)點(diǎn)鍵值對(duì)的數(shù)量。字典字典的結(jié)構(gòu)類(lèi)型特定函數(shù)私有數(shù)據(jù)哈希表兩個(gè)記錄進(jìn)度的標(biāo)志。此外,字典在進(jìn)行時(shí),刪除查找更新等操作會(huì)在兩個(gè)哈希表上進(jìn)行。在對(duì)哈希表進(jìn)行擴(kuò)容或收縮操作時(shí),使用漸進(jìn)式完成。

字典,是一種用于保存鍵值對(duì)的抽象數(shù)據(jù)結(jié)構(gòu)。由于 C 語(yǔ)言沒(méi)有內(nèi)置字典這種數(shù)據(jù)結(jié)構(gòu),因此 Redis 構(gòu)建了自己的字典實(shí)現(xiàn)。

在 Redis 中,就是使用字典來(lái)實(shí)現(xiàn)數(shù)據(jù)庫(kù)底層的。對(duì)數(shù)據(jù)庫(kù)的 CURD 操作也是構(gòu)建在對(duì)字典的操作之上。

除了用來(lái)表示數(shù)據(jù)庫(kù)之外,字典還是哈希鍵的底層實(shí)現(xiàn)之一。當(dāng)一個(gè)哈希鍵包含的鍵值對(duì)比較多,又或者鍵值對(duì)中的元素都是比較長(zhǎng)的字符串時(shí),Redis 就會(huì)適應(yīng)字典作為哈希鍵的底層實(shí)現(xiàn)。

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

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

1.1 哈希表

Redis 字典所使用的哈希表結(jié)構(gòu):

typedef struct dictht {
    dictEntry **table;      // 哈希表數(shù)組
    unsigned long size;     // 哈希表大小
    unsigned long sizemask; // 哈希表大小掩碼,用來(lái)計(jì)算索引
    unsigned long used;     // 哈希表現(xiàn)有節(jié)點(diǎn)的數(shù)量
} dictht;

table 屬性是一個(gè)數(shù)組。數(shù)組中的每個(gè)元素都是一個(gè)指向 dictEntry 結(jié)構(gòu)的指針,每個(gè) dictEntry 結(jié)構(gòu)保存著一個(gè)鍵值對(duì)。

size 屬性記錄了哈希表的大小,也即是 table 數(shù)組的大小。

used 屬性記錄了哈希表目前已有節(jié)點(diǎn)(鍵值對(duì))的數(shù)量。

sizemask 屬性的值總數(shù)等于 size-1,這個(gè)屬性和哈希值一起決定一個(gè)鍵應(yīng)該被放到 table 數(shù)組中哪個(gè)索引上。

圖 1 展示了一個(gè)大小為 4 的空哈希表。

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

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

typedef struct dictEntry {
    void *key;              // 鍵
    union {
        void *val;          // 值類(lèi)型之指針
        uint64_t u64;       // 值類(lèi)型之無(wú)符號(hào)整型
        int64_t s64;        // 值類(lèi)型之有符號(hào)整型
        double d;           // 值類(lèi)型之浮點(diǎn)型
    } v;                    // 值
    struct dictEntry *next; // 指向下個(gè)哈希表節(jié)點(diǎn),形成鏈表
} dictEntry;

key 屬性保存著鍵,而 v 屬性則保存著值。

next 屬性是指向另一個(gè)哈希表節(jié)點(diǎn)的指針。這個(gè)指針可以將多個(gè)哈希值相同的鍵值對(duì)連接在一起,以此來(lái)解決鍵沖突的問(wèn)題。

圖 2 展示了通過(guò) next 指針,將兩個(gè)索引相同的鍵 k1 和 k0 連接在一起的情況。

1.3 字典

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

typedef struct dict {
    dictType *type; // 類(lèi)型特定函數(shù)
    void *privdata; // 私有數(shù)據(jù)
    dictht ht[2];   // 哈希表(兩個(gè))
    long rehashidx; // 記錄 rehash 進(jìn)度的標(biāo)志。值為 -1 表示 rehash 未進(jìn)行
    int iterators;  // 當(dāng)前正在迭代的迭代器數(shù)
} dict;

dictType 的結(jié)構(gòu)如下:

typedef struct dictType {
    // 計(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);
    // 銷(xiāo)毀鍵的函數(shù)
    void (*keyDestructor)(void *privdata, void *key);
    // 銷(xiāo)毀值的函數(shù)
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

type 屬性和 privdata 屬性是針對(duì)不同類(lèi)型的鍵值對(duì),為創(chuàng)建多態(tài)字典而設(shè)置的。其中:

type 屬性是一個(gè)指向 dictType 結(jié)構(gòu)的指針,每個(gè) dictType 結(jié)構(gòu)保存了一簇用于操作特定類(lèi)型鍵值對(duì)的函數(shù)。Redis 會(huì)為用途不用的字典設(shè)置不同的類(lèi)型特定函數(shù)。

privdata 屬性保存了需要傳給那些類(lèi)型特定函數(shù)的可選參數(shù)。

而 ht 屬性是一個(gè)包含兩個(gè)哈希表的數(shù)組。一般情況下,字典只使用 ht[0],只有在對(duì) ht[0] 進(jìn)行 rehash 時(shí)才會(huì)使用 ht[1]。

rehashidx 屬性,它記錄了 rehash 目前的進(jìn)度,如果當(dāng)前沒(méi)有進(jìn)行 rehash,它的值為 -1。至于什么是 rehash,別急,后面會(huì)詳細(xì)說(shuō)明。

圖 3 是沒(méi)有進(jìn)行 rehash 的字典:

2 插入算法

當(dāng)在字典中添加一個(gè)新的鍵值對(duì)時(shí),Redis 會(huì)先根據(jù)鍵值對(duì)的鍵計(jì)算出哈希值和索引值,然后再根據(jù)索引值,將包含新鍵值對(duì)的哈希表節(jié)點(diǎn)放到哈希表數(shù)組指定的索引上。具體算法如下:

# 使用字典設(shè)置的哈希函數(shù),計(jì)算 key 的哈希值
hash = dict->type->hashFunction(key);
# 使用哈希表的 sizemask 屬性和哈希值,計(jì)算出索引值
# 根據(jù)不同情況,使用 ht[0] 或 ht[1]
index = hash & dict[x].sizemask;


如圖 4,如果把鍵值對(duì) [k0, v0] 添加到字典中,插入順序如下:

hash = dict-type->hashFunction(k0);
index = hash & dict->ht[0].sizemask; # 8 & 3 = 0

計(jì)算得出,[k0, v0] 鍵值對(duì)應(yīng)該被放在哈希表數(shù)組索引為 0 的位置上,如圖 5:

2.1 鍵沖突

當(dāng)有兩個(gè)或以上數(shù)量的鍵被分配到了哈希表數(shù)組的同一個(gè)索引上面時(shí),我們認(rèn)為這些鍵發(fā)生了建沖突

Redis 的哈希表使用鏈地址法來(lái)解決建沖突。每個(gè)哈希表節(jié)點(diǎn)都有一個(gè) next 指針,多個(gè)哈希表節(jié)點(diǎn)可以用 next 指針構(gòu)成一個(gè)單向鏈表,被分配到同一個(gè)索引的多個(gè)節(jié)點(diǎn)用 next 指針鏈接成一個(gè)單向鏈表。

舉個(gè)栗子,假設(shè)我們要把 [k2, v2] 鍵值對(duì)添加到圖 6 所示的哈希表中,并且計(jì)算得出 k2 的索引值為 2,和 k1 沖突,因此,這里就用 next 指針將 k2 和 k1 所在的節(jié)點(diǎn)連接起來(lái),如圖 7。

3 rehash 與 漸進(jìn)式 rehash

隨著對(duì)字典的操作,哈希表報(bào)錯(cuò)的鍵值對(duì)會(huì)逐漸增多或者減少,為了讓哈希表的負(fù)載因子維持在一個(gè)合理的范圍之內(nèi),當(dāng)哈希表報(bào)錯(cuò)的鍵值對(duì)數(shù)量太多或者太少時(shí),程序需要對(duì)哈希表進(jìn)行相應(yīng)的擴(kuò)容或收縮。這個(gè)擴(kuò)容或收縮的過(guò)程,我們稱(chēng)之為 rehash。

對(duì)于負(fù)載因子,可以通過(guò)以下公式計(jì)算得出:

# 負(fù)載因子 = 哈希表已保存節(jié)點(diǎn)數(shù)量 / 哈希表大小
load_factor = ht[0].used / ht[0].size;
3.1 哈希表的擴(kuò)容與收縮

擴(kuò)容

對(duì)于哈希表的擴(kuò)容,源碼如下:

if (d->ht[0].used >= d->ht[0].size &&
    (dict_can_resize ||
     d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
{
    return dictExpand(d, d->ht[0].used*2);
}

當(dāng)以下條件被滿(mǎn)足時(shí),程序會(huì)自動(dòng)開(kāi)始對(duì)哈希表執(zhí)行擴(kuò)展操作:

服務(wù)器當(dāng)前沒(méi)有進(jìn)行 rehash;

哈希表已保存節(jié)點(diǎn)數(shù)量大于哈希表大小;

dict_can_resize 參數(shù)為 1,或者負(fù)載因子大于設(shè)定的比率(默認(rèn)為 5);

收縮

哈希表的收縮,源碼如下:

int htNeedsResize(dict *dict) {
    long long size, used;
    size = dictSlots(dict); // ht[2] 兩個(gè)哈希表的大小之和
    used = dictSize(dict);  // ht[2] 兩個(gè)哈希表已保存節(jié)點(diǎn)數(shù)量之和
    # DICT_HT_INITIAL_SIZE 默認(rèn)為 4,HASHTABLE_MIN_FILL 默認(rèn)為 10。
    return (size > DICT_HT_INITIAL_SIZE &&
            (used*100/size < HASHTABLE_MIN_FILL));
}
void tryResizeHashTables(int dbid) {
    if (htNeedsResize(server.db[dbid].dict))
        dictResize(server.db[dbid].dict);
    if (htNeedsResize(server.db[dbid].expires))
        dictResize(server.db[dbid].expires);
}

當(dāng) ht[] 哈希表的大小之和大于 DICT_HT_INITIAL_SIZE(默認(rèn) 4),且已保存節(jié)點(diǎn)數(shù)量與總大小之比小于 4,HASHTABLE_MIN_FILL(默認(rèn) 10,也就是 10%),會(huì)對(duì)哈希表進(jìn)行收縮操作。

3.2 rehash

擴(kuò)容和收縮哈希表都是通過(guò)執(zhí)行 rehash 操作來(lái)完成,哈希表執(zhí)行 rehash 的步驟如下:

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

如果執(zhí)行的是擴(kuò)容操作,那么 ht[1] 的大小為**第一個(gè)大于等于 ht[0].usedx2 的 2^n。

如果執(zhí)行的是收縮操作,那么 ht[1] 的大小為第一個(gè)大于等于 ht[0].used 的 2^n。

將保存在 ht[0] 中的所有鍵值對(duì) rehash 到 ht[1] 上面:rehash 指的是重新計(jì)算鍵的哈希值和索引值,然后將鍵值對(duì)都遷移到 ht[1] 哈希表的指定位置上。

當(dāng) ht[0] 包含的所有鍵值對(duì)都遷移到 ht[1] 后,此時(shí) ht[0] 變成空表,釋放 ht[0],將 ht[1] 設(shè)置為 ht[0],并在 ht[1] 新創(chuàng)建一個(gè)空白哈希表,為下一次 rehash 做準(zhǔn)備。

示例:


假設(shè)程序要對(duì)圖 8 所示字典的 ht[0] 進(jìn)行擴(kuò)展操作,那么程序?qū)?zhí)行以下步驟:
1)ht[0].used 當(dāng)前的值為 4,那么 4*2 = 8,而 2^3 恰好是第一個(gè)大于等于 8 的,2 的 n 次方。所以程序會(huì)將 ht[1] 哈希表的大小設(shè)置為 8。圖 9 是 ht[1] 在分配空間之后的字典。

2)將 ht[0] 包含的四個(gè)鍵值對(duì)都 rehash 到 ht[1],如圖 10。

3)釋放 ht[0],并將 ht[1] 設(shè)置為 ht[0],然后為 ht[1] 分配一個(gè)空白哈希表。如圖 11:

至此,對(duì)哈希表的擴(kuò)容操作執(zhí)行完畢,程序成功將哈希表的大小從原來(lái)的 4 改為了 8。

3.3 漸進(jìn)式 rehash

對(duì)于 Redis 的 rehash 而言,并不是一次性、集中式的完成,而是分多次、漸進(jìn)式地完成,所以也叫漸進(jìn)式 rehash

之所以采用漸進(jìn)式的方式,其實(shí)也很好理解。當(dāng)哈希表里保存了大量的鍵值對(duì),要一次性的將所有鍵值對(duì)全部 rehash 到 ht[1] 里,很可能會(huì)導(dǎo)致服務(wù)器在一段時(shí)間內(nèi)只能進(jìn)行 rehash,不能對(duì)外提供服務(wù)。

因此,為了避免 rehash 對(duì)服務(wù)器性能造成影響,Redis 分多次、漸進(jìn)式的將 ht[0] 里面的鍵值對(duì) rehash 到 ht[1]。

漸進(jìn)式 rehash 就用到了索引計(jì)數(shù)器變量 rehashidx,詳細(xì)步驟如下:

為 ht[1] 分配空間,讓字典同時(shí)持有 ht[0] 和 ht[1] 兩個(gè)哈希表。

在字段中維持一個(gè)索引計(jì)數(shù)器變量 rehashidx,并將它的值設(shè)置為 0,表示開(kāi)始 rehash。

在 rehash 期間,每次對(duì)字典執(zhí)行 CURD 操作時(shí),程序除了執(zhí)行指定的操作外,還會(huì)將 ht[0] 哈希表在 rehashidx 索引上的所有鍵值對(duì)移動(dòng)到 ht[1],當(dāng) rehash 完成后,程序?qū)?rehashidx 的值加一。

隨著不斷操作字典,最終在某個(gè)時(shí)間點(diǎn)上,ht[0] 的所有鍵值對(duì)都會(huì)被 rehash 到 ht[1],這時(shí)程序?qū)?rehashidx 屬性的值設(shè)為 -1,表示 rehash 已完成。

漸進(jìn)式 rehash 才有分而治之的方式,將 rehash 鍵值對(duì)所需要的計(jì)算工作均攤到對(duì)字典的 CURD 操作上,從而避免了集中式 rehash 帶來(lái)的問(wèn)題。

此外,字典在進(jìn)行 rehash 時(shí),刪除、查找、更新等操作會(huì)在兩個(gè)哈希表上進(jìn)行。例如,在字典張查找一個(gè)鍵,程序會(huì)現(xiàn)在 ht[0] 里面進(jìn)行查找,如果沒(méi)找到,再去 ht[1] 上查找。

要注意的是,新增的鍵值對(duì)一律只保存在 ht[1] 里,不在對(duì) ht[0] 進(jìn)行任何添加操作,保證了 ht[0] 包含的鍵值對(duì)數(shù)量只減不增,隨著 rehash 操作最終變成空表。

圖 12 至 圖 17 展示了一次完整的漸進(jìn)式 rehash 過(guò)程:

1)未進(jìn)行 rehash 的字典

2) rehash 索引 0 上的鍵值對(duì)

3)rehash 索引 1 上的鍵值對(duì)

4)rehash 索引 2 上的鍵值對(duì)

5)rehash 索引 3 上的鍵值對(duì)

6)rehash 執(zhí)行完畢

總結(jié)

字段被廣泛用于實(shí)現(xiàn) Redis 的各種功能,其中包括數(shù)據(jù)庫(kù)和哈希鍵。

Redis 中的字典使用哈希表作為底層實(shí)現(xiàn),每個(gè)字典帶有兩個(gè)哈希表,一個(gè)平時(shí)使用,一個(gè)僅在 rehash 時(shí)使用。

哈希表使用鏈地址法來(lái)解決鍵沖突,被分配到同一個(gè)索引上的多個(gè)鍵值對(duì)會(huì)連接成一個(gè)單向鏈表。

在對(duì)哈希表進(jìn)行擴(kuò)容或收縮操作時(shí),使用漸進(jìn)式完成 rehash。

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/62129.html

相關(guān)文章

  • 跟著彬讀源碼 - Redis 6 - 對(duì)象和數(shù)據(jù)類(lèi)型(下)

    摘要:哈希對(duì)象哈希對(duì)象的可選編碼分別是和。編碼的哈希對(duì)象編碼的哈希對(duì)象使用壓縮列表作為底層實(shí)現(xiàn)。關(guān)于哈希編碼轉(zhuǎn)換的函數(shù),可以參考,源碼如下是原始對(duì)象,是目標(biāo)編碼。對(duì)應(yīng)源碼如下對(duì)象元素?cái)?shù)量為,或者總結(jié)哈希對(duì)象有和編碼。 繼續(xù)擼我們的對(duì)象和數(shù)據(jù)類(lèi)型。 上節(jié)我們一起認(rèn)識(shí)了字符串和列表,接下來(lái)還有哈希、集合和有序集合。 1 哈希對(duì)象 哈希對(duì)象的可選編碼分別是:ziplist 和 hashtable。...

    YFan 評(píng)論0 收藏0
  • 跟著彬讀源碼 - Redis 5 - 對(duì)象和數(shù)據(jù)類(lèi)型(上)

    摘要:對(duì)象源碼結(jié)構(gòu)如下對(duì)象類(lèi)型對(duì)象編碼引用統(tǒng)計(jì)指向底層實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)的指針字段對(duì)象類(lèi)型,就是我們常說(shuō)的。。對(duì)象編碼對(duì)應(yīng)跳躍表壓縮列表集合動(dòng)態(tài)字符串等八種底層數(shù)據(jù)結(jié)構(gòu)。 相信很多人應(yīng)該都知道 Redis 有五種數(shù)據(jù)類(lèi)型:字符串、列表、哈希、集合和有序集合。但這五種數(shù)據(jù)類(lèi)型是什么含義?Redis 的數(shù)據(jù)又是怎樣存儲(chǔ)的?今天我們一起來(lái)認(rèn)識(shí)下 Redis 這五種數(shù)據(jù)結(jié)構(gòu)的含義及其底層實(shí)現(xiàn)。 首先要明確...

    antz 評(píng)論0 收藏0
  • 跟著彬讀源碼 - Redis 7 - 對(duì)象編碼簡(jiǎn)單動(dòng)態(tài)字符串

    摘要:沒(méi)有直接使用語(yǔ)言傳統(tǒng)的字符串表示以空字符串結(jié)尾的字符數(shù)組,而是構(gòu)建了一種名為簡(jiǎn)單動(dòng)態(tài)字符串的抽象類(lèi)型,并將用作的默認(rèn)字符串表示。對(duì)比字符串,有幾大優(yōu)點(diǎn)常數(shù)復(fù)雜度獲取字符串長(zhǎng)度杜絕緩沖區(qū)溢出減少修改字符串時(shí)所需的內(nèi)存重分配次數(shù)。 Redis 沒(méi)有直接使用 C 語(yǔ)言傳統(tǒng)的字符串表示(以空字符串結(jié)尾的字符數(shù)組),而是構(gòu)建了一種名為簡(jiǎn)單動(dòng)態(tài)字符串(simple dynamic string)的...

    baishancloud 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<