字典

簡介

• 字典又稱符號表，映射或關聯數組，是一種保存鍵值對的抽象數據結構。
• Redis數據庫的底層也是用字典實現的，對數據庫的增刪改查也是基于對字典的操作之上的。
• 字典還是哈希鍵的底層實現之一，當哈希鍵對比較多或者鍵值對中的元素都是比較長的，Redis就會使用字典作為底層實現。

字典實現

字典的實現是以哈希表作為它的底層實現，一個哈希表可以有多個哈希表節點，每個節點保存了字典中的一個鍵值對。
1.哈希表節點
key就是鍵，v就是鍵中的值（可以是指針，unit64_t 整數， int64_t s64整數），next是將另外一個哈希值相同的鍵值對連接在一起的指針（為了解決沖突）

typedef struct dictEntry{void *key;union{void *var;unit64_t u64;int64_t s64;}v;struct dictEntry *next; }

2.哈希表
table屬性是一個數組，數組中每個元素都指向一個哈希表節點 ，每個哈希表節點都保存著一個鍵值對。
size記錄了哈希表的大小，也就是table數組的大小。
used屬性記錄哈希表目前已有哈希表節點（鍵值對）的數量。
sizemask總是等于size-1（這個屬性和哈希值一起決定一個鍵應該被放到table的那個索引上）。

typedef struct dictht{dictEntry **table；unsigned long size；unsigned long sizemask；unsigned long used； }dictht；

3.字典
type和pribdata是配套的，針對不同類型的鍵值對，為創建多態字典而設置的。
type指向dictType結構的指針，每一個dictType里都保存了一簇用于操作特定類型鍵值對的函數（為用途不同的字典設置不同的類型特定函數）。
privdata保存了需要傳給那些類型特定函數的可選參數（也就是在dictType結構體中的參數）。
ht包含了兩項數組，每個項都是dictht哈希表，字典只使用ht[0]哈希表，ht[1]只會在ht[0]rehash時使用，除了ht[1]之外另一個和rehash（重新散列）有關的就是rehashidx（記錄rehash進度，若沒在進行rehash則值為-1）.

typedef struct dict{dicType *type；void *pribdata；dictht ht[2];int trehashidx; }dict; /* 保存一連串操作特定類型鍵值對的函數 */ typedef struct dictType {uint64_t (*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;

這就是字典實現的數據結構，如果要數據庫性能好，還是要用一些性能較好的算法，Redis使用的MurmurHash2算法來計算鍵的哈希值（數據庫的底層實現或者哈希鍵的底層實現）。

哈希算法

在我們需要把一個新的鍵值對加入到字典里，程序得先根據鍵值對的鍵計算出哈希值和索引值，然后根據索引，將新鍵值對的哈希表節點方法哈希表數組的指定索引（位置）上，這都是由哈希算法來完成的。哈希算法的設計推理就不寫了，因為這個是一個很復雜的過程。
Redis計算哈希值和索引值的方法

//用字典設置的哈希函數計算key的哈希值 hash = dict->type->hashFunction(key); //利用哈希表的sizemask和哈希值來計算出索引值，h[x]可以是h[1]或h[0]因情況而定。 index = hash & dict->ht[x].sizemask;

這種算法的優點就是：對于輸入有規律的鍵仍能給出一個很好的隨機分布性而且計算速度也很快！但是呢，這種算法可能會出現沖突，因此要避免沖突就得由個解決沖突的辦法？（在前面提到過）

解決鍵沖突

什么是沖突：因為算法執行時會有可能多個鍵被分配到哈希數組的同一個索引上。
Redis中解決鍵沖突采用的是鏈地址法，每個節點都有一個next指針，構成沖突的節點可以用next指針構成一個單鏈表來共同占有同一個索引。這個解決方法也是解決沖突比較經典的方法，也是比較簡單的方法。

rehash

rehash是什么？為什么要rehash？
rehash是重新散列的意思，因為在不斷的執行中，哈希表保存的鍵值對在逐漸增多或減少，為了讓哈希表的負載因子（load factor）維持在合理范圍內，當哈希表中的鍵值對過多或者過少時，需要對表的大小進行擴展或收縮。
哈希表執行rehash的步驟：
1.為字典的ht[1]分配空間，此哈希表的大小取決于要執行的操作和h[0]包含的鍵值對的數量（ht[0].used）

• 擴展操作：h[1]的大小等于第一個大于ht[0].used*2的2的n次方。
• 收縮操作：h[1]的大小等于第一個大于ht[0].used的2的n次方。

2.將保存在ht[0]中的鍵值對到ht[1]上：重新計算哈希值和索引，然后將鍵值對放到ht[1]哈希表的指定位置上。
3. ht[0]遷移到ht[1]后，ht[0]變為空表然后釋放掉，然后再將ht[1]設置為ht[0]，并再ht[1]位置上新建一個空白的哈希表，供下一次rehash使用。

哈希表的自動擴展與收縮

如果在負載因子不合理時沒有進行手動的rehash的話，那系統會在某些條件成立下自動進行擴展或收縮。
哈希表的負載因子求法：負載因子=以保存節點數量/哈希表大小

load_factor = ht[0].userd/ht[0].size

• ?

• 當系統滿足以下的任意一個條件程序就會自動開始對哈希表執行擴展操作：
  1.服務器目前沒在執行BGSAVE命令或者BGREWRITEAOF命令并且哈希表的負載因子大于1
  2.服務器目前正執行BGSAVE命令或者BGREWRITEAOF命令并且負載因子大于5
• 當系統滿足負載因子小于0.1，就會自動進行收縮操作。

漸進式rehash

其實在擴展或者收縮哈希表的時候并不是一次性，集中性的執行的，而是分多次，漸進式地完成的。
漸進式的詳細步驟：
1.為ht[1]分配空間，此時字典同時有ht[0]和ht[1]兩個哈希表。
2.在字典中維持一個索引計數器變量rehashidx，并設為0，表示rehash正式開始。
3.在rehash期間，每次對字典進行添加，刪除，查找，更新時，程序除了執行指定操作以外，還會順帶將ht[0]哈希表在rehashidx索引上的所有鍵值對rehash到ht[1]上，rehash完成，然后rehashidx+1。
4.直到全部內移到ht[1]，這時rehashidx屬性的值設為-1，表示rehash操作完成。
采取分而治之的方式，將rehash鍵值對所需的工作均攤到對字典的增刪改查上，避免了集中式rehash帶來的龐大計算量。

漸進式rehash執行期間的哈希表操作

因為在rehash期間字典會同時使用ht[0]和ht[1]，因此，增刪改查會在兩個哈希表上進行，比如查詢操作，先對0表掃描如果沒找到，就再從1表里找。注意的是，如果在此期間進行插入操作的話，那就會插入到1表，而不是0表。因為插入到0表就沒意義了等于浪費體力。也保證了0表只減不增。

總結

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

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