👆🏻👆🏻👆🏻關(guān)注博主，讓你的代碼變得更加優(yōu)雅。

前言

HashMap 大家工作中遇到的太多了，已經(jīng)成了必須使用的類了， 在面試的時候 HashMap 基本是必問題，但是很多同學(xué)只是打開看過原理，沒有真正的去研究過。

里面是大佬寫代碼，為了性能和我們的業(yè)務(wù)代碼寫法差別很大，今天我?guī)Т蠹沂謱懸粋€簡單put 方法，保證用大家看得懂的代碼來寫。

最佳實踐

直接上案例

案例地址GitHub： https://github.com/zhuangjiaju/easytools/blob/main/easytools-test/src/test/java/com/github/zhuangjiaju/easytools/test/demo/hashmap/HashMapTest.java

案例地址gitee： https://gitee.com/zhuangjiaju/easytools/blob/main/easytools-test/src/test/java/com/github/zhuangjiaju/easytools/test/demo/hashmap/HashMapTest.java

HashMap 是什么樣子的數(shù)組結(jié)構(gòu)

首先一定要了解 HashMap 底層是一個數(shù)組，然后根據(jù) key 的 HashCode 和 數(shù)組的長度 取余 ，放到指定的數(shù)組位置。 如果 HashCode 和
數(shù)組的長度 取余后的位置一樣，則放到這個位置的鏈表中。

圖片畫的很明顯，一個 Node 里面包含了 一個 key 和 value,放入 Node1 的時候假設(shè)放到了 1 號位置，Node2 放到 2 號位置，Node3 放到
3 號位置。

Node4的時候 HashCode 和 數(shù)組的長度 取余 也定位到了1 ，所以放到了 1 號位置 Node1的鏈表中。

Node5的時候 HashCode 和 數(shù)組的長度 取余 也定位到了1 ，所以也要 Node1的鏈表中，放到 Node4的后面。

接下來直接上源碼

Node 節(jié)點，包含了 key 、 value、 next 、hash 4個字段。
key 和 value 就不多說了。
next 代表了下一個節(jié)點，為空則代表沒有，有的話類似于上面說的Node3.
hash 實際上是 key 的 hash 值，為了減少次數(shù)，所以存儲了起來。

/*** HashMap 的 Node 節(jié)點** @param <K>* @param <V>*/
@Data
@SuperBuilder
@AllArgsConstructor
@NoArgsConstructor
public class MyHashMapNode<K, V> {/*** key 的hash 值*/private int hash;/*** map 的key*/private K key;/*** map 的value*/private V value;/*** 下一個節(jié)點*/private MyHashMapNode<K, V> next;
}

這一期我們僅僅展示 put 代碼，其他代碼我們后續(xù)實現(xiàn)。

核心邏輯就是通過 key 計算 hash 值，取模后定位到數(shù)組的列表，然后沖突了就放到鏈表里面。

最后，hash 取模以后經(jīng)常沖突然后放到鏈表里面，需要判斷超過 數(shù)組長度的75%就需要擴容到原來的2倍，確保盡可能少的用到鏈表。

