hash的數(shù)據(jù)結(jié)構(gòu)

• hash底層數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)包括兩種：ziplist和字典當(dāng)
• 保存的所有鍵值對字符串長度小于 64 字節(jié)并且鍵值對數(shù)量小于 512 時使用ziplist ，否則使用字典的方式

ziplist底層實現(xiàn)

ziplist是為了提高存儲效率而設(shè)計的一種特殊編碼的雙向鏈表。它可以存儲字符串或者整數(shù)，存儲整數(shù)時是采用整數(shù)的二進制而不是字符串形式存儲。

他能在O(1)的時間復(fù)雜度下完成list兩端的push和pop操作。

但是因為每次修改操作都需要重新分配ziplist的內(nèi)存，所以實際復(fù)雜度和ziplist的內(nèi)存使用量相關(guān)

ziplist 中包含有zlbytes、zltail、zllen、entry、zlend等屬性

• zlbytes：表示整個ziplist所占的空間大小，占4個字節(jié)
• zltail：壓縮列表尾元素相對于壓縮列表起始地址的偏移量，占4個字節(jié)
• zllen：壓縮列表的元素數(shù)目，占兩個字節(jié)；那么當(dāng)壓縮列表的元素數(shù)目超過(2^16)-1怎么處理呢？此時通過zllen字段無法獲得壓縮列表的元素數(shù)目，必須遍歷整個壓縮列表才能獲取到元素數(shù)目
• zlend：壓縮列表的結(jié)尾，占一個字節(jié)，恒為0xFF（255）
• entry：壓縮列表存儲的元素，可以為字節(jié)數(shù)組或者整數(shù)

entry 中包含有previous_entry_length、encoding、content等屬性

• previous_entry_length：記錄前一個節(jié)點的長度

該屬性根據(jù)前一個節(jié)點的大小不同可以是1個字節(jié)或者5個字節(jié)；如果數(shù)值小于254，那就只用一個字節(jié)來表示長度，如果長度大于等于254就用5個字節(jié)，第一個字節(jié)是固定值254(FE)來標(biāo)識這是個特殊的數(shù)據(jù)，剩下的4個字節(jié)來表示實際的長度

為什么要這么設(shè)計？

壓縮列表目的是為了盡可能的節(jié)省存儲空間，數(shù)據(jù)進行緊鄰存儲在一塊連續(xù)的內(nèi)存區(qū)域中；壓縮表中元素的長度的是不同的，且為了減少存儲空間，并沒有保存前后節(jié)點的指針，無法通過后退指針來找到上一個元素，而通過保存上一個節(jié)點的長度，用當(dāng)前的地址減去這個長度，就可以很容易的獲取到了上一個節(jié)點的位置，通過一個一個節(jié)點向前回溯，來達到從表尾往表頭遍歷的操作

• encoding：數(shù)據(jù)的編碼形式（字符串還是數(shù)字，長度是多少）
• content：實際存儲的數(shù)據(jù)

修改操作耗費性能：ziplist在內(nèi)存中是高度緊湊的連續(xù)存儲，這意味著它對修改并不友好，如果要對ziplist做修改類的操作，那就需重新分配新的內(nèi)存來存儲新的ziplist，代價很大

ziplist其實是一個邏輯上的雙向鏈表，可以快速找到頭節(jié)點和尾節(jié)點，然后每個節(jié)點(entry)中也包含指向前/后節(jié)點的"指針"，但作者為了將內(nèi)存節(jié)省到極致，摒棄了傳統(tǒng)的鏈表設(shè)計(前后指針需要16字節(jié)的空間，而且會導(dǎo)致內(nèi)存碎片化嚴(yán)重)，設(shè)計出了內(nèi)存非常緊湊的存儲格式。

內(nèi)存是省下來了，但操作復(fù)雜性也更新的復(fù)雜度上來了

字典

底層實現(xiàn)

字典（dict）：其中包含長度為2的哈希表數(shù)組dictht，rehashIdx(默認-1)如果為-1說明當(dāng)前沒有擴容，如果不為 -1 則表示正在進行擴容，記錄了原h(huán)ash表需rehash的數(shù)組下標(biāo)

hash表數(shù)組中，ht[0] 在第一次往字典中添加鍵值時分配內(nèi)存空間，而另一個 ht[1] 將會在hash表中數(shù)組擴容/縮容才會進行空間分配

hash表(dictht)：字典dictht數(shù)組元素，其中包括了

1 數(shù)據(jù) dictEntry 類型的數(shù)組，每個數(shù)組的 item 可能都指向一個鏈表

2 數(shù)組長度 size

3 sizemask 等于 size - 1

4 當(dāng)前 dictEntry 數(shù)組中包含總共多少節(jié)點

hash表數(shù)組中元素(dictEntry)：真正的數(shù)據(jù)節(jié)點，包括 key、value 和 next 節(jié)點

整體結(jié)構(gòu)如下所示：

擴容

擴容時機：在dict->rehashidx == -1 , 也就是字典沒有正在進行擴容/縮容的前提下，以下三種情況下對哈希表進行擴容并標(biāo)記 dict->rehashidx 字段為0，且擴展的哈希表的數(shù)組大小是第一個hash表長度的 2倍

• 字典已使用節(jié)點數(shù)和數(shù)組大小之間的比率至少為 1：1，并且 dict_can_resize 為true
• 已使用節(jié)點數(shù)和字典大小之間的比率超過 dict_force_resize_ratio,該值默認為5
• 哈希表剛初始化完，是個空表，給哈希數(shù)組設(shè)置默認大小 DICT_HT_INITIAL_SIZE （4）

擴容方式：為ht[1]分配長度為ht[0]2倍長度，rehashIdx設(shè)置為0表示正在進行擴容rehash，采取漸進式rehash

redis對一個字典的rehash操作，不是一次性把該字典 dict->ht[0] 哈希表上所有哈希數(shù)組里的哈希數(shù)組元素全部重新哈希到 dict->ht[1]

而是將全部的rehash操作分散到對該字典操作的各個命令上了，每次進行"一步"哈希操作(增加k/v，刪除k/v，查找key，隨機返回key)

• 下標(biāo)從dict->rehashidx開始，在 dict->ht[0].table 數(shù)組中找到第一個不為NULL的項
• 將該項鏈表上的所有元素全部hash映射到 ditct->ht[1] 上
• 每重新映射一個元素， dict->ht[0].used --, dict->ht[1].used ++
• 該項鏈表處理完后，將 dict->rehashidx ++

如果 dict->ht[0].used == 0，說明 dict->ht[0]中的元素已全部rehash到dict->ht[1],釋放dict->ht[0].table 數(shù)組，設(shè)置 dict->ht[0] = dict->ht[1]，重置 dict->ht[1]的字段，設(shè)置 dict->rehashidx = -1，rehash操作結(jié)束

縮容

字典有擴容也有縮容，從字典中刪除key后，若字典中的元素個數(shù)與字典數(shù)組大小滿足一定關(guān)系，會觸發(fā)縮容操作，縮絨條件是：

哈希數(shù)組長度大于默認值DICT_HT_INITIAL_SIZE (4)，且節(jié)點數(shù)量 與 字典哈希表數(shù)字大小的比例 小于10%

縮容后新數(shù)組長度為hash表中元素個數(shù)

總結(jié)