溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容介紹了“分析Redis中的字典、哈希算法和ReHash原理”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！
Redis 中的字典被廣泛用于實現Redis的各種功能，其中包括數據庫和哈希鍵。
字典的底層實現為哈希表，每個字典帶有兩個哈希表，一個平時使用，另一個在進行rehash擴充空間時才使用。
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
哈希表擴展與收縮的條件如下：
服務器目前沒有在執行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的負載因子大于等于1；
服務器目前正在執行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的負載因子大于等于5；
上述的條件有一個滿足，就會執行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 值；
當哈希表數量多時，如果一下子將數據都復制過去，那么就很有可能對服務器造成影響。所以Redis是分多次進行rehash的，也就是漸進式rehash。
簡單來說就是在第二步操作時，Redis仍然正常處理客戶端請求，每處理一個請求時，從哈希表1中的第一個索引位置開始，順帶著將這個索引位置上所有的entries元素拷貝到哈希表2中；等下一次請求時，再順帶拷貝下一個索引位置的entries。
這樣就很巧妙地將一次性大量拷貝的開銷，分攤到多次處理請求的過程中了，避免了耗時操作，保證了數據的快速訪問。
在進行 漸進式rehash操作時，字典的刪除、查找、更新等操作會在兩個哈希表中執行。例如要在字典中查找一個鍵的話，會先去原表中進行查詢，如果找不到就會去新表查詢。
而字典的添加操作一律只會保存在新表中。
“分析Redis中的字典、哈希算法和ReHash原理”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
