Java 手寫設計HashMap源碼，讓面試官膜拜

Java 手寫HashMap源碼，讓面試官膜拜

一，手寫源碼

這是一個模仿HashMap的put，get功能的自定義的MyHashMap

package cn.wxs.demo;import java.io.Serializable;
import java.util.*;
import java.util.function.BiConsumer;class MyHashMap<K, V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {private static final int DEFAULT_CAPACITY = 16;private static final float DEFAULT_LOAD_FACTOR = 0.75f;private Node<K, V>[] table; // 存儲桶數組private transient int size; // 鍵值對數量private transient int modCount;  //總數private transient int threshold; // 擴容閾值private float loadFactor; // 負載因子@Overridepublic void forEach(BiConsumer<? super K, ? super V> action) {MyHashMap.Node<K,V>[] tab;if (action == null)throw new NullPointerException();if (size > 0 && (tab = table) != null) {int mc = modCount;for (int i = 0; i < tab.length; ++i) {for (MyHashMap.Node<K,V> e = tab[i]; e != null; e = e.next)action.accept(e.key, e.value);}if (modCount != mc)throw new ConcurrentModificationException();}}public MyHashMap() {this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);}public MyHashMap(int initialCapacity, float loadFactor) {if (initialCapacity <= 0)throw new IllegalArgumentException("Invalid initial capacity");if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Invalid load factor");this.table = new Node[initialCapacity];this.size = 0;this.loadFactor = loadFactor;this.threshold = (int) (initialCapacity * loadFactor);}public V get(Object key) {Node<K, V> node = getNode((K) key);return (node != null) ? node.value : null;}public V put(K key, V value) {if (key == null)putForNullKey(value);elseputNonNullKey(key, value);return value;}@Overridepublic Set<Entry<K, V>> entrySet() {return null;}private void putNonNullKey(K key, V value) {int hash = hash(key);int index = indexFor(hash, table.length);// 遍歷鏈表，查找是否已存在相同的鍵for (Node<K, V> node = table[index]; node != null; node = node.next) {if (node.hash == hash && Objects.equals(node.key, key)) {// 如果找到相同的鍵，更新對應的值node.value = value;return;}}// 如果沒有找到相同的鍵，將新的鍵值對添加到鏈表頭部addNode(hash, key, value, index);}private void putForNullKey(V value) {// 對于 null 鍵，存儲在數組的第一個位置for (Node<K, V> node = table[0]; node != null; node = node.next) {if (node.key == null) {// 如果找到 null 鍵，更新對應的值node.value = value;return;}}// 如果沒有找到 null 鍵，將新的鍵值對添加到鏈表頭部addNode(0, null, value, 0);}private void addNode(int hash, K key, V value, int bucketIndex) {// 檢查是否需要擴容if (size >= threshold)resize(2 * table.length);// 將新的節點添加到鏈表頭部Node<K, V> newNode = new Node<>(hash, key, value, table[bucketIndex]);table[bucketIndex] = newNode;size++;modCount++;}private Node<K, V> getNode(K key) {if (key == null)return getNodeForNullKey();int hash = hash(key);int index = indexFor(hash, table.length);// 遍歷鏈表，查找指定的鍵for (Node<K, V> node = table[index]; node != null; node = node.next) {if (node.hash == hash && Objects.equals(node.key, key))return node;}return null;}private Node<K, V> getNodeForNullKey() {// 對于 null 鍵，存儲在數組的第一個位置for (Node<K, V> node = table[0]; node != null; node = node.next) {if (node.key == null)return node;}return null;}private int hash(K key) {// 計算鍵的哈希值return (key == null) ? 0 : key.hashCode();}private int indexFor(int hash, int length) {// 根據哈希值和數組長度計算索引位置return hash & (length - 1);}private void resize(int newCapacity) {Node<K, V>[] oldTable = table;int oldCapacity = oldTable.length;// 檢查是否達到容量上限if (oldCapacity >= 1 << 30)threshold = Integer.MAX_VALUE;elsethreshold = (int) (newCapacity * loadFactor);// 創建新的數組，將舊的鍵值對重新分配到新的數組中Node<K, V>[] newTable = new Node[newCapacity];transfer(oldTable, newTable);table = newTable;}private void transfer(Node<K, V>[] src, Node<K, V>[] dest) {// 遍歷舊的數組，將鍵值對重新分配到新的數組中for (Node<K, V> node : src) {while (node != null) {Node<K, V> next = node.next;int index = indexFor(node.hash, dest.length);node.next = dest[index];dest[index] = node;node = next;}}}static class Node<K, V> {final int hash; // 哈希值final K key; // 鍵V value; // 值Node<K, V> next; // 下一個節點Node(int hash, K key, V value, Node<K, V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next;}}public static void main(String[] args) {MyHashMap<String,String> param = new MyHashMap<>();param.put("你好","你好");param.put("你好1","你好1");param.put("你好2","你好2");param.put("你好3","你好3");param.put("你好4","你好4");param.put("你好5","你好4");param.put("你好6","你好4");param.put("你好7","你好4");param.put("你好8","你好4");param.put("你好9","你好4");param.put("你好10","你好4");param.put("你好11","你好4");param.put("你好12","你好4");param.put("你好13","你好4");param.put("你好14","你好4");param.put("你好15","你好4");param.put("你好16","你好4");param.put("你好17","你好4");param.put("你好18","你好4");param.put("你好20","你好4");param.put("你好21","你好4");param.put("你好22","你好4");param.put("你好23","你好4");param.put("你好24","你好4");param.put("你好25","你好4");param.put("你好26","你好4");param.put("你好27","你好4");param.put("你好28","你好4");param.put("你好29","你好4");param.put("你好30","你好4");param.put("你好31","你好4");param.put("你好32","你好4");param.forEach((k,v)-> System.out.println(k));
//        System.out.println(param.get("你好4"));}
}

