java中HashMap解析put的过程是什么

发布时间：2023-05-06 11:42:22 作者：iii
来源：亿速云阅读：202

Java中HashMap解析put的过程是什么

在Java中，HashMap是一个非常常用的数据结构，它基于哈希表实现，提供了快速的查找、插入和删除操作。HashMap的核心操作之一是put方法，它用于将键值对插入到哈希表中。本文将详细解析HashMap中put方法的实现过程，帮助读者深入理解其工作原理。

1. HashMap的基本结构

在深入探讨put方法之前，我们需要先了解HashMap的基本结构。HashMap内部主要由以下几个部分组成：

数组（table）：HashMap的核心数据结构是一个数组，数组中的每个元素称为“桶”（bucket），每个桶可以存储一个链表或红黑树。数组的长度通常是2的幂次方，这是为了优化哈希计算。
链表（Node）：当多个键值对的哈希值相同（即发生哈希冲突）时，这些键值对会被存储在同一个桶中，形成一个链表。链表的每个节点是一个Node对象，包含键、值、哈希值以及指向下一个节点的引用。
红黑树（TreeNode）：当链表长度超过一定阈值（默认为8）时，链表会转换为红黑树，以提高查找效率。

2. put方法的整体流程

put方法的主要作用是将键值对插入到HashMap中。其整体流程可以分为以下几个步骤：

计算键的哈希值：首先，HashMap会根据键的hashCode方法计算出一个哈希值。
确定桶的位置：根据哈希值和数组长度，计算出键值对应该存储在哪个桶中。
处理哈希冲突：如果该桶中已经有元素，则需要处理哈希冲突，通常是通过链表或红黑树来解决。
插入键值对：将键值对插入到相应的桶中。
扩容检查：如果插入后HashMap的大小超过了阈值，则需要进行扩容操作。

接下来，我们将逐步解析这些步骤。

3. 计算键的哈希值

HashMap在插入键值对时，首先会调用键的hashCode方法来计算哈希值。然而，直接使用hashCode可能会导致哈希冲突较多，因此HashMap会对hashCode进行进一步处理，以减少冲突。

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

在这个方法中，HashMap将hashCode的高16位与低16位进行异或运算，这样可以使得哈希值的高位信息也参与到哈希计算中，从而减少哈希冲突。

4. 确定桶的位置

计算出哈希值后，HashMap需要确定键值对应该存储在数组中的哪个桶中。这个位置是通过哈希值与数组长度进行取模运算得到的。

int index = (n - 1) & hash;

其中，n是数组的长度，hash是计算出的哈希值。由于n是2的幂次方，n-1的二进制表示是一个全1的数，因此(n-1) & hash相当于hash % n，但效率更高。

5. 处理哈希冲突

如果计算出的桶位置已经有元素存在，则说明发生了哈希冲突。HashMap通过链表或红黑树来解决哈希冲突。

5.1 链表处理

如果桶中的元素较少（默认小于8个），则HashMap会使用链表来存储这些元素。链表的每个节点是一个Node对象，包含键、值、哈希值以及指向下一个节点的引用。

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) // -1 for 1st
                    treeifyBin(tab, hash);
                break;
            }
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                break;
            p = e;
        }
    }
    if (e != null) { // existing mapping for key
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
            e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
}

在这个代码片段中，HashMap首先检查桶中的第一个节点是否与要插入的键相同。如果相同，则直接更新值。如果不相同，则遍历链表，直到找到相同的键或到达链表末尾。如果到达链表末尾，则将新节点插入到链表末尾。

5.2 红黑树处理

如果链表长度超过一定阈值（默认为8），则HashMap会将链表转换为红黑树，以提高查找效率。红黑树的插入操作与链表类似，但查找效率更高。

else if (p instanceof TreeNode)
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

在这个代码片段中，HashMap会调用putTreeVal方法将键值对插入到红黑树中。

6. 插入键值对

在确定桶的位置并处理完哈希冲突后，HashMap会将键值对插入到相应的桶中。如果桶中已经有相同的键存在，则更新其值。

if (e != null) { // existing mapping for key
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    afterNodeAccess(e);
    return oldValue;
}

在这个代码片段中，HashMap会检查是否存在相同的键。如果存在，则更新其值，并返回旧值。

7. 扩容检查

在插入键值对后，HashMap会检查当前大小是否超过了阈值。如果超过了阈值，则需要进行扩容操作。

if (++size > threshold)
    resize();

resize方法会将数组的长度扩大为原来的两倍，并重新计算每个键值对的存储位置。

8. 总结

HashMap的put方法是一个复杂但高效的操作，它通过哈希计算、链表或红黑树处理哈希冲突、以及动态扩容等机制，确保了HashMap的高效性。理解put方法的实现过程，有助于我们更好地使用HashMap，并在需要时进行性能优化。

通过本文的解析，相信读者对HashMap中put方法的实现有了更深入的理解。在实际开发中，合理使用HashMap可以大大提高程序的性能。