HashMap源码之put方法详解

　　HashMap没有直接提供putVal接口给用户调用，而实提供put接口，而他通过putVal来实现插入元素。
　　public V put(K key, V value) {     return putVal(hash(key), key, value, false, true); }   /**      *      * @param hash         指定参数key的哈希值      * @param key          指定参数key      * @param value        指定参数value      * @param onlyIfAbsent 如果为true，即使指定参数key在map中已经存在，也不会替换value      * @param evict        如果为false，数组table在创建模式中      * @return 如果value被替换，则返回旧的value，否则返回null。当然，可能key对应的value就是null。      */    public V put(K key, V value) {     return putVal(hash(key), key, value, false, true); }  // 参数解析：onlyIfAbsent表示，如果为true，那么将不会替换已有的值，否则替换 // evict：该参数用于LinkedHashMap，这里没有其他作用（空实现） final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                    boolean evict) {     // tab是该方法中内部数组引用，p是数组中首节点，n是内部数组长度，i是key对应的索引下标     Node[] tab; Node p; int n, i;     // 第一次put的时候，table未初始化，也就是tab为空，需要扩容     if ((tab = table) == null || (n = tab.length) == 0)     	// 这里实现扩容，具体逻辑稍后分析         n = (tab = resize()).length;     // 获取指定key的对应下标的首节点并赋值给p，如果首节点为null，那么创建一个新的Node节点作为首节点     if ((p = tab[i = (n - 1) & hash]) == null)         tab[i] = newNode(hash, key, value, null);     else {         Node e; K k;         if (p.hash == hash &&             ((k = p.key) == key || (key != null && key.equals(k))))             // p此时指向的是不为null的首节点，将p赋值给e             // 如果首节点的key和要存入的key相同，那么直接覆盖value的值（在下一个if中执行的）             e = p;         else if (p instanceof TreeNode)         	// 如果首节点是红黑树的，将键值对插添加到红黑树，该方法后续分析             e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);         else {         	// 能走到这里，说明首节点和新put的的这个节点的key不一样，且该Node节点不是TreeNode类型         	// 开始需要遍历链表，如果链表中存在该键值对，直接覆盖value。         	// 如果不存在，则在末端插入键值对。然后判断链表长度是否大于等于8（其实就是遍历次数 + 1），         	// 尝试转换成红黑树。注意此处使用＂尝试＂，因为在treeifyBin方法中还会判断         	// 当前哈希表长度是否到达64，如果达到，转换为红黑树，否则会放弃次此转换，优先扩充数组容量。             for (int binCount = 0; ; ++binCount) {             	// 当binCount = 0时，也就是第一次if判断，此时p就是首节点，p.next就是第二个节点             	// 其他情况及时链表中其他节点，当e == null的时候，也就是到达了链表的结尾                 if ((e = p.next) == null) {                 	// 新建一个Node并作为链表的最后一个节点                     p.next = newNode(hash, key, value, null);                     // 判断遍历次数是否>=7（首节点未遍历，直接从第二个节点开始遍历的，当次数为7时，说明链表长度为8）                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                     	// ＂尝试＂将链表转换为红黑树，内部还会判断哈希表长度，不一定转换成功，也许是扩容                         treeifyBin(tab, hash);                     break;                 }                 // 只要没走到上面那个if里面，说明链表没有遍历结束，如果在链表中间发现有key一样的，那么就直接将旧值替换成新值                 if (e.hash == hash &&                     ((k = e.key) == key || (key != null && key.equals(k))))                     break;                 // 将正在遍历的节点赋值给p，方便能遍历下一个节点                 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;     if (++size > threshold)     	// 如果满足扩容条件，就扩容         resize();     afterNodeInsertion(evict);     return null; }  //链表转化为红黑树的方法 final void treeifyBin(Node[] tab, int hash) {     int n, index; Node e;     // 在这里判断是否满足扩容条件，如果满足就扩容     if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)         resize();     else if ((e = tab[index = (n - 1) & hash]) != null) {     	// 到这里开始遍历链表         TreeNode hd = null, tl = null;         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);         // TreeNode链表转换成为红黑树         if ((tab[index] = hd) != null)             hd.treeify(tab);     } }
　　在JDK8之后引入了红黑树，当哈希表的桶中链表元素超过8个的时候（此时哈希表长度不小于64），会自动转换成红黑树。若桶中元素小于等于6时，树结构还原成链表形式。
　　红黑树的平均查找长度是log(n)，长度为8，查找长度为log(8)=3，链表的平均查长度为n/2，当长度为8时，平均查找长度为8/2=4，这才有转换成树的必要；链表长度如果是小于等于6，6/2=3，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。以6和8来作为平衡点是因为，中间有个差值7可以防止链表和树之间频繁的转换。
　　假设，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。概括起来就是：链表：如果元素小于8个，查询成本高，新增成本低，红黑树：如果元素大于8个，查询成本低，新增成本高。