HashMap到底是怎么put的？-白红宇

HashMap到底是怎么put 的？

欢迎有时间去来我的csdn博客做客讨论~

关于HashMap中的红黑树这里不做过多讨论

本次讨论的是jdk1.8的源码HashMap.put 直接上源码，

HashMap.put会直接调用putVal(hash(key), key, value, false, true); 直接开始看：

代码片段一

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,               boolean evict) {	// putVal(hash(key), key, value, false, true);	// hash是key的hash值，具体算法见方法，key是put时的key，value是put的value,onlyIfAbSent = false,evict = true;    Node
    
     [] tab; Node
     
       p; int n, i;	// 如果为该Map为空尚未初始化，则调用resize进行初始化，n = 初始化后table的大小16。	//==========================resize过程见代码片段二===================================    if ((tab = table) == null || (n = tab.length) == 0)        n = (tab = resize()).length;	// 如果在计算出来的table数组的第i个位置上，p = null 还没有节点，则创建一个节点即可。（i = (n - 1) & hash）,这个计算方法是完成了类似%的操作，并且因为n-1始终是2进制的1111...,所以在table数组上的位置均分。	// p = table[i];    if ((p = tab[i = (n - 1) & hash]) == null)        tab[i] = newNode(hash, key, value, null);	// 如果在第i个位置上已有节点，即p!=null则进入else方法块。    else {        Node
      
        e; K k;		// 数组table第i个元素的第一个节点 的hash值 = 要put的key的hash值，要put的key如果等于在这个节点上的key（包括null情况，这也就说明，hashMap的key可以为null，但是只能有一个）。		// 在这种情况下则将当前节点用e指代        if (p.hash == hash &&            ((k = p.key) == key || (key != null && key.equals(k))))            e = p;		// 如果p（table第i个元素的第一个节点 的hash值 ） 为 TreeNode，则将新节点放入HashMap里自定义的红黑树。putTreeVal方法会自己完成树的平衡        else if (p instanceof TreeNode)            e = ((TreeNode
       
        )p).putTreeVal(this, tab, hash, key, value);		// table第i个元素的第一个节点 不满足上述情况（第一个节点和put进来的key不一样 + 不为TreeNode），则进入这个方法块。        else {			//遍历table第i个元素上的链表，从头开始遍历，见第一行e = p.next 和for循环最后一行p = e。            for (int binCount = 0; ; ++binCount) {				//遍历到p 的next节点为null的时候，则 p.next指向新节点。（所以hashMap的链表上有新节点时都是在链表尾部插入。）				//e = p.next ；p.next = newNode 这句则是将当前节点记录，用e指代。                if ((e = p.next) == null) {                    p.next = newNode(hash, key, value, null);					//插入到binCount到7的时候，即链表上的元素为第八个，插入了第九个的时候，则将这个链表转变为红黑树，使用treeifyBin方法。                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                        treeifyBin(tab, hash);                    break;                }				//如果循环到一个节点，且满足 【hash值 = 要put的key的hash值，要put的key如果等于在这个节点上的key（包括null情况，这也就说明，hashMap的key可以为null，但是只能有一个）】				// 则将当前节点记录，用e指代。                if (e.hash == hash &&                    ((k = e.key) == key || (key != null && key.equals(k))))                    break;                p = e;            }        }		//由上面的代码执行完，则e肯定是指代了一个当前节点，key与要put的key一致，如果已有值，则value 是oldValue,如果没有，则是新的value		// 下面的代码执行结束，则返回一个value（如果已有则为old,否则为插入的）可以使用map.put(k,v) == v 来判断hashMap以前有没有存储过这个key。		//并返回。        if (e != null) { // existing mapping for key            V oldValue = e.value;            if (!onlyIfAbsent || oldValue == null)                e.value = value;			//预留方法，LinkedList使用            afterNodeAccess(e);            return oldValue;        }    }	// 如果是【在第i个位置上已有节点，即p!=null则进入else方法块。】这个条件，则会在上面return，所以在这里的代码都是第i个节点上没有数据的情况才会执行，即resize这个方法只会在往数组的一个新位置上插入数据的时候才会触发（其实是废话，resize就是table的size不够的情况）。	    ++modCount;    //size为table数组上有数据的数量，如果size大于threshold时则扩容。	if (++size > threshold)		//=====================================这里扩容时的resize见代码片段三====================================        resize();	//预留方法，LinkedList使用    afterNodeInsertion(evict);	//返回null。    return null;}复制代码

代码片段二

