HashMap是Java集合框架中最重要且使用最频繁的Map接口实现类之一，它基于哈希表实现，提供了高效的键值对存储和检索操作。在JDK1.8之前，HashMap采用数组+链表的结构实现，而在JDK1.8及以后版本中，当链表长度超过阈值（默认为8）时，链表会转换为红黑树，以提升极端情况下的性能。

一、数据结构

1.1 数组+链表+红黑树结构

// JDK1.8中的HashMap核心字段
transient Node<K,V>[] table; // 哈希桶数组
transient Set<Map.Entry<K,V>> entrySet; // 键值对集合
transient int size; // 实际存储的键值对数量
int threshold; // 扩容阈值 (capacity * loadFactor)
final float loadFactor; // 负载因子(默认0.75)

HashMap内部维护了一个Node类型的数组table，每个Node包含：

int hash：键的哈希值
K key：键对象
V value：值对象
Node<K,V> next：下一个节点指针

1.2 哈希桶数组与链表

当发生哈希冲突时（不同键对象计算出相同的数组索引），HashMap采用链地址法解决冲突，即在数组的每个元素上挂载一个链表。JDK1.8优化了链表插入方式，从JDK1.7的头插法改为尾插法，避免了多线程环境下可能导致的死循环问题。

1.3 红黑树转换机制

当链表长度超过TREEIFY_THRESHOLD（默认8）且数组长度达到MIN_TREEIFY_CAPACITY（默认64）时，链表会转换为红黑树。当树节点数小于UNTREEIFY_THRESHOLD（默认6）时，红黑树会退化为链表。

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

二、核心实现

2.1 哈希函数设计

HashMap通过以下方式计算键的哈希值：

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

这种设计将高16位与低16位进行异或运算，目的是为了减少哈希冲突，使哈希分布更加均匀。

2.2 确定数组索引

通过哈希值与数组长度取模确定索引位置：

(n - 1) & hash // n为数组长度，必须为2的幂

这种位运算比取模运算效率更高，这也是HashMap数组长度总是2的幂的原因。

2.3 扩容机制

当size超过threshold时，HashMap会进行扩容（resize），扩容过程包括：

创建新数组（大小为原数组的2倍）
重新计算所有元素的位置（rehash）
转移元素到新数组

JDK1.8优化了元素转移过程，通过(e.hash & oldCap) == 0判断元素在新数组中的位置要么是原索引，要么是原索引+oldCap，避免了重新计算哈希值。

三、性能分析与优化

3.1 时间复杂度

操作	平均情况	最坏情况
get()	O(1)	O(log n)
put()	O(1)	O(log n)
put()	O(1)	O(log n)

在理想情况下（哈希分布均匀），HashMap的操作时间复杂度为O(1)；当哈希冲突严重时（所有元素都在同一个桶），链表情况下为O(n)，树化后提升为O(log n)。

3.2 负载因子影响

负载因子(loadFactor)决定了HashMap的空间利用率与时间效率的平衡：

较高的负载因子（如0.75）减少了空间开销但增加了哈希冲突
较低的负载因子减少了哈希冲突但增加了空间开销

3.3 初始化优化

如果能够预估HashMap中元素数量，建议在创建时指定初始容量：

// 预计存储100个元素，负载因子0.75
Map<String, String> map = new HashMap<>(128); // 128 = 100 / 0.75

避免多次扩容带来的性能损耗。

四、总结

HashMap通过精心设计的哈希函数、数组+链表+红黑树的数据结构以及动态扩容机制，实现了高效的键值对存储和检索。在实际开发中，应根据具体需求合理设置初始容量和负载因子，并注意线程安全问题，必要时考虑使用ConcurrentHashMap。

HashMap底层原理及数据结构深度解析