redis 系列6 數據結構之字典(下)

一.概述

　　接著上篇繼續，這篇把數據結構之字典學習完， 這篇知識點包括：哈希演算法，解決鍵衝突， rehash , 漸進式rehash,字典API。

　　1.1 哈希演算法

　　　　當一個新的鍵值對 需要添加到字典裡面時，程式需要先根據“鍵值對”的鍵計算出哈希值和索引值，再根據索引值，將包含新“鍵值對”的哈希表節點放到哈希表數組的指定索引上面。redis計算哈希值和索引值的方法如下:

#使用字典設置的哈希函數，計算鍵key的哈希值
hash = dict -> type->hashFunction(key);
# 使用哈希表的sizemask屬性和哈希值，計算出索引值, ht[x] 可以是ht[0] 或者ht[1]
index = hash & dict->ht[x].sizemask;

　　　　例1： 將一個“鍵值對”K0和V0 添加到字典裡面，那麼程式會使用如下語句，假設hash變數的哈希值為8, sizemask為3, &是指"按位與"運算符。公式如下：

hash = dict -> type->hashFunction(K0);
index= hash $ dict ->ht[0]. sizemask=8 &3 = 0;

　　　　通過公式計算出健K0的索引值為0，這個新的“鍵值對”節點應該放置到哈希表數組的索引0位置，對於哈希演算法的底層實現，redis使用MurmurHash2演算法來計算鍵的哈希值。Murmur哈希是一種非加密散列函數，目前有三個版本(MurmurHash1、MurmurHash2、MurmurHash3),這裡不在深入，例1如下圖所示：

　　1.2 解決鍵衝突

　　　　當有兩個或以上數量的鍵被分配到了哈希表數組的同一個索引上面時，稱為鍵衝突。Redis 的哈希表使用“鏈地址”來解決鍵衝突，每個哈希表節點都有一個next指針，多個哈希表節點可以用next指針構成一個單向鏈表，被分配到哈希表數組同一個索引上，用單向鏈表把多個節點連接一起，解決了鍵衝突問題。

　　　　例2： 程式要將新"鍵值對"k2和v2 添加到哈希表中，計算的k2 索引值為2, 但該哈希表數組索引值2上已有"鍵值對"k1和v1。 解決鍵索引衝突的辦法就是使用next指針將鍵k2和鍵k1的節點連接起來，如下圖所示：

 　　1.3 rehash 重新散列

 　　　　隨著對哈希表數組的不斷操作， 哈希表數組保存的"鍵值對"節點會增多或減少，為了讓哈希表的負載因數維持在一個合理的範圍之內，當哈希表保存的“鍵值對”數量太多或者太少時，程式需要對哈希表的大小進行相應的擴展或收縮。擴展或收縮哈希表的工作是通過執行rehash 操作來完成的，Redis字典的哈希表執行reash的步驟如下：

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

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

　　　　(3) 當ht[0]包含的所有“鍵值對”都遷移到了ht[1]之後,釋放ht[0], 將ht[1]設置為ht[0],併在ht[1]新創建一個空白的哈希表，為下一次rehash準備。

　　　　例3： 下麵是對ht[0]進行擴展操作，在沒有rehash之前，字典如下所示

　　　　ht[0].used當前的值為4(擴展公式為ht[0].used *2,  2^3次方), 程式會將ht[1]哈希表的大小設置為8,ht[1]在分配空間之後，字典如下所示：

　　　　將ht[0]包含的四個“鍵值對”都rehash到ht[1]，此時釋放了ht[0]的哈希表，如下圖所示：

　　　　最後將ht[1] 設置為ht[0], 然後為ht[1]分配一個空白哈希表，至此，對哈希表的擴展操作執行完畢，程式成功將哈希表的大小從原來的4改為了現在的8，如下圖所示：

　　　　總結：哈希表的擴展與收縮。當以下條件中的任意一個被滿足時，程式會自動開始對哈希表執行擴展操作：

　　　　　　(1) 伺服器目前沒有在執行bgsave命令或者bgrewriteaof命令，並且哈希表的負載因數大於等於1。

　　　　　　(2) 伺服器目前正在執行bgsave命令或者bgrewriteaof命令，並且哈希表的負載因數大於等於5。

#負載因數= 哈希表已保存節點數量 / 哈希表大小
load_factor=ht[0].used /ht[0].size

　　　　　　例如：對於一個大小為4,包含4個“鍵值對”的哈希表來說，這個哈希表的負載因數為: load_factor= 4/4=1。 又例如，對於一個大小為512，包含256個“鍵值對“的哈希表來說，這個哈希表的負載因數為: load_factor=256/512=0.5(這個要不需要擴展)。另外當哈希表的負載因數小於0.1時,程式自動開始對哈希表執行收縮操作。

 　　1.4 漸進式 rehash

　　　　上面rehash擴展或收縮哈希表需要將ht[0] 裡面的所有”鍵值對“ rehash到ht[1]裡面， 這個rehash動作並不是一次性，集中式完成的，而是分多次，漸進式完成的。這樣做原因在於考慮到有大量”鍵值對“，如果一次性將大量”鍵值對“全部rehash到ht[1]的話，龐大的計算量可能會導致伺服器在一段時間內停止服務。因此是漸進式的將ht[0]裡面的鍵值對慢慢地rehash到ht[1]。

　　　　例4 以下是哈希表漸進式rehash的詳細步驟：
　　　　　　(1) 為ht[1] 分配空間，讓字典同時持有ht[0]和ht[1]兩個哈希表。此時rehashidx值為-1。

　　　　(2) 在字典中維持一個索引計數器變數rehashidx，並將它的值設置為0,表示rehash工作正式開始(rehash了一個鍵值對)。此時rehashidx值為0。

　　　　(3) 在每次rehash進行期間，除了對字典執行操作，程式還會將ht[0]的rehashidx索引值增一，下圖是全部rehash完成，此時rehashidx值為3。

　　　　(4) 最後當ht[0]的所有鍵值對rehash到ht[1]，此時程式將rehashidx屬性的值為-1, 表示rehash操作全部完成。將ht[1]設置為ht[0],併在ht[1]新創建一個空白的哈希表，為下一次rehash準備

　　　　總結： 在漸進式 rehash執行期間，新添加到字典的鍵值對 一律會被保存到ht[1]裡面，而ht[0]則不再進行任何添加操作，這一措施保證了ht[0]包含的鍵值對數量只減不增，並隨著rehash操作的執行最終變成空表。

　　1.5 字典API (主要操作API)

　　最後字典總結：

　　　　(1) 字典被廣泛用於實現Redis的各種功能，其中包括資料庫和哈希鍵。

　　　　(2) Redis中的字典使用哈希表作為底層實現，每個字典帶有兩個哈希表，一個平時使用，另一個在rehash時使用。

　　　　(3) 當字典被用作資料庫的底層實現，或者哈希鍵的底層實現時，Redis使用MurmurHash2演算法來計算鍵的哈希值。

　　　　(4) 哈希表使用鏈地址法來解決鍵衝突，被分配到同一個索引上的多個“鍵值對”會連接成一個單向鏈表。

　　　　(5) 在對哈希表擴展或收縮操作時，程式需要將現有哈希表包含的所有“鍵值對”rehash到新哈希表裡面，並且這個rehash過程並不是一次性完成的，而是漸近式完成。