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

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

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会执行以下步骤:

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

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

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

3.1 JDK 8之前的处理方式

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

  1. 遍历链表:从该位置的第一个Node开始,遍历链表,检查是否有Node的键与待插入的键相同。
  2. 更新值:如果找到相同的键,则更新该Node的值。
  3. 插入新节点:如果没有找到相同的键,则在链表的末尾插入一个新的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)时,链表会转换为红黑树,以提高查找效率。具体步骤如下:

  1. 遍历链表或红黑树:从该位置的第一个Node开始,遍历链表或红黑树,检查是否有Node的键与待插入的键相同。
  2. 更新值:如果找到相同的键,则更新该Node的值。
  3. 插入新节点:如果没有找到相同的键,则在链表或红黑树中插入一个新的Node
  4. 链表转红黑树:如果链表长度超过阈值(默认为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能够在大多数情况下保持较高的性能,即使在哈希冲突较多的情况下,也能通过红黑树来保证操作的效率。

推荐阅读:
  1. php如何实现判断不为空的方法
  2. jdk是java的什么

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

jdk java hashmap

上一篇:如何理解集成测试工具Tessy

下一篇:5个重要的CCNP协议分别是什么

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》