Redis 數據結構：字典

前言

字典有多種叫法。可以叫 “符號表” ， “關聯數組” 以及 “映射” 。字典主要存儲的是鍵值對。鍵值對的鍵必須唯一。其中Redis的數據庫和哈希鍵的底層實現就是字典。

由於Redis的字典使用了散列表(哈希表)作爲底層實現，下面先了解一下什麼是散列表。

一、什麼是散列表（哈希表）

學習了數據結構我們應該知道，順序存儲結構的底層存儲位置是一塊連續的存儲空間。想要查找某元素，通常是採用循環法逐個對比。如果元素比較多，查詢效率就會很低。

那麼有沒有一種辦法不需要循環，也不需要對比，根據關鍵詞直接定位查詢呢？

通常我們查看通訊錄，並不會從上到下逐個尋找，而是通過姓名的拼音（關鍵詞）就可以直接定位到手機號碼。咦~ 沒錯，這樣的設計方式，正是我們所需要的。散列技術的思想就類似於這種形式。

散列技術就是在記錄的存儲位置和它的關鍵詞之間建立了確定的對應關係 F (function) , 每一個關鍵詞都有對應位置 (key)，通過位置找到值 (value)。

這種關係F 稱作爲散列函數或哈希函數，採用散列技術將記錄存儲在了一塊連續的存儲空間中，這塊連續的存儲空間就被稱爲散列表或哈希表。

舉個例子，想要通過散列技術存儲手機號碼信息。

分析：上圖例子，哈希函數通過拿取手機號碼後四位（這四位是比較有意義的關鍵詞）作爲哈希地址（key）。這個哈希地址（key）就是該手機號碼所存儲位置的鍵，而值就是手機號碼。如右側的綠色部分的鍵，是通過哈希函數處理所得。

#一個簡單哈希函數（截取後四位作爲哈希鍵）
int Hash(string key) {
  #截取後四位字符
  return hashValue =key.Substring(key.Length-4);
}

哈希函數可以參考以下兩個原則去實現。畢竟函數複雜會影響創建和查詢的效率。

計算簡單
散列地址分佈均勻

常規的哈希函數有以下幾種構造方法：

直接地址法
數字分析法
平方取中法
摺疊法
除留餘數法
隨機數法

二、散列衝突的解決方式

儘管再好的哈希函數，也很難避免鍵衝突的現實。仍然是基於上面的例子，假設手機號後四位的數字有兩條相同的，通過哈希算法算出的（key）自然也是相同的，那如果鍵衝突了應該怎麼解決呢？可採用以下四種方式。

2.1 開放定址法

開放定址法就是，對一個key進行哈希，發現算出來的這個地址已經被佔用了。此時，從當前位置逐個向下尋找未被使用的地址，如果找到最後還是沒有找到空餘位置，則重頭開始找，直到找到空餘位置爲止。缺點是找位置和查詢時都會很耗時間。

分析：如上圖所示，紅色箭頭的關鍵詞，和哈希表地址爲3的鍵發生了鍵衝突，此時從當前位置向下逐個找未被使用的地址。直到遇到未被使用的地址纔將數據存儲進去。如果哈希表找到底部，仍舊沒有找到未被使用的位置。則重頭再開始找位置。此時，找位置和後期查詢的時間複雜度O(n)。

2.2 鏈地址法

當發生鍵衝突的時候，會有2個或2個以上的值使用同一個地址。此時將這個地址指向一個鏈表地址，並由鏈表去存儲具體的值。缺點是查找時需要遍歷鏈表的時間。

分析：如上圖所示，紅色箭頭所指向的200003 和 200002 通過哈希函數算出的哈希地址，和哈希表中的鍵發生了衝突。

通過鏈地址法解決鍵衝突的做法是，將哈希表的鍵，指向鏈表的第一個頭結點地址。這樣每次有新的鍵發生了衝突，都將這個值放入鏈表的表頭結點，再由鏈表的表頭結點指向已有的鏈表的第一個頭元素。

鏈式法的缺點是，每次查詢元素時，一旦發現鍵指向的是鏈表的地址，則需要遍歷鏈表中的元素，此時的查詢時間複雜度是O(n)。

2.3 再散列函數法

首先是提供多個散列函數，當發生鍵衝突的時候，我們可以使用關鍵詞，換一個散列函數重新計算位置，直到計算出的位置沒有被使用過。缺點是增加了計算時間。

2.4 公共溢出區法

首先建立一個公共溢出區，當發生鍵衝突的時候，將這些衝突的鍵放到公共溢出區表中存儲。

分析：如上圖所示，在查找的時候，首先根據哈希算法獲得該元素的哈希地址後，在通過哈希地址從哈希表中獲取元素，獲取時間是O(1)，如果相等則查找成功。如果不相等，則到溢出表中進行順序查找。時間複雜度是O(n)。

三、散列表查找性能分析

在最理想的狀態下，散列表不發生鍵衝突，一個好的哈希函數可以儘可能的避免或減少鍵衝突的存在。在不發生鍵衝突的時候，散列表的查詢時間複雜度是O(1) 因爲散列表也是基於數組的，查詢速度非常快。迴歸於現實，鍵往往是會發生衝突的，那麼怎麼檢測一個散列表的是否會頻繁出現鍵衝突的狀態呢？

3.1 散列表的裝載因子和Rehash

裝載因子a = 提入表中的記錄個數/散列表長度

a 標誌着散列表的裝滿程度。當填入表的記錄越多，a 就越大，產生衝突的可能性就會越高。如果 a 太小，則會產生內存空間的不合理使用，造成內存空間的浪費。

