深入理解HashMap(五): 关键源码逐行分析之put

APICloud 发布于2019-08-19 10:51 / 1184人阅读

摘要：当链表长度超过默认是个时，会将链表转换成红黑树以提升查找性能。

前言

系列文章目录

上一篇我们讨论了HashMap的扩容操作, 提到扩容操作发生在table的初始化或者table大小超过threshold后，而这两个条件的触发基本上就发生在put操作中。

本篇我们就来聊聊HashMap的put操作。

本文的源码基于 jdk8 版本.

put方法

HashMap 实现了Map接口, 因此必须要实现put方法:

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
    /*final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) */
}

可以看到, put方法是有返回值的, 这里调用了 putVal 方法, 这个方法很重要, 我们将通过代码注释的方式逐行说明.

在这之前我们先看该方法的参数:

hash

由上面的调用可知, 该值为hash(key), 是key的hash值, 关于hash的概念之前已经讲过了, 这里不再赘述.

key, value

待存储的键值对

onlyIfAbsent

这个参数用于决定待存储的key已经存在的情况下,要不要用新值覆盖原有的value, 如果为true, 则保留原有值, false 则覆盖原有值, 从上面的调用看, 该值为false, 说明当key值已经存在时, 会直接覆盖原有值。

evict

该参数用来区分当前是否是构造模式, 我们在讲解构造函数的时候曾经提到，HashMap的第四个构造函数可以通过已经存在的Map初始化一个HashMap, 如果为 false, 说明在构造模式下, 这里我们是用在put函数而不是构造函数里面, 所以为true。

参数解释完了之后, 下面我们来逐行看代码:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node[] tab; Node p; int n, i;
    
    // 首先判断table是否是空的
    // 我们知道, HashMap的三个构造函数中, 都不会初始Table, 因此第一次put值时, table一定是空的, 需要初始化
    // table的初始化用到了resize函数, 这个我们上一篇文章已经讲过了
    // 由此可见table的初始化是延迟到put操作中的
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
        
    // 这里利用 `(n-1) & hash` 方法计算 key 所对应的下标
    // 如果key所对应的桶里面没有值, 我们就新建一个Node放入桶里面
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    
    // 到这里说明目标位置桶里已经有东西了
    else {
        Node e; K k;
        // 这里先判断当前待存储的key值和已经存在的key值是否相等
        // key值相等必须满足两个条件
        //    1. hash值相同
        //    2. 两者 `==` 或者 `equals` 等
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; // key已经存在的情况下, e保存原有的键值对
        
        // 到这里说明要保存的桶已经被占用, 且被占用的位置存放的key与待存储的key值不一致
        
        // 前面已经说过, 当链表长度超过8时, 会用红黑树存储, 这里就是判断存储桶中放的是链表还是红黑树
        else if (p instanceof TreeNode)
            // 红黑树的部分以后有机会再说吧
            e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
        
        //到这里说明是链表存储, 我们需要顺序遍历链表
        else {
            for (int binCount = 0; ; ++binCount) {
                // 如果已经找到了链表的尾节点了,还没有找到目标key, 则说明目标key不存在，那我们就新建一个节点, 把它接在尾节点的后面
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 如果链表的长度达到了8个, 就将链表转换成红黑数以提升查找性能
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果在链表中找到了目标key则直接退出
                // 退出时e保存的是目标key的键值对
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        
        // 到这里说明要么待存储的key存在, e保存已经存在的值
        // 要么待存储的key不存在, 则已经新建了Node将key值插入, e的值为Null
        
        // 如果待存储的key值已经存在
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            
            // 前面已经解释过, onlyIfAbsent的意思
            // 这里是说旧值存在或者旧值为null的情况下, 用新值覆盖旧值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e); //这个函数只在LinkedHashMap中用到, 这里是空函数
            // 返回旧值
            return oldValue;
        }
    }
    
    // 到这里说明table中不存在待存储的key, 并且我们已经将新的key插入进数组了
    
    ++modCount; // 这个暂时用不到
    
    // 因为又插入了新值, 所以我们得把数组大小加1, 并判断是否需要重新扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict); //这个函数只在LinkedHashMap中用到, 这里是空函数
    return null;
}

