HashMap 是 Java 集合框架中用于存储键值对（key-value pairs）的核心数据结构，它基于哈希表实现，旨在提供高效的数据存取能力。
在使用HashMap的时候是否有想过以下问题：
1. HashMap 的数据结构是怎样的？
2. 如何解决哈希冲突？
3. 当存在哈希冲突时数据是怎么存取的？
下文中将依次解决以上疑问。
一、HashMap底层数据结构是怎样的
在JDK7及以前 HashMap 底层数据结构是：数组+链表，从JDK8开始 HashMap 底层数据结构是：数组+链表+红黑树，这种结构结合了数组的快速随机访问、链表的冲突处理和红黑树在极端情况下的性能保证。下面基于JDK8 分别解释每种结构的作用和为什么需要它们。
1. 整体架构图
HashMap 结构：
┌─────────────────────────────────────────────────────┐
│ Node<K,V>[] table │
│ (数组，每个元素称为一个"桶"bucket) │
├──────────┬──────────┬──────────┬──────────┬──────────┤
│ index=0 │ index=1 │ index=2 │ ... │ index=n-1│
├──────────┼──────────┼──────────┼──────────┼──────────┤
│ null │ 链表/树 │ Node │ ... │ null │
│ │ (冲突时) │ │ │ │
└──────────┴──────────┴──────────┴──────────┴──────────┘
2. 为什么使用数组
核心目的：快速查找，数组的查询速度（O(1)时间复杂度），数组优势如下：
2.1. 内存连续：CPU缓存友好，预读效率高
2.2.寻址快速：通过索引直接计算内存偏移量
2.3.空间局部性：相邻元素可能被连续访问
// 数组的快速随机访问特性
int index = (n - 1) & hash(key); // O(1)操作
Node<K,V> node = table[index]; // 直接内存地址访问相对于链表查询需要O(n)和红黑树查找需要O(log n)相比，数组的查询更快。
3. 为什么用到链表
核心目的：解决哈希冲突（碰撞）
// 当两个不同的key计算到同一个桶时
int hash1 = hash("key1"); // 假设结果为5
int hash2 = hash("key2"); // 假设结果也为5
// 它们都会进入table[5]，形成链表：
// table[5] → Node("key1",v1) → Node("key2",v2)链表的设计考量：
3.1.冲突概率低时的效率高：
统计学原理：Java默认负载因子0.75，当元素数量 < 容量*0.75时，冲突概率较低，链表节点少（通常0-3个），遍历成本可忽略
3.2.内存效率： 链表节点结构简单
class Node {
int hash; // 4字节
K key; // 引用8字节
V value; // 引用8字节
Node next; // 引用8字节
// 总共约28字节+对象头
}3.3.插入删除高效：链表头插法：O(1)时间复杂度
Node newNode = new Node(hash, key, value, first);
table[index] = newNode; // 直接替换头节点3.4.适合少量冲突性能更优：链表在元素≤8时，性能优于红黑树（常量因子更小）
4. 为什么用到红黑树
核心目的：防止极端情况下的性能退化，当大量key都哈希冲突到同一个桶时，链表会退化为O(n)查找，性能较低，而红黑树保证O(log n)查找速度。
红黑树和链表查询复杂度对比：
链表：查找O(n)，插入O(n)，删除O(n)
红黑树：查找O(log n)，插入O(log n)，删除O(log n)
当n=100万时：链表需要100万次比较，红黑树只需20次
和链表相比，红黑树是使用空间换时间的设计，但保证了性能的下线。
// 树节点内存更大
class TreeNode extends Node {
TreeNode parent; // +8字节
TreeNode left; // +8字节
TreeNode right; // +8字节
TreeNode prev; // +8字节（用于退化成链表）
boolean red; // +1字节（对齐后+8字节）
// 总共约60+字节，比链表节点大2倍
}链表和红黑树转换的阈值设计：
链表→树：阈值8（泊松分布计算得出），JDK 8+的进一步优化：链表长度≥8 且数组长度≥64才树化
static final int TREEIFY_THRESHOLD = 8;树→链表：阈值6（避免频繁转换的"抖动"）
static final int UNTREEIFY_THRESHOLD = 6;4. 为什么不只使用一种数据结构或使用其他数据结构
DOS攻击：一般指拒绝服务攻击，拒绝服务攻击即是攻击者想办法让目标机器停止提供服务。
二、哈希冲突解决基本原理及数据存储
1. 哈希冲突解决基本原理
HashMap通过链表（JDK 8之前）或链表+红黑树（JDK 8及以后）来解决哈希冲突。当多个key的哈希值映射到同一个数组索引（桶）时，这些key-value对会以链表或树的形式存储在该位置。
2. 查找值的过程
步骤一：计算哈希值定位桶
// 1. 计算key的哈希值（经过扰动函数处理）
int hash = hash(key);
// 2. 定位到数组中的索引位置
int index = (n - 1) & hash; // n是数组长度步骤二：在桶内查找
// 伪代码表示查找逻辑
public V get(Object key) {
// 1. 计算哈希值
int hash = hash(key);
// 2. 找到对应的桶（数组元素）
Node<K,V> first = table[index];
// 3. 遍历链表/树查找
if (first != null) {
// 检查第一个节点
if (first.hash == hash &&
(first.key == key || (key != null && key.equals(first.key)))) {
return first.value;
}
// 继续遍历后续节点
Node<K,V> e = first.next;
while (e != null) {
if (e.hash == hash &&
(e.key == key || (key != null && key.equals(e.key)))) {
return e.value;
}
e = e.next;
}
}
return null;
}步骤三：根据key进行比较获取值
HashMap通过两个条件来确定是否找到正确的key：
（1）哈希值相等：比较计算出的哈希值是否相同
（2）key相等：通过以下条件判断：
- 内存地址相同（==）
- 或者通过equals()方法比较内容相等
// 实际的比较逻辑
if (node.hash == hash &&
((k = node.key) == key || (key != null && key.equals(k)))) {
// 找到匹配的key
}三、JDK HashMap 源码解析：哈希冲突处理
1. HashMap 的核心数据结构
// HashMap 类中的关键字段
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
// 存储节点的数组（桶数组）
transient Node<K,V>[] table;
// 默认初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
// 链表转换为红黑树的阈值
static final int TREEIFY_THRESHOLD = 8;
// 红黑树退化为链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
// 树化的最小容量
static final int MIN_TREEIFY_CAPACITY = 64;
// 节点类（链表节点）
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;
}
}
// 树节点类（红黑树节点）
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // 父节点
TreeNode<K,V> left; // 左子节点
TreeNode<K,V> right; // 右子节点
TreeNode<K,V> prev; // 前驱节点
boolean red; // 红色标志
}
}2. hash() 方法：扰动函数
// 计算 key 的哈希值（扰动函数）
static final int hash(Object key) {
int h;
// 1. 获取 key 的 hashCode()
// 2. 将高16位与低16位异或，增加低位的随机性
// 目的：减少哈希冲突
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 示例：
// key.hashCode() = 1111 1111 1111 1111 0000 0000 0000 0001
// h >>> 16 = 0000 0000 0000 0000 1111 1111 1111 1111
// hash = h ^ (h >>> 16) = 1111 1111 1111 1111 1111 1111 1111 11103. get() 方法入口
// 公开的 get 方法
public V get(Object key) {
Node<K,V> e;
// 调用 getNode 方法
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
// 核心查找方法
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; // 引用数组
Node<K,V> first, e; // first: 桶的第一个节点
int n; // 数组长度
K k; // 临时存储 key
// 步骤1: 检查数组是否为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) { // 定位桶
// 步骤2: 检查第一个节点是否匹配
if (first.hash == hash && // 哈希值相等
((k = first.key) == key || // 内存地址相同 或
(key != null && key.equals(k)))) // equals 相等
return first; // 直接返回
// 步骤3: 如果第一个节点不匹配，检查后续节点
if ((e = first.next) != null) {
// 步骤3.1: 如果是红黑树节点，使用树查找
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 步骤3.2: 链表遍历
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null; // 未找到
}4. 红黑树查找方法
// TreeNode 的 getTreeNode 方法
final TreeNode<K,V> getTreeNode(int h, Object k) {
// 从根节点开始查找
return ((parent != null) ? root() : this).find(h, k, null);
}
// 在红黑树中查找节点
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this; // 从当前节点开始
do {
int ph, dir;
K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
// 步骤1: 比较哈希值
if ((ph = p.hash) > h)
p = pl; // 向左子树查找
else if (ph < h)
p = pr; // 向右子树查找
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p; // 找到匹配的节点
// 步骤2: 哈希值相等但key不相等，检查子树
else if (pl == null)
p = pr; // 左子树为空，查找右子树
else if (pr == null)
p = pl; // 右子树为空，查找左子树
// 步骤3: 比较 key 的类型和哈希值
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr; // 使用比较器决定方向
// 步骤4: 递归在右子树中查找
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl; // 在左子树中查找
} while (p != null);
return null; // 未找到
}5. put() 方法中的冲突处理
// put 方法的实现（简化版）
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab;
Node<K,V> p;
int n, i;
// 步骤1: 如果数组为空，初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 步骤2: 计算桶索引，如果桶为空，直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// 步骤3: 桶不为空，发生哈希冲突
Node<K,V> e; // 临时节点
K k;
// 情况3.1: 第一个节点就匹配
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 情况3.2: 节点是树节点
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 情况3.3: 链表遍历
else {
for (int binCount = 0; ; ++binCount) {
// 到达链表尾部
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 检查是否需要树化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 找到匹配的节点
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k))))
break;
p = e; // 继续下一个节点
}
}
// 步骤4: 如果找到已存在的key，更新值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 步骤5: 修改计数和扩容检查
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}6. 索引计算详解
// 如何计算桶索引
int hash = hash(key); // 经过扰动函数的哈希值
int index = (n - 1) & hash; // n是数组长度，必须是2的幂
// 示例：
// hash = 1100 1100 1100 1100 0011 0011 0011 0011
// n = 16 (0000 0000 0000 0000 0000 0000 0001 0000)
// n-1 = 15 (0000 0000 0000 0000 0000 0000 0000 1111)
// index = (n-1) & hash = 0000 0000 0000 0000 0000 0000 0000 0011 = 3为什么 n 必须是2的幂？ 因为当 n 是2的幂时，(n-1) 的二进制是全部为1的形式。例如：n=16, n-1=15 (1111)，与运算相当于取模运算 hash % n，但位运算(&)比取模运算(%)快得多。