@Override
public V put(K key, V value) {// 為了簡單期間不考慮 null// 放到table 數(shù)組的哪個位置 真正的hashmap 算法不一樣 我們偷懶int hasCode = key.hashCode();int index = hasCode % table.length;// 我們找到了我們需要放的位置MyHashMapNode<K, V> node = table[index];// 這個位置沒有數(shù)據(jù) 我們直接放進去即可 非常輕松if (node == null) {table[index] = MyHashMapNode.<K, V>builder().hash(hasCode).key(key).value(value).build();} else {// 已經(jīng)有了 我們要放到最后一個node 的最后,所以需要一個個node 的遍歷// 真正的HashMap 還會轉(zhuǎn)紅黑樹，我們就么必要了MyHashMapNode<K, V> nextNode = node;while (true) {// 先判斷 hash值是否一樣 為了提高性能 無所謂性能可以直接比較 key 是否一樣// 如果找到了key 一樣 我們把他替換掉 然后退出if (nextNode.getHash() == hasCode && nextNode.getKey().equals(key)) {// key 一樣 我們直接替換nextNode.setValue(value);break;}// 如果沒有下一個節(jié)點了 我們直接放到最后一個節(jié)點if (nextNode.getNext() == null) {nextNode.setNext(MyHashMapNode.<K, V>builder().hash(hasCode).key(key).value(value).build());break;}// 不為空 則繼續(xù)往后找nextNode = nextNode.getNext();}}// 嘗試重新擴容 當(dāng)table 存儲超過75%的時候 我們需要重新擴容，確保每次key 計算hash 值能直接命中，而不需要一個比較過去if (size > table.length * 0.75) {// 直接擴容成2倍MyHashMapNode<K, V>[] newTable = new MyHashMapNode[table.length * 2];// 遍歷所有舊的數(shù)據(jù)// 所有的子節(jié)點都要迭代掉for (MyHashMapNode<K, V> oldNode : table) {// 空數(shù)據(jù)不管if (oldNode == null) {continue;}// 舊的下一個節(jié)點MyHashMapNode<K, V> oldNodeNext = oldNode;// 這里核心是把數(shù)組+鏈表所有的數(shù)據(jù)都迭代出來while (true) {// 直接獲取下一個節(jié)點 這里要提早獲取 以為要要把 oldNode的next 設(shè)置成nulloldNodeNext = oldNodeNext.getNext();// 清空下一個節(jié)點 因為要重新掛到新的table 上 重新掛的時候會有新的nextoldNode.setNext(null);// 重新計算數(shù)組下標(biāo)int newIndex = oldNode.getHash() % newTable.length;MyHashMapNode<K, V> newNode = newTable[newIndex];// 這個位置沒有數(shù)據(jù) 我們直接放進去即可if (newNode == null) {newTable[newIndex] = oldNode;} else {// 已經(jīng)有了 我們要放到最后一個node 的最后,所以需要一個個node 的遍歷// 真正的HashMap 還會轉(zhuǎn)紅黑樹，我們就么必要了MyHashMapNode<K, V> newNextNode = newNode;while (true) {// 如果沒有下一個節(jié)點了 我們直接放到最后一個節(jié)點if (newNextNode.getNext() == null) {newNextNode.setNext(MyHashMapNode.<K, V>builder().hash(hasCode).key(key).value(value).build());break;}// 不為空 則繼續(xù)往后找newNextNode = newNextNode.getNext();}}// 最后一個節(jié)點了 結(jié)束循環(huán)if (oldNodeNext == null) {break;}}}// 替換舊的tabletable = newTable;}// 條數(shù)加+1size++;return value;
}

以上代碼雖然不多，但是完成了 HashMap put方法的核心邏輯，非常建議大家花時間仔細研究下，這樣后面再也沒有人通過 HashMap 問倒你了。

測試下效果

    /*** 側(cè)測試我們自己寫的HashMap* 在里面放2個值 看看效果*/
@Test
public void putTest() throws Exception {MyHashMap<String, String> myHashMap = new MyHashMap<>();myHashMap.put("a", "a");myHashMap.put("b", "b");log.info("放置后的數(shù)組:{}", JSON.toJSONString(myHashMap.getTable()));Assertions.assertEquals(2, myHashMap.getSize());// 迭代所有節(jié)點for (MyHashMapNode<String, String> node : myHashMap.getTable()) {if (node == null) {continue;}Assertions.assertTrue(StringUtils.equalsAny(node.getKey(), "a", "b"));Assertions.assertTrue(StringUtils.equalsAny(node.getValue(), "a", "b"));}
}

輸出結(jié)果：

放置后的數(shù)組:[null,{"hash":97,"key":"a","value":"a"},{"hash":98,"key":"b","value":"b"},null,null,null,null,null,null,null,null,null,null,null,null,null]

貼一張圖更加的明顯

其中空的數(shù)組沒有展示出來，只有數(shù)組的 1、2 放置了2個數(shù)據(jù)。

測試我們的擴容代碼

我們放15個值 看看效果，會觸發(fā)一次擴容

    /*** 測試擴容的代碼* 我們放15個值 看看效果，會觸發(fā)一次擴容*/
@Test
public void resizeTest() throws Exception {MyHashMap<String, String> myHashMap = new MyHashMap<>();// 放入15條 理論上來擴容過一次for (int i = 0; i < 15; i++) {myHashMap.put("key" + i, "value" + i);}log.info("放置后的數(shù)組:{}", JSON.toJSONString(myHashMap.getTable()));Assertions.assertEquals(15, myHashMap.getSize());Assertions.assertEquals(32, myHashMap.getTable().length);
}

直接貼輸出的圖

可以看到我們的15條數(shù)據(jù)還是非常散列的，只有在17的位置產(chǎn)生了鏈表，這樣子在查的速度會非?？?#xff0c;幾乎就是O(1)。

實際工作中的 HashMap 存儲也查不到，幾乎可以理解成 HashMap 就是O(1)。

總結(jié)

今天帶著大家了手寫了 HashMap 的 put方法，大家是不是感覺 HashMap 原來可以這么簡單，看過還需要自己去試一下喲。

下一節(jié)會給大家介紹 HashMap 的 get 方法，大家敬請期待。

寫在最后

給大家推薦一個非常完整的Java項目搭建的最佳實踐,也是本文的源碼出處，由大廠程序員&EasyExcel作者維護。
github地址：https://github.com/zhuangjiaju/easytools
gitee地址：https://gitee.com/zhuangjiaju/easytools