Redis 遇到 Hash 沖突怎么辦？
在 Redis 中，哈希表是一種常見的數(shù)據(jù)結構，通常用于存儲對象的屬性，對于哈希表，最常遇到的是哈希沖突，那么，當 Redis遇到Hash沖突會如何處理？這篇文章，我們將詳細介紹Redis如何處理哈希沖突，并探討其性能和實現(xiàn)細節(jié)。
Redis中的哈希表實現(xiàn)
在Redis中，哈希表被用于實現(xiàn)多個內(nèi)部數(shù)據(jù)結構，包括數(shù)據(jù)庫的鍵空間（key space）和哈希類型（hash type）。Redis的哈希表實現(xiàn)基于一個稱為 dict 的數(shù)據(jù)結構。dict 結構內(nèi)部使用了兩個哈希表，以支持漸進式rehashing。
哈希表結構
Redis的哈希表結構定義如下：
typedef struct dictht {
dictEntry **table; // 哈希表數(shù)組
unsigned long size; // 哈希表大小
unsigned long sizemask; // 哈希表大小掩碼，用于計算索引
unsigned long used; // 已使用的哈希表節(jié)點數(shù)量
} dictht;dictEntry 是哈希表的節(jié)點，定義如下：
typedef struct dictEntry {
void *key; // 鍵
union {
void *val; // 值
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next; // 指向下一個哈希表節(jié)點，形成鏈表
} dictEntry;每個哈希表節(jié)點包含一個鍵和值，以及一個指向下一個節(jié)點的指針。這個指針用于解決哈希沖突。
哈希沖突解決策略
在Redis中，哈希沖突通過鏈地址法（Chaining）來解決。具體來說，當多個鍵映射到同一個哈希桶時，這些鍵會被存儲在一個鏈表中。鏈地址法的優(yōu)點是實現(xiàn)簡單，且在哈希表負載因子較低時性能較好。
1.鏈地址法實現(xiàn)
當插入一個鍵值對時，Redis首先計算鍵的哈希值，并根據(jù)哈希值找到對應的哈希桶。如果該桶為空，則直接插入；如果該桶不為空，則在鏈表的頭部插入新節(jié)點。因此，Redis的哈希表是一個帶有頭插法的鏈表。
以下是插入操作的偽代碼：
function dictAdd(dict, key, value):
index = hashFunction(key) & dict.sizemask
if dict.table[index] == NULL:
dict.table[index] = new dictEntry(key, value)
else:
newEntry = new dictEntry(key, value)
newEntry.next = dict.table[index]
dict.table[index] = newEntry2.查找操作
查找操作時，Redis首先計算鍵的哈希值，并找到對應的哈希桶。然后在桶內(nèi)的鏈表中進行遍歷查找，直到找到對應的鍵或鏈表結束。
以下是查找操作的偽代碼：
function dictFind(dict, key):
index = hashFunction(key) & dict.sizemask
entry = dict.table[index]
while entry != NULL:
if entry.key == key:
return entry.value
entry = entry.next
return NULL漸進式rehashing
為了保持哈希表的性能，Redis需要在哈希表過于擁擠時進行擴容，或在哈希表過于空閑時進行縮容。Redis采用漸進式rehashing策略，以避免在rehash過程中阻塞服務。
rehashing過程
rehashing的過程如下：
- 創(chuàng)建一個新的哈希表，大小為當前哈希表的兩倍或一半。
- 將舊哈希表中的數(shù)據(jù)逐漸遷移到新哈希表中。
- 遷移完成后，釋放舊哈希表的內(nèi)存。
漸進式rehashing通過分批次將舊哈希表的數(shù)據(jù)遷移到新哈希表來實現(xiàn)。具體來說，每次增刪改查操作都會順便遷移一定數(shù)量的哈希表節(jié)點，直到遷移完成。
以下是漸進式rehashing的偽代碼：
function rehashStep(dict):
if dict.rehashidx == -1:
return
for i = 0 to REHASH_BATCH_SIZE:
if dict.rehashidx >= dict.size:
dict.rehashidx = -1
break
while dict.table[dict.rehashidx] == NULL:
dict.rehashidx += 1
entry = dict.table[dict.rehashidx]
while entry != NULL:
nextEntry = entry.next
index = hashFunction(entry.key) & dict.new_ht.sizemask
entry.next = dict.new_ht.table[index]
dict.new_ht.table[index] = entry
entry = nextEntry
dict.table[dict.rehashidx] = NULL
dict.rehashidx += 1性能分析
Redis的哈希表在負載因子較低時性能優(yōu)越，但在負載因子較高時，鏈表的長度會增加，從而導致查找性能下降。為了解決這個問題，Redis通過漸進式rehashing保持哈希表的負載因子在合理范圍內(nèi)。
總結
Redis通過鏈地址法解決哈希沖突，并通過漸進式 rehashing 保持哈希表的性能。鏈地址法實現(xiàn)簡單且在負載因子較低時性能較好，但在負載因子較高時性能會下降。漸進式rehashing通過分批次遷移數(shù)據(jù)，避免了 rehash過程中的服務阻塞，從而保持了系統(tǒng)的高性能和高可用性。
通過以上機制，Redis在處理哈希沖突時能夠有效地平衡性能和復雜度，確保在各種使用場景下都能提供高效的數(shù)據(jù)存儲和檢索服務。
