【数据结构】--【集合】Map集合总结xmind思维导图HashMap扩容详解

Map集合重点总结

HashMap重要的方法-构造器

HashMAP四种构造器

HashMap重要的方法-put方法

HashMap重要的方法-get方法

HashMap重要的方法-resize（）方法-扩容

final Node<K,V>[] resize() {
	//首先赋值给oldTab相当于是一个temp临时数组的作用
	//因为在后面建立新数组后，需要将old的值传递
        Node<K,V>[] oldTab = table;
		//获取容量
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
		//获取扩容的临界值：当实际大小（容量*填充因子）超过临界值时，会进行扩容
		//初始化值为0，如果带有参数的构造器就是传入的合法参数
		//如果尚未分配表数组，则此字段保存初始数组容量，或者表示DEFAULT_INITIAL_CAPACITY为零。
        int oldThr = threshold;
		//设置新的容量和新的临界值
        int newCap, newThr = 0;
		//如果oldCap不为空的话，就是hash桶数组不为空，表示扩容过
        if (oldCap > 0) {
			//如果大于最大的容量
            if (oldCap >= MAXIMUM_CAPACITY) {
				///如果大于最大容量了，就赋值为整数最大的阀值
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
			//如果当前hash桶数组的长度在扩容后仍然小于最大容量 并且oldCap大于默认值16
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
					 //新的容量和新的阈值扩充两倍
                newThr = oldThr << 1; // double threshold  双倍扩容阀值threshold
        }
		//否则说明hash桶为空，如果临界值不为空，说明有参数，则用来更新新的容量
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;//使用带参数的临界值作为新的容量
         //否则说明hash桶为空同时临界值也为空，使用默认值初始化新的容量（初始容量16、初始临界值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;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
		//根据获得的newCap，新建hash桶数组
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
		//判断原数组是否为空，若不为空将赋值Node对象到hash数组
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    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 {
							//lo就是扩容后仍然在原地的元素链表
                            //hi就是扩容后下标为  原位置+原容量  的元素链表，从而不需要重新计算hash。    
                            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);
						//退出循环后只需要判断lo，hi是否为空，然后把各自链表头结点直接放到对应位置上即可完成整个链表的移动。
                        //原理是：利用了尾指针Tail，完成了尾部插入，不会造成逆序，所以也不会产生并发死锁的问题。
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }