在线观看的黄色小视频,主播大秀一区二区三区,一区二区三区免费播放,色欲一区,美利坚一区二区三区,欧美亚黄片,色婷婷亚洲一,欧美日本在线

字典，又稱映射，是一種用于保存鍵值對(duì)的抽象數(shù)據(jù)結(jié)構(gòu)。在 Redis 中，字典得到了廣泛的使用，比如 Redis 的數(shù)據(jù)庫(kù)就是使用字典來(lái)作為底層實(shí)現(xiàn)的

Redis 中的字典有 dict.h/dict 結(jié)構(gòu)表示，如下：

typedefstruct dict {
// 類型特定函數(shù)
// type里面主要記錄了一系列的函數(shù),可以說(shuō)是規(guī)定了一系列的接口
    dictType *type;

// 私有數(shù)據(jù)
// privdata保存了需要傳遞給那些類型特定函數(shù)的可選參數(shù)
void*privdata;

//兩張哈希表
    dictht ht[2];

//rehash 索引，并沒(méi)有rehash時(shí)，值為 -1
long rehashidx;

//目前正在運(yùn)行的安全迭代器的數(shù)量
unsignedlong iterators; /* number of iterators currently running */
} dict;

type：是一個(gè)指向 dictType 結(jié)構(gòu)的指針，每個(gè) dictType 結(jié)構(gòu)保存了一簇用于操作特定類型鍵值對(duì)的函數(shù)，Redis 會(huì)為用途不同的字典設(shè)置不同的類型特定函數(shù)。
privdata：保存了需要傳給那些類型特定函數(shù)的可選參數(shù)
ht[2]：表示兩張 hash 表（dictht），一般情況下只使用 ht[0]，ht[1] 用于 rehash 時(shí)
rehashidx：記錄 rehash 目前的進(jìn)度，如果目前沒(méi)有在進(jìn)行 rehash，那么他的值就是 -1

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

Redis 字典底層是用哈希表（dictht）實(shí)現(xiàn)，dictht 結(jié)構(gòu)如下：

typedefstruct dictht {

// 哈希表數(shù)組, 每個(gè)元素都是一條鏈表
    dictEntry **table;

// 哈希表大小
unsignedlong size;

// 哈希表大小掩碼，用于計(jì)算索引值
// 總是等于 size - 1
unsignedlong sizemask;

// 該哈希表已有節(jié)點(diǎn)的數(shù)量
unsignedlong used;
} dictht;

table：是一個(gè)數(shù)組，數(shù)組中的每個(gè)元素都是一個(gè)指向 dictEntry 結(jié)構(gòu)的指針，每個(gè) dictEntry 結(jié)構(gòu)都保存著一個(gè)鍵值對(duì)的鏈表
size：表示哈希表的大小
sizemask：哈希表大小掩碼，用于計(jì)算索引值，其值總是等于?size-1
used：表示該哈希表已有節(jié)點(diǎn)的數(shù)量

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

哈希表的節(jié)點(diǎn)用 dictEntry 表示，如下：

typedefstruct dictEntry {

// 鍵
void*key;

// 值
union{
void*val;
uint64_t u64;
int64_t s64;
double d;
} v;

// 指向下個(gè)哈希表節(jié)點(diǎn)，形成鏈表
struct dictEntry *next;
} dictEntry;

key：保存鍵值對(duì)中的鍵
v：保存鍵值對(duì)中的值，可以是一個(gè)指針，可以是unit64t的一個(gè)整數(shù)，也可以是int64t的一個(gè)整數(shù)
next：下一個(gè)哈希表結(jié)點(diǎn)的指針，采用“鏈地址法”解決鍵沖突

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

至此，整個(gè)字典的結(jié)構(gòu)已經(jīng)介紹完畢，下圖是一個(gè)完整的結(jié)構(gòu)圖：

當(dāng)我們需要將一個(gè)鍵值對(duì)插入到字典里面，需要先用哈希函數(shù)計(jì)算 key 的哈希值，然后借助 sizemask 和哈希值得到索引值 index，根據(jù)得到的索引值找到對(duì)應(yīng) dictEntry* 然后插入。插入節(jié)點(diǎn)和查找節(jié)點(diǎn)的邏輯其實(shí)和 HashMap 的 put 和 get 的邏輯沒(méi)區(qū)別，這里就不介紹，下面重點(diǎn)介紹 rehash 過(guò)程。

當(dāng)哈希表的數(shù)據(jù)越來(lái)越多時(shí)，鏈表的長(zhǎng)度就會(huì)越來(lái)越長(zhǎng)，這樣查詢的效率就會(huì)降低，所以有必要進(jìn)行哈希表擴(kuò)展。而隨著元素的過(guò)期在不增加元素的前提下會(huì)導(dǎo)致哈希表的鍵值對(duì)很少但是 size 比較大，這個(gè)時(shí)候又會(huì)造成內(nèi)存的浪費(fèi)，所以有必要進(jìn)行哈希表收縮。這里擴(kuò)展、收縮的過(guò)程就是 rehash 的過(guò)程。

