实战系列-HashMap深入剖析

布满荆棘的人生 2023-02-22 10:36 18阅读 0赞

> **导语**  
>   手撕面试官，面试某公司开发的时候被问到了HashMap底层，问到我怀疑人生，不知道是面试官错了还是我错了。我相信是我错了利用下班时间来分析手撕一下HashMap。

通过手撕源码加上实验来给自己打脸，这些东西你跟面试官真的懂么？想要做出创新的东西真的容易么？就靠着自己对于增删改查就可以驰骋江湖了么？自己离高手的路还有一段距离。

### 文章目录 ###

*   *  实验
     *   *  putVal()
         *  resize()
         *  treeifyBin()
         *  treeify()
         *  moveRootToFront()
     *  总结

## 实验 ##

不用多说直接上源码这里，首先解释一下传入的几个参数。HashMap 传入的就是KV两个值，没有什么好解释的，进入方法之后调用的是putVal的方法这里可以看到。调用了一个hash()的方法。

/** * Associates the specified value with the specified key in this map. * If the map previously contained a mapping for the key, the old * value is replaced. * * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with <tt>key</tt>, or * <tt>null</tt> if there was no mapping for <tt>key</tt>. * (A <tt>null</tt> return can also indicate that the map * previously associated <tt>null</tt> with <tt>key</tt>.) */
        public V put(K key, V value) { 
            return putVal(hash(key), key, value, false, true);
        }

**到这里第一个问题来了：这个HashCode是怎么产生的?**  
   到这里有面试官会问这个时候我们的hashCode是怎么产生的。就是通过这个方法，这里需要通过 (h = key.hashCode()) ^ (h >>> 16) 一个操作，这里解释一下这个操作，希望读者可以擦亮眼睛。看清楚了  
hashCode()方法是native方法，而^操作 表示异或，而 >>> 这个操作，我们都知道>> 这个叫做左移

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

什么是左移，下面这个操作就是左移

原来数据是   1 1 1 1  十进制表示 15
    左移操作  0 1 1 1 十进制表示 7
    左移两位 0 0 1 1 十进制表示 3

**测试一下**  
  通过上面的分析来测试一下上面这个方法返回的值是什么

public class Test { 
    
        static final int hash(Object key) { 
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }
        public static void main(String[] args) { 
            
            int hash = hash(10);
            System.out.println(hash);  // 10 
        }
    }

**分析一下**

10 十进制  二进制表示 1010
    
    首先第一步操作获取了一个HashCode 假设这个值就是 10
    
    那么这里的第一个操作就是 h = key.hashCode() 获取到 h = 10；
    第二个操作 就是 h >>> 16 ，结果为 0 二进制也是 0   最终将两个值做了异或 异或的意思就是 只要有1 就是1 
    
    所以 最后结果还是 10

到这里就应该就差不多了，再要往底层问就是要问一下hashCode()方法体内部是什么操作？有兴趣的可以了解一下。

继续往下就进入了核心方法中，这里就有好日子过了。

### putVal() ###

