關(guān)注公眾號：后端技術(shù)漫談，技術(shù)之路不迷路~

字典是一種用于保存鍵值對的抽象數(shù)據(jù)結(jié)構(gòu)，也被稱為查找表、映射或關(guān)聯(lián)表。

在字典中，一個鍵(key)可以和一個值(value)進行關(guān)聯(lián)，這些關(guān)聯(lián)的鍵和值就稱之為鍵值對。

抽象數(shù)據(jù)結(jié)構(gòu)，啥意思？就是可以需要實際的數(shù)據(jù)結(jié)構(gòu)是實現(xiàn)這個功能。抽象，意味著它這是實現(xiàn)功能的標準，凡是能夠完成這些功能的都可以是其實現(xiàn)。

redis的字典

字典作為一種數(shù)據(jù)結(jié)構(gòu)內(nèi)置在很多高級編程語言里面，但是redis是基于C語言進行開發(fā)的，所以沒有內(nèi)置這種數(shù)據(jù)結(jié)構(gòu)，redis只能構(gòu)建自己的字典實現(xiàn)。

字典通?？梢杂蓛煞N底層數(shù)據(jù)結(jié)構(gòu)組成，分別是線性表(數(shù)組)和hash表。而redis一般是采用hash表的方式進行構(gòu)建

redis字典為啥不用線性表實現(xiàn)

字典基于用線性表實現(xiàn)，如果我這個字典有200個鍵值對，那么我就開辟一個長度為200的數(shù)組對這些元素進行放置。

基于線性表實現(xiàn)的字典的優(yōu)缺點很明顯：

1、實現(xiàn)簡單，適用于任意關(guān)鍵碼類型。

2、平均檢索效率低(線性時間)，表長度n比較大時，檢索比較耗時。

3、刪除操作的效率比較低，不太適合頻繁變動的字典。

字典在插入刪除上的頻繁讓線性表無法勝任此任務(wù)。

哈希如何實現(xiàn)字典

之前寫過一篇文章，關(guān)于java中的hashcode解析，有興趣的讀者可以回看下一些經(jīng)典的hash函數(shù)和實現(xiàn)

面試官問我：hashcode 是什么？和equals是兄弟嗎？

redis字典所使用的哈希表由dict.h/dictht組成

typedef?struct?dictht?{
????dictEntry?**table;????//哈希表數(shù)組
????
????unsigned?long?size;????//哈希表大小，即哈希表數(shù)組大小
????
????unsigned?long?sizemask;?//哈希表大小掩碼，總是等于size-1，主要用于計算索引
????
????unsigned?long?used;????//已使用節(jié)點數(shù)，即已使用鍵值對數(shù)
}dictht;

可以看到redis聲明了一個結(jié)構(gòu)體，里面由一個哈希表數(shù)組，哈希表數(shù)組大小的long值，一個用于計算索引的哈希表大小掩碼以及已使用的節(jié)點數(shù)構(gòu)成。

這個哈希表數(shù)組，存放的是哈希節(jié)點dicEntry，我們會將key-value鍵值對給它放進去。

typedef?struct?dictEntry?{
????void?*key;??//存放key值
????union?{
????????void?*val;????//存放value值
????????uint64_t?u64;????//uint64_t整數(shù)
????????int64_t?s64;????//int64_t整數(shù)
????}v;
????struct?dictEntry?*next;????//指向下個哈希表節(jié)點，形成鏈表
}dictEntry;

如圖所示就通過next指針來將兩個索引相同的鍵k1和k0連接在一起。

Redis 中的字典由 dict.h/dict 結(jié)構(gòu)表示：

typedef?struct?dict?{

????//?類型特定函數(shù)
????dictType?*type;

????//?私有數(shù)據(jù)
????void?*privdata;

????//?哈希表
????dictht?ht[2];

????//?rehash?索引
????//?當(dāng)?rehash?不在進行時，值為?-1
????int?rehashidx;?/*?rehashing?not?in?progress?if?rehashidx?==?-1?*/

}?dict;

可以看到字典里有一個長度為2的哈希表數(shù)組，那么為啥不是三個四個甚至更多呢？感覺哈希表越多不是效率更快嗎？

其實設(shè)置2的原因在于，h[0]用于存儲，h[1]用于當(dāng)容量不足時進行擴充,更多的哈希表也用不上，反而可能在擴充時要同步成為性能瓶頸。

字典如何增添一個元素

當(dāng)要將一個新的鍵值對加入到字典中的時候，首先要計算這個key的哈希值和索引值，然后再根據(jù)這個索引值放入字典中h[0]的索引位置

舉個例子， 對于圖 4-4 所示的字典來說， 如果我們要將一個鍵值對 k0 和 v0 添加到字典里面， 那么程序會先使用語句：

hash?=?dict->type->hashFunction(k0);

計算鍵 k0 的哈希值。

假設(shè)計算得出的哈希值為 8 ， 那么程序會繼續(xù)使用語句：

