Redis解決鍵沖突：使用的是鏈地址法
隨著操作的不斷執(zhí)行何鸡， 哈希表保存的鍵值對會逐漸地增多或者減少脑蠕， 為了讓哈希表的負(fù)載因子（load factor）維持在一個合理的范圍之內(nèi)， 當(dāng)哈希表保存的鍵值對數(shù)量太多或者太少時呢蛤， 程序需要對哈希表的大小進(jìn)行相應(yīng)的擴(kuò)展或者收縮。
擴(kuò)展和收縮哈希表的工作可以通過執(zhí)行 rehash （重新散列）操作來完成， Redis 對字典的哈希表執(zhí)行 rehash 的步驟如下：
- 為字典的
ht[1]哈希表分配空間所坯， 這個哈希表的空間大小取決于要執(zhí)行的操作， 以及ht[0]當(dāng)前包含的鍵值對數(shù)量 （也即是ht[0].used屬性的值）：- 如果執(zhí)行的是擴(kuò)展操作挂捅， 那么
ht[1]的大小為第一個大于等于ht[0].used * 2的 2^n（2的n次方冪）芹助； - 如果執(zhí)行的是收縮操作， 那么
ht[1]的大小為第一個大于等于ht[0].used的 [2^n]。
- 如果執(zhí)行的是擴(kuò)展操作挂捅， 那么
- 將保存在
ht[0]中的所有鍵值對 rehash 到ht[1]上面： rehash 指的是重新計算鍵的哈希值和索引值状土， 然后將鍵值對放置到ht[1]哈希表的指定位置上无蜂。 - 當(dāng)
ht[0]包含的所有鍵值對都遷移到了ht[1]之后 （ht[0]變?yōu)榭毡恚?釋放ht[0]， 將ht[1]設(shè)置為ht[0]蒙谓， 并在ht[1]新創(chuàng)建一個空白哈希表斥季， 為下一次 rehash 做準(zhǔn)備。
<h1>哈希表的擴(kuò)展與收縮</h1>
當(dāng)以下條件中的任意一個被滿足時累驮， 程序會自動開始對哈希表執(zhí)行擴(kuò)展操作：
服務(wù)器目前沒有在執(zhí)行 BGSAVE 命令或者 BGREWRITEAOF 命令酣倾， 并且哈希表的負(fù)載因子大于等于 1 ；
服務(wù)器目前正在執(zhí)行 BGSAVE 命令或者 BGREWRITEAOF 命令谤专， 并且哈希表的負(fù)載因子大于等于 5 躁锡；
根據(jù) BGSAVE 命令或 BGREWRITEAOF 命令是否正在執(zhí)行， 服務(wù)器執(zhí)行擴(kuò)展操作所需的負(fù)載因子并不相同毒租， 這是因為在執(zhí)行 BGSAVE 命令或BGREWRITEAOF 命令的過程中稚铣， Redis 需要創(chuàng)建當(dāng)前服務(wù)器進(jìn)程的子進(jìn)程， 而大多數(shù)操作系統(tǒng)都采用寫時復(fù)制（copy-on-write）技術(shù)來優(yōu)化子進(jìn)程的使用效率墅垮， 所以在子進(jìn)程存在期間惕医， 服務(wù)器會提高執(zhí)行擴(kuò)展操作所需的負(fù)載因子， 從而盡可能地避免在子進(jìn)程存在期間進(jìn)行哈希表擴(kuò)展操作算色， 這可以避免不必要的內(nèi)存寫入操作抬伺， 最大限度地節(jié)約內(nèi)存。
另一方面灾梦， 當(dāng)哈希表的負(fù)載因子小于 0.1 時峡钓， 程序自動開始對哈希表執(zhí)行收縮操作。
