深入理解Redis 資料結構—字典

字典，又稱為

符號表、關聯陣列或對映

，是一種用於儲存

鍵值對

的抽象資料結構。在字典中，一個鍵可以和一個值進行關聯，這些關聯的鍵和值稱為鍵值對。鍵值對中鍵是

唯一的

，我們可以根據

鍵key

透過對映查詢或者更新對應的

值value

。

很多高階開發語言有對應集合支援字典這種資料結構，比如

Java

中的

Map

集合。

C語言

並未內建字典這種資料結構，

Redis

構建了自己的字典實現。

應用

字典在

Redis

中應用非常廣泛，

Redis

資料庫就是使用字典作為資料底層的實現。對資料的

增、刪、改、查

操作也是建立在字典之上操作。

當執行命令：

set msg “hello”

在資料庫中建立一個鍵為

msg

，值為

hello

的鍵值對，這個

鍵值對

就用字典來實現的。建立其他資料型別的鍵值對，比如

list

、

hash

、

set

、

sort set

也是用字典來實現的。

處理用來表示資料中的鍵值對，字典還是

hash

資料型別底層實現之一，比如一個

hash

資料型別

website

，包含

100

個鍵值對，這些鍵值對中的鍵是

網址名稱

，值是

網頁地址

：

redis> HGETALL website1）“Redis”2）“Redis。io”3）“nacos”4）“nacos。io”。。。。。

website

鍵的底層就是一個字典，包好了

100

個

鍵值對

，例如：

鍵值對中的鍵為

“Redis”

，值為

“Redis。io”

。

鍵值對中的鍵為

“nacos”

，值為

“nacos。io”

。

字典的實現

Redis

字典使用雜湊表作為底層實現，一個雜湊表裡面有多個雜湊表節點，每個雜湊表節點儲存字典中的鍵值對。

雜湊表

Redis

字典使用的雜湊表由

dict。h/dictht

結構來表示：

