四、哈希表（Hashtable）
哈希表是一種高效的鍵值對數據結構，通過散列函數將鍵映射到表中的位置，實現快速的插入、刪除和查找操作。Redis 廣泛使用哈希表來實現 Hash 對象和數據庫的鍵值存儲。以下將從結構設計、哈希沖突與鏈式哈希、rehash、漸進式哈希和哈希觸發條件等角度詳細介紹 Redis 中的哈希表。
1. 結構設計
在 Redis 中，哈希表（dict）由兩個哈希表數組（dictht）組成，用于實現漸進式 rehash，以應對數據量增大時的性能問題。每個哈希表數組包含一個哈希表節點（dictEntry）的指針數組。哈希表節點用于存儲實際的鍵值對，并通過鏈地址法處理哈希沖突。
哈希表結構
typedef?struct?dictht?{dictEntry **table;????// 哈希表數組unsigned?long?size;???// 哈希表大小unsigned?long?sizemask;??// 哈希表大小掩碼，用于計算索引值unsigned?long?used;???// 哈希表中已使用的節點數量
} dictht;typedef?struct?dict?{dictType *type;???????// 類型特定函數void?*privdata;???????// 私有數據dictht ht[2];?????????// 哈希表，支持漸進式 rehashlong?rehashidx;???????// rehash 索引，-1 表示沒有進行 rehashunsigned?long?iterators;??// 當前正在運行的安全迭代器數量
} dict;typedef?struct?dictEntry?{void?*key;????????????// 鍵union?{void?*val;????????// 值uint64_t?u64;?????// 無符號整數值int64_t?s64;??????// 有符號整數值double?d;?????????// 雙精度浮點值} v;struct?dictEntry?*next;??// 指向下一個哈希表節點，解決沖突
} dictEntry;
主要字段介紹
- table：指向哈希表節點指針數組的指針。
- size：哈希表的大小，即哈希表數組的長度。
- sizemask：哈希表大小掩碼，用于計算鍵的索引值。
- used：哈希表中已使用的節點數量。
- rehashidx：rehash 的索引，表示當前進行到哪個位置，-1 表示沒有進行 rehash。
- type：指向哈希表類型特定函數的指針，用于實現不同類型的哈希表。
- privdata：指向私有數據的指針，可以用于存儲與哈希表相關的額外信息。
2. 哈希沖突及鏈式哈希
哈希沖突
哈希沖突是指不同的鍵通過哈希函數計算得到相同的索引值，從而映射到哈希表數組的同一位置。哈希沖突是哈希表的一種常見問題，需要有效的處理機制來解決。
鏈式哈希
鏈式哈希是一種解決哈希沖突的常用方法。它通過鏈表的形式，將所有哈希值相同的鍵值對連接在一起。每個哈希表數組的元素（dictEntry）都指向一個鏈表的頭節點，當發生哈希沖突時，新節點被插入到鏈表的頭部。
typedef?struct?dictEntry?{void?*key;????????????// 鍵union?{void?*val;????????// 值uint64_t?u64;?????// 無符號整數值int64_t?s64;??????// 有符號整數值double?d;?????????// 雙精度浮點值} v;struct?dictEntry?*next;??// 指向下一個哈希表節點，解決沖突
} dictEntry;
插入操作
在哈希表中插入鍵值對時，Redis 首先計算鍵的哈希值，并將其映射到哈希表數組中的一個位置。如果該位置已經有其他節點，則通過鏈地址法將新節點插入到鏈表的頭部。
int?dictAdd(dict *d,?void?*key,?void?*val)?{dictEntry *entry = dictAddRaw(d, key);if?(!entry)?return?DICT_ERR;dictSetVal(d, entry, val);return?DICT_OK;
}
查找操作
在哈希表中查找鍵對應的值時，Redis 通過計算鍵的哈希值來確定其在哈希表數組中的位置，然后遍歷鏈表查找對應的鍵值對。
dictEntry *dictFind(dict *d,?const?void?*key)?{if?(d->ht[0].size ==?0)?return?NULL;dictEntry *he = dictFindRaw(d, key);if?(he ==?NULL)?return?NULL;return?he;
}
刪除操作
在哈希表中刪除鍵值對時，Redis 同樣通過計算鍵的哈希值來確定其位置，然后遍歷鏈表找到對應的節點并將其刪除。
int?dictDelete(dict *d,?const?void?*key)?{if?(dictSize(d) ==?0)?return?DICT_ERR;if?(dictDeleteRaw(d, key) == DICT_OK) {if?(d->ht[0].used ==?0) _dictReset(&d->ht[0]);return?DICT_OK;}return?DICT_ERR;
}
3. rehash
rehash 的必要性
隨著哈希表中元素數量的增多，哈希表的負載因子（load factor）會不斷增大，從而影響性能。為了維持哈希表的性能，Redis 需要進行 rehash 操作，即重新分配哈希表的大小，并將原有的鍵值對重新分布到新的哈希表中。
rehash 過程
- 初始化新哈希表：當需要進行 rehash 時，首先為哈希表分配新的哈希表數組，并調整新哈希表的大小。
- 遷移節點：將舊哈希表的所有節點逐個遷移到新哈希表中。遷移過程中，計算每個節點的新哈希值，并將其插入到新哈希表的對應位置。
- 完成 rehash：當所有節點都遷移完成后，釋放舊哈希表的內存，將新哈希表替換為當前哈希表。
void?_dictRehashStep(dict *d) {if?(d->iterators ==?0) dictRehash(d,?1);
}
4. 漸進式 rehash
漸進式 rehash 的基本思想
漸進式 rehash 的基本思想是：將哈希表的擴容操作分攤到多次操作中完成，而不是一次性完成，從而避免一次性 rehash 帶來的性能問題。通過漸進式 rehash，Redis 可以在保證高效操作的同時，平滑地完成哈希表的擴容。
漸進式 rehash 的具體實現
- 分階段遷移：在每次對哈希表進行增刪查改操作時，逐步將舊哈希表的節點遷移到新哈希表中。每次操作遷移一部分節點，直到舊哈希表的所有節點都遷移完成。
- 維護 rehash 狀態：在進行 rehash 過程中，Redis 維護一個 rehash 索引（rehashidx），表示當前遷移到哪個位置。每次操作完成后，rehash 索引會相應更新，直到所有節點遷移完成。
- 完成 rehash：當所有節點遷移完成后，釋放舊哈希表的內存，將新哈希表替換為當前哈希表。
void?_dictRehashStep(dict *d) {if?(d->iterators ==?0) dictRehash(d,?1);
}
漸進式 rehash 的優點
- 平滑過渡：通過逐步遷移節點，避免了一次性 rehash 帶來的性能波動。
- 低延遲：每次操作只遷移一部分節點，保證了每次操作的時間復雜度不會過高，從而降低延遲。
5. 哈希觸發條件
哈希表的 rehash 觸發條件主要有兩個：
- 負載因子：當哈希表的負載因子超過一定閾值時，觸發 rehash 操作。負載因子等于已使用的節點數量除以哈希表的大小。Redis 的默認閾值是 1，當負載因子超過 1 時，會觸發 rehash。
- 內存使用情況：當 Redis 內存使用情況達到
一定水平時，也會觸發 rehash 操作，以保證內存的高效使用。
通過這兩個條件，Redis 可以在適當的時候進行哈希表的 rehash，從而維持哈希表的性能和內存利用率。
結論
通過上述解析，我們可以更好地理解哈希表的設計思想和實現原理，從而在實際開發中更好地利用哈希表提供的優勢。在 Redis 中，哈希表通過高效的鍵值對存儲和漸進式 rehash 機制，實現了高性能和低延遲的操作，適用于多種場景如鍵值存儲、緩存等。了解這些優化策略，可以幫助我們在實際應用中更好地利用 Redis 的性能和功能。
