首頁  >  文章  >  資料庫  >  淺談Redis中的字典、雜湊演算法和ReHash原理

淺談Redis中的字典、雜湊演算法和ReHash原理

青灯夜游
青灯夜游轉載
2021-11-05 10:31:562502瀏覽

這篇文章帶大家了解Redis中的字典、雜湊演算法和ReHash原理,希望對大家有幫助!

淺談Redis中的字典、雜湊演算法和ReHash原理

Redis 中的字典被廣泛用於實作Redis的各種功能,其中包括資料庫和雜湊鍵。

字典的底層實作為雜湊表,每個字典有兩個雜湊表,一個平常使用,另一個在進行rehash擴充空間時才使用。 【相關推薦:Redis影片教學

字典的結構定義

typedef struct dict {
	
	// 类型特定函数
	dictType *type;
	
	// 私有数据
	void *privdata;
	
	// 哈希表,两个元素
	dictht ht[2]
	
	// rehash时记录的索引下标,当没有rehash时,值为-1
	int rehashidx;

} dict;

==在進行rehash時,rehashidx每遷移一個索引的entry資料就會1;==

其中,哈希表dictht 的結構定義為:

typedef struct dictht {
	
	// 哈希表数组
	dictEntry **table;
	
	// 哈希表大小
	unsigned long size;
	
	// 哈希表大小掩码,用于计算索引值
	unsigned long sizenask;
	
	// 该哈希表已有节点的数量
	unsigned long uesd;

} dictht;

其中,table是數組,數組的每一個元素指向dictEntry 類型的指針, dictEntry 類型裡保存一個鍵值對。

在這裡也可以看出雜湊表的節點是鍊錶相連來解決雜湊衝突問題的,也就是鏈結位址法。

哈希衝突與哈希演算法

        為了實現從鍵到值的快速訪問,Redis使用了哈希表來保存所有鍵值對。 對應Redis設定的Key,而對應的並不是值本身,而是指向具體值的指標。使用雜湊表的最大好處就是可以用O(1)的時間複雜度快速找到鍵值對。但既然是哈希表,那麼必然會有哈希衝突的問題。

哈希衝突即指的是,當兩個key的雜湊值和雜湊桶計算對應關係時,剛好落在了同一個哈希桶上。

Redis解決哈希衝突的方式是使用鍊式哈希,即拉鍊法。當多個元素指向同一個雜湊桶時,在同一個雜湊桶中採用鍊錶來保存對應的數據,它們之間依序用指針連接。

雜湊演算法

當要將一個新的鍵值對加入字典裡面時,程式需要先根據鍵值對計算出雜湊值和索引值,然後再根據索引值,將包含新鍵值對的雜湊表節點放到雜湊表數組的指定索引上面。

reHash 過程

        在雜湊表中有個負載因子(load factor)來控制雜湊表所儲存的鍵值對數量。而這就需要rehash(重新散列)操作來完成。其中,負載因子的計算公式為:

// 负载因子 = 哈希表已保存的节点数量 / 哈希表大小
load_factor = ht[0].used / ht[0].size

哈希表擴展與收縮的條件如下:

  • 伺服器目前沒有在執行BGSAVE 指令或BGREWRITEAOF 指令,且雜湊表的負載因子大於等於1;
  • 伺服器目前正在執行BGSAVE 指令或BGREWRITEAOF 指令,且雜湊表的負載因子大於等於5;

上述的條件有一個滿足,就會執行rehash的過程。

如果伺服器正在執行BGSAVE  或BGREWRITEAOF時,Redis會建立目前伺服器程序的子程序

rehash的過程大概分成三步驟:

  • #給哈希表2分配更大的空間,例如是目前哈希表1的兩倍;

  • 把哈希表1中的資料重新映射並拷貝到哈希表2中;

  • 釋放哈希表1的空間;

其中,第一步分配空間的大小是由目前的rehash操作類型以及目前哈希表的鍵值對數量決定的。

  • 當執行的是擴展操作,分配的空間大小為第一個大於等於(哈希表的鍵值對數量* 2) 的2^n 值;

    假設目前的鍵值對數量為4,則4 * 2 = 8,因為8 剛好等於2^3,也就是剛好等於第一個等於2^n的值,所以擴充空間就為8;

  • 如果執行的是收縮操作,則分配的空間大小為第一個大於等於(哈希表的鍵值對數量) 的2^n 值;

######## ########漸進式reHash#########        當雜湊表數量多時,如果一下子將資料都複製過去,那麼就很有可能對伺服器造成影響。所以Redis是分多次進行rehash的,也就是漸進式rehash。 ######        簡單來說就是在第二步驟操作時,Redis仍然正常處理客戶端請求,每處理一個請求時,從哈希表1中的第一個索引位置開始,順從著將這個索引位置上所有的entries元素拷貝到哈希表2中;等下一次請求時,再順帶拷貝下一個索引位置的entries。 ######        這樣就很巧妙地將一次性大量拷貝的開銷,分攤到多次處理請求的過程中了,避免了耗時操作,保證了資料的快速存取。 ###

rehash時期間的雜湊表運算

        在進行 漸進式rehash運算時,字典的刪除、尋找、更新等運算會在兩個雜湊表中執行。例如要在字典中找一個鍵的話,會先去原表中查詢,如果找不到就會去新表查詢。

        而字典的新增作業一律只會儲存在新表中。

更多程式相關知識,請造訪:程式設計入門! !

以上是淺談Redis中的字典、雜湊演算法和ReHash原理的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文轉載於:juejin.cn。如有侵權,請聯絡admin@php.cn刪除