手寫 Redis 系列

java從零手寫實現redis（一）如何實現固定大小的緩存？

java從零手寫實現redis（三）redis expire 過期原理

java從零手寫實現redis（三）內存數據如何重啟不丟失？

java從零手寫實現redis（四）添加監聽器

java從零手寫實現redis（五）過期策略的另一種實現思路

java從零手寫實現redis（六）AOF 持久化原理詳解及實現

java從零手寫實現redis（七）LRU 緩存淘汰策略詳解

java從零開始手寫redis（八）樸素 LRU 淘汰算法性能優化

java從零開始手寫redis（九）LRU 緩存淘汰算法如何避免緩存污染

java從零開始手寫redis（十）緩存淘汰算法 LFU 最少使用頻次

java從零開始手寫redis（十一）緩存淘汰算法 COLOK 算法

java從零開始手寫redis（十二）過期策略如何實現隨機 keys 淘汰

java從零開始手寫redis（十三）redis漸進式rehash詳解

java從零開始手寫redis（十四）JDK HashMap 源碼解析

java從零開始手寫redis（十四）JDK ConcurrentHashMap 源碼解析

java從零開始手寫redis（十五）實現自己的 HashMap

java從零開始手寫redis（十六）實現漸進式 rehash map

思維導圖

上節內容回顧

我們在 從零手寫緩存框架（15）實現自己的 HashMap 中已經實現了自己的簡易版本的 HashMap，下面就讓我們為這個簡易版的 HashMap 加一點特技，讓他變成一個漸進式 HashMap。

漸進式 rehash

好了，接下來，讓我們考慮下，如何實現一個漸進式 rehash 的 Map？

實現流程

讓我們在回顧一遍 redis 的漸進式 rehash 過程：

哈希表漸進式 rehash 的詳細步驟：

（1）為 ht[1] 分配空間， 讓字典同時持有 ht[0] 和 ht[1] 兩個哈希表。

（2）在字典中維持一個索引計數器變量 rehashidx ， 并將它的值設置為 0 ， 表示 rehash 工作正式開始。

（3）在 rehash 進行期間， 每次對字典執行添加、刪除、查找或者更新操作時， 程序除了執行指定的操作以外， 還會順帶將 ht[0] 哈希表在 rehashidx 索引上的所有鍵值對 rehash 到 ht[1] ， 當 rehash 工作完成之后， 程序將 rehashidx 屬性的值增1。

（4）隨著字典操作的不斷執行， 最終在某個時間點上， ht[0] 的所有鍵值對都會被 rehash 至 ht[1] ， 這時程序將 rehashidx 屬性的值設為 -1 ， 表示 rehash 操作已完成。

實現方式

我們直接在上面簡易版本的基礎上進行實現。

實習過程中發現還是有點難度的，代碼量也是成倍增長。

本次編寫耗費的時間較多，大家一次看不完建議收藏，慢慢學習。

無論面試還是工作，都可以做到知其然，知其所以然。升職加薪，不在話下。

類定義

/*** 自己實現的漸進式 rehash map** @since 0.0.3* @param <K> key 泛型* @param <V> value 泛型* @see HashMap* @author binbin.hou*/
public class MyProgressiveReHashMap<K,V> extends AbstractMap<K,V> implements Map<K,V> {
}

和簡易版本類似。

私有變量

private static final Log log = LogFactory.getLog(MyProgressiveReHashMap.class);/*** rehash 的下標** 如果 rehashIndex != -1，說明正在進行 rehash* @since 0.0.3* @author binbin.hou*/
private int rehashIndex = -1;/*** 容量* 默認為 8*/
private int capacity;/*** 處于 rehash 狀態的容量* @since 0.0.3*/
private int rehashCapacity;/*** 統計大小的信息*/
private int size = 0;/*** 閾值* 閾值=容量*factor* 暫時不考慮最大值的問題** 當達到這個閾值的時候，直接進行兩倍的容量擴充+rehash。*/
private final double factor = 1.0;/*** 用來存放信息的 table 數組。* 數組：數組的下標是一個桶，桶對應的元素 hash 值相同。* 桶里放置的是一個鏈表。** 可以理解為 table 是一個 ArrayList* arrayList 中每一個元素，都是一個 DoubleLinkedList*/
private List<List<Entry<K, V>>> table;/*** 漸進式 rehash 時，用來存儲元素信息使用。** @since 0.0.3*/
private List<List<Entry<K, V>>> rehashTable;/*** 是否開啟 debug 模式* @since 0.0.3*/
private boolean debugMode = false;

rehashIndex/rehashCapacity/rehashTable 這三個值都是我們在進行漸進式實現的時候需要使用的值。

構造器

主要是一些值的初始化。

