您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 綜合教學

HashMap 實現原理深度解析與手寫簡易版：數組+鏈表、擴容、Hash 算法優化

編輯：Java 綜合教學

HashMap 實現原理深度解析與手寫簡易版：數組+鏈表、擴容、Hash 算法優化

HashMap 是 Java 開發最高頻集合，底層為數組+鏈表（JDK 1.8+ 鏈表轉紅黑樹）。本文剖析核心源碼邏輯、性能優化點，並提供手寫簡易版實現與性能測試。

核心數據結構

transient Node<K,V>[] table;  // 鏈表數組（JDK 1.8 叫 Node，舊版 Entry）

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;  // 鏈表指針
}

Put 流程源碼邏輯

public V put(K key, V value) {
    int hash = hash(key);                    // 1. 計算 hash
    int i = indexFor(hash, table.length);    // 2. 定位數組下標
    for (Node<K,V> e = table[i]; e != null; e = e.next) {  // 3. 遍歷鏈表
        if (e.hash == hash && (e.key == key || key.equals(e.key))) {
            V old = e.value;
            e.value = value;                 // 4. key 存在：覆蓋值
            return old;
        }
    }
    addEntry(hash, key, value, i);           // 5. key 不存在：頭插法/尾插法插入
    return null;
}

Get 流程

public V get(Object key) {
    int hash = hash(key);
    for (Node<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
        if (e.hash == hash && (e.key == key || key.equals(key)))
            return e.value;
    }
    return null;
}

Hash 算法優化（關鍵）

// JDK 8 擾動函數：高16位參與運算，減少碰撞
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// 索引計算：位運算替代取模，要求 table.length 為 2 的冪次
static int indexFor(int h, int length) {
    return h & (length - 1);
}

原理：h & (length-1) 等價於 h % length（length 為 2ⁿ），位運算極快。擾動函數讓高位特徵參與低位索引計算，分佈更均勻。

自動擴容機制

觸發條件：size > threshold = capacity * loadFactor（默認 0.75）
擴容策略：容量翻倍（2ⁿ → 2ⁿ⁺¹）
重新哈希：遍歷舊表，重新計算索引插入新表（JDK 1.8 優化：利用高位判斷留在原位或移動到 newIndex = oldIndex + oldCap）
性能影響：擴容極其耗時，預估數據量時指定 initialCapacity 避免多次擴容

手寫簡易版核心代碼

public class SimpleHashMap<K,V> {
    private static final int DEFAULT_CAPACITY = 16;
    private static final float LOAD_FACTOR = 0.75f;
    
    private Node<K,V>[] table;
    private int size;
    
    public SimpleHashMap() {
        table = new Node[DEFAULT_CAPACITY];
    }
    
    private int hash(K key) {
        int h = key == null ? 0 : key.hashCode();
        return h ^ (h >>> 16);  // 擾動
    }
    
    private int index(int hash) {
        return hash & (table.length - 1);
    }
    
    public V put(K key, V value) {
        int h = hash(key);
        int i = index(h);
        for (Node<K,V> e = table[i]; e != null; e = e.next) {
            if (e.hash == h && (e.key == key || key.equals(e.key))) {
                V old = e.value;
                e.value = value;
                return old;
            }
        }
        // 頭插法
        table[i] = new Node<>(h, key, value, table[i]);
        if (++size > table.length * LOAD_FACTOR) resize();
        return null;
    }
    
    public V get(K key) {
        int h = hash(key);
        for (Node<K,V> e = table[index(h)]; e != null; e = e.next) {
            if (e.hash == h && (e.key == key || key.equals(e.key)))
                return e.value;
        }
        return null;
    }
    
    private void resize() {
        Node<K,V>[] old = table;
        table = new Node[old.length * 2];
        size = 0;
        for (Node<K,V> e : old) {
            while (e != null) {
                put(e.key, e.value);  // 重新哈希插入
                e = e.next;
            }
        }
    }
    
    static class Node<K,V> {
        final int hash; final K key; V value; Node<K,V> next;
        Node(int h, K k, V v, Node<K,V> n) { hash=h; key=k; value=v; next=n; }
    }
}