面試官：HaspMap很熟了么，講講Redis字典吧！
哈嘍，大家好，我是了不起。
之前給大家介紹了Redis的基本數據結構，
后來聽說了一個故事：
一個Java程序員去面試，前面面試問了幾個 Java 的相關問題，回答還不錯，接下來面試官就問了一句：看來 Java 基礎還不錯，Java HashMap 你熟悉吧？
回答：那家伙老熟了，工作經常用，有看過源碼。紅黑樹鏈表都能給你整明白了！（心里默念：隨便問吧，八股文和源碼早都爛熟于心）
接著面試官說了這么一段話：
那好的，我們來聊聊 Redis 字典吧。
------------------------------------------
借著這個故事，我們聊一下Redis 字典，并對比Java中HashMap的一些異同。
1.前言
我們回顧一下之前講到的Redis的字典結構，示意圖如下：
圖片
Redis的字典本質上來說也是數組+鏈表的數據結構，這與Java中HashMap的數據結構很類似。
由上述結構示意圖也能看出，字典dict中維護了一個ht數組，而且只有兩個元素，這兩個元素是其擴容的關鍵點，這個我們后面會講到。
Redis中的哈希對象在以下條件時，使用ziplist編碼，
- 哈希對象保存的所有鍵值的字符串長度都小于64字節
- 哈希對象保存的鍵值對數量小于512個。
否則哈希對象會使用hashtable編碼， 而hashtable則時使用了字典作為底層實現的。
如下redis 哈希對象編碼由ziplist 變成hashtable
圖片
2.增加元素與鍵沖突
當不同的鍵值經過哈希算法與散列算法之后被分配到了同一個哈希表數組的同一個索引上，那么這之后就會有鍵沖突。
Redis 哈希表解決哈希沖突同樣是使用了鏈表地址法。使用哈希節點的next指針來鏈接同一個哈希表數組索引上的元素。不過Redis會將新添加的哈希節點加入到鏈表的表頭位置。
如下所示：如果程序要將鍵值對 （k2 , v2 ） 添加到如下的哈希表中，而且計算的書的索引為1，那么和 （k1 v1） 將產生沖突。解決沖突時，會將兩個節點使用next指針鏈接起來。而且會將新節點添加到鏈表表頭的位置。
圖片
哈希表1
圖片
鏈表解決hash沖突之后的哈希表
3.rehash 擴容過程
哈希表不斷的增加元素，其元素數量達到一定的比例之后，程序會對哈希表進行相應的擴展。通過執行rehash （重新散列）操作完成操作。其步驟如下：
- 執行擴展操作時會將字典中的ht[1] 哈希表大小設置成 第一個大于等于 ht[0] 的 ht[0].used * 2 的 2^n (2的n次冪)
- 將保存早ht[0] 中的所有的鍵值對 rehash到ht[1] 上， rehash過程中會重新計算哈希值和索引值。
- 當ht[0]中所有的鍵值對都遷移到ht[1]上時，釋放ht[0], 并將ht[1] 設置成 ht[0]， 并在ht[1]上建一個空的哈希表。
將下圖中的字典做rehash操作：
圖片
- ht[0].used 是4，4*2 = 8 ，2的3次方8 是第一個大于4 的 2的n次冪。即程序會將ht[1] 的大小設置成8 ，并分配空間，結構示意如下：
圖片
- 將ht[0] 上的幾個鍵值對全部都rehash到ht[1] 上面，如下圖：
圖片
- 釋放ht[0]，并將ht[1] 設置成 ht[0] , 然后為ht[1]分配一個空白的哈希表 如下圖：
圖片
以上是一個rehash的過程示意。
4.漸進式rehash
上面講的是一個rehash的理論過程，redis實際操作時并不會一次將所有的遷移一次性完成。
如果鍵值對數量非常龐大，那么遷移過程必然需要花費一點時間。由此可知，服務器也不可能一次將所有的鍵值對遷移，需要分多次，逐漸將ht[0] 里面的鍵值對遷移到ht[1]中，
其步驟如下：
- 首先會給ht[1]分配內存空間，此時redis字典擁有兩個哈希表
- 字典中維護一個rehashidx的計數器，將其值設置為0，表示rehash工作開始
- 在rehash期間，程序依然可以進行增刪改查的操作，除此之外還會順帶將ht[0]上 rehashidx索引上所有的鍵值對rehash到ht[1]上，rehash的工作完成后會將rehashidx的值加1
- 隨著字典的操作，ht[0]上的所有鍵值全部都rehash到ht[1]上時，程序會將rehashidx的值設為-1 ，表示rehash操作已經完成
在漸進式rehash的過程中，redis字典依然是可以進行增刪改查的操作， 其中增加元素的時候會將元素直接保存到ht[1]中， 而刪除，查找，更新的操作會在兩個哈希表中進行， 查找時會先在ht[0]中進行查找，然后會在ht[1]中進行查找。以上措施可以保證ht[0]中的元素只會減少，最終變成空表。
總結
Redis字典和Java中的HashMap的相似點和不同。
相似之處：
- 鍵值對存儲：Redis 字典和 Java 的 HashMap 都是鍵值對存儲的數據結構，它們可以通過鍵來快速查找對應的值。
- 高效的查找：Redis 字典和 Java 的 HashMap 都使用了哈希表來實現，因此在查找操作上具有高效性能。
- Redis 字典使用的時哈希表作為底層，并且每個字典維護了兩個哈希表，ht[0] 時主要使用的哈希表，而ht[1] 是在rehash過程是才會使用到的表。
- 哈希表的底層同樣是使用了數組 + 鏈表的結構， 與Java 中HashMap 相似，只不過Java8 以后增加了紅黑樹，在特定情況下會替換鏈表。
不同之處：
- 哈希表增加元素遇到哈希沖突是會將新添加的元素放到鏈表頭，而Java HashMap會將其放到鏈表尾，
- 擴容過程中redis的字典是漸進式擴容，擴容期間還是可以進行操作的，而Java的HashMap擴容需要一次性完成。
- 存儲方式：Redis 字典是一種基于內存的數據結構，用于在內存中存儲鍵值對。而 Java 的 HashMap 可以在內存中存儲，也可以持久化到磁盤上。
- 分布式支持：Redis 是一種分布式數據庫，可以在多臺服務器上進行數據共享和存儲。而 Java 的 HashMap 只能在單個 JVM 中使用。
- 數據類型：Redis 字典可以存儲多種數據類型，如字符串、列表、集合等，而 Java 的 HashMap 只能存儲對象類型。
- 持久化：Redis 字典可以將數據持久化到磁盤上，以便在重啟后恢復數據。而 Java 的 HashMap 需要自己實現數據的序列化和反序列化來實現持久化。
- 并發性：Redis 字典是線程安全的，可以支持多個客戶端并發訪問。而 Java 的 HashMap 在多線程環境下需要進行額外的同步處理才能保證線程安全。