/** * Implements Map.put and related methods * * @param hash hash for key 通过hash计算的hash 值 * @param key the key 具体存入的键值 * @param value the value to put 放入的value值 * @param onlyIfAbsent if true, don't change existing value 如果为true ，则不去改变现有值 传入的值是 false * @param evict if false, the table is in creation mode. 如果为false，则表处于创建模式，传入的值为 true * @return previous value, or null if none */
         
        final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) { 
            //建立新节点数组，建立节点，初始值
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            //首先判断 tab 以及实际存储的table是否为空，第二步就是看 tab的长度是否为0。
            if ((tab = table) == null || (n = tab.length) == 0)
            	// 重新赋值 重置之后会获取到一个新的数组
                n = (tab = resize()).length;
            // 如果 tab[i = (n - 1) & hash] 对应的节点为空，这个怎么理解？
            // 首先来分析一下这个时候 n 的值应该是新创建的数组的长度，拿默认值来说这个长度应该是 16 
            // 这里 n-1 也就是 15 例如放入这个位置的值为 10 也就是 1010 和 1111 做一个与操作，根据分析可以知道 它应该就是 1010 那么就知道这里判断的是这个数组第10个位置是否有数据，如果没有数据则进行一个 newNode(hash, key, value, null)操作也就是创建一个新的节点。源码方法很简单就是创建一个Node 
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else { 
            	//否则就是由Hash冲突了，这里就需要解决这个冲突，首先想到的就是将该节点上的冲突转移到链表中。
                Node<K,V> e; K k;
                // 这里进入hash的判断，假设一个很极端的情况来进行分析，就是存储的所有元素都是10 
                // && 这操作是一个与操作，也就是这两边的表达式操作都要为true才可以。那么首先来看
                //p.hash == hash 如果上面这个场景成立，那么10 和10 的hash应该是一样的，条件成立
                // ((k = p.key) == key || (key != null && key.equals(k)))) 这个表达是很长但是可以根据括号做一个拆分。
                //(k = p.key) == key 还是之前的极端情况这里的key一样 这个条件为真 
                // || 表示或也就是说这个符号左右两边只要有一个为true就可以了。
                // (key != null && key.equals(k))) 继续就是判断这个key的值是否一样，这里有一点需要注意就是，如果放入的就是 大量相同数据那么这个地方条件都成立了，进入的操作应该是e = p; 也就是说如果所有条件都成立了那么最终的结果应该是这个 p 节点就是 e 节点 直接做了指针交换。也就间接的证明一件事情，如果key相同，那么存储到HashMap中的内容无论有多少，只要key相同就看作一个。这个就是为什么在HashMap中的Key不能重复的原因。
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                // 做完上面的判断之后，就开始做TreeNode的判断是否是TreeNode，这里我们知道，这个节点 p 判断的时候 并不是一个TreeNode，而是一个Node那么这个条件是不是一直不成立呢？
                // 首先 Node 实际上继承了Entry 而 TreeNode继承的是LinkedHashMap.Entry<K,V> 也就是HashMap的链表实现。
                // 第一点 p 节点 在什么时候会变成 TreeNode。这个就和resize()中的split()方法有关，这里先不做分析
                // 第二点 变化节点类型之后put的方式也发生了变化。就是下面，这个操作。 
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                // 如果整个的条件都不满足，也就是说既不是树节点，也不是同一个key，这个时候就需要进入下下面这个逻辑 
                else { 
                	// 这里是一个死循环
                    for (int binCount = 0; ; ++binCount) { 
                        // 判断如下，首先获取到p节点的下一个节点判断是否为空
                        if ((e = p.next) == null) { 
                            // 如果为空 则创建新的链表节点。使用链表的尾部插入法
                            p.next = newNode(hash, key, value, null);
                            // 判断一下 计数是否大于等于TREEIFY_THRESHOLD - 1 这里其实就是转换红黑树的临界区，当链表长度大于8的时候就进行了一个treeifyBin(tab, hash);操作，看看具体传入的参数，一个是tab ，另个一是hash，这个hash就是传入的通过 hashCode()计算的哪个值。
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            	// 分析完这个地方的逻辑之后，可以看到，完成转换之后的操作还是与整个的数组扩容没有关系，就是解决数组的hash冲突的问题。最终进行返回
                                treeifyBin(tab, hash);
                            break;
                        }
                        // 如果e节点的hash值 就是满足下面这个条件也是解释了上面分析中的一个key唯一的问题。
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        // 这个时候将e节点赋值给p节点。其实就是拿到这个节点做了一个转换，如果转换没成功则就还是原来的东西还给原来的位置。 
                        p = e;
                    }
                }
                // 这里说是判断键的现有映射
                // 结束上面判断的时候最终可以获取到e的值的只有上面两个判断中的值。一个是往数组中方结果，一个是往数中方结果
                // 放入的时候有可能存在值了 e就不会为null
                if (e != null) {  // existing mapping for key
                	// 获取到老值
                    V oldValue = e.value;
                    // 如果值为空 或者是不存在
                    if (!onlyIfAbsent || oldValue == null)
                    	// 就把对应位置的值进行替换
                        e.value = value;
                    // 进行一个后置访问 最终的这个后置访问是自扩展的，这个扩展在TreeNode继承的LinkedHashMap中进行了实现，这个操作就先不多说了
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            // 这字段表示Hash在结构上被修改的次数，是个全局的变量
            // 这个结构修改值的是HashMap的修改以及其内部的修改，它的作用是
            // 在集合视图上实现迭代器
            ++modCount;
            // size 记录的是 HashMap的大小，这里需要注意的是数组的大小还是里面的结构的大小
            // 在上面的操作中并没有那个地方来修改这个值，而这个值唯一被增加的地方就是这里，所以说
            // size 记录的是内部元素的总共进入了多少个，而不是内部的table的大小
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }

/** * The number of times this HashMap has been structurally modified * Structural modifications are those that change the number of mappings in * the HashMap or otherwise modify its internal structure (e.g., * rehash). This field is used to make iterators on Collection-views of * the HashMap fail-fast. (See ConcurrentModificationException). */
        transient int modCount;

上面提到了一个size的概念，有如下的一个问题来，下面这个代码最后输出的结果是多少

HashMap<Integer,Object> hashMap = new HashMap<>();
      for (int i = 0; i <100 ; i++) { 
          hashMap.put(i,i);
      }
      System.out.println(hashMap.size());
      // 100

### resize() ###

**接上面resize()方法** 从上面进入到重新设置大小的操作。

final Node<K,V>[] resize() { 
       		//记录一下原来的table，这里不管有没有值都记录一下。
            Node<K,V>[] oldTab = table;
            // 如果旧表为空或者不为空那么就需要记录一下器长度
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            // 这里简单的解释一下这个值，capacity * load factor
            // 源码中的英文翻译过来是 要调整大小的下一个大小值（容量*负载系数）。
            // 有人会问这个东西值在什么地方 具体是通过 static final int tableSizeFor(int cap) 操作算出 
            int oldThr = threshold;
            
            int newCap, newThr = 0;
            // 这里表示 这个值 表如果有值
            if (oldCap > 0) { 
            	// 则 看看是否是 比这个 1<<30 大
                if (oldCap >= MAXIMUM_CAPACITY) { 
                	// 如果不是则返回就是一个原来的表也就是说没有办法再操作了，threshold也调成 最大的整数值
                    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;
            else {  // 否则就是一个默认的初始值
                          // zero initial threshold signifies using defaults
                // 在指定newCap 和newThr的时候就使用默认的初始化大小，
                // DEFAULT_INITIAL_CAPACITY = 1<<4
                // DEFAULT_LOAD_FACTOR = 0.75 
                newCap = DEFAULT_INITIAL_CAPACITY;
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            // 在上面的判断结束之后这里做了一个newThr 为0 的判断
            // 这里如何理解 什么时候这个值会是0
            // 经过分析可以看到，这个值在初始化的时候为零，也就是说没有经过上面的两个判断直接进入到了这里，从代码逻辑上来看，上面的判断是对oldCap 和 oldThr的判断。从这里可以看出 下面这个IF判断应该是初始化的逻辑
            if (newThr == 0) { 
            	// 上面可以看到如果没有旧数据，那么newCap 值应该是默认值16。loadFactor的值应该是 默认值 0.75 从而可以知道 ft的值应该是 12.0f
                float ft = (float)newCap * loadFactor;
                // 计算出一个新的 newThr
                // 我们知道MAXIMUM_CAPACITY 值是 1<<30,ft 经过计算应该是 12.0f，
                // 也就是说看看newCap 和 ft的值与 1<<30 的大小。最终的结果应该是 ft ，如果超过对应的大小就是Int类型的最大值。注意这里的大小全部是对于数组来做的
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);
            }
            // 将临界区 改为新的临界区，这里是个人叫法，也就是说如果数据超过这个值就一定会发生 hash冲突。
            threshold = newThr;
            @SuppressWarnings({ "rawtypes","unchecked"})
            // 下面这个操作就是用新的长度去创建一个 新的数组
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
            // 将新的数组指向新的引用
            table = newTab;
            // 接下来就是对于老数据的移动
            if (oldTab != null) { 
            	// 遍历老数组
                for (int j = 0; j < oldCap; ++j) { 
                    Node<K,V> e;
                    // 将老数组中的元素获取出来判断是否为空，
                    if ((e = oldTab[j]) != null) { 
                        // 这里将老数组中的第j个位置的元素给设置为空
                        oldTab[j] = null;
                        if (e.next == null)
                            // 判断是否有链表存在 如果不存在，则进行e.hash & (newCap - 1) // 给整个元素给定一个新的位置
                            newTab[e.hash & (newCap - 1)] = e;
                        else if (e instanceof TreeNode)
                            // 如果 是树的节点 进行了一个split的操作，整个函数代码有点多，放到下面分析
                            ((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 { 
                            	// 首先 将 e 节点的 下一个节点值获取到
                                next = e.next;
                                // 第二步 将e 节点的 hash值与table的长度 做 与运算，假设 10 和 12 做与运算 1010 和 1100 1000 也就是说 存在两个1 才是1 否则都是0
                                // 这个判断的意思是 如果 e元素的hash值 和 老的 table的长度做与运算为0 那么什么时候这操作会为零呢？ 就是这个oldCap为零的时候，那么什么时候oldCap为零，或者说这个oldCap为零会带来什么样的后果。
                                if ((e.hash & oldCap) == 0) { 
                                	// 判断 尾节点是否为空如果不为空则就是它本身是头节点，如果不是则尾节点的将e节点放入到下一个节点中。
                                    if (loTail == null)
                                        loHead = e;
                                    else
                                        loTail.next = e;
                                    loTail = e;
                                }
                                // 如果上面的条件不满足，一般都是有值的不会为零
                                else { 
                                	// 将原来的数据进行记录保存到hiTail中，原则与上面的操作原则是一样的。
                                    if (hiTail == null)
                                        hiHead = e;
                                    else
                                        hiTail.next = e;
                                    hiTail = e;
                                }
                            } while ((e = next) != null);
                            //遍历完成之后
                            // 如果loTail 不为空
                            // 也就是说原来的数据 里面有数据，并且为其加入了新的数据，并且将所有的数据都放到 数组的第j个节点所在的位置对应的内容中
                            if (loTail != null) { 
                                loTail.next = null;
                                newTab[j] = loHead;
                            }
                            // 如果历史有数据，则将数据放入到 j+oldCap 这个位置上，为了解决节点hash冲突而存在的一个机制，这里是放到for循环中所以说这个是解决Hash冲突的一个问题。
                            if (hiTail != null) { 
                                hiTail.next = null;
                                newTab[j + oldCap] = hiHead;
                            }
                        }
                    }
                }
            }
            // 最终返回一个新的数组。而这个数组会根据具体的条件产生 ，继续返回到putVal()方法中
            return newTab;
        }

### treeifyBin() ###

进入到节点到树的操作

/** * Replaces all linked nodes in bin at index for given hash unless * table is too small, in which case resizes instead. */
         // 说明传入的值是tab 数组 和 hash
        final void treeifyBin(Node<K,V>[] tab, int hash) { 
            int n, index; Node<K,V> e;
            // 判断tab是否为空 或者是 长度是否小于MIN_TREEIFY_CAPACITY 这个值是 64，这个被称为是最小树形化参数 ，为什么会有这个判断？链表转换红黑树跟tab 的长度没有关系，为什么会有这样一个判断？带着这个问题继续往下分析
            if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            	// 调用了一个扩容操作，其实这个地方就是为了使用其中的一个split方法。因为此时的链表还没有达到那个程度，想象一个极端的场景，通过上面的分析我们知道了，key值不重复，在一定程度上可以避免hash冲突，假设从1到100000来设置key值，会出现什么结果。假设而已。下面就来分析。在上面的分析中知道 resize()方法中再对 扩容操作的时候其实将数组中存入的都是链表的头节点。如果上面这个情况出现的话就会出现一种情况。GC图如下
                resize();
            // 如果上面条件不满足 也就是说 两个条件都不满足。
            // 这里的 n 代表的是长度 做了减一操作 然后与hash做对比。最后看是否在存在。
            // 理解一下，如果该位置没有值 就不处理了以为看到这个条件结束之后没有其他的处理逻辑
            // 第二点，到了这里一般拿到的位置都是有值的，那么这个值如何处理 
            else if ((e = tab[index = (n - 1) & hash]) != null) { 
            	// 当上面的长度条件不满足的时候也就是说 tab的长度大于 64 之后进入一个树形化的操作，
            	// 首先会看到 e 节点 获取到的hash位置的值。
                TreeNode<K,V> hd = null, tl = null;
                do { 
                    // 替换为树节点，可见上面的分析中 p 为啥变成TreeNode是有原因的。下面这个地方就是将元素替换为TreeNode。 思考一个场景，如果这个地方有1千万的数据，并且hashcode不冲突，那么就会出现下面这个转换场景。
                    TreeNode<K,V> p = replacementTreeNode(e, null);
                    // 这里tl是做什么用的，还记的，在扩展的时候loTail 的作用么，功能类似就是为了记录一下本来的值
                    // 首先会知道第一次进入这个条件的时候这个tl 就是为空
                    // 将转换后的节点赋值给 hd 继续就是
                    if (tl == null)
                    	// 将转换后的值进行赋值
                        hd = p;
                    else { 
                    	// 原来的值也加入到其中。
                        p.prev = tl;
                        // 将 p 节点连接到tl的下一个节点。
                        tl.next = p;
                    }
                    // 最终将 p 节点还给原来的节点
                    // 第一次操作 就会将p的值赋值给 tl ，这个时候 看看 e 节点的下一个节点是否为空。
                    // 根据上面的场景来看，其实这个地方 1千万的数据如果没有重复的HashCode也就表示这个条件其实是不成立的，e节点下面没有next。这个循环只执行了一次。那么将这个节点转换为 TreeNode之后，就会进入到下一次的操作，下一次的操作就继续往第65 个长度放值。继续分析
                    tl = p;
                    // 上面这个操作成立的条件就是 e 存在下一个节点，也就是将整个链表做转换操作
                } while ((e = e.next) != null);
                // 做完有序排列后这个地方会被操作，判断hd 是否是index索引位置的node，并且是否为空。
                // 根据上面的条件可以看到 index = (n - 1) & hash] 这个操作 就是同一个，也就会进入到方法中。
                if ((tab[index] = hd) != null)
                	//会看到上面的所有的转换做成功之后，进行的就是构建的操作将tab上的index位置的设置为hd，整个的tab放入到了 treeify的方法中，需要注意的就是这个条件成立的基础。tab的长度大于64，假设是65，那么 一个无HashCode冲突的数据进入之后，得到的 index 值是 就是对应的hashCode，因为我们知道tab的长度一定是比实际存储的数据要大的。这个时候， replacementTreeNode(e, null);操作是对 e节点进行了一个深拷贝操作，包括所有的节点内容都是原来的，只不过就是结构发生了变化。也就是是将原来的位置的节点设置成了 TreeNode。从这个角度上看，是将所有大于 64 的部分全部用这个逻辑来进行处理。那么继续分析。
                    hd.treeify(tab);
            }
        }

测试程序代码如下。

HashMap<Integer,Object> hashMap = new HashMap<>();
      for (int i = 0; i <100000000 ; i++) { 
         hashMap.put(i,i);
      }
      System.out.println(hashMap.size());

上面场景的GC图

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz_size_16_color_FFFFFF_t_70 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz_size_16_color_FFFFFF_t_70 2]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz_size_16_color_FFFFFF_t_70 3]

![在这里插入图片描述][20200703134831164.png]  
  停止之后实际物理机内存变化使用变化。  
![在这里插入图片描述][202007031349115.png]  
  通过上面的分析可以知道，根据上面的分析可以知道如果在key不存在hash冲突的时候就不会启动链表，也就没有具体的链表到红黑树的转换过程。从而导致了这个现象。那么根据我们对于hash冲突的理解，就是当这个tab中的key出现 n-1&hash 值相同的时候就是hash冲突。那么就来看看下面这种情况  
  当我们把下面代码循环次数从1 到100000000不断扩大的时候，在7个零的时候都没有问题，在8个零的时候就有问题了。那么这个问题到底出现在table还内部的TreeNode或者是链表呢。

HashMap<Object,Object> hashMap = new HashMap<>();
      for (int i = 0; i <100000000 ; i++) { 
         hashMap.put("s"+i,i);
      }
      System.out.println(hashMap.size());

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz_size_16_color_FFFFFF_t_70 4]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz_size_16_color_FFFFFF_t_70 5]  
  分析问题症结所在其实问题还是出现在这个HashCode上，上面的操作在HashCode上是一个规律性的增长操作并没有一个合适的操作组合出现key不同的情况，而在判断的时候我们看到一个判断  
(k = p.key) == key || (key != null && key.equals(k))) 这个判断 最终的意义我们也了解就是判断hashcode 以及key的值是否相同。这里我们测试如下的一个代码，这段代码的神奇之处就在于它的这个组合保证了s和d两个字符串的hashCode 是一样的，但是字符串本身是不一样的。这个是根据String类型对于HashCode重写推算出来的。当然我们可以根据这个思路来实现一个新的内容。

