HashMap实现原理分析-resize()详解_hashmap resize原理

为什么会有resize()方法

介绍resize() 方法前先了解一下Java为什么会有resize()方法，他的作用是什么，我们有一个默认认知是，HashMap的get查找的复杂度是O(1)的，那么如果初始散列表大小是16，加载因子是0.75的话，如果数据量过多（例如256），按照拉链法，每一个bucketIndex位置上的单链表的长度都会很长（并触发上节所贴代码的红黑树转化），在单链表中查找元素的复杂度为O(n),几乎远远不能达到O(1)的性能，在hashMap的情景中优化O(n) 的方式就是使n足够小，即BucketIndex碰撞的机会足够小。那么我们就需要加大散列表的长度，使key的hashCode计算出的bucketIndex均匀分散，所以java中使用了resize() 方法拉大散列表。

*hash碰撞的时候，Java8把链表替换成了TreeMap，使得查询性能提升为O(logN)，这个值为8，即链表长度为8时，将转换链表为TreeMap。

我们先看看Java中hashMap的各成员变量，先忽略与树有关的部分。

     /**
     * The default initial capacity - MUST be a power of two.
	 * 箱子的个数不能太多或太少。如果太少，很容易触发扩容，如果太多，遍历哈希表会比较慢。
     */
    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的30次方  
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;
 
    /**
     * The load factor used when none specified in constructor.
	 * 默认加载因子0.75  
     */
    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.
	 *如果哈希函数不合理，即使扩容也无法减少箱子中链表的长度，因此 Java 的处理方案是当链表太长时，转换成红黑树。这个值表示当某个箱子中，链表长度大于 8 时，有可能会转化成树。
     */
    static final int TREEIFY_THRESHOLD = 8;
 
    /**
     * The bin count threshold for untreeifying a (split) bin during a
     * resize operation. Should be less than T