核心数据结构：数组 + 链表 / 红黑树
HashMap 的底层核心是一个 Node<K,V>[] table 数组（通常称为 桶数组 或 哈希桶数组）。这个数组的每个元素称为一个 桶。
Node<K,V>(链表节点)：这是存储键值对的基本单位，当没有哈希冲突或冲突较少时使用。
定义（简化）：
static class Node<K,V> implements Map.Entry<K,V> { final int hash; // 存储键的最终哈希值（经过扰动处理后的） final K key; // 键，final 确保一旦放入，键引用不可变（但对象内容可变有风险！） V value; // 值，可以修改 Node<K,V> next; // 指向链表下一个节点的引用 // ... 构造函数、getter/setter、equals、hashCode 等方法 ... }当两个不同的键通过
(table.length - 1) & hash计算出的 桶索引（下标）相同时，就发生了 哈希冲突。冲突的键值对会以单向链表的形式存储在同一个桶中。新节点在 Java 8+ 中插入到链表尾部。
TreeNode<K,V>(红黑树节点)：这是
Node的子类，当链表过长时使用。定义（简化）：
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; // 节点颜色 (true=红, false=黑) // ... 树操作相关的方法（如旋转、插入平衡、删除平衡、查找等）... }树化条件： 当某个桶中的链表长度达到阈值
TREEIFY_THRESHOLD(默认为 8) 并且 当前桶数组table的长度达到MIN_TREEIFY_CAPACITY(默认为 64) 时，这个链表会被转换为 红黑树。退化条件： 当桶中的红黑树节点数量减少到阈值
UNTREEIFY_THRESHOLD(默认为 6) 时，红黑树会退化为单向链表。为什么引入红黑树？ 在极端情况下（如大量键哈希冲突），链表会变得非常长，导致查询效率从理想的 O(1) 退化到 O(n)。红黑树是一种自平衡二叉查找树，它能将最坏情况下的查询、插入、删除操作的时间复杂度维持在 O(log n)，显著提升了性能。
关键过程详解
put(K key, V value)- 插入键值对计算哈希 (
hash(key)):首先调用键对象的
key.hashCode()获取原始哈希值h。然后进行 扰动处理：
(h = key.hashCode()) ^ (h >>> 16)为什么扰动？ 原始哈希码的高位变化通常更丰富，但桶索引计算
(n-1) & hash只用到低位（因为n是 2 的幂，n-1低位全是 1）。h ^ (h >>> 16)将原始哈希码的高 16 位特性异或到低 16 位中，增加了低位的随机性，显著减少了不同哈希码但低位相同（导致冲突）的概率，使元素分布更均匀。
计算桶索引 (
i = (n - 1) & hash):n是当前桶数组table的长度（table.length），总是 2 的幂。(n - 1) & hash：因为n是 2 的幂，n-1的二进制表示是低位连续一串1(例如15 -> 0b1111,31 -> 0b11111)。&操作相当于取hash值低log2(n)位的值，效果等同于hash % n，但位运算效率远高于取模运算。结果i就是键值对应该放入的桶的索引（0 到 n-1）。
处理目标桶 (
table[i]):情况 1：桶为空 (
table[i] == null)直接创建一个新的
Node节点newNode(hash, key, value, null)，放入table[i]。
情况 2：桶不为空
遍历桶中的结构（可能是链表或树）。
查找键是否存在： 对于每个节点
p：先比较
p.hash == hash(快速失败，哈希不同肯定不是同一个键)。再比较
(p.key == key)或(key != null && key.equals(p.key))(引用相等或逻辑相等)。
找到匹配节点： 如果找到键相等的节点
p，用新值value覆盖p.value，并返回旧值（put方法本身有返回值）。未找到匹配节点：
如果是链表：
创建新
Node，插入到链表尾部 (Java 8+ 尾插法)。插入后检查链表长度是否
>= TREEIFY_THRESHOLD(8)。如果
>=8且table.length >= MIN_TREEIFY_CAPACITY(64)，则调用treeifyBin(tab, hash)方法将此链表转换为红黑树。如果
>=8但table.length < 64，则只调用resize()进行扩容（扩容可能直接分散冲突，避免树化开销）。
如果是红黑树： 调用红黑树的插入方法
putTreeVal(this, tab, hash, key, value)来插入新节点。该方法内部会处理树的平衡。
修改计数 & 检查扩容：
如果添加了新节点（不是覆盖旧值），则
modCount++（用于 fail-fast 机制）。检查当前元素总数
size是否> threshold(threshold = capacity * loadFactor)。如果超过，则调用resize()进行扩容。
get(Object key)- 获取值计算哈希 (
hash(key)): 同put过程。计算桶索引 (
i = (n - 1) & hash): 同put过程。查找目标桶 (
table[i]):桶为空： 返回
null。桶不为空：
检查第一个节点： 如果桶中第一个节点（链表头或树根）的
hash和key匹配（比较规则同put），直接返回该节点的value。后续节点：
如果是链表： 遍历链表，用
hash和key匹配查找节点。如果是红黑树： 调用红黑树的查找方法
getTreeNode(hash, key)进行查找。
找到匹配节点： 返回其
value。未找到： 返回
null。
resize()- 扩容 (核心难点与优化点)触发条件：
size > threshold或初始化时table == null。目的： 增加桶的数量，减少哈希冲突，保持 O(1) 的访问性能。
过程：
计算新容量和阈值：
旧容量
oldCap，旧阈值oldThr。如果
oldCap > 0：如果
oldCap >= MAXIMUM_CAPACITY：设置阈值为Integer.MAX_VALUE，不再扩容，直接返回。否则，新容量
newCap = oldCap << 1(扩大为 2 倍)，新阈值newThr = oldThr << 1(也是 2 倍)。
否则，如果是初始化 (
oldCap == 0 && oldThr > 0)：newCap = oldThr(使用构造时指定的初始容量)。否则，完全初始化 (
oldCap == 0 && oldThr == 0)：newCap = DEFAULT_INITIAL_CAPACITY(16),newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY)(12)。如果
newThr == 0：重新计算newThr = (int)(newCap * loadFactor)。
创建新数组： 创建一个新的
Node数组newTab，长度为newCap。重新映射节点 (Rehashing - Java 8 优化精髓)：
遍历旧数组
table的每个桶oldTab[j]。如果桶不为空：
情况 1：桶中只有一个节点 (无冲突)： 直接计算该节点在新数组中的位置
e.hash & (newCap - 1)，放入newTab。情况 2：桶中是链表或红黑树：
Java 8 优化关键： 利用
newCap是oldCap2 倍 (oldCap << 1) 的特性。旧数组长度oldCap是 2 的幂，其二进制表示是1后面跟着一串0(如 16:0b10000)。因此，e.hash & oldCap的结果只有两种可能：0或oldCap(非0)。这个位运算实际上是在检查e.hash在oldCap对应二进制位（即新增的最高位）上是0还是1。创建两个链表头节点
loHead/loTail(低位链) 和hiHead/hiTail(高位链)。遍历旧桶中的每个节点
e：如果
(e.hash & oldCap) == 0：则该节点在新数组中的位置= j(原索引位置)。将其添加到loHead/loTail链表尾部。如果
(e.hash & oldCap) != 0：则该节点在新数组中的位置= j + oldCap(原索引 + 旧容量)。将其添加到hiHead/hiTail链表尾部。
链表处理：
如果
loTail != null：将低位链loHead放入newTab[j]。如果
hiTail != null：将高位链hiHead放入newTab[j + oldCap]。
红黑树处理： 如果旧桶是红黑树，会调用
split方法。该方法同样使用(e.hash & oldCap) == 0规则将树节点拆分到lo和hi两个链表/树中。拆分后：如果链表长度
<= UNTREEIFY_THRESHOLD(6)：调用untreeify退化成链表，放入新桶。否则，检查拆分后的两个链表是否还能构成树（通常长度>6会尝试树化），然后放入新桶的相应位置。
更新引用： 将
table指向新数组newTab，更新threshold = newThr。
关键设计点与参数
容量 (
capacity): 桶数组table的长度。必须是 2 的幂。默认初始容量DEFAULT_INITIAL_CAPACITY = 16。构造时可指定，但HashMap会自动调整为大于等于指定值的最小 2 的幂（如指定 10，实际容量为 16）。大小 (
size): 当前HashMap中存储的键值对数量。负载因子 (
loadFactor): 一个浮点数，默认DEFAULT_LOAD_FACTOR = 0.75f。用于计算扩容阈值：threshold = capacity * loadFactor。当size > threshold时扩容。0.75 是空间和时间效率的一个较好平衡点。扩容阈值 (
threshold):capacity * loadFactor。当size超过此值时触发resize()。树化阈值 (
TREEIFY_THRESHOLD): 链表转换为红黑树的链表长度阈值，默认为 8。基于泊松分布统计，链表长度达到 8 的概率已经非常小（约千万分之一），此时树化的收益大于开销。退化阈值 (
UNTREEIFY_THRESHOLD): 红黑树退化为链表的节点数阈值，默认为 6。避免在临界值附近频繁树化退化。最小树化容量 (
MIN_TREEIFY_CAPACITY): 进行树化的最小桶数组容量要求，默认为 64。在桶数量太少时，优先扩容分散节点比树化更有效。
为什么容量必须是 2 的幂？
高效计算桶索引： 使用
(n - 1) & hash代替hash % n，位运算&比取模%快得多。优化扩容时的节点迁移 (Java 8 精髓)： 扩容时，节点的新位置只可能是原位置
j或j + oldCap。这个结论成立的关键就是oldCap是 2 的幂，使得e.hash & oldCap的结果只有 0 或非 0 两种可能。这避免了重新计算每个节点的哈希值，极大提高了扩容效率。
总结
HashMap 的底层核心是一个动态扩容的桶数组。它通过计算键的哈希值（经过扰动）确定桶的位置。使用链表解决哈希冲突，并在链表过长（且桶数组足够大）时将其转换为红黑树以保证最坏情况下的性能。其设计精髓在于：
扰动函数： 减少哈希冲突。
2 的幂容量 & 位运算索引： 高效定位桶。
链表 + 红黑树： 平衡普通情况和最坏情况下的性能。
扩容优化 (Java 8+): 利用
e.hash & oldCap快速确定节点在新数组中的位置（只有两种可能），避免重新哈希，大幅提升扩容效率。