String s ="Ea";
    
        String d ="FB";
    
        HashMap<String,Integer> hashMap= new HashMap<>();
        hashMap.put(s,1);
        hashMap.put(d,2);
        System.out.println(hashMap.size());

根据上面的启示构建了如下的测试代码

public class Test { 
        private static int hash = 0;
        public static void main(String[] args) { 
            HashMap<String,Integer> hashMap= new HashMap<>();
            for (int i = 0; i < 100000000 ; i++) { 
                String s1 = generateShortUUID();
                String s2 = generateShortUUID();
                int hash1 = hashCode(s1.toCharArray());
                int hash2 = hashCode(s2.toCharArray());
                if (hash1 == hash2) { 
                    hashMap.put(s1, 1);
                }
            }
            System.out.println(hashMap.size());
        }
        public static int  hashCode(char[] value) { 
            int h = hash;
            if (h == 0 && value.length > 0) { 
                char val[] = value;
    
                for (int i = 0; i < value.length; i++) { 
                    h = 31 * h + val[i];
                }
                hash = h;
            }
            return h;
        }
        public static String[] chars = new String[] {  "a", "b", "c", "d", "e", "f",
                "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s",
                "t", "u", "v", "w", "x", "y", "z", "0", "1", "2", "3", "4", "5",
                "6", "7", "8", "9", "A", "B", "C", "D", "E", "F", "G", "H", "I",
                "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V",
                "W", "X", "Y", "Z" };
        public static String generateShortUUID() { 
            StringBuffer shortBuffer = new StringBuffer();
            String uuid = UUID.randomUUID().toString().replace("-", "");
            for (int i = 0; i < 8; i++) { 
                String str = uuid.substring(i * 4, i * 4 + 4);
                int x = Integer.parseInt(str, 16);
                shortBuffer.append(chars[x % 0x3E]);
            }
            return shortBuffer.toString();
        }

在之前线性扩展的过程中7个零的速度是非常快的并且最后打印出来的结果值是10000000，但是使用了上面这种方式的时候，当扩展增加到7个零的时候比之前的耗时要严重。  
**7个零**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz_size_16_color_FFFFFF_t_70 6]  
  在8个零的时候也没有像之前的哪个样子出现一个整个的老年代被直接占满的情况。而是一个线性增加的过程。  
