jdk1.8 HashMap學習（包括分析部分源碼）
- 概述
- 底層結構
-
- 為什麼使用這個結構
- 靜态變量
- 成員變量
- 構造函數
- 關鍵内部類
-
- Node 類
- TreeNode
- 關鍵成員方法
-
- hash方法
- get方法
- put方法
- treeifyBin方法
- putAll方法
- resize方法
- remove方法
- clear方法
- 其他一些成員方法
-
- size方法
- isEmpty方法
- containsKey方法
- containsValue方法
- keySet、 values 和 entrySet方法
- 重寫Map中的方法
- hashmap的IO相關方法
- TreeNode類的分析
概述
HashMap是java集合類中很常用的一個資料結構，它是非常典型的，用于存儲（key,value）形式的鍵值對映射。HashMap是基于哈希表的Map接口的非同步實作。此實作提供所有可選的映射操作，并允許使用null值和null鍵。此類不保證映射的順序，特别是它不保證該順序恒久不變
它的繼承關系圖如下：
底層結構
可以說HashMap本質上它是一個數組table，根據經過hash(key)方法得到的哈希值hash按照一定規則散列到這個數組中。不同的key經過散列後可能會配置設定到同一個table索引位置上，這叫哈希沖突(也叫哈希碰撞)，如果發生了哈希沖突，會采用鍊位址法。将這個新加入的映射（被存儲為node節點）連結到節點之後，在jdk1.8之後當連結清單節點超過了一定門檻值，連結清單會轉化為紅黑樹。
jdk1.7之前，HashMap采用了數組+連結清單的結構，而1.8之後，使用了數組+連結清單+紅黑樹的結構。
為什麼使用這個結構
數組特點：
存儲區間是連續，且占用記憶體嚴重，空間複雜也很大，時間複雜為O（1）。
優點：是随機讀取效率很高，原因數組是連續（随機通路性強，查找速度快）。
缺點：插入和删除資料效率低，因插入資料，需要将這個位置後面的資料在記憶體中要往後移的，并且它的大小固定不易動态擴充。
連結清單特點：
區間離散，占用記憶體寬松，空間複雜度小，時間複雜度O(N)。
優點：插入删除速度快，記憶體使用率高，沒有大小固定，擴充靈活。
缺點：不能随機查找，每次都是從第一個開始周遊（查詢效率低）。
哈希表特點：
以上數組和連結清單，都有各自的優缺點，哈希表通過權衡将2個結構進行組合，使得查詢效率和插入删除效率都比較高。
靜态變量
/**
*預設的初始容器大小為2的4次方，初始容器一定是2的次方。
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 最大容量，如果任何構造函數中指定了一個更大的初始化容量，将會被
* MAXIMUM_CAPACITY 取代。
* 此參數必須是 2 的幂，且小于等于 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;//預設負載因子0.75
/**
* 将連結清單轉化為紅黑樹的臨界值。把一個元素添加到至少有
* TREEIFY_THRESHOLD 個節點的桶裡時，桶中的連結清單将被轉化成
* 樹形結構。此變量最小為 8。
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 在調整大小時，把樹結構恢複成連結清單時的桶大小臨界值。此變量應該小于
* TREEIFY_THRESHOLD，最大為 6。
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 當 table 數組大于此容量時，桶内連結清單才可能被轉化成樹形結構的。否則，
* 若桶内元素太多時，直接進行擴容而不是樹形化。容量應該至少為
* 4 * TREEIFY_THRESHOLD 來避免和樹形結構化之間的沖突。
* 即
*/
static final int MIN_TREEIFY_CAPACITY = 64
成員變量
table就是散列的桶數組，數組的每一個位置都代表一個桶(bucket)。用來存放hash值經過雜湊演算法得到相同索引的對象。
threshold 為需要進行resize擴容的門檻值，除了hashmap初始化以及容量超出了最大限制2^30時，大部分情況下，threshold = table.length(capacity)* loadFactor。
loadFactior為負載因子。負載因子大時，優點是填滿的元素多，空間使用率高，負載因子小時，優點是沖突的機率小，連結清單較短，查找效率變高，但可能會進行頻繁的擴容操作，也會消耗性能。預設加載因子為 0.75，是時間效率和空間效率的一種平衡。
size 表示映射的數量，而不是table的長度(桶的數量)。size 大于門檻值threshold時執行擴容操作。
/**
* 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.)
*/
//表，在第一次使用時初始化，并根據需要調整大小。
// 當配置設定時，長度總是2的幂。(我們還允許在一些操作中允許長度為零，以允許目前不需要的引導機制。)
transient Node<K,V>[] table; //桶數組。
//transient表示序列化對象的時候，這個屬性就不會被序列化
/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
* //儲存緩存entrySet ()。注意，AbstractMap字段用于keySet()和values()。
*/
//
transient Set<Map.Entry<K,V>> entrySet;
/**
* The number of key-value mappings contained in this map.
*/
transient int size; //包含key-value 鍵值對的數量
/**
* 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).
*/
//結構修改是指那些改變HashMap中映射數量或修改其内部結構的修改(例如，重新哈希)。
// 此字段用于使HashMap的集合視圖上的疊代器快速失效。(見ConcurrentModificationException)
transient int modCount; //表示哈希表被重新建構的次數。
/**
* The next size value at which to resize (capacity * load factor).
*擴容的臨界值（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.)
//(javadoc描述在序列化時是正确的。此外，如果沒有配置設定表數組，
// 則該字段儲存初始數組容量，為0表示,容量使用預設DEFAULT_INITIAL_CAPACITY)
int threshold; //table為null時字段代表數組的初始容量，否則代表門檻值，超過該值數組将擴容。
/**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor; //哈希表的負載因子
構造函數
其中putMapEntries方法，除了在使用了指定MAP構造函數的使用調用到，在下面putAll方法也用到。
這邊要先介紹 tableSizeFor方法，接收一個整型容量，傳回大于等于它的2的倍數，如果這個傳回值大于了最大容量，則傳回的是最大容量。
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) { //傳回一個給定的容量的大于或等于的2的倍數
int n = cap - 1; //減一是為了保證原數如果已經是2的整數次幂了，那就傳回原值。
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16; //結果就是将等于1的最高位數後面的位數全部變為1.
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; //n超出了最大容量，則指派為最大容量，否則加一變為2的整數次幂
}
一共四個構造函數如下：
/**
* 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
*/
//使用指定的初始容量和負載因子，重新建構空的哈希表。如果初始容量和負載因子出現負數，抛出異常、
public HashMap(int initialCapacity, float loadFactor) {//雙參數的構造函數
if (initialCapacity < 0) //初始容量為負 ，抛出異常。
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY) //如果初始容量大于了哈希表最大容量2的30次方，則以最大容量指派初始容量。
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor)) //如果負載因子小于等于0，或者負載因子not a number，非數字值，則抛出異常
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor; //指派hashmap的負載因子
this.threshold = tableSizeFor(initialCapacity); //将初始容量變為大于等于它的最小的2的整數次幂，然後指派給初始容量
}
/**
* 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.
*/
public HashMap(int initialCapacity) { //隻指定初始容量的構造函數。負載因子預設0.75
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() { //沒有參數的構造函數。初始容量為16.負載因子為0.75
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>.
* 構造一個新的HashMap，使用與指定的Map相同的映射。
* HashMap使用預設負載因子(0.75)和足以容納指定Map中的映射的初始容量建立。
* @param m the map whose mappings are to be placed in this map
* @throws NullPointerException if the specified map is null
*/
public HashMap(Map<? extends K, ? extends V> m) { //使用和指定Map相同的映射來建立哈希表。
this.loadFactor = DEFAULT_LOAD_FACTOR; // 負載因子為預設0.75
putMapEntries(m, false);
}
/**
* Implements Map.putAll and Map constructor
*
* @param m the map
* @param evict false when initially constructing this map, else
* true (relayed to method afterNodeInsertion).
* evict 最初構造此映射時為false，否則為true(在nodeinsert之後轉發給方法)
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { //接上面使用Map建立hashmap的構造函數。evict表示是否為最初構造
int s = m.size(); //存儲映射 鍵值對總數
if (s > 0) { //如果參數map不為空。
if (table == null) { // pre-size //初始化容器的容量。
float ft = ((float)s / loadFactor) + 1.0F; //目前鍵值對數目除以負載因子+1
int t = ((ft < (float)MAXIMUM_CAPACITY) ? //如果上面的值大于最大容量，則直接用最大容量。
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold) //當table為null 時，threshold儲存的是初始容量(未乘0.75)，是以用ft(而不是s)來比較。
threshold = tableSizeFor(t); //如果超出了。就對其進行擴容。得到大于等于它的最小2 的整數次幂作為初始門檻值(将在第一次put時計入容量中)。
}
else if (s > threshold) //如果table 不為空。鍵值對數量大于門檻值。進行擴容。
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { //Iterator周遊 Map
K key = e.getKey(); //得到key,
V value = e.getValue(); //得到value
putVal(hash(key), key, value, false, evict); //把每個key-value鍵值對插入到hashmap中。
}
}
}
關鍵内部類
Node 類
其中Node為普通節點，TreeNode為紅黑樹節點。
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
static class Node<K,V> implements Map.Entry<K,V> { //hash連結清單節點，實作了Map中的Entry接口類。
final int hash; //hashcode值
final K key; // 鍵
V value; //值
Node<K,V> next; //存放下一個連結清單節點
Node(int hash, K key, V value, Node<K,V> next) { //節點構造函數
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; } //得到節點key值
public final V getValue() { return value; } //得到節點value值
public final String toString() { return key + "=" + value; } //toString方法 傳回 key=value形式
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
} //節點類自己的哈希方法。得到哈希值
public final V setValue(V newValue) { //設定值，成員value指派為新值，将舊值傳回。
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) { //節點類的equals 方法，隻有當兩個節點的key和value用== 判斷都相等的情況下，才為true
if (o == this) //如果o就是調用這個方法的對象，那麼肯定相等
return true;
if (o instanceof Map.Entry) { //如果o是實作了Map.Entry類的派生類對象，
Map.Entry<?,?> e = (Map.Entry<?,?>)o; //轉化為Entry，用于比較
if (Objects.equals(key, e.getKey()) && //調用了Object類的equal方法，即簡單的用==比較 key和value存儲位址是否相同。
Objects.equals(value, e.getValue()))
return true; //當key 和value分别用== 比較都相同，傳回true。
}
return false;
}
}
TreeNode
TreeNode繼承了LinkedHashMap.Entry,而這個Entry繼承了上面的node類，當table表中某個桶中節點超過8個，node節點要轉化為TreeNode節點，然後将這些節點構成紅黑樹。TreeNode中含有的方法較多，具體方法作用可以學習TreeMap時再深入。這裡先知道這是一個樹節點類，hashmap關于紅黑樹的增增删改查都在這個類中實作即可。
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links //用于紅黑樹的連接配接
TreeNode<K,V> left; //左孩子節點
TreeNode<K,V> right; //右孩子節點
TreeNode<K,V> prev; // needed to unlink next upon deletion //因為删除時會斷開next連接配接，是以使用prev儲存前一個。
boolean red; //如果為true，說明是紅色節點， 為false則為黑色節點
TreeNode(int hash, K key, V val, Node<K,V> next) {s
super(hash, key, val, next);
} //構造函數
/*下接紅黑樹的類方法*/
關鍵成員方法
hash方法
當一個鍵值對存入時，由前面我們知道需要建立一個Node節點類（或TreeNode類）然後再存入我們的hashmap的桶中，而同樣在删除、查找時，定位鍵值對到桶中位置也是很關鍵的第一步。在節點類中有個成員屬性hash是用于存儲成員的hash值的，而這個hash值正是通過hash（key）計算得到的，hashmap中使用鍵值對節點類中的hash存儲的值與(table.length-1)做&運算得到對應的索引，代表找到的桶的位置。
//因為當桶數很小時，很大的hash值（它的二進制總是高位在變化），
//在散列時，總是發生碰撞，是以使用一種方法将較高位擴充到較低位。
//讓table 在容量較小時，高位也能夠參與散列運算，并且不會造成較大開銷。
static final int hash(Object key) { //重新計算key的hash值
int h; //用于傳回的hash值
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}//如果key為null，傳回0，如果key不為0，原hash值高位右移16位到低位，然後與原數進行異或。
hash方法首先接收key,然後通過key的hashCode()方法計算key的原始hash值，而後hashmap為了保證在table長度很小時，避免很大的hash值總是發生碰撞，通過了上述代碼計算獲得了新的hash值，将其作為傳回值。
在hashmap的很多方法中，找到鍵值對節點在table數組中的位置是方法的第一步。如何根據節點類中的hash值來計算它在桶中的索引呢。hashmap使用了以下方法。
/* index 代表在table數組中的索引位置，hash值等于hash(key),
table.length表示table的長度
*/
int index = hash & (table.length - 1);
對于任意一個給定的對象，隻要它的hashCode()傳回的值相同，那麼通過hash()方法得到的傳回值hash總是相同的，對于一系列的hash值，如何使這些元素在哈希表中散列均勻，以便提高哈希表的操作效率，我們首先想到的是取模運算%。
但是模運算的計算消耗是非常巨大的，是以為了優化模運算，我們使用了上面的代碼取代了模運算，這個優化是基于x mod 2^n = x & (2^n - 1)。在上面的介紹中提到table的長度總是2的n次方，并且取模運算為n mod table.length,是以對應上面公式，可以得到該運算等同于n&(table.length - 1);這是HashMap在速度上的優化，因為&比%具有更高的效率。
get方法
get方法接收一個鍵值對中的鍵key,調用getNode找到這個key對應的節點，然後獲得該節點中value進行傳回。要注意的是傳回為null不一定是因為不包含指定的key，而也有可能是map中這個key對應的value就是為null,以為hashmap允許value為空。而getnode方法，接收key的hash值和key，首先根據hash值找到對應的數組table的位置，判斷這個位置上的桶是否為空，不為空則繼續判斷這個桶存儲的是普通連結清單還是紅黑樹。如果是普通連結清單則通過next屬性依次周遊連結清單，找到hash值和key和傳入的相同，就把節點指派傳回。如果是紅黑樹，則要調用紅黑樹的方法getTreeNode（同樣此方法詳細可以學習TreeMap時再深入）來得到找到這個節點。
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code (key==null ? k==null :
* key.equals(k))}, then this method returns {@code v}; otherwise
* it returns {@code null}. (There can be at most one such mapping.)
*
* <p>A return value of {@code null} does not <i>necessarily</i>
* indicate that the map contains no mapping for the key; it's also
* possible that the map explicitly maps the key to {@code null}.
* The {@link #containsKey containsKey} operation may be used to
* distinguish these two cases.
* 傳回指定 key 對應的 value，如果指定 key 不包含任何映射傳回 null。
*
* 傳回值為 null 并不一定是因為不包含指定 key 對應的映射，也有可能是
* map 允許 value 值為 null。containsKey 方法可以用來區分這兩種情況。
* /
*
* @see #put(Object, Object)
*/
public V get(Object key) { //根據key 獲得value值。
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value; //調用getNode，
}
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) { //根據key,和key的hash出的值，找到hashmap中對應的節點。
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 && //如果表不為空，且表長度大于0，
(first = tab[(n - 1) & hash]) != null) { //根據hash值找到對應的表的索引位置上的桶，桶不為空時，将這個桶的頭結點指派給first。
if (first.hash == hash && // always check first node //判斷first頭結點hash值，
((k = first.key) == key || (key != null && key.equals(k)))) //判斷傳入的hash,key和頭結點first的相同，說明找到了這個點
return first; //傳回first
if ((e = first.next) != null) { //如果沒有傳回，且這個桶的節點不止一個。這是需要分2種情況，是紅黑樹還是普通連結清單
if (first instanceof TreeNode) //如果是紅黑樹
return ((TreeNode<K,V>)first).getTreeNode(hash, key); //調用紅黑樹的找節點方法。并傳回
do { //如果是普通連結清單。則開始周遊
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) //直到周遊到hash和key都相等的節點，就進行傳回。
return e;
} while ((e = e.next) != null);
}
}
return null; //如果以上都沒找到，說明這個找不到這個節點，傳回null。
}
put方法
put方法接收2個參數，即鍵值對的key和對應的value，然後調用putVal方法。該方法先判斷table是否為空，為空則首先調用resize()進行初始化table。再根據傳入的key的hash值找到對應的table上的位置，判斷該位置上是否有其他值，如果為空就使用key,value，建立節點存放在該位置。若該位置不為空，此時有兩種情況，已經存在該key,，則進行value覆寫，另一種情況是不存在該key需要進行插入。具體過程在下面源碼中分析。
需要注意的是，因為節點有可能是Node類和TreeNode類，是以需要判斷兩種情況。且需要注意如果普通連結清單的節點為7個，剛好put成功，連結清單長度變為8個節點，就要調用treeifyBin方法将連結清單轉化為紅黑樹（如果數組長度大于的話），putTreeVal方法用于紅黑樹結構的添加節點（同樣此方法詳細可以學習TreeMap時再深入）。
/*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) { //往hashmap中添加一對鍵值對
return putVal(hash(key), key, value, false, true); //調用putVal方法。
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value 隻有預設才覆寫，為true說明不改變已經存在的值。
* @param evict if false, the table is in creation mode. 為false，說明哈希表處理建立模式
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//判斷table是否為空，或長度為0 ，如果滿足，則調用resize(),進行初始化，并且把數組長度指派給n。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) //(n-1) &hash, 與hash%length 相同，即散列函數，得到索引i，并且判斷對應桶tab[i]是否為空。
tab[i] = newNode(hash, key, value, null); //如果為空，則建立一個連結清單節點放入哈希桶中。
else { //如果對應桶位置tab[i]不為空。
Node<K,V> e; K k;
if (p.hash == hash && //隻有當桶的結點p的hash值和傳入的hash值相同，
((k = p.key) == key || (key != null && key.equals(k)))) //并且節點P的key和傳入的key值相等時
e = p; //如果滿足相等，說明要進行value覆寫，先把這個節點指派給e。
else if (p instanceof TreeNode) //如果桶的節點p是否是紅黑樹節點，如果是，就調用紅黑樹的putTreeVal方法，
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //和上一步同樣傳回周遊到的節點。
else { //走到這裡，說明頭結點不相等，并且，桶并非紅黑樹結構。
for (int binCount = 0; ; ++binCount) { //則周遊桶上的連結清單結構。 binCount用于計算周遊了多少次。
if ((e = p.next) == null) { //e指派為下一個連結清單節點。如果它的p.next為空，說明連結清單周遊到達尾部，
p.next = newNode(hash, key, value, null); // 根據傳入hash,key,value建立一個新的非樹節點，将這個節點放入到連結清單的尾部。
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st //如果周遊了7次(尾部新加1個節點，這時連結清單節點為8),超出了連結清單轉化為紅黑樹的門檻值
treeifyBin(tab, hash); //将連結清單轉化為紅黑樹。 傳入了目前傳入的這個節點的hash值和hashmap的table。
break; //打斷周遊。
}
if (e.hash == hash && //如果還沒到達尾部，就發現了和傳入的hash,key相同的點，說明需要進行value覆寫。此時這個節點就為e。中斷周遊。
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e; //将e指派為p，即周遊。
}
}
//e不為空，說明傳入的hash,key值在桶中找到了相同的節點，需要進行value 覆寫。修改value後直接傳回不參與size++。是以size不變
if (e != null) { // existing mapping for key
V oldValue = e.value; //覆寫需要保留原來的value 值。
if (!onlyIfAbsent || oldValue == null) // 如果沒有要求不能覆寫，或者要求不能覆寫但是值為null,
e.value = value; //将這個節點的vlaue值覆寫為新傳入的value值；
afterNodeAccess(e); //用于LinkedHashMap
return oldValue; //傳回這個舊值。
}
}
++modCount; //Put改變了hashmap的結構，是以modCount自加1.
if (++size > threshold) //插入一個有效的鍵值對後,(即不發生覆寫value),size要加1，并且和容量門檻值進行比較
resize(); //如果大于門檻值，需要調用resize，擴容。
afterNodeInsertion(evict); //用于LinkedHashMap
return null; //未發生覆寫value,就傳回null.
}
treeifyBin方法
當一個桶中的普通連結清單節點超過了8個時，就會調用該方法進行紅黑樹轉化。但是要注意的是，進行轉化還有一個必要前提是table.length要大于等于64，即在容量小于64時，發生了一個桶中連結清單節點到達8個，則這時候是選擇調用resize()進行擴容，而不是轉化為紅黑樹。具體需要轉化紅黑樹時，會先将普通連結清單節點轉化為樹節點，并且構造成雙向連結清單，然後調用treeify将此連結清單轉化為紅黑樹。
//當一個桶中連結清單節點數超過門檻值8個，調用這個方法。
//注意如果這時候，table還很小，首選的是擴容，而不是轉換為紅黑樹。
//門檻值為64，table容量長度大于等于64，且連結清單節點大于8個就轉換為紅黑樹。（新轉換為雙向連結清單，再建構紅黑樹）
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) //容量小于64，選擇擴容。
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) { // 傳入節點的桶位置不為空。且将這個桶頭節點指派給e.
TreeNode<K,V> hd = null, tl = null;
do { //周遊剛索引位置桶上的連結清單。
TreeNode<K,V> p = replacementTreeNode(e, null); //連結清單節點轉換為紅黑樹節點。
if (tl == null) //如果是第一次循環周遊。
hd = p; //則樹的頭結點指派為p.
else {
p.prev = tl; //目前節點的前一個節點指派為tl儲存的上一個節點。
tl.next = p; //上一個節點的next屬性設定為目前節點。
}
tl = p; //tl更新為目前節點。
} while ((e = e.next) != null);
if ((tab[index] = hd) != null) //如果将上面建構的雙向連結清單的頭結點指派給這個桶
hd.treeify(tab); //以這個桶的頭結點為根節點建構紅黑樹。
}
}
putAll方法
putAll方法，接收指定的Map,将map中的所有映射指派到hashmap中，其原理就是周遊map中的每一個鍵值對，将得到的鍵值對作為參數調用上面put用到的putVal方法。
/**
*将指定 map 的所有映射複制到此 map 中。這些映射将替代此 map 中
* 已經存在的 key 對應的映射。
* @param m mappings to be stored in this map
* @throws NullPointerException if the specified map is null
*/
public void putAll(Map<? extends K, ? extends V> m) { //将一組鍵值對全部放入。原理和使用鍵值對構造hashmap差不多，隻是容量定義上有差别。
putMapEntries(m, true); //處理好容量和門檻值問題以後，就是等同于一步一步周遊map，逐個putVal;
}
/** @param m the map
* @param evict false when initially constructing this map, else
* true (relayed to method afterNodeInsertion).
* evict 最初構造此映射時為false，否則為true(在nodeinsert之後轉發給方法)
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { //接上面使用Map建立hashmap的構造函數。evict表示是否為最初構造
int s = m.size(); //存儲映射 鍵值對總數
if (s > 0) { //如果參數map不為空。
if (table == null) { // pre-size //初始化容器的容量。
float ft = ((float)s / loadFactor) + 1.0F; //目前鍵值對數目除以負載因子+1
int t = ((ft < (float)MAXIMUM_CAPACITY) ? //如果上面的值大于最大容量，則直接用最大容量。
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold) //當table為null 時，threshold儲存的是初始容量(未乘0.75)，是以用ft(而不是s)來比較。
threshold = tableSizeFor(t); //如果超出了。就對其進行擴容。得到大于等于它的最小2 的整數次幂作為初始門檻值(将在第一次put時計入容量中)。
}
else if (s > threshold) //如果table 不為空。鍵值對數量大于門檻值。進行擴容。用于putAll;
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { //Iterator周遊 Map
K key = e.getKey(); //得到key,
V value = e.getValue(); //得到value
putVal(hash(key), key, value, false, evict); //把每個key-value鍵值對插入到hashmap中。
}
}
}
resize方法
這個方法對hashmap中table的初始化或者對table的長度進行翻倍。對table的翻倍，需要重新配置設定桶中元素。
擴容的第一步主要是确定newCap和newThr兩個關鍵值。概括來說情況如下：
resize在對長度翻倍時，table!=null,即oldCap>0;（1）如果，原來table的長度oldCap已經是最大容量了，則不能進行翻倍，隻将門檻值設定為最大整數，就将舊表進行傳回；如果，oldCap還沒有達到最大容量，則對其進行翻倍，newCap=oldCap<<1;且若這個新容量大于預設初始容量，小于最大容量，就對門檻值也進行翻倍，newThr=oldThr<<1。
resize在初始化時,table=null,即oldCap<=0：（2）如果使用沒有指定初始容量的構造函數，則oldThr<=0。這時使用預設初始容量16，newThr為預設初始容量乘以預設負載因子。（3）使用了帶有初始容量參數的構造函數，則oldThr儲存了初始容量，是以newCap=oldThr，newThr在容量沒超過門檻值時指派為newCap*loadFact,在超出門檻值時，指派為Integer.MAX_VALUE。
具體分支如下圖：
第二步則是具體擴容過程中，如果table不為空，則需要将原來每個桶中的元素轉移到新的table中，使它們根據新的散列規則重新配置設定，同樣要判斷桶中是紅黑樹結構還是普通連結清單。這一步的具體過程看代碼解釋。
/**
* 初始化 table size 或者對 table size 加倍。如果 table 為 null，對 table
* 進行初始化。如果進行擴容操作，由于每次擴容都是翻倍，每個桶裡的
* 元素要麼待在原來的索引裡面，要麼在新的 table 裡偏移 2 的幂個位置。
*
* @return the table
*/
final Node<K,V>[] resize() { //resize，重新構造哈希表結構大小，傳回 哈希桶數組。
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length; //如果舊表為空，容量桶數顯然為0，如果不為空，則容量桶數為舊表的長度。
int oldThr = threshold; //初始容量門檻值指派給oldThr
int newCap, newThr = 0; //對應的，定義2個用于存儲新表容量(桶數)，和新表門檻值的變量（鍵值對）。
if (oldCap > 0) { //如果舊表不為空，哈希桶數目大于0，說明不是首次put。
if (oldCap >= MAXIMUM_CAPACITY) { //舊容量已經到達了hashmap的最大容量。
threshold = Integer.MAX_VALUE; //那麼隻能将size的門檻值調大到最大整數。
return oldTab; //不能擴大桶數，則調整完門檻值後就隻能傳回。
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && //新的容量擴容2倍
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold //新的門檻值也擴大2倍
}
else if (oldThr > 0) //如果新表沒初始化。但門檻值不為0，是因為使用了帶有初始容量參數的構造函數，首次put時就會出現數組為空，但初始容量不為空。
newCap = oldThr; //是以這是就将指定的初始容量指派給需要建立的容量(哈希桶數)
else { // 如果就容量和舊門檻值都為0，說明未指定初始容量構造了hashmap，則設定初始容量和初始門檻值。
newCap = DEFAULT_INITIAL_CAPACITY; //初始容量就為預設的容量16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //初始門檻值就為預設容量*0.75
}
if (newThr == 0) { //newThr還沒指派，走的上面第二條使用了帶初始容量參數的構造函數，首次put需要将門檻值設為容量的0.75(容量沒超最大值時)，
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? //門檻值應該是新容量的0.75，
(int)ft : Integer.MAX_VALUE); //如果超出了最大容量，則門檻值指派為最大整數。
}
threshold = newThr; //設定好的新門檻值指派給hashmap的threshld屬性。
@SuppressWarnings({"rawtypes","unchecked"})
//定義一個新表，容量為剛才計算出來的新容量。 （到這一步，我們已經計算好新容量，并且設定好門檻值了）
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab; //對hashmap的table成員指派為新表。
if (oldTab != null) { //如果舊表不為空，
for (int j = 0; j < oldCap; ++j) { //周遊舊表
Node<K,V> e;
if ((e = oldTab[j]) != null) { //将周遊到索引為j的表頭節點指派給e,如果表頭節點不為null,說明桶不為空，
oldTab[j] = null; //将表頭節點直接指派為null,便于垃圾回收。
if (e.next == null) //如果上一步存的表頭節點的e為空，代表舊表的這個桶上隻有一個節點，
newTab[e.hash & (newCap - 1)] = e; //隻有一個節點時，這個hash值從新通過%(length-1)求得新索引，直接放入
else if (e instanceof TreeNode) //如果這個節點是紅黑樹節點。
((TreeNode<K,V>)e).split(this, newTab, j, oldCap); //就調用split方法對這個桶中紅黑樹所有節點進行重新hash分布
else { // preserve order //如果為普通連結清單節點
Node<K,V> loHead = null, loTail = null;//存儲跟原索引位置相同的節點。
Node<K,V> hiHead = null, hiTail = null;//存儲跟原索引+oldCap的節點。
//因為在舊表同索引位置，它們的n(n為2^n=oldCap)位右邊相同，則擴容後，n位上為0還是為1決定了它們是散列到原索引，還是索引+oldCap上。
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) { // n位上為零，放入原索引相同位置。即鍊入lo連結清單
if (loTail == null) //首次時，将loHead指派為第一個節點。
loHead = e;
else // 不是第一個節點，就正常周遊，
loTail.next = e; //将周遊到尾節點串在目前節點next後面
loTail = e; //更新尾結點。
}
else { //和上面的情況相似，隻是這邊連接配接的是應該放入原索引+oldCap位置的節點。鍊入hi連結清單
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null); //e指派為下一個連結清單節點。直到末尾。
if (loTail != null) { //如果尾結點不為空，即lo不為空
loTail.next = null; //設定tail尾結點的next為null.
newTab[j] = loHead; //原索引位置桶放入lo連結清單的頭結點
}
if (hiTail != null) { //與上面類似
hiTail.next = null;
newTab[j + oldCap] = hiHead; //原索引位置+oldCap的位置放入hi連結清單頭結點。
}
}
}
}
}
return newTab; //傳回擴容後的表。
}
其中TreeNode.split方法，主要是将将紅黑樹先分為2個子樹，該方法隻在resize擴容時調用，即其中一個子樹的hash經過新散列還是配置設定到原來索引位置桶中，而另一個子樹是配置設定在索引位置+oldCap(舊容器大小)位置， 再對2個子樹進行判斷，如果長度小于等于指定的6，就退化為連結清單結構。具體分析同樣等到學習TreeMap時深入了解。
remove方法
remove方法接收key,調用removeNode方法，如果移除成功傳回删除點的value值，如果移除失敗，即hashmap中沒有改key，則傳回null。
removeNode方法，接收的參數較多，具體在代碼中@param中解釋。該方法可以分為兩步：
第一步是根據傳入的hash，key找到要删除的節點，這個節點會被指派給node,這一步其實和getNode是有點相似的，在定位到table中的桶後，判斷出該桶是紅黑樹結構時也是直接調用了getTreeNode方法。而在判斷出是連結清單節點時，在周遊過程中，當找到這個要删除的點時，會儲存這個節點的上一個節點指派給p,以便用于下一步删除過程。
第二步就是将找到的節點删除。删除時要判斷，找到的點是紅黑樹的節點，還是普通連結清單節點。如果是普通連結清單的節點的頭結點，則直接将頭結點的next指派給table[index];如果是普通連結清單的除頭結點外的其他節點，則将上述查找時存儲的上個節點p的next重新指派為node的next；如果是紅黑樹節點，則調用
TreeNode的類方法removeTreeNode，該方法會删除紅黑樹中對應節點，并且判斷桶中剩餘節點，如果剩餘節點小于等于6，就會轉化為普通連結清單(具體實作在學習TreeMap時深入了解)。
/*
*接收key,若移除成功則傳回移除點的value值，若移除失敗，未找到該點，則傳回null。
*/
public V remove(Object key) { //根據傳入的key删除一個節點。
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value; //如果移除成功，傳回移除點的value值。否則傳回null。
}
/**
* Implements Map.remove and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to match if matchValue, else ignored //可以傳入key對應的value，或null表示不傳入value。
* @param matchValue if true only remove if value is equal //如果為true，表示隻有和傳入的值相同，才删除。
* @param movable if false do not move other nodes while removing 如果為false，在删除時不移動其他節點。
* @return the node, or nul l if none //傳回删除的節點，如果沒找到删除的點，傳回null
*/
//
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index; //removeNode,第一步是從hashmap中找到節點。第二步才是删除。
//哈希表不為空，且容量大于0，并且傳入的hash值計算得到的索引位置上存在節點。
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) { //将頭結點指派給p
Node<K,V> node = null, e; K k; V v; //node用于存儲在hashmap中找到的要删除的節點，如果沒找到則為null。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) //如果頭結點和傳入的key,hash相等，說明找到了要删除的點，指派給node
node = p;
else if ((e = p.next) != null) { //如果該位置不止一個節點。則要判斷是紅黑樹還是普通連結清單
if (p instanceof TreeNode) //如果頭結點是紅黑樹的根節點。
node = ((TreeNode<K,V>)p).getTreeNode(hash, key); //調用紅黑樹的getTreeNode的方法找到樹中節點。指派給node.
else { //如果是普通連結清單，則要進行周遊
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) { //在周遊過程中，找到了hash,key都相等的節點。
node = e; //找到就指派給node. 并退出周遊
break;
}
p = e; //p節點更新為 本次循環的節點。如果上一步找到打斷了，則p儲存了找到節點的上個節點。
} while ((e = e.next) != null); //指向下一個節點。
}
}
//如果找到了這個node，就判斷是否傳入了值，如果傳入value，還要判斷value相同。
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode) //如果這個節點是紅黑樹中的節點。
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); //則調用紅黑樹移除節點的方法。
else if (node == p) //如果為普通連結清單的頭結點。
tab[index] = node.next; //直接舍棄頭結點，将第二個節點或者null指派給表索引上的桶。
else //如果為連結清單節點。
p.next = node.next; //将要删除的上個節點的next指派為删除節點的下一個節點。
++modCount; //删除成功後，記錄一次哈希表改變結構的次數。
--size; //删除成功後，哈希表的鍵值對數量少了1對。
afterNodeRemoval(node); //提供給linkedHashMap使用
return node; //傳回被删除的節點。
}
}
return null; //如果沒有找到這個節點，傳回null。
}
clear方法
這個方法比較簡單，其實就是簡單的将table數組的每一個桶都指派為null，虛拟機就會自己完成垃圾回收，然後将size設定為初始值0；
/**
* Removes all of the mappings from this map.
* The map will be empty after this call returns.
*/
public void clear() { //清空hashmap
Node<K,V>[] tab;
modCount++; //清空也算是改變了哈希表結構，是以次數加1。
if ((tab = table) != null && size > 0) { //如果表不為空，且鍵值對不為0.
size = 0; //将表清空以後，鍵值對為0；
for (int i = 0; i < tab.length; ++i) //将數組中的每一個桶都指派null。友善垃圾回收機制。
tab[i] = null;
}
}
其他一些成員方法
size方法
傳回hashmap中含有的鍵值對的總數。
* Returns the number of key-value mappings in this map.
*
* @return the number of key-value mappings in this map
*/
public int size() { //得到映射中 鍵值對的總數。
return size;
}
isEmpty方法
傳回boolean值，如果hashmap中不存在鍵值對則傳回true，如果存在為false；
/**
Returns <tt>true</tt> if this map contains no key-value mappings.
*
* @return <tt>true</tt> if this map contains no key-value mappings
*/
public boolean isEmpty() { //判斷hashmap是否為空。空傳回true、
return size == 0;
}
containsKey方法
判斷hashmap中是否存在一對鍵值對，它的key等于傳入的參數key。如果存在，傳回true，不存在傳回false。
/**
* Returns <tt>true</tt> if this map contains a mapping for the
* specified key.
*
* @param key The key whose presence in this map is to be tested
* @return <tt>true</tt> if this map contains a mapping for the specified
* key.
*/
public boolean containsKey(Object key) { //根據key判斷是否含有這個映射。和get類似，就是傳回值變為boolean
return getNode(hash(key), key) != null;
}
containsValue方法
該方法，使用雙循環，先周遊每個桶，再周遊每個桶中的節點，對節點的value進行判斷，如果找到相等的就傳回true，否則傳回false；
/**
* Returns <tt>true</tt> if this map maps one or more keys to the
* specified value.
*
* @param value value whose presence in this map is to be tested
* @return <tt>true</tt> if this map maps one or more keys to the
* specified value
*/
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) { //如果表不為空，size不為0.
for (int i = 0; i < tab.length; ++i) { //先周遊每個桶
for (Node<K,V> e = tab[i]; e != null; e = e.next) { //再周遊每個桶中的節點。
if ((v = e.value) == value || //直到找到了value 相同時，傳回true。
(value != null && value.equals(v)))
return true;
}
}
}
return false; //沒找到就傳回false；
}
keySet、 values 和 entrySet方法
/*
* //傳回包含這個映射中鍵值對包含的所有的鍵的集合視圖。這個集合是受到這個map
* 的影響的，是以，如果對這個hashmap 做修改是會影響到這個視圖的。如果
* 在Iteration疊代器疊代這個視圖時，這個映射發生了結構性的修改(除非是疊代
* 器自己的remove操作)，那麼疊代的結果是不确定的。這個集合支援元素删除，通過
* 疊代器Iterator.remove，Set.remove,removeAll,retainAll,clear操作都可以移除映射
* 中相對應的鍵值對關系。但是它不支援add或者addAll操作。
*
* @return a set view of the keys contained in this map
*/
public Set<K> keySet() { //keySet方法，傳回含有所有key的集合set
Set<K> ks = keySet;
if (ks == null) {
ks = new KeySet(); //這個類是定義的内部類，繼承AbstractSet。
keySet = ks;
}
return ks;
}
/*
* 此方法傳回這個hashmap中所有鍵值對的值的一個集合視圖，
* 這個視圖也受到這個映射的影響，如果改變了hashmap會影響到這個視圖。
* 當疊代器Iterator在周遊這個視圖時，如果hashmap結構發生改變（除非是Iterator.remove自己
* 操作改變的），那麼這個視圖傳回的結果是不确定的。這個集合
* 同樣支援元素修改，通過Iterator.remove，Collection.remove，removeAll,
* retainAll，clear等等操作都會删除hashmap中對應的鍵值對。但是它
* 不支援add和addall操作。
* @return a view of the values contained in this map
*/
public Collection<V> values() { //内部方法value（），傳回hashmap中值的結合視圖。
Collection<V> vs = values;
if (vs == null) {
vs = new Values();
values = vs;
}
return vs;
}
/*和上面keySet()以及values()相似意思。因為鍵值對不允許重複，是以
* 使用Set而不是Collection。
* 疊代中如果是通過自己的remove方法，或者通過使用疊代器獲得的entry中的
* setValue方法改變hashmap的值，不會造成此次疊代的結果的不确定性。
* 同樣隻支援移除，不支援添加。
* @return a set view of the mappings contained in this map
*/
public Set<Map.Entry<K,V>> entrySet() { //entrySet()内部方法，獲得hashmap的所有鍵值對關系。
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
重寫Map中的方法
這些方法在學習map時候再了解。
hashmap的IO相關方法
這些方法在學習IO寫入的源碼後再補充學習
TreeNode類的分析
這些成員和類方法，留在對TreeMap的學習中進行深入了解。