所以我們可以控制裝載因子的大小，限定在一個區間範圍之內，纔可以儘可能的將查詢時間複雜度達到O(1)。爲了做到這一點，我們可以採用空間換時間的做法。也可以根據散列表進行收縮空間即rehash，進而改變散列表的大小。

四、Redis中的字典結構

Redis中的字典是採用了哈希表作爲底層實現，一個哈希表裏面可以有多個哈希結點，而每個哈希結點就保存了字典中的一個鍵值對。下圖是一個完整的普通狀態下的字典。

1）依據上圖，從左到右分析結構，首先看最左邊字典的結構。 redis中的字典由 dict.h/dict 結構表示：

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

type 屬性是一個指向dictType結構的指針，每個dictType結構保存了一簇用於操作特定類型鍵值對的函數，redis會根據不同用處的字典設置不同的函數類型。
privdata 屬性則保存了需要傳那些類型特定函數的可選參數。
ht 屬性是一個包含兩個項的數組，每個項都是一個dictht哈希表。一般情況下字典只使用 ht[0] 哈希表。而 ht[1] 哈希表只會對 ht[0] 哈希表進行rehash時使用。
trehashidx 屬性是結合與 ht[1] 來使用的，當沒有存在rehash的時候其值爲 -1。

2）再看一下散列表的結構：redis中的字典所使用的散列表由 dict.h/dictht 結構定義

typedef struct dictht {
    # 哈希表數組
    dictEntry **table;
    # 哈希表大小
    unsigned long size;
    # 哈希表大小掩碼，用於計算索引值
    # 總是等於 size-1
    unsigned long sizemask;
    # 該哈希表已有結點的數量
    unsigned long used;
}

可以設想一下，一個散列表就是一個數組，有大小，有總數量，還有一個索引值。

table 屬性是一個數組，數組中的每個元素都是一個指向 dict.h/dictEntry結構的指針。每個dictEntry結構存在一個鍵值對。
size 屬性記錄了散列表的大小，也是table數組的大小。
sizemask 屬性的值總是等於size-1，這個屬性和哈希值一起決定一個鍵應該放到數組的哪個索引上面。
used 屬性記錄了散列表已有數據（鍵值對）的數量。

3）再看一下哈希表結點的結構：哈希表結點使用dictEntry結構表示。每一個dictEntry結構都保存着一個鍵值對

typedef struct dictEntry {
    # 鍵
    void *key;
    # 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    }v;
    # 指向下個哈希表結點，形成鏈表
    struct dictEntry *next;
}dictEntry;

key 屬性保存着鍵值對的鍵。
v 屬性則保存着鍵值對中的值。其中鍵值對的值可以是一個指針又或者是一個整數。
next 屬性是指向另一個哈希表結點的指針，這個指針用於解決鍵衝突的，將多個相同鍵的值鏈接在一起形成一個鏈表。

五、Redis中的解決鍵衝突

經過上文的學習，我們已經知道，Redis中的字典底層是由哈希表來實現的。如果想要將一個鍵值對添加到字典中去。首先需要通過哈希算法獲得一個哈希鍵，通過這個哈希鍵的位置來儲存這個鍵值對。既然使用了哈希算法，就避免不了鍵衝突的存在，那麼在Redis中又是如果解決鍵衝突的問題呢？

當有兩個或以上的鍵被分配到同一個哈希表的同一個索引上，則稱爲鍵衝突。在 redis 中哈希表使用了鏈地址法來解決鍵衝突。通過哈希表中的 next 指針指向一個單向鏈表。被分配到同一個索引上的值則存儲在這個鏈表裏面。從而解決了哈希鍵衝突的問題。

5.1 Redis中的 rehash

通過上文中學習到，想要讓哈希表的負載因子維持在一個合理的範圍之內，需要對哈希表進行收縮或擴容。這個工作就交給了rehash (重新散列) 來完成。在redis中對字典的哈希表操作執行rehash的步驟如下：

1）爲字典的 ht[1] 哈希表分配空間，這個哈希表的空間大小取決於要執行的操作。以及 ht[0] 當前包含的鍵值對的數量

如果執行的是擴展操作，那麼 ht[1] 的大小爲第一個大於等於 ht[0].used * 2 的 2的n次方冪。
如果執行的是收縮操作，那麼 ht[1] 的大小爲第一個大於等於 ht[0].used 的大小。

2）將保存在 ht[0] 中的所有鍵值對 rehash 到 ht[1] 上面；rehash 指的是重新計算鍵的哈希值和索引值，然後將鍵值對放置到 ht[1] 哈希表的指定位置上。

3）當 ht[0] 包含的所有鍵值對都遷移到了 ht[1] 之後（ht[0]變成了空表）釋放 ht[0] ，再將 ht[1] 設置爲 ht[0] ，並在 ht[1] 新創建一個空的哈希表。爲下次rehash做準備。

舉個例子如下圖所示：

分析上圖，上圖的主要目的是將ht[0]哈希表的所有鍵值對rehash到 ht[1] 哈希表中去。

因爲ht[0] 的哈希表大小爲4，目前已經存儲滿了，需要擴容到2的次方冪升級到大小爲8空間。所以需要rehash擴容。

首先，從圖中最左側的字典中可以看到，rehashidx 從原本的 -1 已經變成了 2。這個是因爲 rehash 索引會從 -1 逐個變成 0、1、2、3 直到變成sizemask的大小爲止，則認爲rehash結束了。而目前 rehashidx 爲 2 則說明，ht[0] 哈希表中還有一個鍵值對待rehash到 ht[1] 中去。

因爲 ht[0] 中有4個元素，所以如果rehashidx 爲 3 的時候則認爲rehash 結束了，此時需要將 ht[1] 設置爲 ht[0] 並重新建立一個 ht[1] 的空哈希表。此時rehash結束。