**8个零**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz_size_16_color_FFFFFF_t_70 7]

### treeify() ###

/** * Forms tree of the nodes linked from this node. * @return root of tree */
            final void treeify(Node<K,V>[] tab) { 
            	// 传入的是数组，这个地方从上面的内容中其实可以看到传入的就是原有的tab
            	// 根据上面的分析思路，这里传入的就是一个64 节点的数组，那么第65 个节点，进入之后，就会进入这个逻辑中。
                TreeNode<K,V> root = null;
                // 首先来初始化 拿到的树是不是当前需要操作的树也就是上面的hd，以及next节点 x 表示hd
                // 这里的this 就是上面的 hd 。我们知道这个hd 其实是没有next的，也就是说 这里的循环只执行了一次
                for (TreeNode<K,V> x = this, next; x != null; x = next) { 
                	// 到这里可以知道其实就是节点链表到树结构的转换 那么tab在什么地方使用呢？
                	// 就是为了定位在数组中那些节点需要进行操作。
                	// 由于没有next 所以说 next 为null；
                    next = (TreeNode<K,V>)x.next;
                    x.left = x.right = null;
                    // 根节点为空的话
                    if (root == null) { 
                    	// x 就是根节点，也就是说这里 这个 65 就是这个65 这个位置树的根节点。
                        x.parent = null;
                        x.red = false;
                        root = x;
                    }
                    // 如果不为空，这里我们就拿一个极端的例子来分析，还是 65 那么这里就不会执行这个步骤
                    else { 
                    	// 否则 就进行操作了
                    	// 首先拿到的key 并且获取到k的hash值
                        K k = x.key;
                        int h = x.hash;
                        // k了类对象
                        Class<?> kc = null;
                        // 进入死循环这里需要注意循环结束的条件
                        for (TreeNode<K,V> p = root;;) { 
                            int dir, ph;
                            
                            K pk = p.key;
                            // 这里的h是x的hash值，ph则是当前节点的hash值，也就是说这个数据的转换其实是一个hash 值的比较
                            if ((ph = p.hash) > h)
                            	// 这个操作主要是用来做红黑树平衡用的。
                                dir = -1;
                            else if (ph < h)
                            	
                                dir = 1;
                            // 进行 判断比较
                            // kc == null Kc为空 && 判断也就是说这个条件与第二个条件需要全部满足。
                            // (kc = comparableClassFor(k)) == null)
                            // 第三个条件与第一个条件和第二个条件的产生的结果做 || 运算
                            // (dir = compareComparables(kc, k, pk)) == 0
                            // 这里条件满足之后进行的操作就是 tieBreakOrder(k, pk);
                            else if ((kc == null &&
                                      (kc = comparableClassFor(k)) == null) ||
                                     (dir = compareComparables(kc, k, pk)) == 0)
                                     
                                dir = tieBreakOrder(k, pk);
    						// 最终，进入到下面这个逻辑
                            TreeNode<K,V> xp = p;
                            // 进行遍历 将 拿到的x全部放入到构建好的树里面 条件不成立的时候进行一个平衡操作
                            if ((p = (dir <= 0) ? p.left : p.right) == null) { 
                            	// 
                                x.parent = xp;
                                if (dir <= 0)
                                    xp.left = x;
                                else
                                    xp.right = x;
                                root = balanceInsertion(root, x);
                                break;
                            }
                        }
                    }
                }
                // 进行一个转换 这个时候用到了 tab 
                moveRootToFront(tab, root);
            }