在這里插入圖片描述

二，代碼介紹

1.這是一個簡單的自定義哈希映射（HashMap）的實現。功能不太完善，代碼不太優雅，細節不夠好，沒有源碼的那么好。后面我會慢慢進行優化
2.這段代碼實現了一個簡化版本的 HashMap，包含了 put 和 get 方法，并使用了數組+鏈表的存儲結構。注意，這里的紅黑樹部分并未實現，只使用了鏈表來處理沖突。由于短時間沒有辦法能按自己的方式寫出來全部的功能和底層設計，難度還是比較大的后期我會慢慢的把存儲結構改成數組+鏈表+紅黑樹的數據結構

請注意，這只是一個簡化版本的實現，并沒有處理擴容、紅黑樹轉換等復雜的細節。實際的 HashMap 實現要復雜得多。如果你對完整的實現感興趣，建議你查閱 Java 的 HashMap 源代碼，以便更好地理解和學習。

三，下期完善功能

size()
remove(key)
containsKey(key)
containsValue(value)

三，HashMap

HashMap 是 Java 中的一個常用的數據結構，它實現了 Map 接口，并且基于哈希表實現。HashMap 允許存儲鍵值對，并且提供了快速的插入、查找和刪除操作。

下面是 HashMap 的一些重要特點和概念：

哈希表：HashMap 內部使用了一個數組來存儲數據，這個數組被稱為哈希表。哈希表的每個元素稱為一個桶（bucket），每個桶可以存儲一個或多個鍵值對。通過計算鍵的哈希值，可以確定鍵值對在哈希表中的位置。
哈希函數：哈希函數用于將鍵映射到哈希表中的索引位置。好的哈希函數能夠將鍵均勻地分布在哈希表的不同位置上，以減少沖突的概率。在 HashMap 中，鍵的 hashCode() 方法被用作哈希函數。
沖突：當兩個不同的鍵通過哈希函數計算得到的索引位置相同時，就發生了沖突。HashMap 使用鏈表或紅黑樹來解決沖突。當沖突較少時，使用鏈表；當鏈表長度超過一定閾值時，轉換為紅黑樹，以提高查找的效率。
鍵的唯一性：在 HashMap 中，鍵是唯一的。如果嘗試將一個已經存在的鍵插入到 HashMap 中，它的值將被更新為新的值。
null 鍵：HashMap 允許存儲一個鍵為 null 的鍵值對。這個鍵將被存儲在哈希表的第一個位置上。
迭代順序：HashMap 不保證鍵值對的迭代順序，它通常是不確定的。如果需要有序的鍵值對集合，可以使用 LinkedHashMap。