HashMap是 Java 中最常用、面试中最常被问到的集合类之一。它基于哈希表实现,提供了存储键值对的功能,具有高效的存取速度。以下是对HashMap的全方位深度解析,包括底层结构、核心原理、扩容机制、版本差异以及常见面试题。
1. 底层数据结构
HashMap 的底层数据结构是 数组 + 链表 + 红黑树(JDK 1.8 及以后)。
- 哈希桶数组(table): 这是
HashMap的骨干,即Node<K,V>[] table(JDK 1.8 中Node是HashMap的内部类,实现了Map.Entry接口)。数组的每个位置称为一个'桶'(bucket),桶中存放的是链表或红黑树的头节点,用于快速定位元素。数组的默认初始容量为 16,且长度始终保持为 2 的幂次方; - 链表: 当不同的键通过哈希函数计算出相同的数组下标(即发生哈希冲突)时,
HashMap采用链地址法来解决冲突。冲突的键值对会以链表形式存储在同一个桶中。链表节点是一个静态内部类Node,它包含了键的哈希值(final int hash)、键(final K key)、值(V value)以及指向下一个节点的指针(Node<K,V> next); - 红黑树: 这是 JDK 1.8 引入的关键优化。当某个桶中的链表长度过长(默认达到 8),且当前哈希桶数组的总长度大于等于 64 时,该链表会被转换为红黑树。红黑树是一种自平衡的二叉查找树,能将最坏情况下的查找时间复杂度从链表的
O(n)优化至O(log n)。当红黑树节点数少于 6 时,又会转回链表(平衡查询和插入性能);
2. 核心成员变量与参数
理解 HashMap 必须知道以下几个关键参数:
initialCapacity(初始容量): 默认是 16。必须是 2 的 n 次幂。loadFactor(负载因子): 默认是 0.75。threshold(扩容阈值) =capacity * loadFactor。当 size(元素个数)大于这个值时,触发扩容。size: 当前 Map 中实际存储的键值对数量。
3. 核心方法原理
3.1 确定 Hash 索引(如何把 Key 放进数组?)
当调用 put(key, value) 时,HashMap 需要计算这个 key 应该放在数组的哪个下标。计算步骤如下:
- 扰动函数:
hash = (h = key.hashCode()) ^ (h >>> 16)- 首先调用
key.hashCode()获得原始哈希值;
- 首先调用