### moveRootToFront() ###

移动根到头

/** * Ensures that the given root is the first node of its bin. */
            static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) { 
                int n;
                // 传入的参数是数组和红黑树节点，这个地方继续插入65 ，
                // 判断 条件所有的都成立
                if (root != null && tab != null && (n = tab.length) > 0) { 
                	// 条件成立 找到索引位置 这里使用的是根节点的hash值。n还是数组的长度。
                	// 这里的index就应该是 65，
                    int index = (n - 1) & root.hash;
                    // 将索引位置的 Node 强转为 TreeNode 
                    // 将TreeNode的第一个节点转换为 第 65 位置的节点
                    TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
                   	// 从上面看 65 这个操作进来之后这个操作其实是一样的。由于65 这个操作进入之后没有冲突，也没有转换，所以说hash是一样的，root 是对65进行了拷贝，所以说这个结果一定是成立的，那么这里判断是不成立。所以说代码不会执行，那么什么情况会出现这个结果不一致，进入到这个判断中呢？首先tab 的index位置的值在什么情况下会发生变化。就是进入到了上面那个方法的else中。那么此时的65其实是没有进行操作的，所以说放入的操作还是继续用tab
                    if (root != first) { 
                        Node<K,V> rn;
                        // 将root 放到了 tab的index位置
                        tab[index] = root;
                        //将根 的记录操作节点 rp 而prev的含义就是 TreeNode 的临时连接存在 TreeNode<K,V> rp = root.prev;
                        // 这里到这里有一个大胆的猜测，就是TreeNode不但有红黑树的特点还有链表的特点。是这样么？
                        if ((rn = root.next) != null)
                        	// 判断了root的next 这个时候有点难以理解的就是root为什么会有next并且不为空的判断？ 
                        	// 这里做的操作就是把 root.next.pre指针指向了 root.pre 所指向的内容
                            ((TreeNode<K,V>)rn).prev = rp;
                        if (rp != null)
                        	//如果 rp不为空 则将rp.next 指向rn
                            rp.next = rn;
                        if (first != null)
                        	// 如果 first不为空 将 frist.prev 指向 root
                            first.prev = root;
                        // 最终转换完成之后，进行 root.next = first 的操作 这里我们知道first是通过根节点的hash值计算出来的链表中的位置。其整个作用就是将红黑树调整的数组的合适位置上。 
                        root.next = first;
                        root.prev = null;
                    }
                    assert checkInvariants(root);
                }
            }

