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

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

ziplist底層實(shí)現(xiàn)

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

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

但是因?yàn)槊看涡薷牟僮鞫夹枰匦路峙鋤iplist的內(nèi)存，所以實(shí)際復(fù)雜度和ziplist的內(nèi)存使用量相關(guān)

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

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

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

• previous_entry_length：記錄前一個(gè)節(jié)點(diǎn)的長度

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

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

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

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

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

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

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

字典

底層實(shí)現(xiàn)

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

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

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

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

2 數(shù)組長度 size

3 sizemask 等于 size - 1

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

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

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

擴(kuò)容

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

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

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

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

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

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

縮容

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

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

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

總結(jié)

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

最新評論