hashmap value占用空间大小_【Java集合框架002】原理层面：HashMap全解析
一、前言
二、HashMap
2.1 HashMap數據結構 + HashMap線程不安全 + 哈希沖突
2.1.1 HashMap數據結構
學習的時候，先整體后細節，HashMap整體結構是 底層數組+鏈表 ，先記住，再開始看下面的
HashMap相關知識點：
底層數據結構：HashMap基于哈希散列表實現 ，可以實現對數據的讀寫。
插入邏輯put()方法：將鍵值對傳遞給put方法時，它調用鍵對象的hashCode()方法來計算hashCode，然后找到相應的bucket位置(即數組)來儲存值對象。當獲取對象時，通過鍵對象的equals()方法找到正確的鍵值對，然后返回值對象。
哈希沖突：插入邏輯中，如果發生哈希沖突，使用鏈表來解決hash沖突問題，即當發生沖突了，對象將會儲存在鏈表的頭節點中。HashMap在每個鏈表節點中儲存鍵值對對象，當兩個不同的鍵對象的hashCode相同時(HashMap在兩個key-value，hashcode相同導致index相同，就認為發生哈希沖突，equals相同任務同一個，不重復插入，HashSet在hashcode和equals相同，認為同一個，不重復插入)，它們會儲存在同一個bucket位置的鏈表中，如果鏈表大小超過閾值(TREEIFY_THRESHOLD,8)，鏈表就會被改造為樹形結構。
HashMap和HashSet：HashMap在兩個key-value，hashcode相同導致index相同，哈希沖突，equals相同任務同一個，不重復插入，HashSet在hashcode和equals相同，認為同一個，不重復插入。
2.1.2 HashMap線程不安全
HashMap是應用更廣泛的哈希表實現，而且大部分情況下，都能在常數時間性能的情況下進行put和get操作。但是，HashMap在多線程并發的情況下是不安全的，通過兩個問題的回答來解釋原因。
問題1：為什么說HashMap是線程不安全的？
回答1：在接近臨界點時，若此時兩個或者多個線程進行put操作，都會進行resize(擴容)和reHash(為key重新計算所在位置)，而reHash在并發的情況下可能會形成鏈表環。即在多線程環境下，使用HashMap進行put操作會引起死循環，導致CPU利用率接近100%，所以在并發情況下不能使用HashMap。
問題2：為什么在并發執行put操作會引起死循環？
回答2：因為多線程會導致HashMap的Entry鏈表形成環形數據結構，一旦形成環形數據結構，Entry的next節點永遠不為空，就會產生死循環獲取Entry。值得注意的是，JDK1.7的情況下，并發擴容時容易形成鏈表環，此情況在1.8時就好太多太多了，因為在1.8中當鏈表長度大于閾值(默認長度為8)時，鏈表會被改成樹形(紅黑樹)結構。
2.1.3 哈希沖突
哈希沖突定義：若干Key的哈希值按數組大小取模后，如果落在同一個數組下標上，將組成一條Entry鏈，對Key的查找需要遍歷Entry鏈上的每個元素執行equals()比較(tip：知道了HashMap的“數組+鏈表”結構，就很好懂哈希沖突了)。
加載因子：為了降低哈希沖突的概率，默認當HashMap中的鍵值對達到數組大小的75%時，即會觸發擴容。因此，如果預估容量是100，即需要設定100/0.75＝134的數組大小，又因為HashMap大小必須是2的整數次冪，所以是大于134的最小的2的整數次冪，即256。
減少哈希沖突兩方法：降低加載因子，加大初始大小。
HashMap中數組擴容相關概念(size capacity size/capacity)：
size是當前現實的記錄數；capacity是理論上的容量，第一次由初始化決定，之后由擴容決定；initial capacity是初始的capacity，第一次的capacity。
負載因子等于“size/capacity”，全稱為當前負載因子，其作用是當負載因子達到負載極限的時候擴容。當負載因子為0，表示空的hash表；負載因子為0.5，表示半滿的散列表，依此類推。輕負載的散列表具有沖突少、適宜插入與查詢的特點(但是使用Iterator迭代元素時比較慢)。
負載極限：“負載極限”是一個0～1的數值，“負載極限”決定了hash表的最大填滿程度。當hash表中的負載因子達到指定的“負載極限”時，hash表會自動成倍地增加容量(桶的數量)，并將原有的對象重新分配，放入新的桶內，這稱為rehashing。HashMap和HashTable的構造器允許指定一個負載極限，HashMap和HashTable默認的“負載極限”為0.75，這表明當該hash表的3/4已經被填滿時，hash表會發生rehashing。
“負載極限”的默認值(0.75)是時間和空間成本上的一種折中：
程序員可以根據實際情況來調整“負載極限”值。
較高的“負載極限”可以降低hash表所占用的內存空間，但會增加查詢數據的時間開銷，而查詢是最頻繁的操作(HashMap的get()與put()方法都要用到查詢)，所以會影響時間性能；
較低的“負載極限”會提高查詢數據的性能，但會增加hash表所占用的內存開銷，影響空間性能；
以上專有名詞連接起來是：size是記錄數，capacity是桶數量，兩者size/capacity得到負載因子，當負載因子達到理論設定的負載極限的時候擴容。專有名詞(size、capacity、負載因子、負載極限、擴容(具體擴容邏輯))，所有的這些都可以在源碼中找到邏輯。
2.2 JDK1.7中HashMap的實現
2.2.1 基本元素Entry
數組中的每一個元素其實就是Entry[] table，Map中的key和value就是以Entry的形式存儲的。Entry包含四個屬性：key、value、hash值和用于單向鏈表的next。關于Entry的具體定義參看如下源碼：
static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry next; int hash; Entry(int h, K k, V v, Entry n) { value = v; next = n; key = k; hash = h; } public final K getKey() { return key; } public final V getValue() { return value; } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry)o; Object k1 = getKey(); Object k2 = e.getKey(); if (k1 == k2 || (k1 != null && k1.equals(k2))) { Object v1 = getValue(); Object v2 = e.getValue(); if (v1 == v2 || (v1 != null && v1.equals(v2))) return true; } return false; } public final int hashCode() { return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue()); } public final String toString() { return getKey() + "=" + getValue(); } /** * This method is invoked whenever the value in an entry is * overwritten by an invocation of put(k,v) for a key k that's already * in the HashMap. */ void recordAccess(HashMap m) { } /** * This method is invoked whenever the entry is * removed from the table. */ void recordRemoval(HashMap m) { }}JDK7中的HashMap，小結為以下幾點：
基本元素為Entry，Entry包含四個屬性：key、value、int類型的hash值和用于單向鏈表的Node類型的next；
hash不是用于新插入的Entry和原有的鏈表節點的hashcode比較的，只是用于計算一下數組index的；
key,value 是用于新插入的Entry和原有的鏈表的節點的 key,value 比較的，只有到equals和hashcode(index)比較都先相同，就認為是相同元素，被認為是相同就不會插入HashMap；
next用于下一個鏈表中下一個節點。
2.2.2 插入邏輯
2.2.2.1 put()方法 = hash()方法 + indexFor()方法 + equals()方法
當向 HashMap 中 put一對鍵值時，它會根據 key的 hashCode 值計算出一個位置， 該位置就是此對象準備往數組中存放的位置。該計算過程參看如下代碼：
transient int hashSeed = 0;final int hash(Object k) { int h = hashSeed; if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h ^= k.hashCode(); h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } static int indexFor(int h, int length) { return h & (length-1);?}hash(Object)方法是用來計算哈希值的，indexFor(hash,length)方法是用來計算數組下標的。
兩者關系：indexFor方法根據hash(Object)方法的返回值作為實參來計算數組下標。
金手指：(put操作中的)hashcode方法和equals方法
第一步，確定數組下標，indexFor使用hash方法計算出來的值得到數組下標；
第二步，插入，如果指定的數組下標無對象存在，不發生哈希沖突，直接插入；
第三步，如果指定的數組下標有對象存在，發生哈希沖突，使用equals對鏈條上對象比較，全部為false插入，其中一個為true，表示已經存在(hash和equals都相同就是存在)
小結：僅以put操作為例，插入操作中hash方法用來作為計算數組下標的輸入，equals用于比較對象是否存在。
問題1：指定數組下標有值，哈希沖突后如何處理？
回答1：put操作的時候，當兩個key通過hashCode計算相同時，則發生了hash沖突(碰撞)，HashMap解決hash沖突的方式是用鏈表(拉鏈法)，當發生hash沖突時，則將存放在數組中的Entry設置為新值的next(比如A和B都hash后都映射到下標i中，之前已經有A了，當map.put(B)時，將B放到下標i中，A則為B的next，所以新值存放在鏈表最頭部的數組中，舊值在新值的鏈表上)。
問題2：哈希沖突發生后，為什么后插入的值要放在鏈表頭部？
回答2：因為后插入的Entry是“熱乎的”，被查找的可能性更大(因為get查詢的時候會遍歷整個鏈表)，既然后插入的Entry是“熱乎的”，那么這個后插入的Entry應該放在哪里呢？當然是放在鏈表頭部，因為鏈表查找復雜度為O(n)，插入和刪除復雜度為O(1)，如果將新值插在末尾，就需要先經過一輪遍歷，這個開銷大，如果是插在頭結點，省去了遍歷的開銷，還發揮了鏈表插入性能高的優勢。
2.2.2.2 addEntry() + createEntry()
添加節點到鏈表中：找到數組下標后，會先進行key判重，如果沒有重復，就準備將新值放入到鏈表的表頭。
void addEntry(int hash, K key, V value, int bucketIndex) { // addEntry方法中，如果當前 HashMap 大小已經達到了閾值，并且新值要插入的數組位置已經有元素了，那么要擴容 if ((size >= threshold) && (null != table[bucketIndex])) { // 擴容 resize(2 * table.length); // 擴容以后，重新計算 hash 值 hash = (null != key) ? hash(key) : 0; // 重新計算擴容后的新的下標 bucketIndex = indexFor(hash, table.length); } // createEntry就是插入新值 createEntry(hash, key, value, bucketIndex); // key value由方法參數提供，未擴容，hash bucketIndex使用方法參數傳遞的，擴容，hash bucketIndex使用新計算的}// 這個很簡單，其實就是將新值放到鏈表的表頭，然后 size++void createEntry(int hash, K key, V value, int bucketIndex) { Entry e = table[bucketIndex]; table[bucketIndex] = new Entry<>(hash, key, value, e); size++;}上述代碼解釋了：JDK7情況下的擴容
addEntry方法中，如果當前 HashMap 大小已經達到了閾值，并且新值要插入的數組位置已經有元素了，那么要擴容
HashMap擴容方式：兩倍擴容
擴容后重新計算要已經插入了的key的數組下標：先hash，然后indexFor
新元素插入指定數組下標的鏈頭，table[bucketIndex] = new Entry<>(hash, key, value, e); 新建一個Entry就是一個元素
這個方法的主要邏輯就是先判斷是否需要擴容，需要帶的話先擴容，然后再將這個新的數據插入到擴容后的數組的相應位置處的鏈表的表頭。
2.2.3 擴容邏輯：resize()
定義：擴容就是用一個新的大數組替換原來的小數組，并將原來數組中的值遷移到新的數組中。
由于是雙倍擴容，遷移過程中，會將原來table[i]中的鏈表的所有節點，分拆到新的數組的newTable[i]和newTable[i+oldLength]位置上。比如：原來數組長度是16，那么擴容后，原來table[0]處的鏈表中的所有元素會被分配到新數組中newTable[0]和newTable[16]這兩個位置。擴容期間，由于會新建一個新的空數組，并且用舊的項填充到這個新的數組中去。所以，在這個填充的過程中，如果有線程獲取值，很可能會取到 null 值，而不是我們所希望的、原來添加的值。
我們對照HashMap的結構來說，如下：
上圖中，左邊部分即代表哈希表，也稱為哈希數組(默認數組大小是16，每對key-value鍵值對其實是存在map的內部類entry里的)，數組的每個元素都是一個單鏈表的頭節點，跟著的藍色鏈表是用來解決沖突的，如果不同的key映射到了數組的同一位置處，就將其放入單鏈表中。
當size>=threshold( threshold等于“容量*負載因子”)時，會發生擴容。
void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); // 擴容 hash = (null != key) ? hash(key) : 0; // 擴容后要用新的hash，不能用參數的 bucketIndex = indexFor(hash, table.length); // 擴容后要用新的bucketIndex，不用用參數的 } createEntry(hash, key, value, bucketIndex); // key value由方法參數提供，未擴容，hash bucketIndex使用方法參數傳遞的，擴容，hash bucketIndex使用新計算的}特別提示：JDK1.7中resize，只有當 size>=threshold 并且 table中的那個槽中已經有Entry時，才會發生resize。即有可能雖然size>=threshold，但是必須等到相應的槽至少有一個Entry時，才會觸發擴容,可以通過上面的代碼看到每次resize都會擴大一倍容量(2 * table.length)。
2.2.4 null處理
前面說過HashMap的key是允許為null的，當出現這種情況時，會放到table[0]中。
private V putForNullKey(V value) { for (Entry e = table[0]; e != null; e = e.next) { if (e.key == null) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(0, null, value, 0); return null;}put()邏輯：hash()方法、indexFor()方法、equals()方法
金手指：(put操作中的)hashcode方法和equals方法
JDK7 put 子步驟：擴容 + createEntry插入 + 哈希沖突 ( JDK8 put 子步驟：擴容 + createEntry插入 + 哈希沖突鏈表/樹化 )
第一步，使用hash和tab.lenght計算數組下標index，準備插入，index=hash&(tab.length-1)；
第二步，執行插入，如果指定的數組下標無對象存在，不發生哈希沖突，直接插入；
第三步，如果指定的數組下標有對象存在，表示發生哈希沖突，使用equals對鏈條上對象比較，全部為false插入，其中一個為true，表示已經存在(hash和equals都相同就是存在)
小結：插入操作中hash方法用來作為計算數組下標的輸入參數，equals用于比較鏈表上對象是否存在
小結：JDK7情況插入情況下的擴容 addEntry
擴容方式：HashMap擴容方式：兩倍擴容 newsize=oldsize *2
數組擴容的觸發-兩個條件：addEntry方法中，如果當前 HashMap 大小已經達到了閾值75%，并且新值要插入的數組位置已經有元素了，才執行擴容(兩個條件，即有可能雖然size>=threshold，但是必須等到相應的槽至少有一個Entry時，才會擴容)
擴容后重新計算要已經插入了的key的數組下標：使用hash和tab.lenght計算數組下標index，準備插入，index=hash&(tab.length-1)；
擴容后的插入，對于原來數組的位置：擴容就是用一個新的大數組替換原來的小數組，并將原來數組中的值遷移到新的數組中。由于是雙倍擴容，遷移過程中，會將原來table[i]中的鏈表的所有節點，分拆到新的數組的newTable[i]和newTable[i+oldLength]位置上。如原來數組長度是16，那么擴容后，原來table[0]處的鏈表中的所有元素會被分配到新數組中newTable[0]和newTable[16]這兩個位置,從而減小鏈表長度。
擴容后的新插入：equals比較全部為false，然后將新元素插入指定數組下標的鏈頭，table[bucketIndex] = new Entry<>(hash, key, value, e); 新建一個Entry就是一個元素
擴容過程中的隱患：擴容期間，由于會新建一個新的空數組，并且用舊的項填充到這個新的數組中去。所以，在這個填充的過程中，如果有線程獲取值，很可能會取到 null 值，而不是我們所希望的、原來添加的值。
tip：ArrayList 1.5倍擴容，Vector兩倍擴容，HashTable newsize=2oldsize +1 ，HashMap newsize=2oldsize
辨析：擴容、樹化、哈希沖突
擴容：擴容的對象是數組，擴容兩個條件：addEntry方法中，如果當前 HashMap 大小已經達到了閾值75%，并且新值要插入的數組位置已經有元素了，才觸發擴容(擴容的第二個條件一定要put操作才能滿足)
樹化：樹化的對象是鏈表，鏈表節點數達到8，且要求數組長度大于64
樹化的時機：鏈表樹化一定要在put操作才會出現，樹鏈表化一定要在remove操作才會出現。
注意：樹化第二個要求：數組長度必須大于等于MIN_TREEIFY_CAPACITY(64)，否則繼續采用擴容策略；
哈希沖突：哈希沖突的定義是要插入的數組index位置有元素了。
JDK7：
(1)如果未發生哈希沖突，直接放到數組中；
(2)如果哈希沖突，沒有達到閾值的75%，插入到鏈表后面；
(3)如果哈希沖突，達到閾值75%，數組擴容操作，擴容后原數組元素和新插入的數組元素都要變動的；
JDK8：
(1)如果未發生哈希沖突，直接放到數組中；插入完成后判斷閾值是否擴容
(2)如果哈希沖突，鏈表節點數未達到8，但是數組長度小于64，尾插法放在鏈表后面，插入完成后判斷閾值是否擴容
(3)如果哈希沖突，鏈表節點數未達到8，但是數組長度大于等于64，尾插法放在鏈表后面，插入完成后判斷閾值是否擴容
(4)如果哈希沖突，鏈表節點數達到8，但是數組長度小于64，尾插法放在鏈表后面，插入完成后判斷閾值是否擴容
(5)如果哈希沖突，鏈表節點數達到8，且要求數組長度大于等于64，尾插法插入到鏈表后面，鏈表樹化，插入完成后判斷閾值是否擴容
小結：擴容是數組擴容，哈希沖突是數組哈希沖突，但是對于JDK8的HashMap，擴容和是否產生哈希沖突無關，擴容是判斷 size/capacity
小結：擴容、樹化、哈希沖突都是在put操作出現，但是三種不同。擴容和樹化都是put操作發生哈希沖突導致的，put操作如果不哈希沖突啥是沒有，所以只最重要的是設計分布均衡的哈希算法，頭插和尾插，擴容和樹化都是緩解措施。JDK7是put涉及哈希沖突、數組擴容，JDK8是put涉及哈希沖突、數組擴容、鏈表樹化，JDK8中remove可以涉及樹鏈表化。
2.3 JDK1.8中HashMap的實現(所有內容圍繞JDK7與JDK8最大不同——鏈表/紅黑樹而展開)
2.3.1 屬性支持
HashMap底層維護的是數組+鏈表，我們可以通過一小段源碼來看看：
/** * 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. * 即 最大容量，必須為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. * 大致意思就是說hash沖突默認采用單鏈表存儲，當單鏈表節點個數大于8時，會轉化為紅黑樹存儲 */ 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. * hash沖突默認采用單鏈表存儲，當單鏈表節點個數大于8時，會轉化 為紅黑樹存儲。* 當紅黑樹中節點少于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. * hash沖突默認采用單鏈表存儲，當單鏈表節點個數大于8時，會轉化為紅黑樹存儲。 * 但是有一個前提：要求數組長度大于64，否則不會進行轉化 */?static?final?int?MIN_TREEIFY_CAPACITY?=?64;通過以上代碼可以看出初始容量(16)、負載因子以及對數組的說明。
小結：HashMap相關的變量：
初始化默認大小是16 initial capacity 16 JDK7+JDK8都一樣
最大容量，必須為2^30 JDK7+JDK8都一樣
默認負載因子為0.75 達到0.75就擴容，JDK7+JDK8都一樣
樹化閾值為8，鏈表化閾值為6 JDK8新增
樹化的兩個條件：鏈表節點數達到8，且要求數組長度大于64
HashMap中最重要的兩個操作是擴容和哈希沖突，但是要注意以下幾點：
擴容是數組擴容，哈希沖突是鏈表/紅黑樹的哈希沖突，兩者是的對象是不同的，關系是擴容是為了減低負載因子，減少哈希沖突；
減少哈希沖突兩個設計：設計一個好的哈希算法 + 數組擴容；
對于真正發生了哈希沖突：JDK7是使用頭插法插入鏈表，JDK8額外添加了樹化邏輯；
無論是數組擴容還是哈希沖突后的鏈表/紅黑樹，都是發生在put操作中的，無論JDK7還是JDK8。put操作中的數組擴容和鏈表/紅黑樹哈希沖突：
JDK7的put方法：擴容 + hashcode生成index插入 + 哈希沖突；
JDK8的put方法：擴容 + hashcode生成index插入 + 哈希沖突。
2.3.2 基本元素Node
在JDK1.8中HashMap的內部結構可以看作是數組(Node[] table)和鏈表的復合結構。
數組被分為一個個桶(bucket)，通過哈希值決定了鍵值對在這個數組中的尋址(哈希值相同的鍵值對，就是哈希沖突，則以鏈表形式存儲。
如果鏈表大小超過閾值(TREEIFY_THRESHOLD,8)，圖中的鏈表就會被改造為樹形(紅黑樹)結構。
Entry的名字變成了Node，原因是和紅黑樹的實現TreeNode相關聯。1.8與1.7最大的不同就是利用了紅黑樹，即由數組+鏈表(或紅黑樹)組成。JDK1.8中，當同一個hash值的節點數不小于8時，將不再以單鏈表的形式存儲了，會被調整成一顆紅黑樹(上圖中null節點沒畫)。這就是JDK1.7與JDK1.8中HashMap實現的最大區別。
在分析JDK1.7中HashMap的哈希沖突時，不知大家是否有個疑問就是萬一發生碰撞的節點非常多怎么辦？如果說成百上千個節點在hash時發生碰撞，存儲一個鏈表中，那么如果要查找其中一個節點，那就不可避免的花費O(N)的查找時間，這將是多么大的性能損失。這個問題終于在JDK1.8中得到了解決，在最壞的情況下，鏈表查找的時間復雜度為O(n),而紅黑樹一直是O(logn),這樣會提高HashMap的效率。
JDK1.7中HashMap采用的是位桶+鏈表的方式，即我們常說的散列鏈表的方式；
JDK1.8中采用的是位桶+鏈表/紅黑樹的方式，雖然加快鏈表查找效率，但是也是非線程安全的，因為只有當某個位桶的鏈表的長度達到某個閥值的時候，這個鏈表才會轉換成紅黑樹。
小結：從JDK7的Entry變為JDK8的Node
基本元素使用Node，意為紅黑樹的節點，Node包含四個屬性：key、value、hash值和用于單向鏈表的next，和JDK7的Entry節點一樣；
hash不是用于新插入的Entry和原有的鏈表節點的hashcode比較的，只是用于計算一下數組index的；
key,value 是用于新插入的Entry和原有的鏈表的節點的 key,value 比較的，只有到equals和hashcode(index)比較都先相同，就認為是相同元素，被認為是相同元素的不插入HashMap；
next用于下一個鏈表中下一個節點。
2.3.3 插入邏輯：put()方法
通過分析put方法的源碼，可以讓這種區別更直觀：
static final int TREEIFY_THRESHOLD = 8; // 樹化 public V put(K key, V value) { return putVal(hash(key), key, value, false, true); // 調用putVal } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; //如果當前map中無數據，執行resize方法。并且返回n JDK7先擴容再插入，可能無效擴容，JDK8先插入再擴容 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //如果要插入的鍵值對要存放的這個位置剛好沒有元素，那么把他封裝成Node對象，放在這個位置上即可，插入的時候沒有哈希沖突 if ((p = tab[i = (n - 1) & hash]) == null) // 這里對p賦值，就是新的要插入的節點 tab[i] = newNode(hash, key, value, null); // 插入 //否則的話，說明這數組上面有元素，插入的時候發生哈希沖突 else { Node e; K k; //如果這個元素的key與要插入的一樣，那么就替換一下。 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 直接將p賦值給局部變量e // 1.如果這個元素的key與要插入的不一樣，如果當前節點是TreeNode類型的數據，執行putTreeVal方法 else if (p instanceof TreeNode) e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); else { // else表示如果這個元素的key與要插入的不一樣，如果還是遍歷這條鏈子上的數據，跟JDK7沒什么區別 for (int binCount = 0; ; ++binCount) { // 循環 if ((e = p.next) == null) { // 循環找到一個空位置的就插入鏈表 p.next = newNode(hash, key, value, null); //2.完成了操作后多做了一件事情，判斷，并且可能執行treeifyBin方法 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; // 插入并判斷是否樹化，break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; // 如果鏈表上已經存在了，直接break;這里不用樹化了，應該根本沒插入 p = e; // 不斷將e賦值給p,更新p,就是p在鏈條上不斷往后移動 } } // e 不為null 要么第一個if替換，要么else if樹插入，要么鏈表插入，總之插入成功了，返回oldValue if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) //true || -- e.value = value; //3. afterNodeAccess(e); return oldValue; } } ++modCount; //判斷閾值，決定是否數組擴容 插入后決定是否擴容 if (++size > threshold) resize(); //4. 插入之后的操作 afterNodeInsertion(evict); return null;????}以上代碼中的特別之處如下：
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st???????treeifyBin(tab,?hash);treeifyBin()就是將鏈表轉換成紅黑樹。
源碼解析putVal()操作(語言組織)，如下：
擴容：如果當前map中無數據，執行resize方法。并且返回n JDK8先擴容再插入，JDK7先插入再擴容，可能無效擴容沒有哈希沖突：如果要插入的鍵值對要存放的這個位置剛好沒有元素，那么把他封裝成Node對象，放在這個位置上即可，插入的時候沒有哈希沖突 這里對p賦值，就是新的要插入的節點 else 表示 否則的話，說明這數組上面有元素，插入的時候發生哈希沖突 if表示 //如果這個元素的key與要插入的一樣，那么就替換一下。 else if 表示 1.如果這個元素的key與要插入的不一樣，如果當前節點是TreeNode類型的數據，執行putTreeVal方法 else表示如果這個元素的key與要插入的不一樣，如果還是遍歷這條鏈子上的數據，跟JDK7沒什么區別 // 循環 // 循環找到一個空位置的就插入鏈表 //2.完成了操作后多做了一件事情，判斷，并且可能執行treeifyBin方法 // 插入并判斷是否樹化，break; // 如果鏈表上已經存在了，直接break;這里不用樹化了，應該根本沒插入 // 不斷將e賦值給p,更新p,就是p在鏈條上不斷往后移動 返回oldValue：e 不為null 要么第一個if替換，要么else if樹插入，要么鏈表插入，總之插入成功了，返回oldValue 插入后判斷是否擴容：判斷閾值，決定是否數組擴容 插入后決定是否擴容 最后 插入之后的操作?完成了。關于putVal()，注意以下三點：
樹化有個要求就是數組長度必須大于等于MIN_TREEIFY_CAPACITY(64)，否則繼續采用擴容策略；
resize方法兼顧兩個職責，創建初始存儲表格，或者在容量不滿足需求的時候；
在JDK1.8中取消了indefFor()方法，直接用(tab.length-1)&hash，所以看到這個，代表的就是數組的下角標。
2.3.4 treeifyBin()樹化為紅黑樹(難點：要看懂這個，一定要懂數據結構紅黑樹)
樹化操作的過程有點復雜，可以結合源碼來看看。將原本的單鏈表轉化為雙向鏈表，再遍歷這個雙向鏈表轉化為紅黑樹。
final void treeifyBin(Node[] tab, int hash) { int n, index; Node e; //樹形化還有一個要求就是數組長度必須大于等于64，否則繼續采用擴容策略 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode hd = null, tl = null;//hd指向首節點，tl指向尾節點 do { TreeNode p = replacementTreeNode(e, null);//將鏈表節點轉化為紅黑樹節點 if (tl == null) // 如果尾節點為空，說明還沒有首節點 hd = p; // 當前節點作為首節點 else { // 尾節點不為空，構造一個雙向鏈表結構，將當前節點追加到雙向鏈表的末尾 p.prev = tl; // 當前樹節點的前一個節點指向尾節點 tl.next = p; // 尾節點的后一個節點指向當前節點 } tl = p; // 把當前節點設為尾節點 } while ((e = e.next) != null); // 繼續遍歷單鏈表 //將原本的單鏈表轉化為一個節點類型為TreeNode的雙向鏈表 if ((tab[index] = hd) != null) // 把轉換后的雙向鏈表，替換數組原來位置上的單向鏈表 hd.treeify(tab); // 將當前雙向鏈表樹形化 }}特別注意：樹化有個要求就是數組長度必須大于等于MIN_TREEIFY_CAPACITY(64)，否則繼續采用擴容策略。
總的來說，HashMap默認采用數組+單鏈表方式存儲元素，當元素出現哈希沖突時，會存儲到該位置的單鏈表中。但是單鏈表不會一直增加元素，當元素個數超過8個時，會嘗試將單鏈表轉化為紅黑樹存儲。但是在轉化前，會再判斷一次當前數組的長度，只有數組長度大于64才處理。否則，進行擴容操作。
將雙向鏈表轉化為紅黑樹的實現：
final void treeify(Node[] tab) { TreeNode root = null; // 定義紅黑樹的根節點 for (TreeNode x = this, next; x != null; x = next) { // 從TreeNode雙向鏈表的頭節點開始逐個遍歷 next = (TreeNode)x.next; // 頭節點的后繼節點 x.left = x.right = null; if (root == null) { x.parent = null; x.red = false; root = x; // 頭節點作為紅黑樹的根，設置為黑色 } else { // 紅黑樹存在根節點 K k = x.key; int h = x.hash; Class> kc = null; for (TreeNode p = root;;) { // 從根開始遍歷整個紅黑樹 int dir, ph; K pk = p.key; if ((ph = p.hash) > h) // 當前紅黑樹節點p的hash值大于雙向鏈表節點x的哈希值 dir = -1; else if (ph < h) // 當前紅黑樹節點的hash值小于雙向鏈表節點x的哈希值 dir = 1; else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) // 當前紅黑樹節點的hash值等于雙向鏈表節點x的哈希值，則如果key值采用比較器一致則比較key值 dir = tieBreakOrder(k, pk); //如果key值也一致則比較className和identityHashCode TreeNode xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { // 如果當前紅黑樹節點p是葉子節點，那么雙向鏈表節點x就找到了插入的位置 x.parent = xp; if (dir <= 0) //根據dir的值，插入到p的左孩子或者右孩子 xp.left = x; else xp.right = x; root = balanceInsertion(root, x); //紅黑樹中插入元素，需要進行平衡調整(過程和TreeMap調整邏輯一模一樣) break; } } } } //將TreeNode雙向鏈表轉化為紅黑樹結構之后，由于紅黑樹是基于根節點進行查找，所以必須將紅黑樹的根節點作為數組當前位置的元素 moveRootToFront(tab, root);}然后將紅黑樹的根節點移動端數組的索引所在位置上：
static void moveRootToFront(Node[] tab, TreeNode root) { int n; if (root != null && tab != null && (n = tab.length) > 0) { int index = (n - 1) & root.hash; //找到紅黑樹根節點在數組中的位置 TreeNode first = (TreeNode)tab[index]; //獲取當前數組中該位置的元素 if (root != first) { //紅黑樹根節點不是數組當前位置的元素 Node rn; tab[index] = root; TreeNode rp = root.prev; if ((rn = root.next) != null) //將紅黑樹根節點前后節點相連 ((TreeNode)rn).prev = rp; if (rp != null) rp.next = rn; if (first != null) //將數組當前位置的元素，作為紅黑樹根節點的后繼節點 first.prev = root; root.next = first; root.prev = null; } assert checkInvariants(root); }}putVal方法處理的邏輯比較多，包括初始化、擴容、樹化，近乎在這個方法中都能體現，針對源碼簡單講解下幾個關鍵點：
如果Node[] table是null，resize方法會負責初始化，即如下代碼：
if ((tab = table) == null || (n = tab.length) == 0)????n?=?(tab?=?resize()).length;resize方法兼顧兩個職責：創建初始存儲表格 + 在容量不滿足需求的時候進行擴容(resize)。
在放置新的鍵值對的過程中，如果發生下面條件，就會發生擴容。
if (++size > threshold)????resize();具體鍵值對在哈希表中的位置(數組index)取決于下面的位運算：
i?=?(n?-?1)?&?hash仔細觀察哈希值的源頭，會發現它并不是key本身的hashCode，而是來自于HashMap內部的另一個hash方法。為什么這里需要將高位數據移位到低位進行異或運算呢？這是因為有些數據計算出的哈希值差異主要在高位，而HashMap里的哈希尋址是忽略容量以上的高位的，那么這種處理就可以有效避免類似情況下的哈希碰撞。
在JDK1.8中取消了indefFor()方法，直接用(tab.length-1)&hash，所以看到這個，代表的就是數組的下角標。
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}2.3.5 JDK8中的HashMap的王牌功能：問題1：HashMap為什么要樹化？
問題：JDK8中的HashMap的王牌功能：為什么HashMap為什么要樹化？
回答：一句話概括：制造哈希碰撞從而造成DOS攻擊，樹化后優化哈希碰撞產生后的存取。
解釋：其實這本質上一個安全問題。因為在元素放置過程中，如果一個對象哈希沖突，都被放置到同一個桶里，則會形成一個鏈表，我們知道鏈表查詢是線性的，會嚴重影響存取的性能。而在現實世界，構造哈希沖突的數據并不是非常復雜的事情，惡意代碼就可以利用這些數據大量與服務器端交互，導致服務器端CPU大量占用，這就構成了哈希碰撞拒絕服務攻擊，國內一線互聯網公司就發生過類似攻擊事件。
哈希碰撞攻擊：用哈希碰撞發起拒絕服務攻擊(DOS，Denial-Of-Service attack),常見的場景是攻擊者可以事先構造大量相同哈希值的數據(制造哈希碰撞從而造成DOS攻擊，樹化后優化哈希碰撞產生后的存取)，然后以JSON數據的形式發送給服務器，服務器端在將其構建成為Java對象過程中，通常以HashTable或HashMap等形式存儲，哈希碰撞將導致哈希表發生嚴重退化，算法復雜度可能上升一個數據級，進而耗費大量CPU資源。
2.3.6 JDK8中的HashMap的王牌功能：問題2：鏈表樹化的兩個條件？/為什么要將鏈表中轉紅黑樹的閾值設為8？
我們可以這么來看，當鏈表長度大于或等于閾值(默認為 8)的時候，如果同時還滿足容量大于或等于 MIN_TREEIFY_CAPACITY(默認為 64)的要求，就會把鏈表轉換為紅黑樹。同樣，后續如果由于刪除或者其他原因調整了大小，當紅黑樹的節點小于或等于 6 個以后，又會恢復為鏈表形態。
每次遍歷一個鏈表，平均查找的時間復雜度是 O(n)，n 是鏈表的長度。紅黑樹有和鏈表不一樣的查找性能，由于紅黑樹有自平衡的特點，可以防止不平衡情況的發生，所以可以始終將查找的時間復雜度控制在 O(log(n))。最初鏈表還不是很長，所以可能 O(n) 和 O(log(n)) 的區別不大，但是如果鏈表越來越長，那么這種區別便會有所體現。所以為了提升查找性能，需要把鏈表轉化為紅黑樹的形式。
還要注意很重要的一點，單個 TreeNode 需要占用的空間大約是普通 Node 的兩倍，所以只有當包含足夠多的 Nodes 時才會轉成 TreeNodes，而是否足夠多就是由 TREEIFY_THRESHOLD 的值決定的。而當桶中節點數由于移除或者 resize 變少后，又會變回普通的鏈表的形式，以便節省空間。
默認是鏈表長度達到 8 就轉成紅黑樹，而當長度降到 6 就轉換回去，這體現了時間和空間平衡的思想，最開始使用鏈表的時候，空間占用是比較少的，而且由于鏈表短，所以查詢時間也沒有太大的問題。可是當鏈表越來越長，需要用紅黑樹的形式來保證查詢的效率。
在理想情況下，鏈表長度符合泊松分布，各個長度的命中概率依次遞減，當長度為 8 的時候，是最理想的值。
事實上，鏈表長度超過 8 就轉為紅黑樹的設計，更多的是為了防止用戶自己實現了不好的哈希算法時導致鏈表過長，從而導致查詢效率低，而此時轉為紅黑樹更多的是一種保底策略，用來保證極端情況下查詢的效率。
通常如果 hash 算法正常的話，那么鏈表的長度也不會很長，那么紅黑樹也不會帶來明顯的查詢時間上的優勢，反而會增加空間負擔。所以通常情況下，并沒有必要轉為紅黑樹，所以就選擇了概率非常小，小于千萬分之一概率，也就是長度為 8 的概率，把長度 8 作為轉化的默認閾值。
鏈表樹化的兩個條件：當鏈表長度大于或等于閾值(默認為 8)的時候，并且同時還滿足容量大于或等于 MIN_TREEIFY_CAPACITY(默認為 64)的要求
處理哈希沖突兩個方法：一個好的哈希算法、鏈表樹化(前者才是根本，后者只是網絡安全制造哈希
問題：JDK8中的HashMap的王牌功能：鏈表樹化的兩個條件？/為什么要將鏈表中轉紅黑樹的閾值設為8？
回答：碰撞從而造成DOS攻擊和不合理哈希算法的處理)，所以設計為8。通常如果 hash 算法正常的話，那么鏈表的長度也不會很長，那么紅黑樹也不會帶來明顯的查詢時間上的優勢，反而會增加空間負擔。所以通常情況下，并沒有必要轉為紅黑樹，所以就選擇了概率非常小，小于千萬分之一概率，也就是長度為 8 的概率，把長度 8 作為轉化的默認閾值。
值得注意的是，實際開發中，發現 HashMap 內部出現了紅黑樹的結構，那可能是我們的哈希算法出了問題，所以需要選用合適的hashCode方法，以便減少沖突。
問題：為什么在JDK1.8中進行對HashMap優化的時候，把鏈表轉化為紅黑樹的閾值是8,而不是7或者不是20呢？
標準回答：
第一，避免頻繁轉換，樹化鏈表化轉換成本與二叉樹優化查詢性能之間的平衡：如果選擇6和8(如果鏈表小于等于6樹還原轉為鏈表，大于等于8轉為樹)，中間有個差值7可以有效防止鏈表和樹頻繁轉換。假設一下，如果設計成鏈表個數超過8則鏈表轉換成樹結構，鏈表個數小于8則樹結構轉換成鏈表，如果一個HashMap不停的插入、刪除元素，鏈表個數在8左右徘徊，就會頻繁的發生樹轉鏈表、鏈表轉樹，效率會很低。
第二，數學證明，泊松分布：還有一點重要的就是由于treenodes的大小大約是常規節點的兩倍，因此我們僅在容器包含足夠的節點以保證使用時才使用它們，當它們變得太小(由于移除或調整大小)時，它們會被轉換回普通的node節點，容器中節點分布在hash桶中的頻率遵循泊松分布，桶的長度超過8的概率非常非常小。所以作者應該是根據概率統計而選擇了8作為閥值
第三，統計學問題：一個統計的問題，java設計一定使用數學方法和統計方法，知道得到這個8，就像豐巢快遞為什么是12小時而不是24小時一樣。
2.4 HashMap在1.7和1.8之間四個不同(對比方式,重要)
我們可以簡單列下HashMap在1.7和1.8之間的變化，四點變化(除了底層結構，都要從源碼層面解釋)：
第一，底層數據結構不同
1.7中采用數組+鏈表，1.8采用的是數組+鏈表/紅黑樹，即在1.7中鏈表長度超過一定長度后就改成紅黑樹存儲。
第二，index：擴容后index的計算
1.7擴容時需要重新計算哈希值hash，根據hash計算索引位置index，equals比較鏈表上的元素。
1.8并不重新計算哈希值hash，巧妙地采用和擴容后容量進行&操作來計算新的索引位置index，即index = hash & (tab.length - 1) 。
第三，插入：哈希沖突的時候插入的值*
1.7是采用表頭插入法插入鏈表，1.8采用的是尾部插入法。
在1.7中采用表頭插入法，
缺點：因為頭插法，在擴容時會改變鏈表中元素原本的順序，以至于在并發場景下導致鏈表成環的問題；
優點：JDK7考慮剛剛插入的值是熱乎的，所以放在表頭；
在1.8中采用尾部插入法，
優點：因為尾插法，所以在擴容時會保持鏈表元素原本的順序，就不會出現鏈表成環的問題了；
缺點：因為尾插法，所有剛剛插入的節點放在最后面了，要找很麻煩，所以引入鏈表樹化，超過8個節點就可以樹化，找新插入的節點只要O(lgN)。
第四，擴容的時機：擴容與插入的先后順序
1.7中是先擴容后插入新值的，1.8中是先插值再擴容
問題：為什么在JDK1.7的時候是先進行擴容后進行插入，而在JDK1.8的時候則是先插入后進行擴容的呢？
答案：代碼就是這樣寫的，JDK8插入的時候使用了樹化，所以將數組擴容放到了后面。
對于JDK1.8
在JDK1.7中的話，是先進行插入新值然后進行擴容操作的，主要是因為對鏈表轉為紅黑樹進行的優化，因為你插入這個節點的時候有可能是普通鏈表節點，也有可能是紅黑樹節點，所以導致先插入后擴容，擴容判斷與resize()函數調用如下：
對于JDK1.7
在JDK1.7中的話，是先進行擴容操作然后進行插入新值的，就是當你發現你插入的桶是不是為空：
(1)如果不為空說明存在值，當前插入會發生哈希沖突，那么就必須得擴容；
(2)如果為空說明不存在值，當前插入不會發生哈希沖突，那么本次插入不需要擴容，那就等到下一次發生Hash沖突的時候在進行擴容，但是當如果以后都沒有發生hash沖突產生，那么就不會進行擴容了，減少了一次無用擴容，也減少了內存的使用。
先擴容后插入代碼邏輯如下：
三、其他：HashTable、TreeMap、ConcurrentHashMap
3.1 HashTable
3.2 TreeMap
TreeMap需要注意的三點：
key-value是否為null，和HashTable一樣：
與HashMap不同的是，TreeMap鍵、值都不能為null；
紅黑樹是排序二叉樹：
TreeMap自定義排序器，底層如何實現排序：樹中的每個節點的值都會大于或等于它的左子樹中的所有節點的值，并且小于或等于它的右子樹中的所有節點的值；
紅黑樹是平衡二叉樹-時間復雜度：
與HashMap不同的是它的get、put、remove之類操作都是O(log(n))的時間復雜度。
對TreeMap做成如下小結：
TreeMap是基于紅黑樹的一種提供順序訪問的Map，與HashMap不同的是它的get、put、remove之類操作都是o(log(n))的時間復雜度，具體順序可以由指定的Comparator來決定，或者根據鍵的自然順序來判斷。
3.3 ConcurrentHashMap(核心:鎖機制)
Java5提供了ConcurrentHashMap，它是HashTable的替代，比HashTable的擴展性更好，ConcurrentHashMap底層采用分段的數組+鏈表實現，是線程安全。
先看一下ConcurrentHashMap的類圖：
由上面類圖，左邊是HashMap，右邊是ConcurrentHashMap，它都是繼承自AbstractMap抽象類，但是，在存儲結構中，ConcurrentHashMap比HashMap多出了一個類Segment，而Segment就是一個可重入鎖，這個Segment就是ConcurrentHashMap實現分段鎖的關鍵，ConcurrentHashMap也正是使用這種鎖分段技術來保證線程安全的。
鎖分段技術定義：首先將數據分成一段一段的存儲，然后給每一段數據配一把鎖，當一個線程占用鎖訪問其中一個段數據的時候，其他段的數據也能被其他線程訪問。
ConcurrentHashMap與HashTable的不同：
HashTable中采用的鎖機制是一次鎖住整個hash表，從而在同一時刻只能由一個線程對其進行操作；而ConcurrentHashMap中則是一次鎖住一個桶。
ConcurrentHashMap默認將hash表分為16個桶，諸如get、put、remove等常用操作只鎖住當前需要用到的桶。這樣，原來只能一個線程進入，現在卻能同時有16個寫線程執行，并發性能的提升是顯而易見的。
問題：ConcurrentHashMap是如何實現鎖機制的？
回答：
實現上，Segment內部類實現分段：
ConcurrentHashMap具有一個內部類Segment，正是因為內部類Segment，將數據分成一段一段的存儲，然后給每一段數據配一把鎖，當一個線程占用鎖訪問其中一個段數據的時候，其他段的數據也能被其他線程訪問；
實現上，ConcurrentHashMap分段鎖就是Lock鎖：
Segement extends ReentrantLock implements Serializable，所以說ConcurrentHashMap中的分段鎖就是一種普通的Lock鎖；
方法上，段內方法，分段操作，性能提高16倍，get() put() remove()：
ConcurrentHashMap默認將hash表分為16個桶，諸如get、put、remove等常用操作只鎖住當前需要用到的桶。ConcurrentHashMap是HashTable的替代，HashTable中采用的鎖機制是一次鎖住整個hash表，從而在同一時刻只能由一個線程對其進行操作，而ConcurrentHashMap中則是一次鎖住一個桶；
方法上，擴容方法，分段鎖實現段內擴容resize()：
段內數組擴容(段內元素超過該段對應Entry數組長度的75%觸發擴容，不會對整個Map進行擴容)，插入前檢測需不需要擴容，有效避免無效擴容；
方法上，跨段方法，跨段方法size()和containsValue()：
有些方法需要跨段，比如size()和containsValue()，它們可能需要鎖定整個表而而不僅僅是某個段，這需要按順序鎖定所有段，操作完畢后，又按順序釋放所有段的鎖；
讀不加鎖、寫加鎖：
讀操作不加鎖，由于HashEntry的value變量是 volatile的，也能保證讀取到最新的值。
3.4 HashTable/ConcurrentHashMap、HashMap、TreeMap
存儲內容為key-value鍵值對：
存儲的內容是基于key-value的鍵值對映射，不能有重復的key，而且一個key只能映射一個value。HashSet底層就是基于HashMap實現的。
key、value是否為null：
HashTable的key、value都不能為null；TreeMap鍵、值都不能為null；HashMap的key、value可以為null，不過只能有一個key為null，但可以有多個null的value；
HashTable、HashMap具有無序特性，TreeMap默認升序，可以自定義排序方式：
HashTable、HashMap具有無序特性，TreeMap是利用紅黑樹實現的(金手指：TreeMap自定義排序器，底層如何實現排序：樹中的每個節點的值都會大于或等于它的左子樹中的所有節點的值，并且小于或等于它的右子樹中的所有節點的值)，實現了SortMap接口，能夠對保存的記錄根據鍵進行排序。所以一般需求排序的情況下首選TreeMap，默認按鍵的升序排序(深度優先搜索)，也可以自定義實現Comparator接口實現排序方式。
選用原則：一般用HashMap，需要排序使用TreeMap，需要保證線程安全使用ConcurrentHashMap
一般情況下選用HashMap，因為HashMap的鍵值對在取出時是隨機的，其依據鍵的hashCode和鍵的equals方法存取數據，具有很快的訪問速度，所以在Map中插入、刪除及索引元素時其是效率最高的實現。其他的，TreeMap的鍵值對在取出時是排過序的，效率會低一點，而HashTable/ConcurrentHashMap是線程安全的，效率也低一點。
四、小結
HashMap全解析，完成了。
天天打碼，天天進步！！！
寫留言
總結
以上是生活随笔為你收集整理的hashmap value占用空间大小_【Java集合框架002】原理层面：HashMap全解析的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： php 获取京东交易账号,PHP爬虫爬取
- 下一篇： 公积金一定要买房才能用吗？公积金怎么提取