【JVM】-NO.113.JVM.1 -【JDK11 HashMap详解-0-全局-put】

Style：Mac

Series：Java

Since：2018-09-10

End：2018-09-10

Total Hours：1

Degree Of Diffculty：5

Degree Of Mastery：5

Practical Level：5

Desired Goal：5

Archieve Goal：3

Gerneral Evaluation：3

Writer:kingdelee

Related Links：

http://www.cnblogs.com/kingdelee/

http://www.runoob.com/java/java-operators.html

1.解析常见的HaspMap操作背后的故事

package jdk11.map;

import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;

public class Client {

    private static final Logger logger = LogManager.getLogger(Client.class);


    public static void main(String[] args) {


        Map<Father, Integer> map = new HashMap<>();
        Father f1 = new Father("f1");
        f1.setHashcode(1);
        Father f2 = new Father("f2");
        f2.setHashcode(1);
        Father f3 = new Father("f3");
        f2.setHashcode(1);
        Father f4 = new Father("f4");
        f2.setHashcode(1);
        Father f5 = new Father("f5");
        f2.setHashcode(1);
        Father f6 = new Father("f6");
        f2.setHashcode(1);
        Father f7 = new Father("f7");
        f2.setHashcode(1);
        Father f8 = new Father("f8");
        f2.setHashcode(1);
        Father f9 = new Father("f9");
        f2.setHashcode(1);

        map.put(f1, 1);
        map.put(f2, 2);
        map.put(f3, 3);
        map.put(f4, 4);
        map.put(f5, 5);
        map.put(f6, 6);
        map.put(f7, 7);
        map.put(f8, 8);
        map.put(f9, 9);
        map.put(new Father("10", 1), 10);
        map.put(new Father("11", 1), 11);
        map.put(new Father("12", 1), 12);
        map.put(new Father("13", 1), 13);
        map.put(new Father("14", 1), 14);
        map.put(new Father("15", 1), 15);
        map.put(new Father("16", 1), 16);
        map.put(new Father("17", 1), 17);
        map.put(new Father("18", 1), 18);
        map.put(new Father("19", 1), 19);
        map.put(new Father("20", 1), 20);
        map.put(new Father("21", 1), 21);
        logger.info(map.get(f1));
        logger.info(map.get(f2));
        logger.info(map.get(new Father("21", 1)));


    }
}

class Father {
    public String name;

    public int hashcode;

    public Father(String name, int hashcode) {
        this.name = name;
        this.hashcode = hashcode;
    }

    public Father(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getHashcode() {
        return hashcode;
    }

    public void setHashcode(int hashcode) {
        this.hashcode = hashcode;
    }

    @Override
    public int hashCode() {
        return getHashcode();
    }

    @Override
    public boolean equals(Object obj) {
        return name.equals(((Father) obj).name) && hashcode == (((Father) obj).hashcode);
    }
}

2.new

很简单，仅仅对一些常量做初始化其中比较重要的有

public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
    }

loadFactor=0.75，扩展因子

DEFAULT_INITIAL_CAPACITY=16，初始化的容量为16

....

3.put

3.1 算出hash()

 public V put(K key, V value) {
        logger.info("put---------------------modCount:" + modCount);
        return putVal(hash(key), key, value, false, true);
    }

3.2 putVal()

声明Node[] tab，以便该数组类型做横向数组填充

进行多个判断：

当tab为空时，会创建tab，并给tab重新构建空间resize（）

当需要填坑的坑位是空时，横向创建坑位

如果需要填的坑已被占，则考虑纵向创建该坑位关联节点；

考虑情况有3，1.如果是指向同一个内存地址则忽略操作；2.如果需要创建的链式节点已经进化成红黑树，则执行插入红黑树的操作；3.还不是红黑树，则执行该节点的链表创建关联链式节点操作

以上是宏观上看待put。

3.2.1 微观上看putVal()

3.2.1.1 即tab未创建时，通过resize()创建tab

if ((tab = table) == null || (n = tab.length) == 0) {
            logger.info("table为null");
            n = (tab = resize()).length;    // 1.当未指定初始容量时，进行resize, 得到容量值赋给n=16; 获得新的节点给tab；已经存在节点时不再进来
            logger.info("tab renTab");
        }

如果要put的坑位是空的，就将创建该坑位Node　　

if ((p = tab[i = (n - 1) & hash]) == null)  // i: (16-1) & 10 = 10，未存在节点的情况下，让新节点P指向数组节点tab中的hash后的节点，创建节点数组；已经存在节点时不再进来
        {
            logger.info("创建一个新节点，tab["+i+"]指向这个节点" + "hash:" + hash + ",value:" + value);
            tab[i] = newNode(hash, key, value, null);   // 仅在p节点为空的情况下，创建刚刚新节点指向hash后为空的节点的位置
        }

3.2.1.2 否则执行一段非常复杂的逻辑

3.2.1.2.1 　　

判断是否为指向统一内存地址，如果是，则break

 Node<K,V> e; K k;
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))){
                e = p;  // hash相等 && key相等 的情况下，用节点e存储原来的已经存在的节点k
                logger.info("相同对象");
            }

不是同一内存地址，继续判断，需要该坑位是否已经进化成红黑树，如果是，就执行红黑树的put，不是则继续判断

else if (p instanceof TreeNode)     // 是否已经进化成红黑树
            {
                logger.info("进化红黑树");
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            }

以上条件都不是，说明这货要以链表或者首次进化成树的方式put进来

通过for依次遍历坑位的链表( 以这个坑位为首索引，通过next连接的各个子节点 )

如果该坑位或者坑位的子节点为空，则为其创建新的节点，形成链表形式；紧接着判断子节点数(算上坑位)是否>=7，即链表串元素>=7时，进行put会进行treeifyBin()进化成红黑树，不满足则break

如果需要put的这货在坑位的子节点中已经存在了，break

  else {
                logger.info("发生碰撞, 当前p.hash:" + p.hash + ",p.value:" + value + ",进入搜索next节点的循环");
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        logger.info("p.next为空，为其创建新的节点，p.next.hash:" + hash + ", p.next.value:" + value);
                        p.next = newNode(hash, key, value, null); // 将当前的节点的下一个节点指向新创建的节点
                        if (binCount >= TREEIFY_THRESHOLD - 1) // 只有>=7次迭代才会执行进化树结构
                        {
                            logger.info("binCount >= (TREEIFY_THRESHOLD - 1), binCount:" + binCount + ", (TREEIFY_THRESHOLD - 1):" + (TREEIFY_THRESHOLD - 1));
                            treeifyBin(tab, hash);
                        }
                        logger.info("跳出循环");
                        break;
                    }
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
                        logger.info("同一个对象");
                        break;
                    }
                    logger.info("p.next有值, p.next.hash：" +  p.next.hash + ",p.next.value:" + p.next.value + ", 把当前p指针指向p.next");
                    p = e;
                }
            }

最后，put成功的话会count++，判断是否需要resize，结束put。

++modCount; //执行put操作的次数
        logger.info("modCount:" + modCount);
        if (++size > threshold) //已经存放元素的容量+1 与 扩容阀值进行对比
        {
            logger.info("++size > threshold, size:" + size + ", threshold:" + threshold);
            resize();
        }

3.2.1.3 判断是否需要扩容

3.2.1.1 When&How执行 resize()

3.2.1.2 When&How进行链式或者红黑树操作

3.3 get()