前言
很高興遇見你~
HashMap是一個非常重要的集合，日常使用也非常的頻繁，同時也是面試重點。本文并不打算講解基礎的使用api，而是深入HashMap的底層，講解關于HashMap的重點知識。需要讀者對散清單和HashMap有一定的認識。
HashMap本質上是一個散清單，那麼就離不開散清單的三大問題： 散列函數、哈希沖突、擴容方案 ；同時作為一個資料結構，必須考慮多線程并發通路的問題，也就是 線程安全 。這四大重點則為學習HashMap的重點，也是HashMap設計的重點。
HashMap屬于Map集合體系的一部分，同時繼承了Serializable接口可以被序列化，繼承了Cloneable接口可以被複制。他的的繼承結構如下：
阿裡二面：說一下Hashmap散清單的三大問題與線程安全問題
HashMap并不是全能的，對于一些特殊的情景下的需求官方拓展了一些其他的類來滿足，如線程安全的ConcurrentHashMap、記錄插入順序的LinkHashMap、給key排序的TreeMap等。
文章内容主要講解四大重點： 散列函數、哈希沖突、擴容方案、線程安全 ，再補充關鍵的源碼分析和相關的問題。
本文所有内容如若未特殊說明，均為JDK1.8版本。
哈希函數
哈希函數的目标是計算key在數組中的下标。判斷一個哈希函數的标準是：散列是否均勻、計算是否簡單。
HashMap哈希函數的步驟：
對key對象的 hashcode 進行擾動
通過取模求得數組下标
擾動是為了讓hashcode的随機性更高，第二步取模就不會讓是以的key都聚集在一起，提高散列均勻度。擾動可以看到 hash() 方法：
static final int hash(Object key) {
int h;
// 擷取到key的hashcode，在高低位異或運算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
也就是低16位是和高16位進行異或，高16位保持不變。一般的數組長度都會比較短，取模運算中隻有低位參與散列；高位與地位進行異或，讓高位也得以參與散列運算，使得散列更加均勻。具體運算如下圖(圖中為了友善采用8位進行示範，32位同理)：
阿裡二面：說一下Hashmap散清單的三大問題與線程安全問題
對hashcode擾動之後需要對結果進行取模。HashMap在jdk1.8并不是簡單使用 % 進行取模，而是采用了另外一種更加高性能的方法。HashMap控制數組長度為2的整數次幂，好處是對hashcode進行求餘運算和讓hashcode與數組長度-1進行位與運算是相同的效果。如下圖：
阿裡二面：說一下Hashmap散清單的三大問題與線程安全問題
但位與運算的效率卻比求餘高得多，進而提升了性能。在擴容運算中也利用到了此特性，後面會講。取模運算的源碼看到 putVal() 方法，該方法在 put() 方法中被調用：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
...
// 與數組長度-1進行位與運算，得到下标
if ((p = tab[i = (n - 1) & hash]) == null)
...
}
完整的hash計算過程可以參考下圖：
阿裡二面：說一下Hashmap散清單的三大問題與線程安全問題
上面我們提到HashMap的數組長度為2的整數次幂，那麼HashMap是如何控制數組的長度為2的整數次幂的？修改數組長度有兩種情況：
初始化時指定的長度
擴容時的長度增量
先看第一種情況。預設情況下，如未在HashMap構造器中指定長度，則初始長度為16。 16是一個較為合适的經驗值，他是2的整數次幂，同時太小會頻繁觸發擴容、太大會浪費空間 。如果指定一個非2的整數次幂，會自動轉化成 大于該指定數的最小2的整數次幂 。如指定6則轉化為8，指定11則轉化為16。結合源碼來分析，當我們初始化指定一個非2的整數次幂長度時，HashMap會調用 tableSizeFor() 方法：
public HashMap(int initialCapacity, float loadFactor) {
...
this.loadFactor = loadFactor;
// 這裡調用了tableSizeFor方法
this.threshold = tableSizeFor(initialCapacity);
}
static final int tableSizeFor(int cap) {
// 注意這裡必須減一
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
tableSizeFor() 方法的看起來很複雜，作用是使得最高位1後續的所有位都變為1，最後再+1則得到剛好大于initialCapacity的最小2的整數次幂數。如下圖(這裡使用了8位進行模拟，32位也是同理)：
阿裡二面：說一下Hashmap散清單的三大問題與線程安全問題
那為什麼必須要對 cap 進行 -1 之後再進行運算呢？如果指定的數剛好是2的整數次幂，如果沒有-1結果會變成比他大兩倍的數，如下：
00100 --高位1之後全變1--> 00111 --加1---> 01000
第二種改變數組長度的情況是擴容。HashMap每次擴容的大小都是原來的兩倍，控制了數組大小一定是2的整數次幂，相關源碼如下：
final Node[] resize() {
...
if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 設定為原來的兩倍
newThr = oldThr << 1;
...
}
小結：
HashMap通過高16位與低16位進行異或運算來讓高位參與散列，提高散列效果；
HashMap控制數組的長度為2的整數次幂來簡化取模運算，提高性能；
HashMap通過控制初始化的數組長度為2的整數次幂、擴容為原來的2倍來控制數組長度一定為2的整數次幂。
哈希沖突解決方案
再優秀的hash算法永遠無法避免出現hash沖突。hash沖突指的是兩個不同的key經過hash計算之後得到的數組下标是相同的。解決hash沖突的方式很多，如開放定址法、再哈希法、公共溢出表法、鍊位址法。HashMap采用的是鍊位址法，jdk1.8之後還增加了紅黑樹的優化，如下圖：
阿裡二面：說一下Hashmap散清單的三大問題與線程安全問題
出現沖突後會在目前節點形成連結清單，而當連結清單過長之後，會自動轉化成紅黑樹提高查找效率。紅黑樹是一個查找效率很高的資料結構，時間複雜度為O(logN)，但紅黑樹隻有在資料量較大時才能發揮它的優勢。關于紅黑樹的轉化，HashMap做了以下限制
當連結清單的長度>=8且數組長度>=64時，會把連結清單轉化成紅黑樹。
當連結清單長度>=8，當數組長度<64時，會優先進行擴容，而不是轉化成紅黑樹。
當紅黑樹節點數<=6，自動轉化成連結清單。
那就有了以下問題：
為什麼需要數組長度到64才會轉化紅黑樹？當數組長度較短時，如16，連結清單長度達到8已經是占用了最大限度的50%，意味着負載已經快要達到上限，此時如果轉化成紅黑樹，之後的擴容又會再一次把紅黑樹拆分平均到新的數組中，這樣非但沒有帶來性能的好處，反而會降低性能。是以在數組長度低于64時，優先進行擴容。
為什麼要大于等于8轉化為紅黑樹，而不是7或9？樹節點的比普通節點更大，在連結清單較短時紅黑樹并未能明顯展現性能優勢，反而會浪費空間，在連結清單較短是采用連結清單而不是紅黑樹。在理論數學計算中(裝載因子=0.75)，連結清單的長度到達8的機率是百萬分之一；把7作為分水嶺，大于7轉化為紅黑樹，小于7轉化為連結清單。紅黑樹的出現是為了在某些極端的情況下，抗住大量的hash沖突，正常情況下使用連結清單是更加合适的。
注意，紅黑樹在jdk1.8之後出現的，jdk1.7采用的是數組+連結清單模式。
小結：
HashMap采用鍊位址法，當發生沖突時會轉化為連結清單，當連結清單過長會轉化為紅黑樹提高效率。
HashMap對紅黑樹進行了限制，讓紅黑樹隻有在極少數極端情況下進行抗壓。
擴容方案
當HashMap中的資料越來越多，那麼發生hash沖突的機率也就會越來越高，通過數組擴容可以利用空間換時間，保持查找效率在常數時間複雜度。那什麼時候進行擴容？由HashMap的一個關鍵參數控制： 裝載因子 。
裝載因子=HashMap中節點數/數組長度，他是一個比例值。當HashMap中節點數到達裝載因子這個比例時，就會觸發擴容；也就是說，裝載因子控制了目前數組能夠承載的節點數的門檻值 。如數組長度是16，裝載因子是0.75，那麼可容納的節點數是16*0.75=12。裝載因子的數值大小需要仔細權衡。裝載因子越大，數組使用率越高，同時發生哈希沖突的機率也就越高；裝載因子越小，數組使用率降低，但發生哈希沖突的機率也降低了。是以 裝載因子的大小需要權衡空間與時間之間的關系 。在理論計算中，0.75是一個比較合适的數值，大于0.75哈希沖突的機率呈指數級别上升，而小于0.75沖突減少并不明顯。HashMap中的裝載因子的預設大小是0.75，沒有特殊要求的情況下，不建議修改他的值。
那麼在到達門檻值之後，HashMap是如何進行擴容的呢？HashMap會把數組長度擴充為原來的兩倍，再把舊數組的資料遷移到新的數組，而HashMap針對遷移做了優化： 使用HashMap數組長度是2的整數次幂的特點，以一種更高效率的方式完成資料遷移 。
JDK1.7之前的資料遷移比較簡單，就是周遊所有的節點，把所有的節點依次通過hash函數計算新的下标，再插入到新數組的連結清單中。這樣會有兩個缺點： 1、每個節點都需要進行一次求餘計算；2、插入到新的數組時候采用的是頭插入法，在多線程環境下會形成連結清單環。 jdk1.8之後進行了優化，原因在于他控制數組的長度始終是2的整數次幂，每次擴充數組都是原來的2倍，帶來的好處是key在新的數組的hash結果隻有兩種：在原來的位置，或者在原來位置+原數組長度。具體為什麼我們可以看下圖：
阿裡二面：說一下Hashmap散清單的三大問題與線程安全問題
從圖中我們可以看到，在新數組中的hash結果，僅僅取決于高一位的數值。如果高一位是0，那麼計算結果就是在原位置，而如果是1，則加上原數組的長度即可。這樣我們 隻需要判斷一個節點的高一位是1 or 0就可以得到他在新數組的位置，而不需要重複hash計算 。HashMap 把每個連結清單拆分成兩個連結清單，對應原位置或原位置+原數組長度，再分别插入到新的數組中，保留原來的節點順序 ，如下：
阿裡二面：說一下Hashmap散清單的三大問題與線程安全問題
前面還遺留一個問題：頭插法會形成連結清單環。這個問題線上程安全部分講解。
小結：
裝載因子決定了HashMap擴容的門檻值，需要權衡時間與空間，一般情況下保持0.75不作改動；
HashMap擴容機制結合了數組長度為2的整數次幂的特點，以一種更高的效率完成資料遷移，同時避免頭插法造成連結清單環。
線程安全
HashMap作為一個集合，主要功能則為CRUD，也就是增删查改資料，那麼就肯定涉及到多線程并發通路資料的情況。并發産生的問題，需要我們特别關注。
HashMap并不是線程安全的，在多線程的情況下無法保證資料的一緻性。舉個例子：HashMap下标2的位置為null，線程A需要将節點X插入下标2的位置，在判斷是否為null之後，線程被挂起；此時線程B把新的節點Y插入到下标2的位置；恢複線程A，節點X會直接插入到下标2，覆寫節點Y，導緻資料丢失，如下圖：
阿裡二面：說一下Hashmap散清單的三大問題與線程安全問題
jdk1.7及以前擴容時采用的是頭插法，這種方式插入速度快，但在多線程環境下會造成連結清單環，而連結清單環會在下一次插入時找不到連結清單尾而發生死循環。限于篇幅，關于這個問題可參考 面試官：HashMap 為什麼線程不安全？ ，作者詳細解答了關于HashMap的并發問題。jdk1.8之後擴容采用了尾插法，解決了這個問題，但并沒有解決資料的一緻性問題。
那如果結果資料一緻性問題呢？解決這個問題有三個方案：
Collections.synchronizeMap()
ConcurrentHashMap
前兩個方案的思路是相似的，均是每個方法中，對整個對象進行上鎖。Hashtable是老一代的集合架構，很多的設計均以及落後，他在每一個方法中均加上了 synchronize 關鍵字保證線程安全
// Hashtable
public synchronized V get(Object key) {...}
public synchronized V put(K key, V value) {...}
public synchronized V remove(Object key) {...}
public synchronized V replace(K key, V value) {...}
...
第二種方法是傳回一個 SynchronizedMap 對象，這個對象預設每個方法會鎖住整個對象。如下源碼：
阿裡二面：說一下Hashmap散清單的三大問題與線程安全問題
這裡的mutex是什麼呢？直接看到構造器：
final Object mutex; // Object on which to synchronize
SynchronizedMap(Map m) {
this.m = Objects.requireNonNull(m);
// 預設為本對象
mutex = this;
}
SynchronizedMap(Map m, Object mutex) {
this.m = m;
this.mutex = mutex;
}
可以看到預設鎖的就是本身，效果和Hashtable其實是一樣的。這種簡單粗暴鎖整個對象的方式造成的後果是：
鎖是非常重量級的，會嚴重影響性能。
同一時間隻能有一個線程進行讀寫，限制了并發效率。
ConcurrentHashMap的設計就是為了解決此問題。他通過降低鎖粒度+CAS的方式來提高效率。簡單來說，ConcurrentHashMap鎖的并不是整個對象，而是一個 數組的一個節點 ，那麼其他線程通路數組其他節點是不會互相影響，極大提高了并發效率；同時ConcurrentHashMap的操作并不需要擷取鎖，如下圖：
阿裡二面：說一下Hashmap散清單的三大問題與線程安全問題
關于ConcurrentHashMap和Hashtable的更多内容，限于篇幅，我會在另一篇文章講解。
那麼，使用了上述的三種解決方案是不是絕對線程安全？先觀察下面的代碼：
ConcurrentHashMap map = new ConcurrentHashMap<>();
map.put("abc","123");
Thread1:
if (map.containsKey("abc")){
String s = map.get("abc");
}
Thread2:
map.remove("abc");
當Thread1調用containsKey之後釋放鎖，Thread2獲得鎖并把“abc”移除再釋放鎖，這個時候Thread1讀取到的s就是一個null了，也就出現了問題了。是以 ConcurrentHashMap 類或者 Collections.synchronizeMap() 方法或者Hashtable都隻能在一定的限度上保證線程安全，而無法保證絕對線程安全。
關于線程安全，還有一個 fast-fail 問題，即快速失敗。當使用HashMap的疊代器周遊HashMap時，如果此時HashMap發生了結構性改變，如插入新資料、移除資料、擴容等，那麼Iteractor會抛出fast-fail異常，防止出現并發異常，在一定限度上保證了線程安全。如下源碼：
final Node nextNode() {
...
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
...
}
建立Iteractor對象時會記錄HashMap的 modCount 變量，每當HashMap發生結構性改變時， modCount 會加1。在疊代時判斷HashMap的 modCount 和自己儲存的expectedModCount 是否一緻即可判斷是否發生了結構性改變。
fast-fail異常隻能當做周遊時的一種安全保證，而不能當做多線程并發通路HashMap的手段。若有并發需求，還是需要使用上述的三種方法。
小結
HashMap并不能保證線程安全，在多線程并發通路下會出現意想不到的問題，如資料丢失等
HashMap1.8采用尾插法進行擴容，防止出現連結清單環導緻的死循環問題
解決并發問題的的方案有 Hashtable 、 Collections.synchronizeMap() 、ConcurrentHashMap 。其中最佳解決方案是 ConcurrentHashMap
上述解決方案并不能完全保證線程安全
快速失敗是HashMap疊代機制中的一種并發安全保證
源碼解析
關鍵變量的了解
HashMap源碼中有很多的内部變量，這些變量會在下面源碼分析中經常出現，首先需要了解這些變量的意義。
// 存放資料的數組
transient Node[] table;
// 存儲的鍵值對數目
transient int size;
// HashMap結構修改的次數，主要用于判斷fast-fail
transient int modCount;
// 最大限度存儲鍵值對的數目(threshodl=table.length*loadFactor)，也稱為門檻值
int threshold;
// 裝載因子，表示可最大容納資料數量的比例
final float loadFactor;
// 靜态内部類，HashMap存儲的節點類型；可存儲鍵值對，本身是個連結清單結構。
static class Node implements Map.Entry {...}
擴容
HashMap源碼中把初始化操作也放到了擴容方法中，因而擴容方法源碼主要分為兩部分：确定新的數組大小、遷移資料。詳細的源碼分析如下，我打了非常詳細的注釋，可選擇檢視。擴容的步驟在上述已經講過了，讀者可以自行結合源碼，分析HashMap是如何實作上述的設計。
final Node[] resize() {
// 變量分别是原數組、原數組大小、原門檻值；新數組大小、新門檻值
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 如果原數組長度大于0
if (oldCap > 0) {
// 如果已經超過了設定的最大長度(1<<30,也就是最大整型正數)
if (oldCap >= MAXIMUM_CAPACITY) {
// 直接把門檻值設定為最大正數
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 設定為原來的兩倍
newThr = oldThr << 1;
}
// 原數組長度為0，但最大限度不是0，把長度設定為門檻值
// 對應的情況就是建立HashMap的時候指定了數組長度
else if (oldThr > 0)
newCap = oldThr;
// 第一次初始化，預設16和0.75
// 對應使用預設構造器建立HashMap對象
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果原數組長度小于16或者翻倍之後超過了最大限制長度，則重新計算門檻值
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 建立新的數組
Node[] newTab = (Node[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 循環周遊原數組，并給每個節點計算新的位置
for (int j = 0; j < oldCap; ++j) {
Node e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 如果他沒有後繼節點，那麼直接使用新的數組長度取模得到新下标
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果是紅黑樹，調用紅黑樹的拆解方法
else if (e instanceof TreeNode)
((TreeNode)e).split(this, newTab, j, oldCap);
// 新的位置隻有兩種可能：原位置，原位置+老數組長度
// 把原連結清單拆成兩個連結清單，然後再分别插入到新數組的兩個位置上
// 不用多次調用put方法
else {
// 分别是原位置不變的連結清單和原位置+原數組長度位置的連結清單
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
// 周遊老連結清單，判斷新增判定位是1or0進行分類
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 最後指派給新的數組
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
// 傳回新數組
return newTab;
}
添加數值
調用 put() 方法添加鍵值對，最終會調用 putVal() 來真正實作添加邏輯。代碼解析如下：
public V put(K key, V value) {
// 擷取hash值，再調用putVal方法插入資料
return putVal(hash(key), key, value, false, true);
}
// onlyIfAbsent表示是否覆寫舊值，true表示不覆寫，false表示覆寫，預設為false
// evict和LinkHashMap的回調方法有關，不在本文讨論範圍
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// tab是HashMap内部數組，n是數組的長度，i是要插入的下标，p是該下标對應的節點
Node[] tab; Node p; int n, i;
// 判斷數組是否是null或者是否是空，若是，則調用resize()方法進行擴容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 使用位與運算代替取模得到下标
// 判斷目前下标是否是null，若是則建立節點直接插入，若不是，進入下面else邏輯
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// e表示和目前key相同的節點，若不存在該節點則為null
// k是目前數組下标節點的key
Node e; K k;
// 判斷目前節點與要插入的key是否相同，是則表示找到了已經存在的key
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 判斷該節點是否是樹節點，如果是調用紅黑樹的方法進行插入
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
// 最後一種情況是直接連結清單插入
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 長度大于等于8時轉化為紅黑樹
// 注意，treeifyBin方法中會進行數組長度判斷，
// 若小于64，則優先進行數組擴容而不是轉化為樹
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
// 找到相同的直接跳出循環
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 如果找到相同的key節點，則判斷onlyIfAbsent和舊值是否為null
// 執行更新或者不操作，最後傳回舊值
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 如果不是更新舊值，說明HashMap中鍵值對數量發生變化
// modCount數值+1表示結構改變
++modCount;
// 判斷長度是否達到最大限度，如果是則進行擴容
if (++size > threshold)
resize();
// 最後傳回null(afterNodeInsertion是LinkHashMap的回調)
afterNodeInsertion(evict);
return null;
}
代碼中關于每個步驟有了詳細的解釋，這裡來總結一下：
總體上分為兩種情況：找到相同的key和找不到相同的key。找了需要判斷是否更新并傳回舊value，沒找到需要插入新的Node、更新節點數并判斷是否需要擴容。
查找分為三種情況：數組、連結清單、紅黑樹。數組下标i位置不為空且不等于key，那麼就需要判斷是否樹節點還是連結清單節點并進行查找。
連結清單到達一定長度後需要擴充為紅黑樹，當且僅當連結清單長度>=8且數組長度>=64。
最後畫一張圖總體再加深一下整個流程的印象：
阿裡二面：說一下Hashmap散清單的三大問題與線程安全問題
其他問題
為什麼jdk1.7以前控制數組的長度為素數，而jdk1.8之後卻采用的是2的整數次幂？
答：素數長度可以有效減少哈希沖突；JDK1.8之後采用2的整數次幂是為了提高求餘和擴容的效率，同時結合高低位異或的方法使得哈希散列更加均勻。
為何素數可以減少哈希沖突？若能保證key的hashcode在每個數字之間都是均勻分布，那麼無論是素數還是合數都是相同的效果。例如hashcode在1~20均勻分布，那麼無論長度是合數4，還是素數5，分布都是均勻的。而如果hashcode之間的間隔都是2，如1,3,5...,那麼長度為4的數組，位置2和位置4兩個下标無法放入資料，而長度為5的數組則沒有這個問題。 長度為合數的數組會使間隔為其因子的hashcode聚集出現，進而使得散列效果降低 。詳細的内容可以參考這篇部落格： 算法分析：哈希表的大小為何是素數 ,這篇部落格采用資料分析證明為什麼素數可以更好地實作散列。
為什麼插入HashMap的資料需要實作hashcode和equals方法？對這兩個方法有什麼要求？
答：通過hashcode來确定插入下标，通過equals比較來尋找資料；兩個相等的key的hashcode必須相等，但擁有相同的hashcode的對象不一定相等。
這裡需要區分好他們之間的差別：hashcode就像一個人的名，相同的人名字肯定相等，但是相同的名字不一定是同個人；equals比較内容是否相同，一般由對象覆寫重寫，預設情況下比較的是引用位址；“==”引用隊形比較的是引用位址是否相同，值對象比較的是值是否相同。
HashMap中需要使用hashcode來擷取key的下标，如果兩個相同的對象的hashcode不同，那麼會造成HashMap中存在相同的key；是以equals傳回相同的key他們的hashcode一定要相同。HashMap比較兩個元素是否相同采用了三種比較方法結合： p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))) 。關于更加深入的講解可以參考這篇文章： Java提高篇——equals()與hashCode()方法詳解 ，作者非常詳細地剖析了這些方法之間的差別。
最後
關于HashMap的内容很難在一篇文章講完，他的設計到的内容非常多，如線程安全的設計可以延伸到ConcurrentHashMap與Hashtable，這兩個類與HashMap的差別以及内部設計均非常重要，這些内容我将在另外的文章做補充。
最後，希望文章對你有幫助。如果覺得本文對你有幫助，可以點贊關注支援一下