HashMap 作为 java 和 Android 开发中面试的必问问题，很有必要对其有一个详细的了解。在 JDK 1.8 中，HashMap 的底层实现有了一些重要的优化。本文将从源码角度详细解析其底层原理。

JDK 1.8 相比 1.7 有了较大优化（比如引入红黑树）

源码部分重点在四个地方：

1. 根据key获取哈希桶数组索引位置
2. put方法的详细执行
3. 扩容过程
4. get方法过程

一、核心数据结构

HashMap 底层最核心的数据结构是一个数组，这个数组的每个元素都是一个链表。在 JDK 1.8 中，为了解决链表过长导致的查找效率下降问题，当链表长度超过一定阈值（默认为 8）时，链表会被转换为红黑树。当红黑树的节点数量低于一定阈值（默认为 6）时，又会重新退化为链表。

所以，在 JDK 1.8 中，HashMap 的核心数据结构是 数组 + 链表 + 红黑树

数组（Node\<K,V>\[] table）

存储哈希桶（bucket），数组索引由 hash(key) 计算得出，每个桶可以是空、链表或红黑树。

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;}
}

Node 是 HashMap 的一个内部静态类，它实现了 Map.Entry<K,V> 接口，存储了键、值、哈希值以及指向下一个节点的引用。

链表 (Node.next)

当桶内有哈希冲突时，节点以链表形式连接。

红黑树 (TreeNode)

当链表长度超过阈值（默认 8），会转为红黑树，以降低搜索时间复杂度 O(n) → O(log n)。

TreeNode 是 Node 的子类，增加了红黑树相关的属性（如父节点、左右子节点、颜色）。

二、核心字段

transient Node<K,V>[] table;   // 哈希桶数组
transient int size;            // 当前存储的键值对数量
int threshold;                 // 扩容阈值 = 容量 * 负载因子
final float loadFactor;        // 负载因子，默认 0.75

• 初始容量：默认 16，必须是 2 的幂次方（用于快速取模）。
• 负载因子：控制空间利用率与冲突率的平衡。
• 扩容阈值：当 size > threshold 触发扩容（resize）。

三、hash 计算与索引

HashMap 的核心在于如何根据键的哈希值找到其在数组中的位置。

源码：

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

高位参与运算：通过右移 16 位异或，减少哈希冲突。

是不是有疑问，为什么要无符号右移 16 位，使高两位参与运算？

因为 HashMap 的数组索引是通过 (n - 1) & hash 来计算的，其中 n 是数组的长度。如果哈希值的高位变化不大，而低位经常相同，那么不同的哈希值经过 & (n - 1) 运算后可能会得到相同的索引，导致哈希冲突。通过高位异或低位，可以将哈希值的高位也参与到索引的计算中，从而减少哈希冲突的概率，使得元素在数组中分布更加均匀。

h ^ (h >>> 16) 把高位“混合”进低位

可能有人还不是很理解，没错，这个人就是我：）下面继续分析：

只用低位 → 容易冲突！

• HashMap 容量 n = 16 → (n-1) = 15 = 0b1111（4 个 1）
• 那么 index = hash & 15 → 只看 hash 的低 4 位

如果 key.hashCode() 的分布不好，比如：

• key1.hashCode() = 0b...0000_1000（8）
• key2.hashCode() = 0b...0001_1000（24）
• key3.hashCode() = 0b...0010_1000（40）

它们的低 4 位都是 1000 → 所以 index = 8，全冲突！

即使高位完全不同，也无法影响索引！

举个栗子：

假设两个 key：

• key1.hashCode() = 0b 0100_0000_0000_0000_1000（十进制 16392）
• key2.hashCode() = 0b 1100_0000_0000_0000_1000（十进制 49160）

它们的低 4 位都是 1000，如果直接用，index = 8，冲突！

对 key1：h ^ (h>>>16) = 0b 0100\_0000\_0000\_0000\_1100 ← 扰动后 hash

hash     = 0b ...1100
& 15     = 0b ...1111----------
index    = 0b     1100 = 12

