Redis之字典

• 字典是什么(hashtable)
• 總體結構
• dict
• • dictht(散列表)
  • • dictEntry
• 如何解決哈希沖突
• • 1. 鏈表法
  • 2.rehash法

字典是什么(hashtable)

簡單來說就是Redis中hash數據結構的底層實現
當數據小, 并且數量不多的時候會用ziplist來實現hash結構

總體結構

這里先給出大體的結構, 便于理解

dict

字典底層又是由dict實現的, 下圖是dict的結構

typedef struct dict{//類型特定函數void *type;//私有數據void *privdata;//哈希表(散列表)dictht ht[2];//rehash 索引 當rehash不在進行時 值為-1int trehashidx; }dict;

dictht[]數組長度為2, 一般我們使用dictht[0], 另外一個dictht[1]作為rehash使用

dictht(散列表)

接下來我們看一下dictht(散列表的實現)

typedef struct dictht {//哈希表數組dictEntry **table;//哈希表大小unsigned long size;//哈希表大小掩碼，用于計算索引值unsigned long sizemask;//該哈希已有節點的數量unsigned long used; }dictht;

dictEntry

• dictEntry是一個散列表節點
  散列表的節點是由下定義的

//哈希表節點定義dictEntry結構表示，每個dictEntry結構都保存著一個鍵值對。 typedef struct dictEntry {//鍵void *key;//值union{void *val;uint64_tu64;int64_ts64;}v;// 指向下個哈希表節點，形成鏈表struct dictEntry *next; }dictEntry;

• key就是實際存儲鍵的地方
• 聯合體中就是實際存儲值的地方
• 散列表節點還有一個next域指向下一個節點, 可以用來解決哈希沖突問題

如何解決哈希沖突

1. 鏈表法

當有兩個或以上的鍵被分配到散列表數組同一個索引上時，就發生了鍵沖突。Redis使用鏈表法解決散列沖突。
值得一提的是比如V0先加入這個節點中, 又來一個V1和V0的值一個都被分配 到了一個地址, 那么就會在V0的頭部插入V1.

2.rehash法

隨著操作的進行, dict內保存的鍵值對,會不斷的減少或者增加, 我們需要保證負載因子的正常, 那么就要重新進行分配內存
這個時候dicht[1]就可以起到作用了, 并且rehashids也會設置為0表示正在rehash中

rehash的過程
1.為字典的ht[1]散列表分配空間，這個空間的大小取決于要執行的操作以及ht[0]當前包含的鍵值對數量(即:ht[0].used的屬性值)

• 擴展操作：ht[1]的大小為 第一個大于等于ht[0].used2的2的n次方冪。如:ht[0].used=3則ht[0] = 32 = 6, 第一個大于或者等于的2^n就是 2 ^ 3=8所以ht[1]的大小為8，ht[0].used=4則ht[1]的大小也為8。
• 收縮操作: ht[1]的大小為 第一個大于等于ht[0].used的2的n次方冪。

2.將保存在ht[0]中的鍵值對重新計算鍵的散列值和索引值，然后放到ht[1]指定的位置上. 當然這不是一步完成的, 是一部分一部分的賦值過去
3.當我們把ht[0]上面所有的鍵值對都給移過去到h[1]之后, 就會釋放h[0]的空間, 并且將h[1]記為ht[0], 最后再創建一個新的ht[1]散列表為下一次rehash做準備。

這就是本次全部內容,若是看不懂建立配合著圖來理解

總結

以上是生活随笔為你收集整理的Redis之字典(hashtable)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。