/* This is our hash table structure。 Every dictionary has two of this as we * implement incremental rehashing， for the old to the new table。 */typedef struct dictht { // table 陣列 dictEntry **table； // 雜湊表的大小 unsigned long size； // 等於size-1，用於計算索引值 unsigned long sizemask； // 已有的鍵值對數量 unsigned long used；} dictht；

註釋：這是雜湊表結構，每個字典有兩個實現增量重雜湊，從舊的雜湊表到新的雜湊表。

table

屬性的是一個數組，陣列中的每個元素都指向雜湊節點

dictEntry

，每個

dictEntry

結構都儲存一個鍵值對。

size

記錄了雜湊表的大小，也就是

table

陣列的大小。

used

屬性記錄了雜湊表目前已有的鍵值對數量。

sizemask

的值等於

size-1

，這個屬性和雜湊表一起決定鍵應該放在

table

陣列的那個位置上。

下圖展示一個大小為

4

空雜湊表（沒有包含任務的鍵值對）：

雜湊表節點

雜湊表節點使用

dictEntry

結構來表示，每個

dictEntry

結構都儲存著一個

鍵值對

：

typedef struct dictEntry { // 鍵 void *key； // 值 union { void *val； uint64_t u64； int64_t s64； } v； // 指向下一個雜湊表節點，形成連結串列 struct dictEntry *next；} dictEntry；

其中：

key

儲存鍵值

v

保持值，

v

可以是一個指標，可以是

uint64_t

整數，也可以是一個

int64_t

整數。

next

指向另一個雜湊表節點的指標，這個指標將多個

雜湊值相同

的鍵值對連線在一起，以此解決

hash衝突

的問題。

下圖展示兩個

鍵的hash值

相同的雜湊表節點

k0

和

k1

，兩者透過

next

指標連線在一起。

字典

Redis

中的字典由

dict。h/dict

結構表示：

typedef struct dict { // 型別特定的函式 dictType *type； // 私有函式 void *privdata； // 雜湊表 dictht ht［2］； // rehash 索引 int rehashidx； /* rehashing not in progress if rehashidx == -1 */ int iterators； /* number of iterators currently running */} dict；

type

屬性和

privadata

屬性是針對不同型別的鍵值對，為建立多型的字典而設定。

type

是指向

dictType

結構的指標，每個

dictType

包含幾組針對特定型別的鍵值對操作的函式，

Redis

會為用途不同的字典設定不同的函式。下圖展示

dictType

字典型別：

typedef struct dictType { // 計算雜湊值 unsigned int （*hashFunction）（const void *key）； // 複製鍵 void *（*keyDup）（void *privdata， const void *key）； // 複製值 void *（*valDup）（void *privdata， const void *obj）； // 對比鍵 int （*keyCompare）（void *privdata， const void *key1， const void *key2）； // 銷燬鍵 void （*keyDestructor）（void *privdata， void *key）； // 銷燬值 void （*valDestructor）（void *privdata， void *obj）；} dictType；

privdata

屬性儲存針對不同的型別操作的函式傳的可選引數。

ht［2］

是包含兩個數大小的陣列，型別為

dictht

雜湊表。字典只使用

ht［0］

雜湊表，ht

［1］

只會對

ht［0］

雜湊表進行

rehash

時使用。

rehashidx

記錄了

rehash

的進度，如果目前沒有進行的

rehash

，那麼它的值為

-1

。

下圖為一個普通狀態下（沒有進行rehash）的字典：

雜湊演算法

當要將一個新的鍵值對新增到字典中，程式需要先根據鍵值對中的鍵計算出雜湊值和索引值，然後根據索引值，將包含新鍵值的雜湊表放在雜湊表陣列的指定索引上。

Redis

計算雜湊值和索引值的步驟如下：

使用字典設定的雜湊函式，計算鍵的雜湊值。

hash = dict—>type->hashFunction(key)

使用雜湊表的

sizemask

屬性和雜湊值，取餘計算出雜湊值。

index = hash & dict ->ht[x].sizemask

瞭解過HashMap底層原理的同學應該知道，上面計算索引值和HashMap找到索引下標的原理是類似的。

什麼是取餘

&

運算？

取餘就是計算兩數相除的餘數， 比如一個數組長度為4，索引範圍是

0~3

，需要放置

0，1，7

，放置如下圖所示：

舉個例子，要將一個鍵值對

k0

和

v0

新增到下方的空字典表中：

首先計算鍵的雜湊值：

hash = dict—>type->hashFunction（key）

計算鍵

k0

的雜湊值。

假設計算出來的雜湊值為

8

，然後計算索引值：

index = dict -> hash & ht［0］。sizemask = 8 & 3 = 0；

計算出鍵

k0

的索引值

0

，這表示鍵值對

k0

和

v0

的節點放置到雜湊表陣列下標

0

的位置上，如下圖所示：

鍵衝突

當兩個或者兩個以上的計算出陣列索引值一致時，就發生了

鍵衝突

。

Redis的雜湊表採用

連結串列法

來解決鍵衝突，每個雜湊表的節點都有一個

next

指標，多個雜湊表節點用

next

指標組成一個單鏈表，被分配到同一個陣列索引上的多個節點使用單向連結串列連線起來，這就很好的解決了

鍵衝突

的問題。

舉個例子，程式要將一個鍵值對

k2

和

v2

新增到下圖的雜湊表中，並且計算

k2

的索引值為

2

，那麼鍵

k1

和

k2

將發生衝突：

解決衝突的辦法

就是使用

next

指標將

k2

和

k1

所在的節點連線起來，如下圖所示：

總結

字典是一種對映的

鍵值對

資料結構，其中鍵是唯一的，透過唯一的鍵可以快速找到對應的值。

字典包含廣泛用在

Redis

資料庫中。

其中所有資料型別的鍵值對都使用字典作為底層實現。

Hash

型別的鍵值對也是基於字典實現。

字典的結構

包含一個字典，包含根據特定型別處理的函式

dictType

、兩個雜湊表

ht［2］

，字典只用到了

ht［0］

，遇到了擴容才會使用

ht［1］

。

一個字典包含

兩個雜湊表

，每個雜湊表

dictht

包含一個

table

陣列，

size

記錄陣列的大小，

sizemask

等於

size-1

，

sizemask

和雜湊值決定資料存在在

table

的位置。

used

記錄已有的鍵值對。

雜湊表節點dictEntry

結構儲存一個鍵值對，其中

key

儲存鍵，

V

儲存值，

V

可以是一個指標、可以是

uint64_t

整數、也可以是

int64_t

的整數。

next

是為了解決

鍵hash衝突

，兩個鍵的計算出的索引在陣列的同一個地方，就使用

next`指標連線在一起。

新增一個鍵值對，首先透過呼叫

dict—>type->hashFunction（key）

計算

鍵的雜湊值

，再和

dictht

的

sizemask

做取餘操作，計算得到要存放

table

陣列的索引位置。如果發生

鍵衝突

時，使用

連結串列法

將多個雜湊節點透過

next

指標組成一個單鏈表。

Redis

字典的實現和

Java

中的

HashMap

資料結構有以下類似的點：

確定索引位置：

鍵首先使用雜湊演算法算出雜湊值，再和陣列的

長度-1

做取餘操作，確定存放陣列的下標。

解決hash衝突:

兩個鍵值計算的索引一致，採用

連結串列法

，將多個節點透過

next

指標連在一起。

參考

Redis設計與實現