hashMap get put resize方法源码解析

hashMap源码学习

简单介绍一下hashMap，hashMap的顶级父类接口为Map为key-value存贮，在在根据key查找单个元素时时间复杂度为ON（1），但是不能保证元素顺序，即元素存进去和取出来的顺序不一致，在jdk1.7采用数组+链表实现线程不安全，但是在大量存贮元素时可能会出现某种极端情况，链表过长(或元素全部存贮到一条链表上)，查找元素变慢；在jdk1.8时为了解决这个问题，hashMap底层使用了数组+链表+红黑树的方式实现，当链表元素过长时jdk将会把链表转化为红黑树来增加查找速率，但1.8的hashMap仍然不是线程安全的。

为什么jdk1.8采用红黑树而不采用其他的树：

而二叉树在有种极端情况，所有元素全部存储到树的一边上，这样的话树在查找某个元素时就和链表类似，没有体现出树的优势，而二叉树是一种平衡二叉树，树的左右子树高度相差不超过一，超过时通过左旋或右旋调整。

参考https://juejin.cn/post/6844903519632228365#comment

下面我们来看一下具体jdk1.8底层是怎么实现的：

静态变量

静态变量来定制hashMpa中一些规范如：初始容量、扩容阈值等

    /**
     * The default initial capacity - MUST be a power of two.
     * 默认初始容量-必须是2的幂。
     * 初始容量
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     * 如果隐式指定了更高的值，则使用最大容量由带有参数的构造函数之一执行。
     * 必须是2的幂<=1<<30。
     * HashMap的最大容量
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * The load factor used when none specified in constructor.
     * 构造函数中未指定时使用的负载系数
     * 容量到达容器的0.75时HashMap将会进行扩容操作
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * The bin count threshold for using a tree rather than list for a
     * bin.  Bins are converted to trees when adding an element to a
     * bin with at least this many nodes. The value must be greater
     * than 2 and should be at least 8 to mesh with assumptions in
     * tree removal about conversion back to plain bins upon
     * shrinkage.
     * 对于bin使用树而不是列表的bin计数阈值。将元素添加到具有至少这么多节点的bin时，
     * bin将转换为树。该值必须大于2，并且至少应为8，
     * 以便与树木移除中关于收缩时转换回普通箱的假设相匹配
     * 
     * 当链表长度超过8时HashMap会将链表转换为红黑树
     * HashMap会优先将数组扩容到64时才会进行红黑树的转化
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * The bin count threshold for untreeifying a (split) bin during a
     * resize operation. Should be less than TREEIFY_THRESHOLD, and at
     * most 6 to mesh with shrinkage detection under removal.
     * 在调整大小操作过程中取消筛选（拆分）垃圾箱的垃圾箱计数阈值。
     * 应小于TREEIFY_THRESHOLD，最多为6，以便在移除时进行收缩检测
     * 
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * The smallest table capacity for which bins may be treeified.
     * (Otherwise the table is resized if too many nodes in a bin.)
     * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
     * between resizing and treeification thresholds.
	 * 可将箱子树化的最小工作台容量。
	 *（否则，如果bin中的节点过多，将调整表的大小。）
	 * 应至少为4*TREEIFY_THRESHOLD以避免冲突
	 * 在调整大小和树化阈值之间。
	 * 
	 * 当数组长度到达64时且链表长度大于等于8时链表转换为红黑树
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

构造方法及相关属性

	//初始无参构造
	//Constructs an empty HashMap with the default initial capacity (16) and the default load factor (0.75).
	//使用默认初始容量（16）和默认负载因子（0.75）构建一个空的HashMap
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }



    /**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and the default load factor (0.75).
     *
     * @param  initialCapacity the initial capacity.
     * @throws IllegalArgumentException if the initial capacity is negative.
     */
	//使用指定的初始容量和默认负载因子（0.75）构造空HashMap。 
	//参数: initialCapacity–初始容量。 
	//抛出: IllegalArgumentException–如果初始容量为负数
	//构造一个含有初始容量的HashMap
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }


    /**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and load factor.
     *
     * @param  initialC