HaspMap的put原理解析

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

里面的hash方法

// 作用
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
				   // tab 引用当前hashMap的散列表
				   // p: 表示当前散列表的元素
				   // n: 表示散列表数组的长度
				   // i: 表示路由寻址的结果
				   
    Node<K,V>[] tab; Node<K,V> p; int n, i;
	// 延迟初始化逻辑，第一次调用putval时会初始化hashMap对象中的最耗内存的散列表
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
	// 最简单一种情况：寻址找到的桶位，刚好是null，这时就可以直接扔进去就可以了
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
		// e:是node临时元素，找到了一个要与当前插入的key-value一致的key元素
		// k:表示临时的一个key
        Node<K,V> e; K k;
		// 表示桶中该元素，与你当前插入的元素的key完全一致，表示后续需要进行替换操作
		if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
			// 判断结构是否树化
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
			// 链表的处理，而且链表的头元素与我们要插入的key不一致
            for (int binCount = 0; ; ++binCount) {
				// 条件成立的话，说明迭代到最后一个元素了，也没有找到一个与要插入的key一直的node
                if ((e = p.next) == null) {
					// 就当前最后一个节点插入数据
                    p.next = newNode(hash, key, value, null);
					// 判斷鏈表d的长度是否大于8，>8就要进行树化
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
				// 表示在当前的链表中找到了一个相同的元素 
                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;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
	// 表示散列表结构被修改的次数，替换的不算
    ++modCount;
	// 插入新元素，size自增，如果自增后的值大于扩容阈值，则触发扩容
    if (++size > threshold)
		// 扩容的机制
        resize();
    afterNodeInsertion(evict);
    return null;
}

三、扩容机制

		// 为了解决hash冲突导致的链化影响查询效率的问题，扩容会缓解改问题
final Node<K,V>[] resize() {
// oldTab 引用扩容前的hash表
Node<K,V>[] oldTab = table;
// oldCap 表示扩容之前table数组的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 扩容之前的扩容阈值，触发本次扩容的阈值
int oldThr = threshold;
// newCap 扩容之后table数组的大小
// newThr 扩容之后，下次在触发扩容的条件
int newCap, newThr = 0;
// 条件如果成立说明 hashMap中的散列表已经初始化过了，是一次正常扩容
if (oldCap > 0) {
	// 扩容之前的table数组大小已经达到 最大阈值后，则不扩容，且设置扩容条件为int最大值
    if (oldCap >= MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return oldTab;
    }
	// 数据左移动一位，数据翻一倍数据 并赋值给newCap newCap小于数组最大阈值 且 扩容之前的阈值 >= 16
	// 这种情况下 则下一次扩容的阈值 等于当前阈值翻倍
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
             oldCap >= DEFAULT_INITIAL_CAPACITY)
        newThr = oldThr << 1; // double threshold
}
// oldCap == 0，说明hashMap的散列表是null
// new HashMap(initCap,loadFactor)
// new HashMap(initCap)
// new HashMap(map)
else if (oldThr > 0) // initial capacity was placed in threshold
    newCap = oldThr;
else {               // zero initial threshold signifies using defaults
   // 什么值都没有设置
   // oldCap == 0,oldThr=0
   // new HashMap()
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 什么条件下 DEFAULT_INITIAL_CAPACITY > oldCap 就没有读newThr赋值
// newThr为零时，通过newCap和loadFactor计算出一个newThr
if (newThr == 0) {
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
              (int)ft : Integer.MAX_VALUE);
}
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
	// 本次扩容之前 table不为null
    if (oldTab != null) {
		// 遍历以前旧数组中的长度
        for (int j = 0; j < oldCap; ++j) {
			//  当前node节点
            Node<K,V> e;
			// 说明当前桶中有数据，但是数据具体是 单个数据 还是链表  还是数结构
            if ((e = oldTab[j]) != null) {
				// 方便jvm 中GC进行回收
                oldTab[j] = null;
				// 单个数据就是计算  放哪个位置
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
				// 树的情况
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
				    // 对于链表的处理
				    // 低位链表：存放在扩容之后的数组下标位置，与当前数组的下标位置一致
                    Node<K,V> loHead = null, loTail = null;
					// 高位链表 存放在扩容之后的数组下标位置，当前数组下标位置 + 扩容之前的数组长度
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
					//
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}