index?=?hash?&?dict->ht[0].sizemask?=?8?&?3?=?0;

計算出鍵 k0 的索引值 0 ， 這表示包含鍵值對 k0 和 v0 的節(jié)點應(yīng)該被放置到哈希表數(shù)組的索引 0 位置上， 如圖 所示。

什么時候會進行擴容

按照java中hashmap的說法，當(dāng)負載因子loadFactor>0.75的情況下會進行擴容

在redis中，字典里的哈希會根據(jù)以下兩種情況進行擴容：

服務(wù)器目前沒有在執(zhí)行 BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的負載因子大于等于 1 ；

服務(wù)器目前正在執(zhí)行 BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的負載因子大于等于 5 ；

其中哈希表的負載因子可以通過公式：

#?負載因子?=?哈希表已保存節(jié)點數(shù)量?/?哈希表大小
load_factor?=?ht[0].used?/?ht[0].size

漸進式rehash如何實現(xiàn)

首先要清楚為什么rehash的時候要漸進式。

這就好比去參加高考，肯定是初中畢業(yè)后讀三年高中，一點點學(xué)習(xí)高中知識后才可以參加高考，這才可以取得不錯的成績。學(xué)習(xí)是循序漸進的，hash也要，不然中考完直接去參加高考，這誰頂?shù)米“　?/p>

Rehash操作分為兩種：

擴展：當(dāng)負載因子較大時，應(yīng)該擴大 dictht::size 以降低平均長度，加快查詢速度。
收縮：當(dāng)負載因子較小時，應(yīng)該減小 dictht::size 以減少對內(nèi)存的浪費。

當(dāng)整體的數(shù)據(jù)量比較少，如百八十個key-value對存儲的時候，hash的過程肯定耗時不會很多。但是在生產(chǎn)換鏡下，一個數(shù)據(jù)庫下key-value值都是有百萬級別的，在進行rehash操作的時候勢必會達到秒級別的運算。所以這個hash的過程不是一次性集中的完成，而是分多次漸進式的完成。

以下是哈希表漸進式 rehash 的詳細步驟：

為 ht[1] 分配空間， 讓字典同時持有 ht[0] 和 ht[1] 兩個哈希表。

在字典中維持一個索引計數(shù)器變量 rehashidx ， 并將它的值設(shè)置為 0 ， 表示 rehash 工作正式開始。

在 rehash 進行期間， 每次對字典執(zhí)行添加、刪除、查找或者更新操作時， 程序除了執(zhí)行指定的操作以外， 還會順帶將 ht[0] 哈希表在 rehashidx 索引上的所有鍵值對 rehash 到 ht[1] ， 當(dāng) rehash 工作完成之后， 程序?qū)?rehashidx 屬性的值增1。

隨著字典操作的不斷執(zhí)行， 最終在某個時間點上， ht[0] 的所有鍵值對都會被 rehash 至 ht[1] ， 這時程序?qū)?rehashidx 屬性的值設(shè)為 -1 ， 表示 rehash 操作已完成。

rehash的過程中有數(shù)據(jù)變化怎么辦

關(guān)于字典的操作無非就是四個，增刪改查。

操作類型過程

增加	直接將key-value對增加到h[1]中
刪除	先刪除h[0]，再刪除h[1]
修改	直接修改h[1]
查找	先在h[0]中查找，查詢不到再到h[1]中

這樣就能保證redis在h[0]上是只少不多，所有的記錄都會被遷移到h[1]上。

如何解決哈希碰撞

這個問題還是我面試騰訊的時候面試官問我的原題。

一開始我說了兩個思路，一個是無限增大線性表的容量，一個是采用數(shù)組+鏈表的方式。

面試官：對這兩個都是構(gòu)成hash的方式，但是如果我的兩個鍵值對的hashcode是一樣的呢？

我：那就可以將這個hash算法設(shè)計的復(fù)雜化，比如hash里頭再嵌套一層hash，這樣碰撞的幾率就會變小了。

面試官：這種方法其實也是可以的，那還有沒有其他方法呢？

我：....(支支吾吾中)

然后面試就結(jié)束了orz

其實還有另一種方法我不知道就是公共溢出區(qū)法

建立一個公共溢出區(qū)，假設(shè)哈希函數(shù)的值域為[0,m-1],則設(shè)向量HashTable[0..m-1]為基本表，另外設(shè)立存儲空間向量OverTable[0..v]用以存儲發(fā)生沖突的記錄。

參考文獻：
《redis設(shè)計與實現(xiàn)》
https://blog.csdn.net/Time_Limit/article/details/106633269

往期精彩文章：

闊別2020 ?| ?我的年度總結(jié)

Socket粘包問題的3種解決方案，最后一種最完美！

一條失去where的動態(tài)SQL導(dǎo)致的線上故障

一枚程序猿的MacBook M1使用體驗

半夜里，有程序從虛擬機里跑出來了！

總結(jié)

以上是生活随笔為你收集整理的开发 数组里面的字典_Redis字典结构与rehash解读的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。