????HashMap的重要性就不多說了，經(jīng)常用到渤弛，面試也很喜歡問，所以有必要研究下。
HashMap結(jié)構(gòu)1.png
????當(dāng)調(diào)用put方法往HashMap存入數(shù)據(jù)時，HashMap的數(shù)據(jù)分布可能如下，需要注意的是齐婴，數(shù)組里面裝的元素是一個節(jié)點，Node類型或者TreeNode型；這種類型包裝了我們傳進(jìn)來的鍵值對key ---> value：
HashMap結(jié)構(gòu)2.png
????可以看到，這些數(shù)據(jù)不一定是連續(xù)的匀哄；那么這些數(shù)據(jù)是怎么確定放在數(shù)組的哪個桶的呢？這就要借助于hash算法了法梯，當(dāng)一個數(shù)據(jù)要存入HashMap時，拿鍵的hash值與數(shù)組長度 - 1做與運算，即：
(n - 1) & hash
????其中n是數(shù)組長度捂掰，hash是key的hash鸥昏。
????當(dāng)存入的數(shù)據(jù)很多時敛腌，每個key之間的hash值可能就一樣了像樊，不同的key也可能產(chǎn)生不同的hash值；如果hash值一樣的話涂滴，那么根據(jù)上面的公式柔纵，桶的位置也就一樣了；一個桶裝多個數(shù)據(jù)或详，怎么辦霸琴？
HashMap結(jié)構(gòu)3.png
????如上圖所示枝笨，如果E的hash和X的hash值相等，那么就發(fā)生了hash沖突，這時候把X連在E的后面徙融；對于一個HashMap來說洒缀，碰撞發(fā)生的越少树绩，查找效率就越高饺饭；因為碰撞太多的話瘫俊，這個鏈表就越長(或者紅黑樹越高)悴灵，這樣在get數(shù)據(jù)的時候就需要遍歷鏈表或者紅黑樹，這樣就降低了效率胸哥；總之空厌，數(shù)據(jù)分布越均勻银酬，查找效率越高揩瞪。
????當(dāng)鏈表的長度過長時李破，HashMap就會把鏈表轉(zhuǎn)換成紅黑樹：
HashMap結(jié)構(gòu)4.png
????鏈表轉(zhuǎn)換成紅黑樹的過程叫做樹化(下篇文章會分析)；當(dāng)鏈表的節(jié)點快速增加時毛嫉，會造成搜索效率的降低承粤，而紅黑樹能夠解決搜索效率問題，所以樹化就出現(xiàn)了仙粱。
????廢話不多說彻舰，直接上源碼刃唤，先看類信息和構(gòu)造函數(shù)：
//繼承自AbstractMap透揣，實現(xiàn)了Map辐真、Cloneable和Serializable接口
//AbstractMap是一個實現(xiàn)了Map接口的抽象類，他對Map接口進(jìn)行了有限
//的擴(kuò)展侍咱，同時實現(xiàn)了部分接口方法楔脯，比如size()胯甩、clear()偎箫、hashCode()等
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
/**
* The default initial capacity - MUST be a power of two.
*/
//HashMap的默認(rèn)初始化容量16淹办，這個容量比如是2的n次冪
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.
*/
//HashMap的最大容量，2的30次冪
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
*/
//HashMap的默認(rèn)加載因子速挑，加載因子的作用是判斷是不是需要擴(kuò)容了
//比如初始容量是16姥宝，加載因子是0.75，16 * 0.75 = 12伶授，也就是說
//當(dāng)HashMap里面的元素個數(shù)達(dá)到12個的時候就需要對HashMap進(jìn)行擴(kuò)容了
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.
*/
//當(dāng)鏈表中的節(jié)點達(dá)到8個時违诗，就將鏈表轉(zhuǎn)換成紅黑樹
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.
*/
//當(dāng)紅黑樹的節(jié)點數(shù)量小于等于6時疮蹦，將紅黑樹轉(zhuǎn)換成鏈表
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.
*/
//鏈表轉(zhuǎn)換成樹的必要條件之一愕乎，除了上面的閾值判斷之外，還會判斷HashMap的容量
//只有容量大于64的時候绅项，才會轉(zhuǎn)換比肄；小于這個值時芳绩，HashMap寧愿選擇擴(kuò)容妥色，而不是
//樹化建立初期，多個鍵值對放入同一個鏈表中而導(dǎo)致不必要的轉(zhuǎn)換
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* 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.)
*/
//注釋比較簡單撮竿，自己看幢踏。HashMap里面的數(shù)據(jù)首先是存放在數(shù)組里面
//的長度不夠的時候惑折，我們可以擴(kuò)容惨驶，這個容量都是2的n次冪粗卜，transient
//代表該變量無法被序列化(HashMap本身是實現(xiàn)了序列化接口的)
transient Node<K,V>[] table;
/**
* The number of key-value mappings contained in this map.
*/
//size代表該Map里面鍵值對的個數(shù)纳击，其實就是HashMap的元素個數(shù)
transient int size;
/**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
//擴(kuò)容閾值，當(dāng)HashMap里面的元素個數(shù)達(dá)到這個值的時候就必須
//擴(kuò)容了刨啸，這個值是由容量*加載因子確定的，默認(rèn)的加載因子是0.75
int threshold;
/**
* The load factor for the hash table.
*
* @serial
*/
//加載因子
final float loadFactor;
/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
transient int modCount;
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
//構(gòu)造函數(shù)，開發(fā)中直接調(diào)用這個構(gòu)造函數(shù)的比較少离例，這個構(gòu)造函數(shù)指定了默認(rèn)
//容量和加載因子
public HashMap(int initialCapacity, float loadFactor) {
//安全判斷悉稠，簡單
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
/**
* 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.
*/
//只指定默認(rèn)容量的構(gòu)造函數(shù)耀盗，加載因子還是用默認(rèn)的0.75
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
//這種構(gòu)造函數(shù)用的最多袍冷，什么都是默認(rèn)的
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
* Constructs a new <tt>HashMap</tt> with the same mappings as the
* specified <tt>Map</tt>. The <tt>HashMap</tt> is created with
* default load factor (0.75) and an initial capacity sufficient to
* hold the mappings in the specified <tt>Map</tt>.
*
* @param m the map whose mappings are to be placed in this map
* @throws NullPointerException if the specified map is null
*/
//根據(jù)一個Map構(gòu)造一個HashMap
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
}
