您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

Java HashMap 深度解析：JDK 1.7 源碼級剖析（佈局、擴容、迭代器）

編輯：Java 相關知識

HashMap 核心特徵

允許 null Key/Value（Hashtable 不允許）
非線程安全（多線程用 ConcurrentHashMap 或 Collections.synchronizedMap）
迭代器 fail-fast：結構修改時拋 ConcurrentModificationException
遍歷複雜度與 capacity 成正比，初始容量過大反而降低遍歷效能

底層數據結構：數組 + 鏈表（Separate Chaining）

Entry<K,V>[] table 為桶數組，衝突以單鏈表形式存儲。JDK 1.7 使用頭插法，擴容時鏈表順序反轉，高併發下可能形成環導致 CPU 100%（JDK 1.8 改為尾插+紅黑樹）。

核心源碼走讀（JDK 1.7）

Entry 節點

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key; V value; Entry<K,V> next; int hash;
    Entry(int h, K k, V v, Entry<K,V> n) { value=v; next=n; key=k; hash=h; }
}

get 流程 O(1)

public V get(Object key) {
    if (key == null) return getForNullKey(); // table[0] 遍歷
    Entry<K,V> e = getEntry(key);
    return e == null ? null : e.value;
}
final Entry<K,V> getEntry(Object key) {
    int hash = (key == null) ? 0 : hash(key);
    for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next)
        if (e.hash == hash && (e.key == key || key.equals(e.key))) return e;
    return null;
}

put 流程 O(1) 含擴容

public V put(K key, V value) {
    if (table == EMPTY_TABLE) inflateTable(threshold);
    if (key == null) return putForNullKey(value);
    int hash = hash(key), i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next)
        if (e.hash == hash && (e.key == key || key.equals(e.key))) {
            V old = e.value; e.value = value; e.recordAccess(this); return old;
        }
    modCount++; addEntry(hash, key, value, i); return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
    if (size >= threshold && table[bucketIndex] != null) {
        resize(2 * table.length); // 擴容 2 倍
        hash = (key == null) ? 0 : hash(key);
        bucketIndex = indexFor(hash, table.length);
    }
    createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e); // 頭插
    size++;
}

hash 函數與 indexFor

final int hash(Object k) {
    int h = hashSeed;
    if (h != 0 && k instanceof String) return sun.misc.Hashing.stringHash32((String)k);
    h ^= k.hashCode();
    h ^= (h >>> 20) ^ (h >>> 12); // 攪亂高位降低衝突
    return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) { return h & (length - 1); } // length 必須 2^n

擴容 resize 遷移

void resize(int newCapacity) {
    Entry[] old = table; int oldCap = old.length;
    if (oldCap == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; }
    Entry[] neu = new Entry[newCapacity];
    transfer(neu, initHashSeedAsNeeded(newCapacity));
    table = neu;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
void transfer(Entry[] newTable, boolean rehash) {
    for (Entry<K,V> e : table) while (e != null) {
        Entry<K,V> next = e.next;
        if (rehash) e.hash = (e.key == null) ? 0 : hash(e.key);
        int i = indexFor(e.hash, newTable.length);
        e.next = newTable[i]; newTable[i] = e; // 頭插遷移
        e = next;
    }
}