欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java HashMap的put方法

程序员文章站 2022-03-10 18:37:38
...

实习半年,基本上在写scala和python。很少碰Java了,趁最近闲,补一波Java集合的东西。这篇主要分析HashMap的插入方法。之后再抽时间看下红黑树。

可能出现的几种插入情况:

1、初次插入。

Java HashMap的put方法

2、插入与任何结点不产生地址冲突。

Java HashMap的put方法

3、产生地址冲突,table数组下面结点以单链表形式存在,插入时直接挂在单链表最后。

Java HashMap的put方法

4、产生地址冲突,key值和之前结点一样。

Java HashMap的put方法

5、产生地址冲突,table数组下面结点以红黑树形式存在,插入时需要在树中查找合适位置。

Java HashMap的put方法

下面是对代码的分析:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; 
        Node<K,V> p; 
        int n, i;
        // 如果table为空,表明是第一元素插入,则先resize。初次大小默认16。
        if ((tab = table) == null || (n = tab.length) == 0)		
            n = (tab = resize()).length;
        // 如果要插入结点的位置是空,也就是没有产生Hash地址冲突,直接放入table。
        if ((p = tab[i = (n - 1) & hash]) == null)		
            tab[i] = newNode(hash, key, value, null);
        else {				// 如果产生了冲突,那么有两种情况。1、key相同。2、key不同。
            Node<K,V> e; K k;
    // 要插入的结点key值和table现有位置上的结点的key值相同,则直接赋值e。p为当前位置上的元素,e为需要被修改的元素。
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
            	// 如果p是TreeNode的实例,说明p下面挂着红黑树,需要在树中找到一个合适的位置e插入。
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {	// p下面的结点数未超过8,则以单向链表的形式存在。
                    if ((e = p.next) == null) {			// 逐个往下找到空位置
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st	-1 0 1 2 3 4 5 6
                            treeifyBin(tab, hash);	// TREEIFY_THRESHOLD=8,当容量超过8则转化成红黑树
                        break;
                    }
                    // 如果与单向链表上的某个结点key值相同,则跳出循环,此时e是需要修改的结点,p是e的前驱结点。
                    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;
                // 如果onlyIfAbsent为True则不改变旧值。如果插入中遇见key一样的结点,则保留第一次插入的结果。
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;		// 修改次数++
        // 如果插入后大小大于threshold,则出发resize
        if (++size > threshold)	
            resize();
        afterNodeInsertion(evict);
        return null;
    }