Java集合-HashMap

前言

HashMap 是 Java 集合框架中一个非常重要的类，广泛应用于键值对（key-value pair）的存储和快速查找场景。它实现了 Map 接口，基于哈希表实现，提供高效的性能。本文将从 HashMap 的基本概念入手，深入分析其内部实现，包括数据结构、哈希函数、插入过程、扩容机制和线程安全性，并结合关键源码进行讲解。

HashMap 的主要特点包括：

键值特性：允许一个 null 键和多个 null 值。
无序性：不保证键值对的存储顺序。
高效性：在平均情况下，查找、插入和删除操作的时间复杂度为 $O(1)$。

HashMap 的高效性使其成为开发中常用的工具，尤其适用于需要快速访问数据的场景。

源码分析

数据结构

HashMap 的核心是一个哈希表，其底层实现依赖数组和链表或红黑树的组合。具体来说：

Java 8 之前的实现：HashMap 使用数组 + 链表结构。数组的每个元素是一个链表，用于处理哈希冲突（即多个键映射到同一索引的情况）。
Java 8 之后的优化：当链表长度过长时（超过 8 且数组长度 ≥ 64），链表会转换为红黑树。红黑树是一种自平衡二叉查找树，能将最坏情况下的查找时间复杂度从 $O(n)$ 优化为 $O(log n)$。

HashMap 的核心数据结构是一个 Node<K,V>[] table 数组，其中 Node<K,V> 是一个静态内部类，定义如下：

static class Node<K,V> implements Map.Entry<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;
    }
    // ... getter 方法省略
}

哈希函数

HashMap 使用哈希函数将键映射到数组索引，其哈希值的计算由 hash() 方法完成：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

如果键为 null，哈希值为 0。
否则，调用键的 hashCode() 方法获取原始哈希值 h，然后通过 h ^ (h >>> 16) 将高 16 位与低 16 位异或。
目的：让高位信息参与计算，减少哈希冲突，提高分布均匀性。

最终的索引通过 (table.length - 1) & hash 计算，确保索引落在数组范围内。

插入元素的逻辑

插入键值对时，调用 put(K key, V value) 方法，其核心逻辑在 putVal() 方法中。插入过程如下：

初始化检查：如果 table 为空或长度为 0，调用 resize() 初始化。
计算索引：根据哈希值计算索引 i = (n - 1) & hash，其中 n 是数组长度。
无冲突情况：如果 table[i] 为空，直接创建新节点插入。
冲突处理：

链表情况：遍历链表，若找到相同 key（通过 hash 和 equals() 判断），更新 value；否则在链表末尾添加新节点。
红黑树情况：调用红黑树的插入方法 putTreeVal()。

树化检查：插入后，若链表长度 ≥ 8 且数组长度 ≥ 64，调用 treeifyBin() 将链表转为红黑树。
扩容检查：若元素总数超过阈值（capacity * loadFactor），调用 resize() 扩容。

以下是 putVal() 的核心源码：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; // 找到相同 key，准备更新 value
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // TREEIFY_THRESHOLD = 8
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // 更新已有 key 的 value
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            return oldValue;
        }
    }
    ++size;
    if (size > threshold)
        resize();
    return null;
}

扩容机制

当元素数量超过阈值（threshold = capacity * loadFactor）时，HashMap 调用 resize() 进行扩容：

容量翻倍：新数组容量为原来的 2 倍（初始容量默认 16，负载因子默认 0.75）。
元素重分配：重新计算每个元素的索引并移动到新数组。
优化：利用容量为 2 的幂次特性，通过 (e.hash & oldCap) 判断元素是留在原索引还是移动到 原索引 + oldCap。

resize() 的核心逻辑如下：

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int newCap = oldCap << 1; // 容量翻倍
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else {
                    Node<K,V> loHead = null, loTail = null; // 原索引链表
                    Node<K,V> hiHead = null, hiTail = null; // 新索引链表
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null) loHead = e;
                            else loTail.next = e;
                            loTail = e;
                        } else {
                            if (hiTail == null) hiHead = e;
                            else hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

后记

HashMap 不是线程安全的。在多线程环境下，多个线程同时操作（如 put）可能导致：

数据覆盖或丢失。
在 Java 7 及以前，扩容时的链表转移可能形成环，导致死循环。

解决方案：

使用 Collections.synchronizedMap() 包装 HashMap。
使用 ConcurrentHashMap，它通过分段锁或 CAS 机制提供更高的并发性能。