HashMap之putMapEntries、putVal

putMapEntries

putMapEntries使用的是默认修饰符，因此只能被本类或者该包下的类访问到

 /**
     * Implements Map.putAll and Map constructor.
     * 实现了Map.putAll方法 和Map的构造方法
     *
     * @param m the map
     * @param evict false when initially constructing this map, else
     * true (relayed to method afterNodeInsertion).
     * 在构造函数使用的时候是false其他时候是true
     */
    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        //获取传入的map的长度
        int s = m.size();
        if (s > 0) {
        	//当长度大于0才需要处理
            if (table == null) { // pre-size
            	// s/loadFactor 计算传进来的map的长度是否要达到阈值，因为会计算出小数因此+1.0F向上取整
                float ft = ((float)s / loadFactor) + 1.0F;
                //当不大于最大值的时候使用ft的长度
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                //如果大于当前数组下次要扩容的值
                if (t > threshold)
                	//重新计算下次扩容值的大小，在下面putVal方法当中进行map数组的初始化
                    threshold = tableSizeFor(t);
            } else {
                // Because of linked-list bucket constraints, we cannot
                // expand all at once, but can reduce total resize
                // effort by repeated doubling now vs later
                //因为链表桶限制，我们不能一次全部展开，但是我们可以减少总大小，通过立即加倍和以后插入时候加倍。所以在计算扩容限制的时候是通过传入进来的map长度s来与threshold进行对比，而不是通过s+this.size与threshold进行对比，因为s>threshold表示链表肯定长度不够需要立即扩容，而如果小于可以等到遍历插入putVal的时候再去扩容
                while (s > threshold && table.length < MAXIMUM_CAPACITY)
                    resize();
            }

            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            	//遍历赋值
                K key = e.getKey();
                V value = e.getValue();
                putVal(hash(key), key, value, false, evict);
            }
        }
    }

putMapEntries当中注意两点，第一个是当本数组没初始化的时候，是通过((float)s / loadFactor) + 1.0F来进行阈值计算，+1.0F的情况当我们初始化赋值加载因子loadFactor非0.75F的时候可能出现s/loadFactor出现小数，这样+1在强转的时候就能够向上取整。第二点，当数组初始化的时候，我们考虑是否扩容只需要考虑传进来的map的长度s是否超过threshold就行，假如存在s+this.size>threshold也会在下面遍历插入的时候进行扩容

putVal

putval也是使用的默认修饰符，因此只能被本类或者该包下的类访问到

 /**
     * Implements Map.put and related methods.
     * 实现了map的put和相关方法
     * @param hash hash for key key的hash值（key的hash高16位+高16位与低16位的异或运算）
     * @param key the key  键
     * @param value the value to put	值  
     * @param onlyIfAbsent if true, don't change existing value onlyIfAbsent为true的时候不要修改已经存在的值
     * @param evict if false, the table is in creation mode. evict如果为false表示构造函数调用
     * @return previous value, or null if none 返回前一个值，如果没有返回null
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        //定义一个Node数组tab，和一个node节点
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
        	//将table赋值给tab，并且判断tab是否为空，或者长度为0，如果是则扩容(resize)
            n = (tab = resize()).length;
            //计算index用n-1与hash值，同时可以知道为什么hash计算的时候需要将高16位右移到低16位当n-1为15即00000000 00000000 00001111与hash做与运算，那么hash值4位以上的数据就没有意义了，如果不将高位右移这样会导致hash冲突增多，同一位置出现概率过大。
        if ((p = tab[i = (n - 1) & hash]) == null)
        	//直接数组上面新建链表
            tab[i] = newNode(hash, key, value, null);
        else {
        	//如果出现冲突p在上面if中已经赋值，p = tab[i = (n - 1) & hash]
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                //当数组头节点的hash值与传入的hash相等，且p的key与传入的key相等 == 或者equals,就将当前节点赋值给e
                e = p;
            else if (p instanceof TreeNode)
            	//数组元素头节点是TreeNode类型，如果key存在与红黑树当中，就返回key的节点，如果不是则返回要插入的叶子节点
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
            	//遍历寻找是否存在key，如果不存在在最后一个节点插入key，value，存在就返回key的那个节点
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        	//当链表层数达到阈值(第一次的时候为7)链表转换成红黑树
                            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
            	//e存在与链表或者红黑树当中就直接修改
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                //将该节点移到最后，++modCount里面也会+1
                afterNodeAccess(e);
                return oldValue;
            }
        }
        //修改次数+1
        ++modCount;
        if (++size > threshold)
        	//长度超过下次修改值时扩容
            resize();
        afterNodeInsertion(evict);
        return null;
    }

从putVal方法当中，我们可以看到在put的时候首先判断table[(n-1)&hash]是否存在，如果不存在直接新增节点，如果存在取头节点，判断对应的key是否在链表或者红黑树中存在，如果存在就覆盖value值，并且将节点移到最后，如果不存在则在链表的尾节点进行插入，或者红黑树的叶子节点插入。同时根据(n-1)为15的时候001111与hash值与运算，如果不将hash的高16位右移到低十六位进行异或运算，那么高16位在001111这种数做与运算将不起作用，会导致hash冲突过多链表过长
afterNodeInsertion可以参考这份回答，afterNodeInsertion