【java集合】HashMap源码分析

	
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    
    static final int MAXIMUM_CAPACITY = 1 << 30;

    
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    
    static final int TREEIFY_THRESHOLD = 8;

    
    static final int UNTREEIFY_THRESHOLD = 6;

    
    static final int MIN_TREEIFY_CAPACITY = 64;

	
	transient Node[] table;

    
    transient Set> entrySet;

    
    transient int size;

    
    transient int modCount;

    
    int threshold;

    
    final float loadFactor;

	
	public HashMap(int initialCapacity, float loadFactor) {
		// 数组初始长度不能小于 0，否则抛异常
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        // 数组的初始长度不能大于最大值
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        // 负载因子小于0，或者not a number则 抛出异常， 
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        // 设置负载因子
        this.loadFactor = loadFactor;
		// 计算数组的容量，暂时存到threshold（扩容阈值）
        this.threshold = tableSizeFor(initialCapacity);
    }

    
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

    
    public HashMap(Map m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

构造函数1.2.3都不会创建table数组，HashMap会在第一次put数据时才创建table数组

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
@Override
public V putIfAbsent(K key, V value) {
    return putVal(hash(key), key, value, true, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    // 临时表量 tab=》table数组，p =》临时node节点， n =》table长度， i =》临时桶下标
    Node[] tab; Node p; int n, i;
    // 判断是否初始化table数组  table为null，长度为0 表示未初始化
    if ((tab = table) == null || (n = tab.length) == 0)
    	// 调用扩容方法进行初始化，后面扩容部分再分析
        n = (tab = resize()).length;
    // 通过hash码计算出桶下标，该桶位还没有放置元素
    if ((p = tab[i = (n - 1) & hash]) == null)
    	// 直接构造一个node节点作为首节点
        tab[i] = newNode(hash, key, value, null);
    // 该桶位已经有元素了（只有一个node、node链表 或者 红黑树）
    else {
        Node e; K k;
        // 第一个元素就发生hash冲突
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; // 临时变量e暂时指向key值相同的node，后续根据putIfAbsent决定是否替换旧的value值
        // 桶位放置的是红黑树 （TreeNode继承于Node）
        else if (p instanceof TreeNode)
        	// 红黑树中没有相同的key，插入成功，返回null
        	// 红黑树中已经存在相同的key，临时变量e暂时指向key值相同的node，后续根据putIfAbsent决定是否替换旧的value值
            e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);
        // 链表情况
        else {
        	// 遍历链表
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) { // 遍历到链表尾部，构造Node 完成插入
                    p.next = newNode(hash, key, value, null);
                    // 插入完成后检查链表长度是否超过 8
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                    	// 尝试树化，树化前要检查table数组的长度是否小于64，小于64时优先扩容
                        treeifyBin(tab, hash);
                    break;
                }
                // 遍历链表过程中发生hash冲突，有相同的key
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 直接结束循环，e已经指向了那个key相同的Node
                    break;
                p = e; // e =>遍历的当前节点， p => 上一个节点
            }
        }
        // e ==null 没有遇到相同的key，已经完成了插入
        // e != null 遇到相同的key值，统一处理
        if (e != null) { // existing mapping for key
            V oldValue = e.value; // 先保存旧值
            // onlyIfAbsent为false 或者 旧值为空 做更新操作
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e); // 节点访问后序处理
            return oldValue; // Hash冲突，涉及更新操作时，返回旧值
        }
    }
    ++modCount; // 插入成功（没有发生更新操作）结构修改次数加1
    if (++size > threshold) // 元素个数超过阈值，触发扩容
        resize();
    afterNodeInsertion(evict); // 节点插入后续处理
    return null;  // 没有发生hash冲突，插入成功返回null
}

补充一下后续处理
以下这三个函数定义于HashMap，作用分别是：节点访问后、节点插入后、节点移除后做一些事情。linkedHashMap继承于HashMap，重新实现了这3个函数，也就是说linkedHashMap会用自己的实现做后置处理，而对HashMap来说啥也没做（方法体为空）！

// Callbacks to allow linkedHashMap post-actions
void afterNodeAccess(Node p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node p) { }

扩容入口
2. 链表长度大于8，执行树化流程时发现table长度没到64，优先进行扩容
3. 插入元素后检查元素个数超过阈值threShold

