HashMap 源码分析

JavaJuice约 1284 字大约 4 分钟

HashMap 源码分析

1. 概述

HashMap 是一个基于哈希表实现的 Map 接口，它存储键值对 (key-value) 的映射关系。它允许键和值为 null，并且是线程不安全的。HashMap 提供了常数时间的查找、插入和删除操作，前提是哈希函数分布均匀。

2. 类声明

public class HashMap<K,V> extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable {
    // 成员变量和方法
}

继承关系：
- AbstractMap<K,V>：实现了 Map 接口的基本方法。
实现的接口：
- Map<K,V>：实现 Map 接口，提供了键值对的存储和操作。
- Cloneable：支持克隆。
- Serializable：支持序列化。

3. 关键成员变量

transient Node<K,V>[] table; // 哈希表数组
transient int size;          // 当前键值对的数量
transient int threshold;     // 哈希表的扩容阈值
final float loadFactor;      // 哈希表的负载因子
int modCount;                // 记录修改次数，用于 `Iterator` 的 fail-fast 机制

table：存储 Node 对象的数组，每个 Node 对象代表一个链表的头节点（链表解决哈希冲突）。
size：当前 HashMap 中存储的键值对数量。
threshold：哈希表的扩容阈值，threshold = capacity * loadFactor。
loadFactor：负载因子，用于决定何时扩容，默认值为 0.75。
modCount：记录结构修改的次数，用于检测并发修改。

4. 构造方法

(1) 默认构造方法

public HashMap() {
    this.loadFactor = 0.75f;  // 默认负载因子
    this.threshold = 12;      // 默认阈值
}

默认负载因子为 0.75，默认容量为 16（通过 threshold 计算）。

(2) 带初始容量和负载因子的构造方法

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0) throw new IllegalArgumentException("Illegal capacity: " + initialCapacity);
    if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor);

    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

设置初始容量和负载因子，并根据容量计算扩容阈值。

(3) 带初始容量的构造方法

public HashMap(int initialCapacity) {
    this(initialCapacity, 0.75f);
}

只有初始容量时，负载因子使用默认值 0.75。

5. 主要方法

(1) put(K key, V value) 方法

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Node<K,V> e = table[i]; e != null; e = e.next) {
        K k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            return oldValue;
        }
    }
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

计算键的哈希值，找到对应的数组索引 i。
如果哈希冲突发生（即该位置已有节点），则遍历链表，查找是否已存在该键的映射，如果存在则替换值。
如果不存在，调用 addEntry() 方法将新元素插入到链表中。

(2) addEntry(int hash, K key, V value, int bucketIndex) 方法

private void addEntry(int hash, K key, V value, int bucketIndex) {
    Node<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Node<>(hash, key, value, e);
    if (size++ >= threshold)
        resize(2 * table.length);
}

创建一个新的 Node，并将其插入到哈希表数组的相应位置。
如果插入后元素数量超过了阈值，则调用 resize() 扩容。

(3) resize(int newCapacity) 方法

private void resize(int newCapacity) {
    Node<K,V>[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    Node<K,V>[] newTable = new Node[newCapacity];
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}

扩容，将哈希表数组大小扩展为原来的两倍，并重新计算扩容阈值。

(4) transfer(Node<K,V>[] newTable) 方法

private void transfer(Node<K,V>[] newTable) {
    for (int j = 0; j < table.length; j++) {
        Node<K,V> e = table[j];
        if (e != null) {
            table[j] = null;
            do {
                Node<K,V> next = e.next;
                int i = indexFor(e.hash, newTable.length);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

遍历原哈希表中的每个链表，将每个节点重新计算位置并插入到新的哈希表中。

6. 访问元素

(1) get(Object key) 方法

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

通过计算键的哈希值和对应的数组索引来查找元素，如果存在则返回值。

7. 迭代器与 fail-fast 机制

HashMap 使用 modCount 来实现 fail-fast 机制，确保在遍历时，若 HashMap 被结构修改（插入、删除键值对等），则会抛出 ConcurrentModificationException。这一机制能有效防止多线程并发修改带来的问题。

8. 性能分析

优点：

查找、插入、删除操作的时间复杂度为 O(1)，前提是哈希函数良好、哈希表没有过多的冲突。
高效的动态扩容机制，负载因子为 0.75 时，内存和性能平衡较好。

缺点：

如果哈希函数不好，可能会导致哈希冲突过多，从而退化为链表，导致查询性能降低。
内存占用较大，尤其是当元素较少时，哈希表仍然有一定的空间浪费。

9. 总结

HashMap 作为 Java 中非常常用的集合类，其基于哈希表的实现使得其具有高效的插入、删除和查找性能。通过链表解决哈希冲突，动态扩容确保了在高负载情况下的性能。然而，它的查询性能依赖于哈希函数的质量，如果哈希函数不好，可能会导致大量的冲突，降低性能。