偷偷摘套内射激情视频,久久精品99国产国产精,中文字幕无线乱码人妻,中文在线中文a,性爽19p

阿里面試官:談?wù)剬?duì)Redis哈希表的理解

存儲(chǔ) 存儲(chǔ)軟件 Redis
哈希表是一種存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu),他有很多名字(鍵值對(duì)、字典、符號(hào)表、映射、關(guān)聯(lián)數(shù)組)。在哈希表中,鍵和值是一一對(duì)應(yīng)的關(guān)系,一個(gè)鍵key對(duì)應(yīng)一個(gè)值value。哈希表這個(gè)數(shù)據(jù)結(jié)構(gòu)可以通過鍵key,在O(1)時(shí)間復(fù)雜度的情況下獲得對(duì)應(yīng)的值。

[[433454]]

Hash表回顧

哈希表是一種存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu),他有很多名字(鍵值對(duì)、字典、符號(hào)表、映射、關(guān)聯(lián)數(shù)組)。在哈希表中,鍵和值是一一對(duì)應(yīng)的關(guān)系,一個(gè)鍵key對(duì)應(yīng)一個(gè)值value。哈希表這個(gè)數(shù)據(jù)結(jié)構(gòu)可以通過鍵key,在O(1)時(shí)間復(fù)雜度的情況下獲得對(duì)應(yīng)的值。

由于C語言自己沒有內(nèi)置哈希表這一數(shù)據(jù)結(jié)構(gòu),因此Redis自己實(shí)現(xiàn)了Hash表。

哈希沖突及處理辦法

哈希表最關(guān)鍵的問題就在于哈希沖突。即,兩個(gè)項(xiàng),經(jīng)過哈希函數(shù)計(jì)算,發(fā)現(xiàn)其對(duì)應(yīng)的存儲(chǔ)方式位置一致。對(duì)于這種情況,就需要進(jìn)行進(jìn)一步處理了。

解決哈希沖突的辦法

大家應(yīng)該背過我寫的數(shù)據(jù)結(jié)構(gòu)與算法八股文背誦版,還記得解決Hash沖突的方法嘛。

線性探查法(開放地址)。

這個(gè)方法的核心是:一旦碰見有沖突,該項(xiàng)往后順延.

來看個(gè)例子吧。

1.按hash算法,新鍵值對(duì)應(yīng)該存在箭頭所處位置,可惜該位置有值了:

開放地址法

2.因此需要存儲(chǔ)順延的位置:

開放地址法

3.順延位置也有值了,再往后順延

開放地址法

4.順延位置還是有值,再往后順延,終于存儲(chǔ)上了

開放地址法

鏈地址法(拉鏈法)

Redis采用的方法就是這種拉鏈法。來看下面例子。新鍵值對(duì)計(jì)算應(yīng)該存到二號(hào),二號(hào)此時(shí)已經(jīng)有一個(gè)鍵值對(duì)了。因此,直接通過鏈表的方式掛到二號(hào)鍵值對(duì)1的下面。

拉鏈法

對(duì)于新的鍵值對(duì)也是如此,通過鏈表的方式掛到二號(hào)鍵值對(duì)2的下面。

Rehash

在講rehash之前,首先需要引入一個(gè)定義:負(fù)載因子。來看一下負(fù)載因子的定義吧:

負(fù)載因子 = 散列表內(nèi)元素個(gè)數(shù)/散列表的長度

如果負(fù)載因子高,就說明哈希沖突概率大,這樣會(huì)嚴(yán)重拖慢查找效率。

如果負(fù)載因子低,就說明這哈希表好像占用空間太多了,大部分空間都沒元素。

為了使負(fù)載因子值在合理范圍內(nèi),程序需要對(duì)哈希表進(jìn)行擴(kuò)展或收縮。由于空間變大或縮小,之前的鍵在老表的存儲(chǔ)位置,在新表中就不一定一樣了,需要重新計(jì)算。這個(gè)重新計(jì)算,并把老表元素轉(zhuǎn)移到新表元素的過程就叫做rehash。當(dāng)然無論是java中的hashmap,concurrenthashmap,還是今天要講的Redis哈希表,都涉及rehash過程。

Redis中哈希表的數(shù)據(jù)結(jié)構(gòu)

來看一下Redis的Hash表邏輯設(shè)計(jì)結(jié)構(gòu) Redis的哈希表主要由三個(gè)結(jié)構(gòu)構(gòu)成:

dictht。單純表示一個(gè)哈希表

dictEntry。哈希表的一項(xiàng),可以看作就是一個(gè)鍵值對(duì)

dict。Redis給外層調(diào)用的哈希表結(jié)構(gòu),包含兩個(gè)dictht

  1. typedef struct dictht {  
  2.     dictEntry **table; //哈希表數(shù)組(哈希表項(xiàng)集合) 
  3.     unsigned long size; //Hash表大小  
  4.     unsigned long sizemask; //哈希表掩碼 
  5.     unsigned long used;//Hash表已使用的大小 
  6. } dictht; 

