Redisbook學習筆記（1）字典（1）

字典（dictionary），又名映射（map）或關聯數組（associative array）， 它是一種抽象資料結

構，由一集鍵值對（key-value pairs）組成，各個鍵值對的鍵各不相同，程式可以将新的鍵值對

添加到字典中，或者基于鍵進行查找、更新或删除等操作。

字典的主要用途有以下兩個：

1. 實作資料庫鍵空間（key space）

2. 用作Hash 類型鍵的其中一種底層實作

實作資料庫鍵空間

Redis 是一個鍵值對資料庫，資料庫中的鍵值對就由字典儲存：每個資料庫都有一個與之相對

應的字典，這個字典被稱之為鍵空間（key space）。

當使用者添加一個鍵值對到資料庫時（不論鍵值對是什麼類型），程式就将該鍵值對添加到鍵空

間；當使用者從資料庫中删除一個鍵值對時，程式就會将這個鍵值對從鍵空間中删除；等等。

用作Hash 類型鍵的其中一種底層實作

Redis 的Hash 類型鍵使用以下兩種資料結構作為底層實作:

1. 字典；

2. 壓縮清單；

因為壓縮清單比字典更節省記憶體，是以程式在建立新Hash 鍵時，預設使用壓縮清單作為底層

實作，當有需要時，程式才會将底層實作從壓縮清單轉換到字典。

字典的實作

實作字典的方法有很多種：

 最簡單的就是使用連結清單或數組，但是這種方式隻适用于元素個數不多的情況下；

 要兼顧高效和簡單性，可以使用哈希表；

 如果追求更為穩定的性能特征，并且希望高效地實作排序操作的話，則可以使用更為複

雜的平衡樹；

在衆多可能的實作中，Redis 選擇了高效且實作簡單的哈希表作為字典的底層實作。

dict.h/dict 給出了這個字典的定義：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

<code>/*</code>

<code>* 字典</code>

<code>**</code>

<code>每個字典使用兩個哈希表，用于實作漸進式rehash ，即哈希表擴容</code>

<code>*/</code>

<code>typedef struct dict {</code>

<code>// 特定于類型的處理函數</code>

<code>dictType *type;</code>

<code>// 類型處理函數的私有資料</code>

<code>void</code> <code>*privdata;</code>

<code>// 哈希表（2 個）</code>

<code>dictht ht[</code><code>2</code><code>];</code>

<code>// 記錄rehash 進度的标志，值為-1 表示rehash 未進行</code>

<code>int</code> <code>rehashidx;</code>

<code>// 目前正在運作的安全疊代器數量</code>

<code>int</code> <code>iterators;</code>

<code>} dict;</code>

注意dict 類型使用了兩個指針分别指向兩個哈希表。

其中，0 号哈希表（ht[0]）是字典主要使用的哈希表，而1 号哈希表（ht[1]）則隻有在程式

對0 号哈希表進行rehash 時才使用。

哈希表實作

字典所使用的哈希表實作由dict.h/dictht 類型定義：

<code>* 哈希表</code>

<code>typedef</code> <code>struct</code> <code>dictht {</code>

<code>// 哈希表節點指針數組（俗稱桶，bucket）</code>

<code>dictEntry **table;</code>

<code>// 指針數組的大小</code>

<code>unsigned </code><code>long</code> <code>size;</code>

<code>// 指針數組的長度掩碼，用于計算索引值</code>

<code>unsigned </code><code>long</code> <code>sizemask;</code>

<code>// 哈希表現有的節點數量</code>

<code>unsigned </code><code>long</code> <code>used;</code>

<code>} dictht;</code>

table 屬性是一個數組，數組的每個元素都是一個指向dictEntry 結構的指針。

每個dictEntry 都儲存着一個鍵值對，以及一個指向另一個dictEntry 結構的指針：

<code>* 哈希表節點</code>

<code>typedef</code> <code>struct</code> <code>dictEntry {</code>

<code>// 鍵</code>

<code>void</code> <code>*key;</code>

<code>// 值</code>

<code>union</code> <code>{</code>

<code>void</code> <code>*val;</code>

<code>uint64_t u64;</code>

<code>int64_t s64;</code>

<code>} v;</code>

<code>// 鍊往後繼節點</code>

<code>struct</code> <code>dictEntry *next;</code>

<code>} dictEntry;</code>

next 屬性指向另一個dictEntry 結構，多個dictEntry 可以通過next 指針串連成連結清單，從

這裡可以看出，dictht 使用鍊位址法來處理鍵碰撞：當多個不同的鍵擁有相同的哈希值時，哈

希表用一個連結清單将這些鍵連接配接起來。

下圖展示了一個由dictht 和數個dictEntry 組成的哈希表例子：

<a href="http://s3.51cto.com/wyfs02/M01/11/91/wKioL1LVSEeTpFxrAADhOazr_ic213.jpg" target="_blank"></a>

如果再加上之前列出的dict 類型，那麼整個字典結構可以表示如下：

<a href="http://s3.51cto.com/wyfs02/M00/11/92/wKiom1LVSHmALDvWAAD7DusTTJY742.jpg" target="_blank"></a>

在上圖的字典示例中，字典雖然建立了兩個哈希表，但正在使用的隻有0 号哈希表，這說明字

典未進行rehash 狀态。

建立新字典

<a href="http://s3.51cto.com/wyfs02/M00/11/92/wKiom1LVSOLQhSS3AAD7vuy5spI163.jpg" target="_blank"></a>

新建立的兩個哈希表都沒有為table 屬性配置設定任何空間：

 ht[0]-&gt;table 的空間配置設定将在第一次往字典添加鍵值對時進行；

 ht[1]-&gt;table 的空間配置設定将在rehash 開始時進行；

添加鍵值對到字典

根據字典所處的狀态，将一個給定的鍵值對添加到字典可能會引起一系列複雜的操作：

 如果字典為未初始化（也即是字典的0 号哈希表的table 屬性為空），那麼程式需要對0

号哈希表進行初始化；

 如果在插入時發生了鍵碰撞，那麼程式需要處理碰撞；

 如果插入新元素使得字典滿足了rehash 條件，那麼需要啟動相應的rehash 程式；

當程式處理完以上三種情況之後，新的鍵值對才會被真正地添加到字典上。

整個添加流程可以用下圖表示：

<a href="http://s3.51cto.com/wyfs02/M02/11/91/wKioL1LVShjCy-JnAAFF_PDoi_k441.jpg" target="_blank"></a>

<a href="http://s3.51cto.com/wyfs02/M01/11/92/wKiom1LVSlbhsZeCAABfLA8zDRw223.jpg" target="_blank"></a>

在接下來的三節中，我們将分别看到添加操作如何在以下三種情況中執行：

1. 字典為空;

2. 添加新鍵值對時發生碰撞處理；

3. 添加新鍵值對時觸發了rehash 操作；

~~每次遇到指針，就有點頭大，明天繼續吧！

本文轉自shayang8851CTO部落格，原文連結：http://blog.51cto.com/janephp/1351687，如需轉載請自行聯系原作者