hash擴(kuò)容原理？

Redis一共支持5種數(shù)據(jù)結(jié)構(gòu)，hash是其中的一種，在hash擴(kuò)容的時(shí)候采用的是漸進(jìn)式rehash的方式。

rehash原理

字典中包含一個(gè)數(shù)據(jù)結(jié)構(gòu)dictht的ht數(shù)組，一般情況下字典只是用ht[0]用來(lái)存儲(chǔ)數(shù)據(jù)，ht[1]在rehash時(shí)使用。

隨著操作的不斷執(zhí)行，哈希表中的元素會(huì)逐漸增加或者減少，為了讓哈希表的負(fù)載因子維持在一個(gè)合理的范圍內(nèi)，程序需要對(duì)哈希表的大小進(jìn)行相應(yīng)的擴(kuò)容和收縮。步驟如下：

為ht[1]哈希表分配空間。如果是擴(kuò)容操作，ht[1]的大小為第一個(gè)大于等于ht[0].used*2的2的n次方冪，如果是收縮操作，ht[1]的大小為第一個(gè)大于等于ht[0].used的2的n次方冪

將保存在ht[0]中的所有鍵值對(duì)rehash到ht[1]：rehash指的是重新計(jì)算鍵的哈希值和索引值，然后將鍵值對(duì)放到ht[1]對(duì)應(yīng)位置上

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