Redis的字典使用哈希表作為底層實作，一個哈希表中可以有多個哈希表節點，而每個哈希節點就保存在字典中的一個鍵值對，
redis字典所用的哈希表由disht結構定義，
typedef struct dictht{ dictEntry **table;//哈希表陣列 unsigned long size;//哈希表大小 unsigned long sizemask;//哈希表大小掩碼，用于計算索引值 ，總是等于size -1 unsigned long used;//該哈希表已有節點數量 }
table 屬性是一個陣列，陣列中的每個元素都是一個指向dictEntry結構的指標，每個dictEntry結構保存著一個鍵值對，其他的屬性不多說，
哈希表節點
哈希表節點使用dictEntry結構標識，每個dictEntry保存一個鍵值對，
typedef struct dictEntry{ void *key;//鍵 union{ void *val; uint64_tu64' int64_ts64' } v;//值 struct dictEntry *next;//指向下個哈希節點，形成鏈表 } ductEntry;
*next 屬性是指向另一個哈希表節點的指標，這個指標可以將多個哈希值相同的鍵值對連接在一起，解決鍵沖突的問題，所以，每一個哈希索引為一個單向鏈表，
Redis中的字典由dict結構表示：
typedef struct dict{ dictType *type;//型別特定函式 void *orivdata;//私有資料 dictht ht[2];//哈希表 int trehashidx;//rehash 索引 ，當rehash不再進行時，值為-1 } dict;
Redis計算哈希值和索引值的方法：
hash = dict->type->hashFunction(key);
index = hash & dict->ht[x].sizemask;
解決鍵沖突：
當兩個或兩個一個數量的鍵被分配到了哈希表陣列的同一個索引上面時，為我們稱作這些鍵發生沖突，Redis的哈希表使用鏈地址法來解決沖突，每個哈希表節點的next指標構成了一個單向鏈表，以此來解決鍵沖突，
另外由于鏈表沒有指向鏈表結尾的指標，為考慮速度，每次將新加的節點放到鏈表表頭位置（復雜度為O(1)），
Rehash
隨著哈希表保存的鍵增多或減少，為了讓哈希表的負載因子維持在一個合理的范圍內，程式會對哈希表的小小進行rehash（重新散列），
1、為字典表的ht[1]哈希表分配空間，這個哈希表的空間大小取決于要執行的操作以及ht[0]包含的鍵值對數量
（1）如果執行擴展，ht[1] =第一個>=ht[0].used * 2 的2的n次方冪，
（2）如果收縮 ht[1] = 第一個>=ht[0].used 的2的n次方冪
2、h[0] 遷移至h[1]，
3、清空h[0]，將h[1]設定為h[0]，新建h[1]，
漸進式rehash
字典表同時使用ht[0],ht[1],ht[0]通過索引計數器分批量的遷移至ht[1]，為解決ht[0]所持有的鍵值對量太大的問題，
不為別的，每天學一點，總會有識訓，
說明：尊重作者知識產權，文中內容參考《Redis設計與實作》，僅在此做學習與大家分享，
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/4611.html
標籤：NoSQL
上一篇：Redis學習筆記（二） 鏈表