HashMap 是 Java 开发中使用频率最高的键值对存储容器，用于存储 key-value 映射关系。日常业务中缓存、参数映射、分组统计都离不开它。
前言
Map 接口用于存储键值对映射，key 唯一，value 可重复。 常用实现类：HashMap、TreeMap、LinkedHashMap、HashTable。
- HashMap：无序，底层哈希表，查询插入 O (1)，非线程安全；允许一个 null key，多个 null value；
- TreeMap：有序（key 自然排序 / 自定义比较器），红黑树；
- LinkedHashMap：保留插入顺序，继承 HashMap；
- HashTable：线程安全，方法加 synchronized，锁整张哈希表，性能差，已基本废弃。
核心：HashMap 底层是哈希表。哈希表本质思想：通过 hash 函数，把 key 映射到数组下标，实现快速定位。多个 key 映射到同一个下标，就产生哈希冲突。
一、核心成员变量（JDK8）
// 默认初始容量：16，必须是2的整数次幂 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 最大容量 static final int MAXIMUM_CAPACITY = 1 << 30; // 默认负载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 链表转为红黑树阈值：链表节点数量 >=8，触发树化判断 static final int TREEIFY_THRESHOLD = 8; // 红黑树退化成链表阈值：节点数量 <=6 static final int UNTREEIFY_THRESHOLD = 6; // 树化的最小数组容量：数组容量>=64，才真正树化；小于64优先扩容 static final int MIN_TREEIFY_CAPACITY = 64; // 哈希表数组，存放Node节点 transient Node<K,V>[] table; // 缓存entrySet transient Set<Map.Entry<K,V>> entrySet; // 集合存储KV总数量 transient int size; // 修改计数器，add/remove/clear都会++，用于快速失败 transient int modCount; // 阈值：threshold = 容量 * 负载因子，size超过阈值，触发扩容resize int threshold; // 负载因子 final float loadFactor;变量重点解读
容量必须是 2 的整数次幂为什么要求数组长度是 2 的幂？ 数组下标计算公式：hash & (table.length -1)。 当 length=2^n，length-1二进制全部为 1，按位与等价于取模hash % length，位运算比取模运算速度快很多。
如果长度不是 2 的幂，掩码会出现 0 位，大量 hash 值映射到同一个下标，哈希冲突暴增。
负载因子 loadFactor = 0.75负载因子 = 元素数量 / 哈希表容量。代表哈希表填充程度。
- 负载因子越大：数组填充越满，内存利用率高，但哈希冲突概率变高，链表变长，查询变慢；
- 负载因子越小：冲突少，查询性能好，但数组大量空位，内存浪费。 0.75 是统计学泊松分布计算后的折中值，平衡时间开销与内存开销。
threshold 阈值threshold = capacity * loadFactor。当size > threshold，执行扩容 resize。
注意：size 是 KV 键值对总数，不是链表长度。
Node 节点源码
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; } // ... get/set方法 }Node 存储 hash 值、key、value、下一个节点引用，单向链表结构。 当转为红黑树时，节点升级为TreeNode，继承 Node，增加红黑树相关属性（父节点、左右孩子、颜色）。
二、Hash 扰动函数
static final int hash(Object key) { int h; // key.hashCode() 异或 hashCode无符号右移16位 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }扰动函数设计思想
hashCode()返回 32 位 int 值。hash & (length-1)，只有低位参与下标计算。 如果两个 key 的 hashCode 高位不同、低位相同，会发生哈希冲突。h >>>16：把 hashCode高 16 位右移，和低 16 位做异或，把高位信息混入低位。
目的：增加低位随机性，减少哈希冲突。
JDK7 扰动：4 次移位异或扰动；JDK8 简化为一次扰动，兼顾性能与冲突抑制效果。
key 为 null，hash=0，所以 HashMap 允许一个 null key，放在数组下标 0 位置。
三、JDK8 put () 完整流程（重点）
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } 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. table为空或者长度为0，先执行扩容初始化table if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 2. 计算下标 i = hash & (n-1)，桶为空，直接新建Node放入 if ((p = tab[i = hash & (n - 1)]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; // 3. 桶头节点key和当前key相等，找到旧节点 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 4. 判断当前桶是红黑树节点，走红黑树新增逻辑 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { // 5. 遍历单向链表 for (int binCount = 0; ; ++binCount) { // 遍历到链表尾部，插入新节点【尾插法】 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // binCount >=7 代表链表长度达到8，触发树化判断 if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); break; } // 链表中找到相同key，跳出循环，准备覆盖value if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 6. 如果找到key，覆盖旧value if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // 7. size自增，超过阈值触发扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }put 流程文字总结
1.计算 key 的 hash 值；
2.如果 table 数组还未初始化，调用 resize 初始化数组；
3.根据 hash 定位桶下标；桶为空，直接新建 Node 放入；
4.桶不为空：
- 桶头节点 key 相同：覆盖 value；
- 桶是红黑树节点，走树节点新增；
- 遍历单向链表，找到相同 key 则覆盖；遍历到尾部，尾插新增节点；
5.链表新增节点后，判断链表长度达到 8，调用treeifyBin做树化判断；
6.size++，判断超过阈值，触发扩容 resize。
JDK7 是头插法：新节点插到链表头部。并发扩容会形成环形链表，get 操作死循环 CPU100%。JDK8 改为尾插，修复死循环 BUG，但 HashMap 依然线程不安全。
四、treeifyBin 链表树化 & untreeify 红黑树退化
final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; // 关键判断：数组容量小于64，不树化，优先扩容！ if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = hash & (n - 1)]) != null) { // 链表转为红黑树TreeNode TreeNode<K,V> hd = null, tl = null; do { TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); if ((tab[index] = hd) != null) hd.treeify(tab); } }完整树化条件（两个条件必须同时满足）
- 当前桶链表节点数量 ≥ 8；
- 哈希表数组容量 ≥ 64。 数组容量不足 64，优先扩容，不做树化。因为扩容之后，节点会分散到新桶，链表长度变短，树化开销很大。
红黑树退化条件：当扩容 / 删除节点后，桶内红黑树节点数量 ≤ 6，红黑树退化成单向链表。
阈值 8 和 6 之间留有缓冲区间，防止频繁在链表、红黑树之间来回转换，避免震荡带来性能损耗。
五、resize () 扩容机制
扩容：当 size > threshold，数组容量扩大为原来2 倍。 新容量newCap = oldCap << 1。
扩容时，原有桶内节点迁移到新数组，不需要重新计算 hash。 利用hash & oldCap判断：
hash & oldCap == 0：节点留在原下标位置；hash & oldCap !=0：节点迁移到原下标 + oldCap的新桶。
原理：oldCap 是 2 的幂，二进制只有最高位是 1。hash & oldCap判断 hash 在这一位是 0 还是 1，直接决定新下标。
JDK8 扩容优化，省去重新 hash 计算，提升扩容性能。
JDK7 扩容
扩容后需要重新计算 hash，并且头插法迁移节点，并发场景容易形成环形链表。
六、get 查询流程
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : null; } final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { // 检查桶头节点 if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { // 红黑树，走树查找 if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); // 遍历链表查找 do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }get 逻辑：
- 计算 hash 定位桶；
- 桶头匹配直接返回；
- 如果是红黑树，树内查找 O (logn)；链表遍历 O (n)。
七、JDK7 HashMap VS JDK8 HashMap 完整对比
| 对比项 | JDK7 HashMap | JDK8 HashMap |
|---|---|---|
| 底层存储结构 | 数组 + 单向链表 | 数组 + 单向链表 + 红黑树 |
| 节点插入方式 | 头插法 | 尾插法 |
| hash 扰动算法 | 4 次移位异或扰动 | 1 次高低位异或扰动 |
| 扩容节点迁移 | 重新计算 hash；头插迁移 | 不需要重算 hash；高低位判断，尾插迁移 |
| 并发扩容问题 | 多线程扩容容易形成环形链表，get 死循环 CPU 100% | 修复环形链表，但依旧线程不安全，会丢数据 |
| 树化功能 | 无 | 链表 >=8 且数组 >=64，转为红黑树；<=6 退链表 |
| 节点类 | Entry | Node / TreeNode |
八、hashCode () 和 equals () 规范
自定义对象作为 HashMap 的 key，必须同时重写 hashCode () 和 equals ()！规则：
- equals 返回 true 的两个对象，hashCode 必须相等；
- hashCode 相等，equals 不一定相等（哈希冲突）。
如果只重写 equals 不重写 hashCode：两个逻辑相等对象，hashCode 不同，存到不同桶，无法覆盖，会存入两个 key，造成 bug。
String、Integer 等包装类已经重写 hashCode 与 equals，可以直接做 key。 key 尽量使用不可变对象。可变对象修改属性后 hashCode 变化，会导致存进去之后无法 get 到。
九、HashMap 线程不安全详细表现
HashMap 没有任何锁保护，多线程并发操作会出现问题：
- 并发 put 丢失数据：多个线程同时 put 到同一个桶，节点覆盖，元素丢失；
- JDK7 并发扩容：链表形成环，get 死循环 CPU100%；
- 并发 put + get：读到半更新数据；
- size 计数错乱。
重点：JDK8 虽然修复 JDK7 的环形链表问题，但依然不是线程安全。并发场景请使用 ConcurrentHashMap。
十、开发实战踩坑清单
1.初始化不指定容量，频繁扩容HashMap 默认容量 16。预估要存放 N 个元素，初始化容量计算公式：new HashMap((int)(N / 0.75f)+1)，减少 resize 扩容次数。
不要直接写 new HashMap<>(N)，阈值是容量 * 0.75，N 个元素会触发扩容。
2.可变对象作为 key。修改 key 属性，hash 改变，map.get (key) 无法找到元素。
3.put 相同 key，旧 value 会被覆盖，很多业务忽略旧值。
4.遍历 HashMap 时执行 put/remove，modCount 增加，触发快速失败ConcurrentModificationException。
遍历删除推荐
removeIf，或者迭代器删除。
5.HashMap 允许一个 null key；多个 null value。get (null) 可以获取。
6.HashMap 无序，每次扩容后元素顺序可能变化。如果需要保留插入顺序，使用 LinkedHashMap。
十一、常用 API 与时间复杂度
| 方法 | 说明 | 平均时间复杂度 | 最坏情况 |
|---|---|---|---|
| put(k,v) | 新增 / 覆盖键值对 | O(1) | O (n)（极端哈希冲突全部成链表） |
| get(k) | 根据 key 取值 | O(1) | O(n) |
| remove(k) | 删除 key | O(1) | O(n) |
| containsKey(k) | 判断 key 是否存在 | O(1) | O(n) |
| size() | 获取键值对数量 | O(1) | O(1) |
最坏情况：大量哈希冲突，全部落到同一个桶，退化成链表，查询 O (n)。红黑树优化后最坏 O (logn)。
十二、问答
Q1：HashMap 底层结构？JDK8 引入红黑树目的？
A：JDK8：数组 + 链表 + 红黑树。哈希冲突严重时链表过长，查询遍历 O (n)；红黑树查询 O (logn)，提升查询性能。
Q2：负载因子为什么是 0.75，不是 0.5 或者 1？
A：负载因子代表哈希表填充程度。0.5 内存利用率低；1 冲突概率极高。0.75 是泊松分布的经验值，平衡内存占用与哈希冲突概率。
Q3：链表什么时候转为红黑树，什么时候退化？为什么阈值 8 和 6 不一样？
A：链表 >=8，数组容量 >=64 才树化；节点 <=6 退链表。设置缓冲区间，避免链表长度在 8 附近频繁树化、退化，减少性能震荡。
Q4：HashMap 数组容量为什么必须是 2 的幂？
A：为了hash & (length-1)快速计算下标，替代取模运算，提升性能。同时让 hash 值分布更均匀。
Q5：自定义对象作为 HashMap key 有什么要求？
A：必须重写 hashCode () 和 equals ()；尽量使用不可变对象。equals 相等的对象 hashCode 必须相同。
Q6：HashMap 线程安全吗？并发场景用什么？
A：非线程安全，并发会丢数据。并发场景推荐 ConcurrentHashMap。
Q7：JDK8 为什么把头插改成尾插？
A：JDK7 头插法并发扩容会形成环形链表，get 死循环。尾插法不会产生环形链表，修复该 BUG，但 HashMap 依旧线程不安全。
结语
HashMap 是集合框架面试重中之重。很多人背结构，但是忽略底层设计思想：哈希寻址、冲突解决、负载因子、树化条件、扩容迁移逻辑。 理解 HashMap，核心是理解哈希冲突的取舍。工程上没有完美方案，负载因子、树化阈值都是时间与内存之间的权衡。 开发中合理设置初始容量、选对 key 类型，避开可变 key、并发修改等坑。
