JKD1.8 hashmap源码分析

“道可道，非常道；名可名，非常名。
无名，万物之始，有名，万物之母。
故常无欲，以观其妙，常有欲，以观其徼。
此两者，同出而异名，同谓之玄，玄之又玄，众妙之门。” ^1

Nosql的鼻祖往前追朔在Java这一支是要落到HashMap的头上的。关于HashMap，jdk1.8和之前的版本相比有较大的改动。在JDK1.8之前，HashMap采用数组+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。而JDK1.8中，HashMap采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。

先来看一下 HashMap 的继承图：

HashMap 根据键的 hashCode 值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap 最多只允许一条记录的键为 null ，允许多条记录的值为 null 。HashMap 非线程安全，即任一时刻可以有多个线程同时写 HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap 方法使 HashMap 具有线程安全的能力，或者使用ConcurrentHashMap 。
#####HashMap 存储结构
HashMap是数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的，链表和红黑树都是为了优化hash值冲突而实行的优化方案，当链表的长度大于8时链表将转换成红黑树，如下图所示：

#####HashMap 各常量、成员变量作用　

/**
     * The table, initialized on first use, and resized as
     * necessary. When allocated, length is always a power of two.
     * (We also tolerate length zero in some operations to allow
     * bootstrapping mechanics that are currently not needed.)
     * table就是存储Node类的数组
*/  
transient Node<K,V>[] table;  

/**
  * The number of key-value mappings contained in this map.
  *  记录hashmap中存储键-值对的数量
  */  
transient int size;  

/**
  * hashmap结构被改变的次数，fail-fast机制
  */  
transient int modCount;  

    /**
     * The next size value at which to resize (capacity * load factor).
     * 扩容的门限值，当size大于这个值时，table数组进行扩容
     */  
    int threshold;  

    /**
     * The load factor for the hash table.
     *
     */  
 float loadFactor;  
/**
     * The default initial capacity - MUST be a power of two.
     * 默认初始化数组大小为16
     */  
    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.
     */  
    static final int MAXIMUM_CAPACITY = 1 << 30;  

    /**
     * The load factor used when none specified in constructor.
     * 默认装载因子，
     */  
    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.
     * 这是链表的最大长度，当大于这个长度时，链表转化为红黑树
     */  
    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.
     */  
    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.
     */  
    static final int MIN_TREEIFY_CAPACITY = 64;

1	/**
2	* The table, initialized on first use, and resized as
3	* necessary. When allocated, length is always a power of two.
4	* (We also tolerate length zero in some operations to allow
5	* bootstrapping mechanics that are currently not needed.)
6	* table就是存储Node类的数组
7	*/
8	transient Node<K,V>[] table;
9
10	/**
11	* The number of key-value mappings contained in this map.
12	* 记录hashmap中存储键-值对的数量
13	*/
14	transient int size;
15
16	/**
17	* hashmap结构被改变的次数，fail-fast机制
18	*/
19	transient int modCount;
20
21	/**
22	* The next size value at which to resize (capacity * load factor).
23	* 扩容的门限值，当size大于这个值时，table数组进行扩容
24	*/
25	int threshold;
26
27	/**
28	* The load factor for the hash table.
29	*
30	*/
31	float loadFactor;
32	/**
33	* The default initial capacity - MUST be a power of two.
34	* 默认初始化数组大小为16
35	*/
36	static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
37
38	/**
39	* The maximum capacity, used if a higher value is implicitly specified
40	* by either of the constructors with arguments.
41	* MUST be a power of two <= 1<<30.
42	*/
43	static final int MAXIMUM_CAPACITY = 1 << 30;
44
45	/**
46	* The load factor used when none specified in constructor.
47	* 默认装载因子，
48	*/
49	static final float DEFAULT_LOAD_FACTOR = 0.75f;
50
51	/**
52	* The bin count threshold for using a tree rather than list for a
53	* bin. Bins are converted to trees when adding an element to a
54	* bin with at least this many nodes. The value must be greater
55	* than 2 and should be at least 8 to mesh with assumptions in
56	* tree removal about conversion back to plain bins upon
57	* shrinkage.
58	* 这是链表的最大长度，当大于这个长度时，链表转化为红黑树
59	*/
60	static final int TREEIFY_THRESHOLD = 8;
61
62	/**
63	* The bin count threshold for untreeifying a (split) bin during a
64	* resize operation. Should be less than TREEIFY_THRESHOLD, and at
65	* most 6 to mesh with shrinkage detection under removal.
66	*/
67	static final int UNTREEIFY_THRESHOLD = 6;
68
69	/**
70	* The smallest table capacity for which bins may be treeified.
71	* (Otherwise the table is resized if too many nodes in a bin.)
72	* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
73	* between resizing and treeification thresholds.
74	*/
75	static final int MIN_TREEIFY_CAPACITY = 64;