HashMap put原理详解（基于JDK 1.8）

HashMap put原理详解（基于JDK 1.8）

HashMap是Java中最常用的数据结构之一，它基于哈希表实现，提供了高效的键值对存储和检索功能。在JDK 1.8中，HashMap的实现经过了一些优化，包括链表转红黑树等。本文将详细解析HashMap的put方法实现原理，帮助读者深入理解HashMap的工作原理。

一、哈希计算

HashMap的put方法首先会对键进行哈希计算，得到一个哈希码。哈希码的计算是通过键的hashCode方法实现的，该方法由键的类实现。HashMap通过哈希码计算得到在数组中的索引位置，公式为：index = hash & (capacity - 1)。其中，hash是键的哈希码，capacity是数组容量，&是按位与运算符。通过这个公式，可以快速找到键值对在数组中的存储位置。

二、扩容

当HashMap中的元素数量达到数组容量的一定比例（默认为0.75）时，需要对HashMap进行扩容。扩容的过程是创建一个新的数组，其容量是原数组容量的两倍，并将原数组中的元素重新哈希并放入新数组中。扩容操作是一个耗时的操作，因为它涉及到大量元素的重新哈希和复制。因此，在设计HashMap时，合理的初始容量和加载因子可以有效减少扩容操作的次数，提高性能。

三、链表转红黑树

在JDK 1.8中，HashMap对链表进行了优化，当链表长度达到一定阈值（默认为8）时，会将链表转换为红黑树。红黑树是一种自平衡的二叉搜索树，具有较高的查找效率。将链表转换为红黑树可以有效提高HashMap在元素数量较多时的查找性能。需要注意的是，当链表长度小于6时，会将红黑树转换回链表，以节省空间。

四、put方法实现

现在，我们来看HashMap的put方法的具体实现。首先，对键进行哈希计算，得到在数组中的索引位置。然后，检查该索引位置是否已经有元素存在。如果存在，说明有哈希冲突，需要进行处理。处理哈希冲突的方法有两种：一是链地址法，即将具有相同哈希码的元素放入一个链表中；二是开放地址法，通过一定的探测策略找到其他可用的存储位置。HashMap采用了链地址法来解决哈希冲突。

在链表中，从头节点开始遍历，如果找到相同的键，则更新其值并返回旧值。如果遍历到链表末尾仍未找到相同键，则在链表末尾插入新的键值对。插入后，检查链表长度是否达到阈值，如果达到则转换为红黑树。

如果索引位置没有元素存在，则直接在该位置创建一个新的节点，存储键值对。插入后，检查HashMap中的元素数量是否达到扩容阈值，如果达到则进行扩容。

五、总结

本文详细解析了JDK 1.8中HashMap的put方法实现原理，包括哈希计算、扩容、链表转红黑树等关键步骤。通过深入理解HashMap的工作原理，我们可以更好地应用它来解决实际问题。在实际应用中，我们需要根据具体情况选择合适的初始容量和加载因子，以提高HashMap的性能。

六、参考代码

以下是HashMap的put方法的简化版实现代码，供读者参考：

```java
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

modCount++;
addEntry(hash, key, value, i);
return null;

}

void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);