java中HashMap当插入位置不为空的时候JDK是怎么处理

发布时间：2021-11-24 17:36:58 作者：小新
来源：亿速云阅读：211

Java中HashMap当插入位置不为空的时候JDK是怎么处理

在Java中，HashMap是一种非常常用的数据结构，它基于哈希表实现，允许存储键值对，并且提供了快速的查找、插入和删除操作。HashMap的核心思想是通过哈希函数将键映射到数组的某个位置，然后在该位置存储对应的值。然而，由于哈希函数的性质，不同的键可能会被映射到同一个位置，这种情况称为哈希冲突。本文将详细探讨在Java中，当插入位置不为空时，JDK是如何处理这种情况的。

1. HashMap的基本结构

在深入讨论如何处理插入位置不为空的情况之前，我们首先需要了解HashMap的基本结构。

HashMap内部维护了一个数组，数组的每个元素是一个Node对象（在JDK 8之前是Entry对象），Node对象包含了键、值以及指向下一个Node的指针（用于处理哈希冲突）。这个数组通常被称为桶数组（bucket array），数组的每个位置被称为桶（bucket）。

transient Node<K,V>[] table;

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

    // 其他方法省略
}

2. 插入操作的基本流程

当我们向HashMap中插入一个键值对时，HashMap会执行以下步骤：

计算哈希值：首先，HashMap会通过键的hashCode()方法计算出一个哈希值。
确定桶的位置：通过哈希值与数组长度取模运算，确定键值对应该存储在数组的哪个位置。
插入键值对：如果该位置为空，则直接插入；如果该位置不为空，则需要处理哈希冲突。

3. 处理插入位置不为空的情况

当插入位置不为空时，意味着该位置已经存在一个或多个Node对象。此时，HashMap需要处理哈希冲突。JDK 8之前和JDK 8及之后的版本在处理哈希冲突时有所不同。

3.1 JDK 8之前的处理方式

在JDK 8之前，HashMap采用链表法来处理哈希冲突。具体步骤如下：

遍历链表：从该位置的第一个Node开始，遍历链表，检查是否有Node的键与待插入的键相同。
更新值：如果找到相同的键，则更新该Node的值。
插入新节点：如果没有找到相同的键，则在链表的末尾插入一个新的Node。

for (Entry<K,V> 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;
        return oldValue;
    }
}

3.2 JDK 8及之后的处理方式

在JDK 8及之后的版本中，HashMap在处理哈希冲突时引入了红黑树的概念。当链表长度超过一定阈值（默认为8）时，链表会转换为红黑树，以提高查找效率。具体步骤如下：

遍历链表或红黑树：从该位置的第一个Node开始，遍历链表或红黑树，检查是否有Node的键与待插入的键相同。
更新值：如果找到相同的键，则更新该Node的值。
插入新节点：如果没有找到相同的键，则在链表或红黑树中插入一个新的Node。
链表转红黑树：如果链表长度超过阈值（默认为8），则将链表转换为红黑树。

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

3.3 红黑树的优势

红黑树是一种自平衡的二叉查找树，它的查找、插入和删除操作的时间复杂度为O(log n)。相比于链表，红黑树在处理大量数据时具有更高的效率。因此，当链表长度超过一定阈值时，HashMap会将链表转换为红黑树，以提高性能。

4. 总结

在Java中，HashMap通过哈希表实现快速的键值对存储和查找。当插入位置不为空时，HashMap会根据JDK版本的不同，采用链表法或红黑树法来处理哈希冲突。JDK 8之前的版本使用链表法，而JDK 8及之后的版本在链表长度超过阈值时，会将链表转换为红黑树，以提高查找效率。

通过这种方式，HashMap能够在大多数情况下保持较高的性能，即使在哈希冲突较多的情况下，也能通过红黑树来保证操作的效率。