/** * Splits nodes in a tree bin into lower and upper tree bins, * or untreeifies if now too small. Called only from resize; * see above discussion about split bits and indices. * * @param map the map * @param tab the table for recording bin heads * @param index the index of the table being split * @param bit the bit of hash to split on */
             // 将树容器中的节点拆分为较低和较高的树容器，如果现在太小，则取消搜索。仅从resize调用
            final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) { 
            	// 这个方法属于 TreeNode的方法，首先this就是需要操作的节点，就是上面内容中满足条件的节点。那么它具体有什么样的作用？这个拆分到底有什么样的效果。
                TreeNode<K,V> b = this;
                // Relink into lo and hi lists, preserving order
                // 重新连接到lo 和 hi 的列表中，保持顺序
                TreeNode<K,V> loHead = null, loTail = null;
                TreeNode<K,V> hiHead = null, hiTail = null;
                int lc = 0, hc = 0;
                // 遍历 TreeNode ，既然这样，还是65 放入之后这个节点就只有一个元素，它所对应的next还是null
                for (TreeNode<K,V> e = b, next; e != null; e = next) { 
                	// next 为null
                    next = (TreeNode<K,V>)e.next;
                    // e 节点的next也为null；
                    e.next = null;
                    // 这里就 e 的hash 和bit 做了 & 运输是否为0 那么 1100 和 1111 做 & 结果是什么呢？ 1100 ，bit 是传入的for循环中j 的值。j的范围是老的容量。那么当65 进入之后，与65 进行&操作 还是 65，那么进入到这个循环的条件是第j个位置有数据，并且是TreeNode，上面的内容分析中可以知道这个条件都满足，也就是说进入了，并且，这个& 操作也不是0 也就是说进入不到下面这个操作中。
                    if ((e.hash & bit) == 0) { 
                        if ((e.prev = loTail) == null)
                            loHead = e;
                        else
                            loTail.next = e;
                        loTail = e;
                        ++lc;
                    }
                    // 65 的操作进入到这里
                    else { 
                        // e节点的prev指针指向了hiTail 这个时候这个条件都是null也就是第一个判断就成功了。
                        // 那么hiHead 就是 e 了也就是65. 到这里会看到其实如果是顺序key的话并不适合与这种场景，如果是顺序key的话可以考虑其他数据结构，如果非要是以中KV形式来存储的话，这个性能其实并不是最高效的。
                        if ((e.prev = hiTail) == null)
                            hiHead = e;
                        else
                            hiTail.next = e;
                        // 最终会发现其实 hiTail也是 e 65 最终到这里就结束了
                        hiTail = e;
                        ++hc;
                    }
                }
    			// 那么 如果没有特殊策略进来的话在64 以后对于进入到其中的数据会强制转换。
    			// 分别表示,表示低部分容器
                if (loHead != null) { 
                    if (lc <= UNTREEIFY_THRESHOLD)
                        tab[index] = loHead.untreeify(map);
                    else { 
                        tab[index] = loHead;
                        if (hiHead != null) // (else is already treeified)
                            loHead.treeify(tab);
                    }
                }
                // 表示高部分容器
                if (hiHead != null) { 
                    if (hc <= UNTREEIFY_THRESHOLD)
                        tab[index + bit] = hiHead.untreeify(map);
                    else { 
                        tab[index + bit] = hiHead;
                        if (loHead != null)
                            hiHead.treeify(tab);
                    }
                }
            }

