Redis的hash結(jié)構(gòu)跟Java的HashMap十分相似，同樣都是用數(shù)組加鏈表組成（還是是數(shù)組和鏈表侦讨，和上一節(jié)的quicklist組成是一樣的吧窘面，只不過(guò)quicklist的結(jié)構(gòu)是由數(shù)組組成的鏈表，而hash則是由鏈表組成的數(shù)組）件相。Set內(nèi)部結(jié)構(gòu)也是hash再扭，只不過(guò)hashEntry中所有的 value 都是一個(gè)值NULL（又抄我java）。hash表就不多說(shuō)了夜矗，直接上圖泛范，哦，這里要注意紊撕，hash結(jié)構(gòu)的值只能是string類型（redis中整數(shù)什么的都可以視為string）罢荡。
探索hash字典內(nèi)部原理
struct hashEntry {
void* key;
void* val;
hashEntry* next; // 下一個(gè) entry的地址值
}
struct hashTable{
hashEntry** table; // 二維數(shù)組，相當(dāng)于java中的 new Entry[][]
long size; // 第一維數(shù)組的長(zhǎng)度对扶，hash表中數(shù)組部分的長(zhǎng)度
long used; // hash 表中的所有元素個(gè)數(shù)
...
}
這個(gè)二維數(shù)組的行代表著hash表中數(shù)組的部分的長(zhǎng)度区赵，列代表著hash表中的每一個(gè)鏈表的長(zhǎng)度。
兩個(gè)hashTable
實(shí)際上浪南，每個(gè)hash類型的數(shù)據(jù)結(jié)構(gòu)里面都會(huì)有兩個(gè)hashTable笼才，就是因?yàn)樵跀U(kuò)容的時(shí)候采取了一種漸進(jìn)式的擴(kuò)容方式，這種方式會(huì)提前創(chuàng)建一個(gè)新的hashtable络凿，容量為當(dāng)前used*2骡送，觸發(fā)擴(kuò)容條件時(shí)昂羡，將老hashTable的數(shù)據(jù)分批次遷移到新的hashtable當(dāng)中，這種方式最大的好處就是不會(huì)因?yàn)橐淮涡赃w移的數(shù)據(jù)量太大而導(dǎo)致讀寫的阻塞摔踱。（CopyOnWriteArrayList是嘛）
在讀請(qǐng)求進(jìn)來(lái)時(shí)虐先，如果發(fā)現(xiàn)擴(kuò)容還未結(jié)束，會(huì)先從老hashTable查派敷，查不到會(huì)再?gòu)男碌膆ashTable查赴穗。而有寫請(qǐng)求時(shí)，會(huì)順便將這個(gè)元素rehash一次膀息，把值直接存到新hashTable中般眉。
擴(kuò)容時(shí)機(jī)
1.當(dāng)hash中元素總個(gè)數(shù)=hash中數(shù)組的長(zhǎng)度時(shí)，且沒(méi)有正在進(jìn)行bgsave或bgrewriteaof操作（持久化內(nèi)存快照）潜支。
2.當(dāng)hash中元素總個(gè)數(shù)=hash中數(shù)組的長(zhǎng)度的5倍時(shí)甸赃，即使正在進(jìn)行bgsave或bgrewriteaof操作，也會(huì)強(qiáng)制擴(kuò)容冗酿。（我覺得紅黑樹還能再挺一下）
縮容時(shí)機(jī)
當(dāng)hash中元素總個(gè)數(shù)=hash中數(shù)組的長(zhǎng)度的1/10時(shí)埠对，便會(huì)縮容。
Set中的intset
struct intset {
uint32_t encoding;//編碼方式裁替，可選16/32/64位
uint32_t length;//數(shù)組長(zhǎng)度
int8_t contents[];//元素
}
當(dāng)set內(nèi)元素個(gè)數(shù)較少且都為整型時(shí)项玛，set內(nèi)部結(jié)構(gòu)會(huì)優(yōu)化為一個(gè)intset，結(jié)構(gòu)和壓縮列表類似弱判，不過(guò)intset的元素都為整型襟沮，在intset中定位一個(gè)元素時(shí)，會(huì)使用二分法查找昌腰，時(shí)間復(fù)雜度為O(logn)开伏。
intset 只能升級(jí)，不能降級(jí)遭商。將一個(gè)大于當(dāng)前encoding位數(shù)的元素插入到intset 固灵，會(huì)導(dǎo)致intset升級(jí)，或者直接變成hash結(jié)構(gòu)劫流。
