Java HashMap 原理的全面解读
Java HashMap 基础概念
在 Java 集合框架中，HashMap 是一个非常重要且常用的类。它用于存储键值对（key - value pairs），并且允许使用 null 键和 null 值。HashMap 基于哈希表实现，提供了快速的查找、插入和删除操作。
从本质上讲，HashMap 是一个数组和链表（在 Java 8 及之后版本，链表在长度达到一定阈值后会转换为红黑树）的结合体。数组的每个元素称为一个桶（bucket），每个桶中可以存放一个链表或者红黑树。当我们向 HashMap 中插入一个键值对时，会根据键的哈希值计算出应该存储在哪个桶中。如果该桶为空，就直接将键值对放入该桶；如果该桶不为空，说明发生了哈希冲突，此时会将键值对以链表（或红黑树）的形式连接到该桶上。
数据结构
数组
HashMap 内部使用一个数组来存储桶。这个数组在 HashMap 类中被定义为 Node<K, V>[] table，其中 Node 是一个静态内部类，用于表示键值对节点。数组的长度在 HashMap 初始化时确定，并且会根据元素数量的增长动态调整。
链表
当多个键值对通过哈希计算后映射到同一个桶时，就会发生哈希冲突。在 Java 8 之前，HashMap 通过链表来解决哈希冲突，将冲突的键值对以链表的形式存储在同一个桶中。链表的每个节点就是 Node 类的实例，它包含了键（key）、值（value）、下一个节点的引用（next）以及哈希值（hash）。
红黑树
在 Java 8 中，为了提高在哈希冲突严重情况下的查找效率，当链表的长度达到一定阈值（默认为 8）时，链表会转换为红黑树。红黑树是一种自平衡的二叉查找树，它保证了在最坏情况下，树的高度为 O(log n)，从而提高了查找、插入和删除操作的效率。HashMap 中红黑树的节点由 TreeNode 类表示，它继承自 Node 类，并增加了红黑树相关的属性和方法。
构造函数
HashMap 提供了多个构造函数，以满足不同的使用场景。
默认构造函数
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
这个构造函数使用默认的初始容量（16）和负载因子（0.75）来初始化 HashMap。默认初始容量是 2 的幂次方，这样可以在哈希计算时利用位运算提高效率。负载因子表示在 HashMap 自动扩容之前可以达到的填满程度。
带初始容量的构造函数
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
这个构造函数接受一个初始容量参数，并使用默认的负载因子。需要注意的是，传入的初始容量不一定就是最终 HashMap 的容量，HashMap 会将其调整为大于等于该值的最小的 2 的幂次方。
带初始容量和负载因子的构造函数
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
这个构造函数允许用户指定初始容量和负载因子。在构造函数中，会对传入的参数进行合法性检查，并根据初始容量计算出阈值（threshold）。阈值是 HashMap 进行扩容的临界值，当 HashMap 中的元素数量达到阈值时，就会触发扩容操作。tableSizeFor 方法用于计算大于等于传入参数的最小的 2 的幂次方。
带另一个 Map 的构造函数
public HashMap(Map<? extends K,? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
这个构造函数接受一个 Map 类型的参数，并将其所有的键值对复制到新创建的 HashMap 中。在复制过程中，会根据传入 Map 的大小来确定合适的初始容量，并使用默认的负载因子。
哈希算法
哈希算法在 HashMap 中起着至关重要的作用，它决定了键值对在数组中的存储位置。HashMap 的哈希算法主要涉及两个步骤：计算哈希值和确定桶的索引。
计算哈希值
在 Java 8 中，HashMap 对键的哈希值计算进行了优化。首先，调用键的 hashCode() 方法获取哈希码，然后对哈希码进行扰动处理，以减少哈希冲突的发生。扰动处理的代码如下：
static final int hash(Object key) {
int h;
return (key == null)? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这里，如果键为 null，则直接返回 0。否则，获取键的哈希码 h，并将其与 h 无符号右移 16 位的结果进行异或运算。这样做的目的是让高位和低位都参与到哈希计算中，从而使哈希值更加分散，减少哈希冲突。
确定桶的索引
计算出哈希值后，需要根据哈希值确定键值对应该存储在数组的哪个桶中。HashMap 使用取模运算来确定桶的索引，但为了提高效率，实际采用的是位与运算。假设数组的长度为 n，则桶的索引计算公式为：
(n - 1) & hash
由于 HashMap 的数组长度始终是 2 的幂次方，所以 n - 1 的二进制表示是全 1 的形式。这样，位与运算 (n - 1) & hash 就相当于对 hash 取模 n，并且位与运算比取模运算效率更高。
核心方法
put 方法
put 方法用于向 HashMap 中插入一个键值对。其实现逻辑如下：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
put 方法首先调用 hash 方法计算键的哈希值，然后调用 putVal 方法进行实际的插入操作。putVal 方法的实现如下：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
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;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
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)
treeifyBin(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;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
- 检查数组是否为空或长度为 0：如果是，则调用
resize方法进行扩容。 - 计算桶的索引：根据哈希值计算键值对应该存储的桶的索引。
- 检查桶是否为空：如果桶为空，则直接在该桶创建一个新的
Node节点。 - 处理哈希冲突：如果桶不为空，说明发生了哈希冲突。
- 检查是否为相同键：如果桶中的第一个节点的键与要插入的键相同，则直接更新其值。
- 检查是否为红黑树节点：如果桶中的第一个节点是红黑树节点，则调用红黑树的
putTreeVal方法进行插入操作。 - 处理链表情况：如果是链表节点，则遍历链表，找到合适的位置插入新节点。如果链表长度达到阈值（默认为 8），则将链表转换为红黑树。
- 更新值并返回旧值：如果找到相同键的节点，则更新其值，并返回旧值。
- 检查是否需要扩容：插入新节点后，检查
HashMap的大小是否超过阈值，如果超过，则调用resize方法进行扩容。
get 方法
get 方法用于根据键获取对应的值。其实现逻辑如下：
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null? null : e.value;
}
get 方法首先调用 hash 方法计算键的哈希值，然后调用 getNode 方法查找对应的节点。getNode 方法的实现如下：
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;
}
- 检查数组和桶是否为空：如果数组不为空且对应桶不为空，则继续查找。
- 检查桶中的第一个节点：如果第一个节点的键与要查找的键相同，则直接返回该节点。
- 处理哈希冲突：如果第一个节点不是要查找的节点，且存在下一个节点。
- 检查是否为红黑树节点：如果是红黑树节点，则调用红黑树的
getTreeNode方法进行查找。 - 处理链表情况：如果是链表节点，则遍历链表，查找对应的节点。
- 检查是否为红黑树节点：如果是红黑树节点，则调用红黑树的
- 返回结果：如果找到对应的节点，则返回该节点的值；否则，返回
null。
remove 方法
remove 方法用于根据键删除对应的键值对。其实现逻辑如下：
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null?
null : e.value;
}
remove 方法首先调用 hash 方法计算键的哈希值，然后调用 removeNode 方法删除对应的节点。removeNode 方法的实现如下：
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
- 检查数组和桶是否为空：如果数组不为空且对应桶不为空，则继续查找。
- 检查桶中的第一个节点：如果第一个节点的键与要删除的键相同，则直接将该节点作为待删除节点。
- 处理哈希冲突：如果第一个节点不是要删除的节点，且存在下一个节点。
- 检查是否为红黑树节点：如果是红黑树节点，则调用红黑树的
getTreeNode方法查找待删除节点。 - 处理链表情况：如果是链表节点，则遍历链表，查找待删除节点。
- 检查是否为红黑树节点：如果是红黑树节点，则调用红黑树的
- 删除节点：如果找到待删除节点，且满足删除条件（键相同且值匹配或不要求值匹配），则删除该节点。
- 红黑树节点删除：如果是红黑树节点，则调用红黑树的
removeTreeNode方法进行删除操作。 - 链表节点删除：如果是链表节点，则调整链表指针，将待删除节点从链表中移除。
- 红黑树节点删除：如果是红黑树节点，则调用红黑树的
- 更新相关属性：删除节点后，更新
modCount和size，并调用afterNodeRemoval方法进行后续处理。 - 返回结果：返回被删除节点的值；如果未找到匹配的节点，则返回
null。
扩容机制
HashMap 的扩容机制是为了在元素数量增加时，保持哈希表的性能。当 HashMap 中的元素数量达到阈值（threshold）时，就会触发扩容操作。扩容操作包括两个步骤：创建一个新的更大的数组，并将旧数组中的所有键值对重新哈希并插入到新数组中。
扩容方法
resize 方法是 HashMap 进行扩容的核心方法，其实现如下：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null)? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
}
else if (oldThr > 0)
newCap = oldThr;
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (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;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
- 计算新的容量和阈值：
- 旧容量大于 0：如果旧容量已经达到最大容量（
MAXIMUM_CAPACITY），则将阈值设置为Integer.MAX_VALUE，并返回旧数组，不再进行扩容。否则，将新容量设置为旧容量的两倍，并根据情况更新阈值。 - 旧阈值大于 0：将新容量设置为旧阈值。
- 其他情况：使用默认的初始容量和负载因子计算新的容量和阈值。
- 旧容量大于 0：如果旧容量已经达到最大容量（
- 创建新的数组：根据新的容量创建一个新的
Node数组。 - 重新哈希并插入键值对：遍历旧数组，将每个桶中的键值对重新哈希并插入到新数组中。
- 单个节点情况：如果桶中只有一个节点，则直接根据新的容量计算其在新数组中的位置并插入。
- 红黑树情况：如果桶中的节点是红黑树节点，则调用红黑树的
split方法进行处理。 - 链表情况：将链表根据节点哈希值与旧容量的按位与结果分为两个链表，一个链表中的节点哈希值与旧容量按位与结果为 0，另一个链表中的节点哈希值与旧容量按位与结果不为 0。然后将这两个链表分别插入到新数组的不同位置。
线程安全性
需要注意的是，HashMap 是非线程安全的。在多线程环境下使用 HashMap 可能会导致数据不一致或其他问题。例如，在多个线程同时进行插入操作时，可能会导致链表形成环，从而在遍历链表时出现死循环。
如果需要在多线程环境下使用哈希表，可以考虑使用 ConcurrentHashMap。ConcurrentHashMap 是线程安全的哈希表，它通过分段锁等机制来提高并发性能。
示例代码
下面是一个简单的 HashMap 使用示例代码：
import java.util.HashMap;
import java.util.Map;
public class HashMapExample {
public static void main(String[] args) {
// 创建一个 HashMap
Map<String, Integer> hashMap = new HashMap<>();
// 插入键值对
hashMap.put("apple", 10);
hashMap.put("banana", 20);
hashMap.put("cherry", 30);
// 获取值
int value = hashMap.get("apple");
System.out.println("The value of apple is: " + value);
// 删除键值对
hashMap.remove("banana");
// 遍历 HashMap
for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
}
}
在上述代码中，我们首先创建了一个 HashMap，然后向其中插入了三个键值对。接着，通过 get 方法获取了键为 "apple" 的值，并将其打印出来。之后，使用 remove 方法删除了键为 "banana" 的键值对。最后，通过遍历 HashMap 打印出剩余的所有键值对。
通过以上全面的解读，相信你对 Java HashMap 的原理有了深入的了解。在实际应用中，根据具体的需求合理使用 HashMap，可以提高程序的性能和效率。同时，在多线程环境下，要注意选择合适的线程安全的哈希表实现。