## 总结 ##

从源码的阅读中，可以看到其实我们都不是真的懂HashMap的真的消耗性能在什么地方。如果我们真的懂了，应该是合理的组合，让这个HashMap性能用到极致。什么是极致。就是由一万个长度的HashMap，table的长度如果是一万的话，至少我们可以高效利用让其存储一百万的数据。而不是研究第一个元素怎么把它放入。当然我们要了解第一个元素的放入，而不是纠结第一个元素怎么放入。这个是第一点。

第二点，我们真的了解table的解决冲突的机制么？难道真的就是数组加链表或者是数组加红黑树么？有没有更加优化的地方等待我们探索呢？其实这三个点我们都只是略懂皮毛，来说你精通Java，来写个JVM出来。写不出来。保证一个HashMap都写不出来。怎么在用到极致的过程中产生出自己的方法论，到底这个HashMap怎么使用才能更高效。或者像是LinkHashMap一样可不可以继承HashMap实现自己的扩展高效Map。这个研究才有意义。

第三点，面试官自已以为自己了解到够深刻，其实不然，这个世界上知识很多，其实没有必要找一个航天工程师来给你打扫卫生。航天工程师其实还有他其他的作用。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200703134623417.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200703134256502.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200703134442745.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200703134730548.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz,size_16,color_FFFFFF,t_70
[20200703134831164.png]: https://img-blog.csdnimg.cn/20200703134831164.png
[202007031349115.png]: https://img-blog.csdnimg.cn/202007031349115.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200703135950933.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200703140224958.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200703144031192.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/2020070314415858.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz,size_16,color_FFFFFF,t_70