這篇文章帶大家了解Redis中的字典、雜湊演算法和ReHash原理，希望對大家有幫助！
Redis 中的字典被廣泛用於實作Redis的各種功能，其中包括資料庫和雜湊鍵。
字典的底層實作為雜湊表，每個字典有兩個雜湊表，一個平常使用，另一個在進行rehash擴充空間時才使用。 【相關推薦：Redis影片教學】
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privdata;
// 哈希表，两个元素
dictht ht[2]
// rehash时记录的索引下标，当没有rehash时，值为-1
int rehashidx;
} dict;==在進行rehash時，rehashidx每遷移一個索引的entry資料就會1;==
其中，哈希表dictht 的結構定義為：
typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码，用于计算索引值
unsigned long sizenask;
// 该哈希表已有节点的数量
unsigned long uesd;
} dictht;其中，table是數組，數組的每一個元素指向dictEntry 類型的指針， dictEntry 類型裡保存一個鍵值對。
在這裡也可以看出雜湊表的節點是鍊錶相連來解決雜湊衝突問題的，也就是鏈結位址法。
為了實現從鍵到值的快速訪問，Redis使用了哈希表來保存所有鍵值對。 鍵對應Redis設定的Key，而值對應的並不是值本身，而是指向具體值的指標。使用雜湊表的最大好處就是可以用O(1)的時間複雜度快速找到鍵值對。但既然是哈希表，那麼必然會有哈希衝突的問題。
哈希衝突即指的是，當兩個key的雜湊值和雜湊桶計算對應關係時，剛好落在了同一個哈希桶上。
Redis解決哈希衝突的方式是使用鍊式哈希，即拉鍊法。當多個元素指向同一個雜湊桶時，在同一個雜湊桶中採用鍊錶來保存對應的數據，它們之間依序用指針連接。
當要將一個新的鍵值對加入字典裡面時，程式需要先根據鍵值對計算出雜湊值和索引值，然後再根據索引值，將包含新鍵值對的雜湊表節點放到雜湊表數組的指定索引上面。
在雜湊表中有個負載因子（load factor）來控制雜湊表所儲存的鍵值對數量。而這就需要rehash（重新散列）操作來完成。其中，負載因子的計算公式為：
// 负载因子 = 哈希表已保存的节点数量 / 哈希表大小 load_factor = ht[0].used / ht[0].size
哈希表擴展與收縮的條件如下：
上述的條件有一個滿足，就會執行rehash的過程。
如果伺服器正在執行BGSAVE 或BGREWRITEAOF時，Redis會建立目前伺服器程序的子程序
rehash的過程大概分成三步驟：
#給哈希表2分配更大的空間，例如是目前哈希表1的兩倍；
把哈希表1中的資料重新映射並拷貝到哈希表2中；
釋放哈希表1的空間；
其中，第一步分配空間的大小是由目前的rehash操作類型以及目前哈希表的鍵值對數量決定的。
當執行的是擴展操作，分配的空間大小為第一個大於等於（哈希表的鍵值對數量* 2） 的2^n 值;
假設目前的鍵值對數量為4，則4 * 2 = 8，因為8 剛好等於2^3，也就是剛好等於第一個等於2^n的值，所以擴充空間就為8;
如果執行的是收縮操作，則分配的空間大小為第一個大於等於（哈希表的鍵值對數量） 的2^n 值;
在進行 漸進式rehash運算時，字典的刪除、尋找、更新等運算會在兩個雜湊表中執行。例如要在字典中找一個鍵的話，會先去原表中查詢，如果找不到就會去新表查詢。
而字典的新增作業一律只會儲存在新表中。
更多程式相關知識，請造訪：程式設計入門！ ！
以上是淺談Redis中的字典、雜湊演算法和ReHash原理的詳細內容。更多資訊請關注PHP中文網其他相關文章！