稍微解釋一下各個(gè)項(xiàng)。

  • table:哈希表項(xiàng)的指針數(shù)組
  • size:哈希表大小,這應(yīng)該不用多解釋吧
  • sizemask:掩碼。這個(gè)值其實(shí)設(shè)計(jì)思想很棒,假設(shè)Redis長度是3,你想訪問第5個(gè)元素,如果按之前的方法,那肯定是訪問到超出redis哈希表范圍的地址空間了。所以redis規(guī)定,你想訪問元素,先把index與size做與,把超過redis長度的部分就截?cái)嗔耍筒粫?huì)發(fā)生內(nèi)存安全問題。
  • Hash表已使用的大小。不解釋。

講了Hash表,來看看哈希項(xiàng)

  1. typedef struct dictEntry {  
  2.     void *key;  
  3.     union {  
  4.         void *val;  
  5.         uint64_t u64;  
  6.         int64_t s64;  
  7.         double d;  
  8.     } v;  
  9.     struct dictEntry *next
  10. } dictEntry; 

我們知道,Redis采用拉鏈法解決哈希沖突的問題。因此,Redis的哈希表項(xiàng)就有一個(gè)next指針,指向下一個(gè)元素,通過該指針,就可以訪問多個(gè)具有相同哈希值的鍵值對(duì)。

最后我們來看看dict結(jié)構(gòu)。

  1. typedef struct dict { 
  2.     dictType *type; 
  3.     void *privdata; 
  4.     dictht ht[2]; 
  5.     int reshaidx; 
  6. } dict; 

大家肯定很好奇,好好的dict,搞兩個(gè)哈希表做啥?當(dāng)然也有不好奇的小伙伴,但沒辦法,架不住面試官也很好奇啊。

答案揭曉,兩個(gè)hash表是為了rehash。

那什么情況下需要rehash呢?

  • 如果redis沒在執(zhí)行后臺(tái)備份,當(dāng)負(fù)載因子大于等于1就執(zhí)行。(反正CPU閑著也是閑著)
  • 如果redis在執(zhí)行后臺(tái)備份,當(dāng)負(fù)載因子大于等于5就執(zhí)行。(CPU在干備份了,咱對(duì)于實(shí)在擠的表改一改,等CPU閑下來,再把稍微偏擠的rehash)

我們來看一下如果出現(xiàn)需要rehash的情況,需要的執(zhí)行步驟:

  1. 分配空間給ht[1]。分配空間由ht[0]的具體參數(shù)決定。
  2. 將ht[0]存儲(chǔ)的鍵值對(duì),重新計(jì)算hash值和索引值,并賦值到ht[1]的對(duì)應(yīng)位置中。
  3. 當(dāng)賦值完成后,釋放ht[0]所占用空間,并把ht[0]指向ht[1]目前的地址。
  4. ht[1]指向空表。

漸進(jìn)式rehash

由于步驟二采用的計(jì)算方式如果在一定時(shí)間做,占用資源過高,所以redis提出了漸進(jìn)式rehash的方式。拿大白話來講,就是原來是一次,一次性的搬運(yùn),現(xiàn)在變成了分批搬運(yùn)。

在分批搬運(yùn)的過程中,難免會(huì)收到其他各式各樣的請(qǐng)求。

  • 對(duì)于寫請(qǐng)求,即往redis哈希表增加新的鍵值對(duì)時(shí),redis會(huì)把數(shù)據(jù)直接存放到ht[1]表中。
  • 對(duì)于查請(qǐng)求,即查詢特定鍵對(duì)應(yīng)的值時(shí),redis首先會(huì)在ht[0]中查找,如果查找失敗,就會(huì)在ht[1]表中查找。
  • 對(duì)于更新請(qǐng)求,redis首先會(huì)在ht[0]中查找,如果查找失敗,就會(huì)在ht[1]表中更新。
  • 對(duì)于刪除請(qǐng)求,redis首先會(huì)在ht[0]中查找,如果查找失敗,就會(huì)在ht[1]表中刪除。

參考

https://www.cnblogs.com/tekkaman/p/5141936.html

https://blog.csdn.net/yangbodong22011/article/details/78467583

Redis的設(shè)計(jì)與實(shí)現(xiàn)

 

Redis源碼剖析與實(shí)戰(zhàn)

 

責(zé)任編輯:武曉燕 來源: 后端技術(shù)小牛說
相關(guān)推薦

2024-06-13 08:01:19

2024-09-27 15:43:52

零拷貝DMAIO

2025-02-21 15:25:54

虛擬線程輕量級(jí)

2022-03-21 09:05:18

volatileCPUJava

2024-10-24 16:14:43

數(shù)據(jù)傳輸CPU零拷貝

2025-03-21 00:00:05

Reactor設(shè)計(jì)模式I/O 機(jī)制

2024-08-27 12:36:33

2025-04-09 00:00:00

2019-07-26 06:42:28

PG架構(gòu)數(shù)據(jù)庫

2024-10-12 16:25:12

2024-09-26 16:01:52

2024-08-26 14:52:58

JavaScript循環(huán)機(jī)制

2024-08-23 09:02:56

2021-11-25 10:18:42

RESTfulJava互聯(lián)網(wǎng)

2021-08-09 07:47:40

Git面試版本

2025-01-13 09:24:32

2020-12-01 08:47:36

Java異常開發(fā)

2020-06-12 15:50:56

options前端服務(wù)器

2021-09-27 07:11:18

MySQLACID特性

2018-10-22 14:28:26

面試官數(shù)據(jù)公司
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)