总结

在put之前会检查table是否为空，说明table真正的初始化并不是发生在构造函数中，而是发生在第一次put的时候。

查找当前key是否存在的条件是p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))

如果插入的key值不存在，则值会插入到链表的末尾。

每次插入操作结束后，都会检查当前table节点数是否大于threshold, 若超过，则扩容。

当链表长度超过TREEIFY_THRESHOLD（默认是8）个时，会将链表转换成红黑树以提升查找性能。

(完)

查看更多系列文章：系列文章目录

混合云专线服务深入理解webrtc之aec 深入理解系列深入理解linux 深入理解webrtc

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/76560.html

系列文章目录

摘要：为了避免一篇文章的篇幅过长，于是一些比较大的主题就都分成几篇来讲了，这篇文章是笔者所有文章的目录，将会持续更新，以给大家一个查看系列文章的入口。前言大家好，笔者是今年才开始写博客的，写作的初衷主要是想记录和分享自己的学习经历。因为写作的时候发现，为了弄懂一个知识，不得不先去了解另外一些知识，这样以来，为了说明一个问题，就要把一系列知识都了解一遍，写出来的文章就特别长。为了避免一篇...

lijy91 2019-06-28 16:36 评论0 收藏0
系列文章目录

摘要：为了避免一篇文章的篇幅过长，于是一些比较大的主题就都分成几篇来讲了，这篇文章是笔者所有文章的目录，将会持续更新，以给大家一个查看系列文章的入口。前言大家好，笔者是今年才开始写博客的，写作的初衷主要是想记录和分享自己的学习经历。因为写作的时候发现，为了弄懂一个知识，不得不先去了解另外一些知识，这样以来，为了说明一个问题，就要把一系列知识都了解一遍，写出来的文章就特别长。为了避免一篇...

Yumenokanata 2019-08-19 10:58 评论0 收藏0
深入理解HashMap(四): 关键源码逐行分析之resize扩容

摘要：前言系列文章目录上一篇我们说明了的构造函数谈到构造函数中并不会初始化变量变量是在过程中初始化的本篇我们就来聊聊的扩容本文的源码基于版本用于以下两种情况之一初始化在大小超过之后进行扩容下面我们直接来对照源码分析原中已经有值已经超过最大限制不再前言系列文章目录上一篇我们说明了HashMap的构造函数, 谈到构造函数中并不会初始化table 变量, table 变量是在 resize过...

aristark 2019-08-19 10:50 评论0 收藏0
深入理解HashMap(二): 关键源码逐行分析之hash算法

摘要：散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值，，，或的指纹。前言系列文章目录前面我们讨论了HashMap的结构, 接下来几篇我们从源码角度来看HashMap的实现细节. 本篇我们就来聊聊HashMap的hash算法本文的源码基于 jdk8 版本. hash算法上一篇文章我们提到, 为了利用数组索引进行快速查...

chunquedong 2019-08-19 10:50 评论0 收藏0
深入理解HashMap(三): 关键源码逐行分析之构造函数

摘要：前言系列文章目录上一篇我们说明了的算法说到在构造时会自动将设为的整数次幂本篇我们就来聊聊的构造函数本文的源码基于版本构造函数共有四个构造函数默认初始大小默认负载因子没有指定时使用默认值即默认初始大小默认负载因子指定初始大小但使用默认负载因子前言系列文章目录上一篇我们说明了HashMap的hash算法, 说到HashMap在构造时会自动将table设为2的整数次幂. 本篇我们就来聊...

QiuyueZhong 2019-08-19 10:50 评论0 收藏0