// 在初始化的时候的调用场景final Node
    
     [] resize() {	//空    Node
     
      [] oldTab = table;	// 0    int oldCap = (oldTab == null) ? 0 : oldTab.length;	//0    int oldThr = threshold;    int newCap, newThr = 0;	//不进去    if (oldCap > 0) {        if (oldCap >= MAXIMUM_CAPACITY) {            threshold = Integer.MAX_VALUE;            return oldTab;        }        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;	//进去，设置容量为默认容量为16 ，threshold = 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是成员变量    threshold = newThr;	//创建出一个newTab，数组大小为 newCap  = 16    @SuppressWarnings({"rawtypes","unchecked"})        Node
      
       [] newTab = (Node
       
        [])new Node[newCap];	//将变量 table 设置为刚才创建出来的newTab。 table 是成员变量。	//总结一下，这个方法在初始化的时候只是将table设置为初始化的大小为16的数组，threshold =12。    table = newTab;	//不进去    if (oldTab != null) {        for (int j = 0; j < oldCap; ++j) {            Node
        
          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
         
          )e).split(this, newTab, j, oldCap); else { // preserve order Node
          
            loHead = null, loTail = null; Node
           
             hiHead = null, hiTail = null; Node
            
              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;}复制代码

代码片段三

final Node
    
     [] resize() {	//将要扩容的table，容量到达0.75*capacity    Node
     
      [] oldTab = table;	//当前的capacity    int oldCap = (oldTab == null) ? 0 : oldTab.length;    //当前的threshold	int oldThr = threshold;    //设置新的容量和threshold	int newCap, newThr = 0;	//扩容时进入    if (oldCap > 0) {		//如果已经到达int最大值，则只能这样了...直接返回不扩容（所以，也不是到了就扩容，毕竟有上限）。        if (oldCap >= MAXIMUM_CAPACITY) {            threshold = Integer.MAX_VALUE;            return oldTab;        }		//如果还没到，则新的容量设置为老的容量的2倍，threshold也变成以前的两倍（16->32...）        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;    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;	//创建一个新的数组，容量为新容量（2倍老容量）    @SuppressWarnings({"rawtypes","unchecked"})        Node
      
       [] newTab = (Node
       
        [])new Node[newCap];	//这里将成员变量设置为新的数组（在这时候如果put，则可能会有问题，想想）    table = newTab;	//扩容时进入    if (oldTab != null) {		//遍历旧的数组        for (int j = 0; j < oldCap; ++j) {            Node
        
          e;			//用e指向旧数组的遍历到的位置，如果不为空，则进入，为空则不用管。            if ((e = oldTab[j]) != null) {                oldTab[j] = null;				//如果e.next==null,则是只有一个元素，则只需要将这个元素 e 平移到新数组上即可。newTab[e.hash & (newCap - 1)] = e                if (e.next == null)                    newTab[e.hash & (newCap - 1)] = e;				//如果这个位置上的存储结构是树结构，则进行分割这个树结构到新数组上，与下面的else情况类似，分为在新数组的老位置还是新位置。                else if (e instanceof TreeNode)                    ((TreeNode
         
          )e).split(this, newTab, j, oldCap); //除此的情况，不是只有1个元素，且不是树结构（链表大小小于8），则进入。 else { // preserve order //这里的处理我第一次看到的时候觉得很是佩服。 //定义两个Node,一个低位Node loHead ，一个高位Node hiNode，为什么高，为什么低下面说。 Node
          
            loHead = null, loTail = null; Node
           
             hiHead = null, hiTail = null; Node
            
              next; // 循环遍历e开头的链表,直到 e 的最后一个节点 do { next = e.next; //遍历过程中，如果 e 满足 (e.hash & oldCap) == 0 则将这个节点放到 loHead链表。 //这里这么处理的原因是 oldCap 一定是2的幂次方，在2进制下为10000....这种，所以当e.hash如果满足(e.hash & oldCap) == 0 时则说明，e的高位也为0。而newCap-1 的二进制是1111111...（与oldCap的长度一样） //比如16扩容后变成32 ，则oldCap = 10000，newCap -1 = 11111; //在这种情况下，前面说过e的高位为0。其实e.hash &（newCap -1）实际上的最高位肯定 =0 ，而如果高位等于0，则e.hash &（newCap -1） == e.hash &（oldCap -1）,这个元素则新旧数组table中的位置肯定是一个。 // 所以还在第j 个位置。 //如果不为0 ，则高位为1，则e.hash &（newCap -1） = e.hash &（oldCap -1） + 10000...（oldCap的二进制） if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } // 不满足的 (e.hash & oldCap) != 0 则将这个节点放到 hiTail 链表。 else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); //遍历完毕，if满足部分进入数组的原有位置 j ，else 满足部分进入 数组新位置 j+oldCap 。 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } //返回新数组，结束扩容。 return newTab;}复制代码