对 key2：h ^ (h>>>16) = 0b 1100\_0000\_0000\_0000\_0100 ← 扰动后 hash

hash     = 0b ...0100
& 15     = 0b ...1111----------
index    = 0b     0100 = 4

结果：key1 → index=12，key2 → index=4，不再冲突！

这就是 HashMap 设计的精妙之处：用一个简单的异或操作，极大提升了性能和健壮性。

索引计算：

int index = (table.length - 1) & hash; // 等同于 hash % table.length

由于 HashMap 的数组长度始终是 2 的幂次方，所以 (table.length - 1) 的二进制表示将全部是 1（例如，如果长度为 16，16-1 就是 15，二进制为 0...01111）。这种 & 运算实际上等同于取模运算 hash % table.length，但位运算效率更高，但 hash % table.length更容易理解😃。

四、put() 流程

主要方法：putVal(hash, key, value, false, true)

源码：

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;// 如果 table 为空或长度为 0，则进行扩容（初始化）if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 计算索引，如果该位置没有元素，则直接创建新节点if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;// 如果头节点的键与要插入的键相同（哈希值和equals都相同）if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p; // 找到相同的键，e 指向该节点// 如果是红黑树节点else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 如果是链表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 1sttreeifyBin(tab, hash);break;}// 如果链表中有键相同的节点if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}// 如果找到了相同的键，则进行值覆盖if (e != null) {V oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e); // 钩子方法return oldValue;}}++modCount; // 结构性修改次数加1// 增加 size，如果超过阈值则扩容if (++size > threshold)resize();afterNodeInsertion(evict); // 钩子方法return null;
}

1. 计算哈希值和索引
2. 检查数组位置是否为空：如果 table[i] 为空，说明该位置没有元素，直接创建一个新的 Node 并放入该位置。
3. 处理哈希冲突：如果 table[i] 不为空，说明发生了哈希冲突，需要进一步处理：

• 检查头节点：如果 table[i] 的键与当前要插入的键相等（key.equals(node.key)）且哈希值也相等，则直接覆盖旧值，并返回旧值。
• 遍历链表/红黑树：

• 如果是红黑树：调用红黑树的插入方法 putTreeVal() 进行插入。红黑树会保证节点的有序性。
• 如果是链表：遍历链表，直到找到尾部或者找到键相等的节点。

• 键相等：如果遍历过程中发现有与当前键相等的节点，则覆盖旧值，并返回旧值。
• 遍历到链表尾部：在链表尾部添加新的 Node。
• 判断是否需要树化：在添加新节点后，检查当前链表的长度是否达到 TREEIFY_THRESHOLD (默认为 8)。如果达到，并且数组容量 MIN_TREEIFY_CAPACITY (默认为 64) 足够大，则将链表转换为红黑树 (treeifyBin() 方法)。如果数组容量较小，会优先进行扩容而不是树化。

4. 增加 size 并检查扩容：每次成功插入一个新元素（不是覆盖），size 都会加 1。然后会检查 size 是否超过 threshold，如果超过，则进行扩容 (resize() 方法)。

五、get() 流程

先定位桶 → 检查首节点 → 遍历链表或树。查找复杂度：O(1) 平均，最坏 O(log n)。

源码：

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; int n; K k;// 如果 table 不为空，并且该索引位置有元素if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {// 检查头节点if (first.hash == hash && // always check first node((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;
}

1. 计算哈希值和索引
2. 检查数组位置：如果 table[i] 为空，则直接返回 null。
3. 遍历链表/红黑树：

• 检查头节点：如果 table[i] 的键与当前要查找的键相等（key.equals(node.key)）且哈希值也相等，则直接返回头节点的值。
• 如果是红黑树：调用红黑树的查找方法 getTreeNode() 进行查找。
• 如果是链表：遍历链表，直到找到键相等的节点，返回其值。如果遍历完链表都没找到，则返回 null。

六、 扩容机制（resize）

当 HashMap 中的元素数量 (size) 超过 threshold 时，会触发 resize() 方法进行扩容。

源码：

final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;// ... 计算 newCap 和 newThr ...Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab; // 更新 tableif (oldTab != null) {for (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) {oldTab[j] = null; // 释放原引用if (e.next == null) // 如果该桶只有一个节点newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode) // 如果是红黑树((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // 链表Node<K,V> loHead = null, loTail = null; // 低位链表Node<K,V> hiHead = null, hiTail = null; // 高位链表Node<K,V> next;do {next = e.next;// 通过 e.hash & oldCap == 0 判断节点是去原位置还是新位置if ((e.hash & oldCap) == 0) { // 去原位置if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else { // 去新位置 (j + oldCap)if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loHead != null)newTab[j] = loHead; // 将低位链表放入原位置if (hiHead != null)newTab[j + oldCap] = hiHead; // 将高位链表放入新位置}}}}return newTab;
}

1. 创建新数组：创建一个新的 Node 数组，其容量是原数组的两倍。
2. 数据迁移：遍历原数组中的每个桶（bucket），将桶中的所有元素（链表或红黑树）重新计算哈希值和索引，然后放入新数组的相应位置。

• rehash：由于数组长度发生变化，原来计算索引的方式 (oldCap - 1) & hash 会失效，需要根据新的数组长度 (newCap - 1) & hash 重新计算索引。
• 链表优化：在 JDK 1.8 中，链表在扩容时进行了优化。对于链表中的每个节点，其在新数组中的位置只有两种可能：原位置 i 或 i + oldCap。这是因为 newCap 是 oldCap 的两倍，并且都是 2 的幂。通过判断 (e.hash & oldCap) == 0，可以将链表中的节点分为两部分：一部分保留在原索引位置，另一部分移动到 原索引 + oldCap 的位置，从而避免了对每个节点都进行复杂的重新哈希和遍历操作。
• 红黑树优化：红黑树的节点也会进行拆分，生成新的红黑树或退化为链表。

七、树化与退化

树化 (treeifyBin(Node<K,V>[] tab, int hash))：

• 当链表长度达到 TREEIFY_THRESHOLD（默认为 8）时，并且数组容量达到 MIN_TREEIFY_CAPACITY（默认为 64）时，会将链表转换为红黑树。
• 如果数组容量小于 MIN_TREEIFY_CAPACITY，则会优先进行扩容 (resize()) 而不是树化（防止小容量下频繁树化），因为扩容后，链表中的元素可能会分散到新的桶中，从而减少单个链表的长度。

退化 (untreeify(Node<K,V> node))：

• 在 remove() 或 resize() 方法中，当红黑树的节点数量减少到 UNTREEIFY_THRESHOLD（默认为 6）时，红黑树会退化为链表。

八、总结

JDK 1.8 对 HashMap 的优化主要体现在以下几个方面：

• 数组 + 链表 + 红黑树：有效解决了哈希冲突严重时链表过长导致查询效率下降的问题，将最坏情况下的时间复杂度从 O(n) 降低到 O(logn)。
• 改进的哈希算法：hash(Object key) 方法通过高位异或低位，使得哈希值的高位也能参与到索引计算中，降低了哈希冲突的概率，使得元素分布更均匀。
• 扩容优化：在 resize() 过程中，链表元素的重新定位变得更加高效，避免了每个元素的重新哈希计算。
• 懒初始化：table 数组在第一次 put 操作时才进行初始化，节省了内存空间。

九、适用场景与注意事项

HashMap 适用于需要快速查找、插入和删除键值对的场景。

注意事项：

• 键的 hashCode() 和 equals() 方法：作为键的对象必须正确重写 hashCode() 和 equals() 方法。hashCode() 相同的对象，equals() 也必须为 true。如果违反这个约定，HashMap 可能会出现不正确的行为，导致相同的键存储了多个值，或者无法找到已存储的值。
• 线程不安全：HashMap 是非线程安全的。在多线程环境下，如果存在并发修改操作，可能会导致数据不一致或死循环。在并发场景下，应使用 ConcurrentHashMap。
• 初始容量和负载因子：合理设置初始容量和负载因子可以减少扩容次数，提高性能。如果预估 HashMap 会存储大量元素，可以设置一个较大的初始容量。