先看看扩容过程中高链和低链的概念
以table长度16扩容到32为例，如图，当hash码后四位为1111时，和数组长度N-1进行与操作(N-1) & hash得到的下标都是(16-1) & hash = 15，扩容后这个链表的元素重新计算下标(32-1) & hash，此时hash码的第五位参与计算，得到下标有两种情况：

1. hash码第五位为0时，下标不变，还是15，这些元素组成新的链表（低链），在新数组中桶下标不变
2. hash码第五位为1时，下标需要加上旧数组的长度16，等于31，这些元素组成新的链表（高链），在新数组中的桶下标加在原来的基础上加原数组的长度

HashMap扩容时不管是链表还是红黑树都通过hash & 旧数组长度计算得到高低链，然后分别将链表放入新的桶位中，比如：

1. …01111 & 1000 == 0 node放到低链
2. …11111 & 1000 != 0 node放到高链
   其中红黑树完成两个链表的转移之后还要进一步判断数否需要树化（拆分后的两个链表长度还有可能大于8）。
   

final Node[] resize() {
	// 临时变量接收旧table
    Node[] oldTab = table;
    // 旧table的长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 旧table触发扩容的阈值
    int oldThr = threshold;
    // 新数组的长度和阈值都先给0
    int newCap, newThr = 0;
    // oldCap等于0表示初始化时调用resize，大于0就是扩容场景
    if (oldCap > 0) {
    	// 数组长度不能超过最大值 1 << 30
        if (oldCap >= MAXIMUM_CAPACITY) {
        	// 阈值给大，防止再次触发扩容
            threshold = Integer.MAX_VALUE;
            return oldTab; // 直接返回
        }
        // 新数组长度乘2后不超过数组的最大值 且 旧数组长度大于等于16
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold 阈值翻倍
    }
    
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr; // 初始化前threshold存的是计算的数组长度
    // oldThr 等于0 对应无参构造 数组长度用默认19，阈值使用16*0.75 = 12
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    
    if (newThr == 0) {
    	// 数组长度*负载因子
        float ft = (float)newCap * loadFactor;
        // 判断是否到达数组长度的上限，如果到达上限直接把扩容阈值给最大值Integer.MAX_VALUE，防止再次触发扩容
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr; // 接收临时变量计算好的值
    @SuppressWarnings({"rawtypes","unchecked"})
    // 扩容/初始化正式开始
    // 构建table数组
    Node[] newTab = (Node[])new Node[newCap];
    table = newTab; // 赋值给table成员变量，到此初始化完成
    // 扩容
    // oldTab == null为初始化场景，不执行if块里的代码
    if (oldTab != null) {
    	// 遍历旧数组
        for (int j = 0; j < oldCap; ++j) {
            Node e;
            // 桶位不为空
            if ((e = oldTab[j]) != null) {
            	// 临时变量e已经接收了这个同为的值，原来桶位置null，方便GC
                oldTab[j] = null;
                // 情况1 只有一个元素，则放到新数组对应下标的桶位即可
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 情况2 e是红黑树的头结点
                else if (e instanceof TreeNode)
                	// 数据迁移，后面分析
                    ((TreeNode)e).split(this, newTab, j, oldCap);
                // 情况三 e是链表头结点
                else { // preserve order
                	// 低链头结点、低链尾结点
                    Node loHead = null, loTail = null;
    				// 高链头结点、高链尾结点
                    Node hiHead = null, hiTail = null;
                    Node next;
                    do {
                        next = e.next;
                        // 低链：loHead -> e1 -> e2 ->...-> en <- loTail 
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 高链：hiHead -> e1 -> e2 ->...-> en <- hiTail
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null); // 遍历到null为止

					
                    if (loTail != null) {
                        loTail.next = null;
                        // 低链桶下标不变
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        // 高链桶下标加旧数组的容量
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

//TODO 比较简单 后面在分析

table某个桶位node链表长度超过8时，会调用treeifyBin，检查table数组长度达到64的情况下，先把原来的单链表结构变成了双链表结构，然后调用TreeNode::treeify(table)进行树化。红黑树的结构同时维持着双链表的结构，

final void treeifyBin(Node[] tab, int hash) {
    int n, index; Node e;
    // table数组长度不到64时，优先进行扩容
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    // 获取首节点，判断不为空
    else if ((e = tab[index = (n - 1) & hash]) != null) {
    	// 定义头结点head和尾结点tail
        TreeNode hd = null, tl = null;
        // do-while循环 将把Node对象转换成了TreeNode对象，把单向链表转换成了双向链表:
        // hd => p1 <=> p2 <=> ... <=> pn <= tl 
        do {
        	// 将该Node节点转换为TreeNode节点
            TreeNode p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        // 把转换后的双向链表，替换原来位置上的单向链表
        if ((tab[index] = hd) != null)
            hd.treeify(tab);// 双向链表转红黑树，后面分析
    }
}

简单理解下单链表转双链表的过程

• 首先将Node节点转换为TreeNode节点，TreeNode节点中的next和prev分别维护双向链表的两个指针
• hd和tl分别指的是双向链表头尾两个节点的引用，给tl赋值prev和next，就等于赋值最后一个节点赋值。
• 方法执行完hd和tl作为局部变量生命周期结束，双链表的头结点的地址放在了table的桶位tab[index] = hd
  

// TODO if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) 这个tab==null的判断对应的场景暂时没搞清楚 后面搞懂了再补充

put流程调用putTreeval将元素插入红黑树

final TreeNode putTreeval(HashMap map, Node[] tab,
	               int h, K k, V v) {
	Class kc = null;
	// 标识是否被搜索过，后面用到再做说明
	boolean searched = false;
	// 查找根节点, 索引位置的头节点并不一定为红黑树的根节点
	TreeNode root = (parent != null) ? root() : this;
	// 根节点赋值给临时变量p，二分查找
	// 
	for (TreeNode p = root;;) {
	    int dir, ph; K pk;
	    // 传入的hash值h小于p节点的hash值，将dir赋值为-1，代表向p的左子树查找
	    if ((ph = p.hash) > h)
	        dir = -1;
	    // 传入的hash值大于p节点的hash值， 将dir赋值为1，代表向p的右子树查找
	    else if (ph < h)
	        dir = 1;
	    // 传入的hash值h等于p节点的哈希值，进一步判断key值等于p节点的key值, 如果相等就是找到与要插入的key相同的节点。将这个节点返回，在上层方法中决定是否替换value值
	    else if ((pk = p.key) == k || (k != null && k.equals(pk)))
	        return p;
	    
	    else if ((kc == null &&
	              (kc = comparableClassFor(k)) == null) ||
	             (dir = compareComparables(kc, k, pk)) == 0) {
	        // 由于要用递归的方式在左右子树中搜索，所以如果已经搜索过，那么把searched设置为true，避免下次循环重复搜索
	        if (!searched) {
	            TreeNode q, ch;
	            searched = true;
	            // 在左右子树递归的寻找 是否有key的hash相同 并且equals相同的节点
	            if (((ch = p.left) != null &&
	                 (q = ch.find(h, k, kc)) != null) ||
	                ((ch = p.right) != null &&
	                 (q = ch.find(h, k, kc)) != null))
	                // 找到了 就直接返回
	                return q;
	        }
	        // 说明红黑树中没有与之equals相等的 那就必须进行插入操作 必须将两个key分出大小 dir的结果必须是-1或1  
	        dir = tieBreakOrder(k, pk);
	    }
	
	    TreeNode xp = p;
	    if ((p = (dir <= 0) ? p.left : p.right) == null) {
	        Node xpn = xp.next;
	        TreeNode x = map.newTreeNode(h, k, v, xpn);
	        if (dir <= 0)
	            xp.left = x;
	        else
	            xp.right = x;
	        xp.next = x;
	        x.parent = x.prev = xp;
	        if (xpn != null)
	            ((TreeNode)xpn).prev = x;
	        moveRootToFront(tab, balanceInsertion(root, x));
	        return null;
	    }
	}
}

补充说明：
for (TreeNode p = root;;) {...} 比较key是否相等，用到一个约定：对象相等，hash一定相等，hash相等，对象不一定相等，这个技术细节总结在hashCode和equals中，所以在上面源码中到了hash相等的情况需要进一步判断key值是否相等，如果key不相等，需要再判断是否实现Comparable，没有实现Comparable接口或者Comparable比较结果相同（芭比Q了，不是没法比，就是两个不相等的key比较出来是相等的QAQ）这种情况只能从子树中找是否有key的hash相同 并且equals相同的节点，找到了返回，找不到必须想办法分出大小，做插入操作。