2023-06-15：說一說Redis的Key和Value的數(shù)據(jù)結(jié)構(gòu)組織?

答案2023-06-15：

全局哈希表

Redis使用哈希表作為保存鍵值對的數(shù)據(jù)結(jié)構(gòu)，通過哈希函數(shù)將Key映射為哈希表中的一個索引位置，使得Key-Value可以在O(1)時間復(fù)雜度內(nèi)被快速訪問。在Redis中，哈希表是由多個哈希桶（也稱為槽位/數(shù)組元素）組成的，每個哈希桶可以存放多個Key-Value值，同一個哈希桶中的多個鍵值對可以通過Key進行快速查找。

在Redis中，哈希表由多個哈希桶組成，每個哈希桶中保存著一個鏈表，鏈表中每個節(jié)點都是一個鍵值對，其中鍵key和值value都是指針類型，指向?qū)嶋H的鍵和值數(shù)據(jù)。這樣一來，即使值是一個集合，也可以通過value指針指向的地址在內(nèi)存中獲取到實際的集合值。因為這個哈希表保存了所有的鍵值對，所以，也可以把它稱為全局哈希表。

哈希表的最大優(yōu)勢在于可以以O(shè)(1)的時間復(fù)雜度快速查找鍵值對。通過哈希函數(shù)將鍵映射為一個索引位置，就可以快速訪問所在的哈希桶，從而訪問相應(yīng)的entry元素，獲取鍵值對數(shù)據(jù)。

當(dāng)寫入大量數(shù)據(jù)到Redis中時，有時會發(fā)現(xiàn)操作突然變慢。這很可能是由哈希表的沖突問題和rehash操作可能帶來的阻塞引起。由于哈希表為每個鍵計算哈希值，將其映射到不同的桶中。然而，不同的鍵可能具有相同的哈希值，這就是哈希表沖突的存在。

隨著向哈希表中寫入更多數(shù)據(jù)，哈希沖突是一個不可避免的問題。當(dāng)兩個鍵計算出的哈希值映射到同一個桶中時，就會發(fā)生哈希沖突。Redis使用鏈表或跳表解決哈希沖突，將具有相同哈希值的鍵值對存儲在同一個桶中的鏈表或跳表中。雖然這種方法可以在一定程度上有效解決沖突問題，但當(dāng)鏈表或跳表過長時，讀寫性能會逐漸降低。因此，適當(dāng)調(diào)整哈希表的大小，或使用跳表代替鏈表，可以提高哈希表的性能和可靠性。

Redis解決哈希沖突采用鏈?zhǔn)焦?，即將哈希表中哈希值相同的鍵值對用鏈表連接起來存儲在同一個桶中，這樣的設(shè)計稱為“開鏈法”。開鏈法可以有效地避免哈希沖突，同時適用于哈希桶數(shù)量確定或變化不頻繁的場景。

具體來說，鏈?zhǔn)焦Ｊ褂弥羔槍⒍鄠€元素連接在一起，形成鏈表。當(dāng)哈希表中存在多個哈希值相同的鍵值對時，這些鍵值對可以通過指針順序訪問。由于實現(xiàn)簡單且常用，鏈?zhǔn)焦３Ｓ糜诮鉀Q哈希表沖突，被廣泛應(yīng)用于數(shù)據(jù)結(jié)構(gòu)中，是一種重要且實用的數(shù)據(jù)存儲方式。