在 Redis 中，哈希表是一種常見的數(shù)據(jù)結(jié)構(gòu)，通常用于存儲(chǔ)對(duì)象的屬性，對(duì)于哈希表，最常遇到的是哈希沖突，那么，當(dāng) Redis遇到Hash沖突會(huì)如何處理？這篇文章，我們將詳細(xì)介紹Redis如何處理哈希沖突，并探討其性能和實(shí)現(xiàn)細(xì)節(jié)。

Redis中的哈希表實(shí)現(xiàn)

在Redis中，哈希表被用于實(shí)現(xiàn)多個(gè)內(nèi)部數(shù)據(jù)結(jié)構(gòu)，包括數(shù)據(jù)庫(kù)的鍵空間（key space）和哈希類型（hash type）。Redis的哈希表實(shí)現(xiàn)基于一個(gè)稱為 dict 的數(shù)據(jù)結(jié)構(gòu)。dict 結(jié)構(gòu)內(nèi)部使用了兩個(gè)哈希表，以支持漸進(jìn)式rehashing。

哈希表結(jié)構(gòu)

Redis的哈希表結(jié)構(gòu)定義如下：

typedef struct dictht {
    dictEntry **table;  // 哈希表數(shù)組
    unsigned long size; // 哈希表大小
    unsigned long sizemask; // 哈希表大小掩碼，用于計(jì)算索引
    unsigned long used; // 已使用的哈希表節(jié)點(diǎn)數(shù)量
} dictht;

dictEntry 是哈希表的節(jié)點(diǎn)，定義如下：

typedef struct dictEntry {
    void *key; // 鍵
    union {
        void *val; // 值
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; // 指向下一個(gè)哈希表節(jié)點(diǎn)，形成鏈表
} dictEntry;

每個(gè)哈希表節(jié)點(diǎn)包含一個(gè)鍵和值，以及一個(gè)指向下一個(gè)節(jié)點(diǎn)的指針。這個(gè)指針用于解決哈希沖突。

哈希沖突解決策略

在Redis中，哈希沖突通過鏈地址法（Chaining）來解決。具體來說，當(dāng)多個(gè)鍵映射到同一個(gè)哈希桶時(shí)，這些鍵會(huì)被存儲(chǔ)在一個(gè)鏈表中。鏈地址法的優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單，且在哈希表負(fù)載因子較低時(shí)性能較好。

1.鏈地址法實(shí)現(xiàn)

當(dāng)插入一個(gè)鍵值對(duì)時(shí)，Redis首先計(jì)算鍵的哈希值，并根據(jù)哈希值找到對(duì)應(yīng)的哈希桶。如果該桶為空，則直接插入；如果該桶不為空，則在鏈表的頭部插入新節(jié)點(diǎn)。因此，Redis的哈希表是一個(gè)帶有頭插法的鏈表。

以下是插入操作的偽代碼：

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] = newEntry

2.查找操作

查找操作時(shí)，Redis首先計(jì)算鍵的哈希值，并找到對(duì)應(yīng)的哈希桶。然后在桶內(nèi)的鏈表中進(jìn)行遍歷查找，直到找到對(duì)應(yīng)的鍵或鏈表結(jié)束。

以下是查找操作的偽代碼：

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

漸進(jìn)式rehashing

為了保持哈希表的性能，Redis需要在哈希表過于擁擠時(shí)進(jìn)行擴(kuò)容，或在哈希表過于空閑時(shí)進(jìn)行縮容。Redis采用漸進(jìn)式rehashing策略，以避免在rehash過程中阻塞服務(wù)。

rehashing過程

rehashing的過程如下：

• 創(chuàng)建一個(gè)新的哈希表，大小為當(dāng)前哈希表的兩倍或一半。
• 將舊哈希表中的數(shù)據(jù)逐漸遷移到新哈希表中。
• 遷移完成后，釋放舊哈希表的內(nèi)存。

漸進(jìn)式rehashing通過分批次將舊哈希表的數(shù)據(jù)遷移到新哈希表來實(shí)現(xiàn)。具體來說，每次增刪改查操作都會(huì)順便遷移一定數(shù)量的哈希表節(jié)點(diǎn)，直到遷移完成。

以下是漸進(jìn)式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的哈希表在負(fù)載因子較低時(shí)性能優(yōu)越，但在負(fù)載因子較高時(shí)，鏈表的長(zhǎng)度會(huì)增加，從而導(dǎo)致查找性能下降。為了解決這個(gè)問題，Redis通過漸進(jìn)式rehashing保持哈希表的負(fù)載因子在合理范圍內(nèi)。

總結(jié)

Redis通過鏈地址法解決哈希沖突，并通過漸進(jìn)式 rehashing 保持哈希表的性能。鏈地址法實(shí)現(xiàn)簡(jiǎn)單且在負(fù)載因子較低時(shí)性能較好，但在負(fù)載因子較高時(shí)性能會(huì)下降。漸進(jìn)式rehashing通過分批次遷移數(shù)據(jù)，避免了 rehash過程中的服務(wù)阻塞，從而保持了系統(tǒng)的高性能和高可用性。

通過以上機(jī)制，Redis在處理哈希沖突時(shí)能夠有效地平衡性能和復(fù)雜度，確保在各種使用場(chǎng)景下都能提供高效的數(shù)據(jù)存儲(chǔ)和檢索服務(wù)。