Redis 對(duì)字典的哈希表進(jìn)行 rehash 的過(guò)程如下：

為 dict 的 ht[1] 分配內(nèi)存空間，分配內(nèi)存空間的大小取決于操作類型以及?ht[0].used:

如果執(zhí)行的操作是擴(kuò)展操作，則 ht[1] 的大小為第一個(gè)大于等于 $ht[0].used * 2 * 2^n$ 的整數(shù)
如果執(zhí)行的操作是收縮操作，則 ht[1] 的大小為第一個(gè)大于等于 $ht[0].used * 2^n$ 的整數(shù)

重新計(jì)算 ht[0] 中所有的鍵值對(duì)，將其遷移到 ht[1] 指定的位置。需要注意的是，這個(gè)過(guò)程并不是一次性完成的，而是漸進(jìn)式完成的。
當(dāng) ht[0] 中所有的鍵值對(duì)都遷移到 ht[1] 中去后（ht[0] 為空），則把 ht[0] 釋放掉，把ht[1] 設(shè)置為 ht[0] ，并重新在 ht[1] 上新建一個(gè)空表，為下次 rehash 做準(zhǔn)備。

ht[0] 采用漸進(jìn)式的方式將其中元素遷移到 ht[1] 中的主要原因?yàn)榱吮苊鈱?duì)服務(wù)器性能造成影響，因?yàn)槿绻?ht[0] 中的元素非常多，幾百萬(wàn)，幾千萬(wàn)甚至上億，那么要一次性將這些鍵值對(duì)全部遷移到 ht[1] 中的話，龐大的計(jì)算可能會(huì)造成服務(wù)器在一定時(shí)間內(nèi)停止服務(wù)，所以需要采用漸進(jìn)式、分多次的方式進(jìn)行 rehash。詳細(xì)步驟如下：

為 ht[1] 分配空間，讓字典同時(shí)持有 ht[0] 和 ht[1] 兩個(gè)哈希表
在字典中維持一個(gè)索引計(jì)數(shù)器變量 rehashidx，并將其值設(shè)置為 0，表示 rehash 過(guò)程正式開始
在 rehash 期間，每次對(duì)字典執(zhí)行任意操作時(shí)，程序除了執(zhí)行對(duì)應(yīng)操作之外，還會(huì)順帶將 ht[0] 在 rehashidx 索引上的所有鍵值對(duì) rehash 到 ht[1] ，操作完后將 rehashidx 的值加一
在 rehash 期間，對(duì)字典進(jìn)行 ht[0].size 次操作之后，rehashidx 的值會(huì)增加到 ht[0].size，此時(shí) ht[0] 的所有鍵值對(duì)都已經(jīng)遷移到 ht[1] 了，程序會(huì)將 rehashidx 重新置為-1，以此表示 rehash 完成

這里需要注意的是，在 rehash 的過(guò)程中，ht[0] 和 ht[1] 可能同時(shí)存在鍵值對(duì)，因此在執(zhí)行查詢操作的時(shí)候兩個(gè)哈希表都得查，而如果是執(zhí)行插入鍵值對(duì)操作，則直接在 ht[1] 上操作就行，不在 ht[0] 上進(jìn)行任何的添加操作。

租后再說(shuō)下 Redis 在什么條件下會(huì)對(duì)哈希表進(jìn)行擴(kuò)展或者收縮呢：

服務(wù)器當(dāng)前沒(méi)有在執(zhí)行 BGSAVE 或 BGREWRITEAOF 命令且哈希表的負(fù)載因子大于等于 1 時(shí)進(jìn)行擴(kuò)展操作
服務(wù)器正在執(zhí)行 BGSAVE 或 BGREWRITEAO F命令且哈希表的負(fù)載因子大于等于5時(shí)進(jìn)行擴(kuò)展操作
當(dāng)前負(fù)載因子小于0.1時(shí)進(jìn)行收縮操作

之所以在服務(wù)器進(jìn)行BGSAVE或BGREWRITEAOF的時(shí)候負(fù)載因子比較大才進(jìn)行擴(kuò)展操作是因?yàn)榇藭r(shí)Redis會(huì)創(chuàng)建子進(jìn)程，而大多數(shù)操作系統(tǒng)采取了寫時(shí)復(fù)制的技術(shù)來(lái)優(yōu)化子進(jìn)程使用效率，不適合在這種時(shí)候會(huì)做大規(guī)模的數(shù)據(jù)遷移活動(dòng)，說(shuō)白了就是為了節(jié)約內(nèi)存和提升效率）