public MyProgressiveReHashMap() {this(8);
}/*** 初始化 hash map* @param capacity 初始化容量*/
public MyProgressiveReHashMap(int capacity) {this(capacity, false);
}/*** 初始化 hash map* @param capacity 初始化容量* @param debugMode 是否開啟 debug 模式* @since 0.0.3* @author binbin.hou*/
public MyProgressiveReHashMap(int capacity, boolean debugMode) {this.capacity = capacity;// 初始化最大為容量的個數，如果 hash 的非常完美的話。this.table = new ArrayList<>(capacity);// 初始化為空列表for(int i = 0; i < capacity; i++) {this.table.add(i, new ArrayList<Entry<K, V>>());}this.debugMode = debugMode;this.rehashIndex = -1;this.rehashCapacity = -1;this.rehashTable = null;
}

put() 方法

這個方法相對難度比較大：

put() 的過程可以見方法的注釋。

需要考慮是否為 rehash 階段，還需要考慮是否為更新。

/*** put 一個值** （1）如果不處于 rehash 階段** 1.1 判斷是否為 table 更新，如果是，則進行更新* 1.2 如果不是更新，則進行插入** 插入的時候可能觸發 rehash** （2）如果處于 rehash 階段** 2.0 執行一次漸進式 rehash 的動作** 2.1 判斷是否為更新，需要遍歷 table 和 rehashTable* 如果是，執行更新** 2.2 如果不是，則執行插入* 插入到 rehashTable 中** @param key 鍵* @param value 值* @return 值* @author binbin.hou*/
@Override
public V put(K key, V value) {boolean isInRehash = isInReHash();if(!isInRehash) {//1. 是否為更新Pair<Boolean, V> pair = updateTableInfo(key, value, this.table, this.capacity);if(pair.getValueOne()) {V oldVal = pair.getValueTwo();if(debugMode) {log.debug("不處于漸進式 rehash，此次為更新操作。key: {}, value: {}", key, value);printTable(this.table);}return oldVal;} else {// 插入return this.createNewEntry(key, value);}} else {//2.0 執行一個附加操作，進行漸進式 rehash 處理if(debugMode) {log.debug("當前處于漸進式 rehash 階段，額外執行一次漸進式 rehash 的動作");}rehashToNew();//2.1 是否為 table 更新Pair<Boolean, V> pair = updateTableInfo(key, value, this.table, this.capacity);if(pair.getValueOne()) {V oldVal = pair.getValueTwo();if(debugMode) {log.debug("此次為更新 table 操作。key: {}, value: {}", key, value);printTable(this.table);}return oldVal;}//2.2 是否為 rehashTable 更新Pair<Boolean, V> pair2 = updateTableInfo(key, value, this.rehashTable, this.rehashCapacity);if(pair2.getValueOne()) {V oldVal = pair2.getValueTwo();if(debugMode) {log.debug("此次為更新 rehashTable 操作。key: {}, value: {}", key, value);printTable(this.table);}return oldVal;}//2.3 插入return this.createNewEntry(key, value);}
}

是否為 rehash 階段

這個實現比較簡單，就是判斷 rehashIndex 是否為 -1：

/*** 是否處于 rehash 階段* @return 是否* @since 0.0.3* @author binbin.hou*/
private boolean isInReHash() {return rehashIndex != -1;
}

更新列表信息

這里為了復用，對方法進行了抽象。可以同時使用到 table 和 rehashTable 中。

/*** 是否為更新信息* @param key key* @param value value* @param table table 信息* @param tableCapacity table 的容量（使用 size 也可以，因為都默認初始化了。）* @return 更新結果* @since 0.0.3* @author binbin.hou*/
private Pair<Boolean, V> updateTableInfo(K key, V value, final List<List<Entry<K,V>>> table,final int tableCapacity) {// 計算 index 值int hash = HashUtil.hash(key);int index = HashUtil.indexFor(hash, tableCapacity);// 判斷是否為替換List<Entry<K,V>> entryList = new ArrayList<>();if(index < table.size()) {entryList = table.get(index);}// 遍歷for(Entry<K,V> entry : entryList) {// 二者的 key 都為 null，或者二者的 key equals()final K entryKey = entry.getKey();if(ObjectUtil.isNull(key, entryKey)|| key.equals(entryKey)) {final V oldValue = entry.getValue();// 更新新的 valueentry.setValue(value);return Pair.of(true, oldValue);}}return Pair.of(false, null);
}

這個和以前基本是類似的。

返回結果時，為了同時保存是否為更新，以及更新的 value 值。所以使用了 Pair 工具類。

插入新的元素

插入方法也比較麻煩，需要區分是否處于漸進式 rehash 階段。還要考慮是否需要擴容。

/*** 創建一個新的明細** （1）如果處于漸進式 rehash 中，則設置到 rehashTable 中* （2）如果不是，則判斷是否需要擴容** 2.1 如果擴容，則直接放到 rehashTable 中。* 因為我們每次擴容內存翻倍，一次只處理一個 index 的信息，所以不會直接 rehash 結束，直接放到新的 rehashTable 中即可* 2.2 如果不擴容，則放入 table 中** @param key key* @param value value* @since 0.0.3* @author binbin.hou*/
private V createNewEntry(final K key,final V value) {Entry<K,V> entry = new DefaultMapEntry<>(key, value);// 重新計算 tableIndexint hash = HashUtil.hash(key);//是否處于 rehash 中？if(isInReHash()) {int index = HashUtil.indexFor(hash, this.rehashCapacity);List<Entry<K,V>> list = this.rehashTable.get(index);list.add(entry);if(debugMode) {log.debug("目前處于 rehash 中，元素直接插入到 rehashTable 中。");printTable(this.rehashTable);}}// 是否需要擴容 && 不處于漸進式 rehash// rehash 一定是擴容 rehashTable// 如果發生了 rehash，元素是直接放到 rehashTable 中的if(isNeedExpand()) {rehash();// 放入到 rehashTable 中int index = HashUtil.indexFor(hash, this.rehashCapacity);List<Entry<K,V>> list = this.rehashTable.get(index);list.add(entry);if(debugMode) {log.debug("目前處于 rehash 中，元素直接插入到 rehashTable 中。");printTable(this.rehashTable);}} else {int index = HashUtil.indexFor(hash, this.capacity);List<Entry<K,V>> list = this.table.get(index);list.add(entry);if(debugMode) {log.debug("目前不處于 rehash 中，元素直接插入到 table 中。");printTable(this.table);}}this.size++;return value;
}

是否需要擴容的方法也比較簡單：

/*** 是否需要擴容** 比例滿足，且不處于漸進式 rehash 中* @return 是否* @since 0.0.3* @author binbin.hou*/
private boolean isNeedExpand() {// 驗證比例double rate = size*1.0 / capacity*1.0;return rate >= factor && !isInReHash();
}

不過我們這次添加了一個不要處于漸進式 rehash 過程中。

其中 rehash 的實現也發生了很大的變化，具體實現如下：

/*** 直接 rehash 的流程** （1）如果處于 rehash 中，直接返回* （2）初始化 rehashTable，并且更新 rehashIndex=0;* （3）獲取 table[0]，rehash 到 rehashTable 中* （4）設置 table[0] = new ArrayList();** @since 0.0.3* @author binbin.hou*/
private void rehash() {if(isInReHash()) {if(debugMode) {log.debug("當前處于漸進式 rehash 階段，不重復進行 rehash!");}return;}// 初始化 rehashTablethis.rehashIndex = -1;this.rehashCapacity = 2*capacity;this.rehashTable = new ArrayList<>(this.rehashCapacity);for(int i = 0; i < rehashCapacity; i++) {rehashTable.add(i, new ArrayList<Entry<K, V>>());}// 遍歷元素第一個元素，其他的進行漸進式更新。rehashToNew();
}

漸進式更新的方法，可以在 get/put/remove 等操作時，執行附加操作時使用。

所以單獨抽成了一個方法，實現如下：

/*** 將信息從舊的 table 遷移到新的 table 中** （1）table[rehashIndex] 重新 rehash 到 rehashTable 中* （2）設置 table[rehashIndex] = new ArrayList();* （3）判斷是否完成漸進式 rehash*/
private void rehashToNew() {rehashIndex++;List<Entry<K, V>> list = table.get(rehashIndex);for(Entry<K, V> entry : list) {int hash = HashUtil.hash(entry);int index = HashUtil.indexFor(hash, rehashCapacity);//  添加元素// 獲取列表，避免數組越界List<Entry<K,V>> newList = rehashTable.get(index);// 添加元素到列表// 元素不存在重復，所以不需要考慮更新newList.add(entry);rehashTable.set(index, newList);}// 清空 index 處的信息table.set(rehashIndex, new ArrayList<Entry<K, V>>());// 判斷大小是否完成 rehash// 驗證是否已經完成if(rehashIndex == (table.size()-1)) {this.capacity = this.rehashCapacity;this.table = this.rehashTable;this.rehashIndex = -1;this.rehashCapacity = -1;this.rehashTable = null;if(debugMode) {log.debug("漸進式 rehash 已經完成。");printTable(this.table);}} else {if(debugMode) {log.debug("漸進式 rehash 處理中, 目前 index：{} 已完成", rehashIndex);printAllTable();}}
}

get() 操作

漸進式 rehash 將動作分散到每一個操作中，我們對 get 方法進行重寫，當做一個例子。其他的方法如果實現也是類似的。

/*** 查詢方法* （1）如果處于漸進式 rehash 狀態，額外執行一次 rehashToNew()* （2）判斷 table 中是否存在元素* （3）判斷 rehashTable 中是否存在元素* @param key key* @return 結果*/
@Override
public V get(Object key) {if(isInReHash()) {if(debugMode) {log.debug("當前處于漸進式 rehash 狀態，額外執行一次操作");rehashToNew();}}//1. 判斷 table 中是否存在V result = getValue(key, this.table);if(result != null) {return result;}//2. 是否處于漸進式 rehashif(isInReHash()) {return getValue(key, this.rehashTable);}return null;
}

測試

我們歷經千辛萬苦，終于實現了一個簡單版本的漸進式 hash map。

下面來測試一下功能是否符合我們的預期。

put 操作

Map<String, String> map = new MyProgressiveReHashMap<>(2, true);
map.put("1", "1");
map.put("1", "2");

日志：

[DEBUG] [2020-10-11 21:30:15.072] [main] [c.g.h.d.s.c.u.m.MyProgressiveReHashMap.createNewEntry] - 目前不處于 rehash 中，元素直接插入到 table 中。
{1: 1} 
[DEBUG] [2020-10-11 21:30:15.076] [main] [c.g.h.d.s.c.u.m.MyProgressiveReHashMap.put] - 不處于漸進式 rehash，此次為更新操作。key: 1, value: 2
{1: 2} 

第一次是插入，第二次是更新。

這里都沒有觸發擴容，下面我們看一下觸發擴容的情況。

擴容測試

Map<String, String> map = new MyProgressiveReHashMap<>(2, true);
map.put("1", "1");
map.put("2", "2");
map.put("3", "3");Assert.assertEquals("1", map.get("1"));
Assert.assertEquals("2", map.get("2"));
Assert.assertEquals("3", map.get("3"));

日志如下：

[DEBUG] [2020-10-11 21:31:12.559] [main] [c.g.h.d.s.c.u.m.MyProgressiveReHashMap.createNewEntry] - 目前不處于 rehash 中，元素直接插入到 table 中。
{1: 1} 
[DEBUG] [2020-10-11 21:31:12.560] [main] [c.g.h.d.s.c.u.m.MyProgressiveReHashMap.createNewEntry] - 目前不處于 rehash 中，元素直接插入到 table 中。
{2: 2} 
{1: 1} 
[DEBUG] [2020-10-11 21:31:12.563] [main] [c.g.h.d.s.c.u.m.MyProgressiveReHashMap.rehashToNew] - 漸進式 rehash 處理中, 目前 index：0 已完成
原始 table 信息: 
{1: 1} 
新的 table 信息: 
{2: 2} 
[DEBUG] [2020-10-11 21:31:12.563] [main] [c.g.h.d.s.c.u.m.MyProgressiveReHashMap.createNewEntry] - 目前處于 rehash 中，元素直接插入到 rehashTable 中。
{2: 2} 
{3: 3} 
[DEBUG] [2020-10-11 21:31:12.564] [main] [c.g.h.d.s.c.u.m.MyProgressiveReHashMap.get] - 當前處于漸進式 rehash 狀態，額外執行一次操作
[DEBUG] [2020-10-11 21:31:12.564] [main] [c.g.h.d.s.c.u.m.MyProgressiveReHashMap.rehashToNew] - 漸進式 rehash 已經完成。
{2: 2} 
{1: 1} 
{3: 3} 

當放入元素【3】的時候，已經觸發了 rehash。

（1）第一次漸進式 rehash 將 table[0] 的元素 rehash 到了新的節點。

（2）插入的元素直接插入到 rehashTable 中

（3）get 操作時，額外觸發一次 rehash，然后所有的 rehash 已經完成。

ps: 寫完的那一刻，感覺自己又變強了！

小結

本節我們自己動手實現了一個簡易版本的漸進式 rehash HashMap。

為了實現這個功能，我們做了很多準備工作，HashMap 的源碼學習，redis 漸進式 rehash 原理，HashMap 的手寫實現。

跨過這幾個難關之后，終于實現了一個自己的 rehash HashMap。

本實現是我個人完全獨立創造，只參考了 redis 的實現流程，如有雷同，肯定是抄【老馬嘯西風】的。

本節的內容較長，書寫也花費了大量的時間，一切都是值得的。希望你喜歡。

可以先收藏轉發一波，然后細細品味。后續將帶給大家更多高性能相關的原理和手寫框架，感興趣的伙伴可以關注一波，即使獲取最新動態~

開源地址：https://github.com/houbb/cache

覺得本文對你有幫助的話，歡迎點贊評論收藏關注一波。你的鼓勵，是我最大的動力~

不知道你有哪些收獲呢？或者有其他更多的想法，歡迎留言區和我一起討論，期待與你的思考相遇。