Jdk8-HashMap

HashMap插入的流程主要包括：计算下标、何时扩容、何时链表转红黑树等，具体如下：

首先对key进行hash值的扰动，获取一个新的hash值。

(key == null) ? 0 : h = key.hashCode() ^ (h >>> 16)

判断tab是否为null或者长度为0，如果是则进行扩容操作。

if ((tab == table) == null || (n = tab.length == 0))
	n = (tab = resize()).length;

根据hash值计算下标，如果tab对应下标没有存放数据，则直接插入该数据。

if ((p = tab[i = (n-1) & hash]) == null)
	tab[i] = newNode(hash, key, value, null);

如果键值对键的值以及节点 hash 等于链表中的第一个键值对节点时，则将e指向该键值对。

if (p.hash == hash && 
	((k = p.key) == key || (key != null && key.equals(k))))
	e = p;

如果桶中引用类型是树节点，则向树插入该节点，否则向链表中插入该节点。

else if (p instanceof TreeNode)
    e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);

如果链表插入节点的时候，链表长度大于等于8，则需要将链表转换为红黑树。treeifyBin是一个链表转树的方法，但不是所有链表长度大于等于8时都会转成树，还需要对当前数组桶长度是否小于64做判断，如果小于则需要扩容，大于64则进行链表转树操作。因为当数组长度小于64时，使用链表比使用红黑树查询速度更快。数组长度较小时应该尽量避开红黑树，因为红黑树需要进行左旋、右旋、变色操作来保持平衡。

if (binCount >= TREEIFY_THRESHOLD - 1)
	treeifyBin(tab, hash);

if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    resize();

判断需要插入的键值对是否存在HashMap中，如果存在根据onlyIfAbsent(默认false)或者值为null，则更新值。

if (e != null) {
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null) {
        e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
}

最后元素处理完成之后，判断容量是否超过阙值，如果超过则进行扩容操作。

if (++size > threshold)
	resize();

JDK1.8 HashMap的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) {
    Node[] tab; Node p; int n, i;
    // 判断数组桶tab是否为null或者长度为0，如果是则进行扩容操作
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 如果桶中不包含键值对节点引用, 则将新键值对节点的引用存入桶中
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node e; K k;
        // 如果键值对键的值以及节点hash等于链表中的第一个键值对节点时, 则将e指向该键值对
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果桶中的引用类型为TreeNode, 则调用红黑树插入值
        else if (p instanceof TreeNode)
            e = ((TreeNode)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)
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果当前链表包含需要插入的键值对时, 终止遍历
                if (e.hash == hash 
                    && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 判断要插入的键值对是否存在HashMap中,
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // onlyIfAbsent 表示是否仅在 oldValue 为 null 的情况下更新键值对的值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            =return oldValue;
        }
    }
    ++modCount;
    // 键值对数量超过阙值时, 则进行扩容操作
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

扩容时计算出新的newCap、newThr，这两个单词是Capacity、Threshold，分别代表容量、阙。newCap用于创建新的数组桶new Node[new Cap]。随着扩容后，原来那些因为hash碰撞，存放成链表和红黑树的元素，都需要进行拆分存放到新的位置中。

HashMap这种散列表的数据结构，最大的性能在于可以O(1)时间复杂度定位到元素，但是因为哈希碰撞不得已在一个下标里存放多组数据，在jdk1.8之前的设计只是采用链表的方式进行存放，时间复杂度为O(n)，链表越长性能越低。所以在jdk1.8把链表长度超过8个(包含8个)的链表转成自平衡的红黑树结构，以此让定位元素的时间复杂度为O(logn)提升查找效率。

链表树化源码：

final void treefyBin(Node[] tab, int hash) {
    int n, index; Node e;
    // 数组容量大于64才进行链表树化
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // 头部、尾部
        TreeNode hd = null, tl = null;
    	do {
            
        } while ((e = e.next) != null) {
            // 将普通节点转换为树节点, 此时还不是红黑树
            TreeNode p = replacementTreeNode(e, null);
            if (t1 == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        }
    	if((tab[index] == hd) != null)
            // 转红黑树操作
            hd.treeify(tab);
    }     
} 

流程如下：

链表树化的条件有两个：链表长度大于等于8、桶容量大于64，否则只是扩容，不会树化。链表树化的过程中是先由链表转成树节点，此时的树还不是平衡树。同时在树转换过程中会记录链表的顺序，tl.next = p，这主要是方便后续树转链表和拆分更方便。链表转换成树完成之后，再进行红黑树的转换。

因为在链表树化的时候，记录了原有链表的顺序，所以直接把TreeNode转换成Node即可，源码如下：

final Node untreeify(HashMap map) {
    Node hd = null, tl = null;
    // 遍历TreeNode
    for (Node q = this; q != null; q = q.next) {
        // TreeNode转成Node
        Node p = map.replacementNode(q, null);
        if (tl = null)
            hd = p;
        else 
            t1.next = p;
        tl = p;
    }
    return hd;
}

Node replacementNode(Node p, Node next) {
    return new Node(p.hash, p.key, p.value, next);
}

get方法源码如下：

public V get(Object key){
    Node e;
    // 通过扰动函数计算hash值
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node getNode() {
    Node[] tab; Node first, e; int n; K k;
    // 判断桶数组不为空, 且通过hash值计算下标存在节点
    if ((tab = table) != null && (n = tab.length) > 0 &&
       	(first = tab[(n - 1) & hash]) != null){
        // 判断是否为第一个节点
        if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if((e = first.next) != null){
            // 如果为红黑树节点 调用红黑树查找方法
            if(first instanceof TreeNode)
                return ((TreeNode first)).getTreeNode(hash, key);
            // 如果是链表节点遍历查找
            do {
               if (e.hash == hash 
                   && ((k = e.key) == key || (key != null && key.equals(k)))) 
                   return e;
            } while((e = e.next) != null);
        }
    }
}

流程如下：

通过扰动函数计算hash值。通过hash值计算下标，并判断数组桶不为空且该下标存在节点。判断存在的节点是否为第一个节点。判断节点是红黑树节点还是链表节点，再进行节点获取。