HashMap簡介
HashMap是Java中一中非常常用的數據結構，也基本是面試中的「必考題」。它實現了基於「K-V」形式的鍵值對的高效存取。JDK1.7之前，HashMap是基於數組+鍊表實現的，1.8以後，HashMap的底層實現中加入了紅黑樹用於提升查找效率。
HashMap根據存入的鍵值對中的key計算對應的index，也就是它在數組中的存儲位置。當發生哈希衝突時，即不同的key計算出了相同的index，HashMap就會在對應位置生成鍊表。當鍊表的長度超過8時，鍊表就會轉化為紅黑樹。
手寫HashMap之前，我們討論一個小問題：當我們在HashMap中根據key查找value時，在數組、鍊表、紅黑樹三種情況下，平均要做多少次比較？
在數組中查找時，我們可以通過key的hashcode直接計算它在數組中的位置，比較次數為1
在鍊表中查找時，根據next引用依次比較各個節點的key，長度為n的鍊表節點平均比較次數為n/2
在紅黑樹中查找時，由於紅黑樹的特性，節點數為n的紅黑樹平均比較次數為log(n)
前面我們提到，鍊表長度超過8時樹化（TREEIFY），正是因為n=8，就是log(n) < n/2的閾值。而n<6時，log(n) > n/2，紅黑樹解除樹化（UNTREEIFY）。另外我們可以看到，想要提高HashMap的效率，最重要的就是儘量避免生成鍊表，或者說儘量減少鍊表的長度，避免哈希衝突，降低key的比較次數。
手寫HashMap
定義一個Map接口
也可以使用Java中的 java.util.Map
public interface MyMap {
V put(K k, V v);
V get(K k);
int size();
V remove(K k);
boolean isEmpty();
void clear();
} 然後編寫一個MyHashMap類，實現這個接口，並實現裡面的方法。
成員變量
final static int DEFAULT_CAPACITY = 16;
final static float DEFAULT_LOAD_FACTOR = 0.75f;
int capacity;
float loadFactor;
int size = 0;
Entry[] table; class Entry{
K k;
V v;
Entry next;
public Entry(K k, V v, Entry next){
this.k = k;
this.v = v;
this.next = next;
}
} 我們參照HashMap設置一個默認的容量capacity和默認的加載因子loadFactor，table就是底層數組，Entry類保存了"K-V"數據，next欄位表明它可能會是一個鍊表節點。
構造方法
public MyHashMap(){
this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public MyHashMap(int capacity, float loadFactor){
this.capacity = upperMinPowerOf2(capacity);
this.loadFactor = loadFactor;
this.table = new Entry[capacity];
}這裡的 upperMinPowerOf2 的作用是獲取大於capacity的最小的2次冪。在HashMap中，開發者採用了更精妙的位運算的方式完成了這個功能，效率比這種方式要更高。
private static int upperMinPowerOf2(int n){
int power = 1;
while(power <= n){
power *= 2;
}
return power;
}為什麼HashMap的capacity一定要是2次冪呢？這是為了方便HashMap中的數組擴容時已存在元素的重新哈希（rehash）考慮的。
put方法
@Override
public V put(K k, V v) {
// 通過hashcode散列
int index = k.hashCode() % table.length;
Entry current = table[index];
// 判斷table[index]是否已存在元素
// 是
if(current != null){
// 遍歷鍊表是否有相等key, 有則替換且返回舊值
while(current != null){
if(current.k == k){
V oldValue = current.v;
current.v = v;
return oldValue;
}
current = current.next;
}
// 沒有則使用頭插法
table[index] = new Entry(k, v, table[index]);
size++;
return null;
}
// table[index]為空 直接賦值
table[index] = new Entry(k, v, null);
size++;
return null;
} put方法中，我們通過傳入的K-V值構建一個Entry對象，然後判斷它應該被放在數組的那個位置。回想我們之前的論斷：
想要提高HashMap的效率，最重要的就是儘量避免生成鍊表，或者說儘量減少鍊表的長度
想要達到這一點，我們需要Entry對象儘可能均勻地散布在數組table中，且index不能超過table的長度，很明顯，取模運算很符合我們的需求 int index = k.hashCode() % table.length 。關於這一點，HashMap中也使用了一種效率更高的方法——通過&運算完成key的散列，有興趣的同學可以查看HashMap的源碼。
如果table[index]處已存在元素，說明將要形成鍊表。我們首先遍歷這個鍊表（長度為1也視作鍊表），如果存在key與我們存入的key相等，則替換並返回舊值；如果不存在，則將新節點插入鍊表。插入鍊表又有兩種做法： 頭插法 和 尾插法 。如果使用尾插法，我們需要遍歷這個鍊表，將新節點插入末尾；如果使用頭插法，我們只需要將table[index]的引用指向新節點，然後將新節點的next引用指向原來table[index]位置的節點即可，這也是HashMap中的做法。
如果table[index]處為空，將新的Entry對象直接插入即可。
get方法
@Override
public V get(K k) {
int index = k.hashCode() % table.length;
Entry current = table[index];
// 遍歷鍊表
while(current != null){
if(current.k == k){
return current.v;
}
current = current.next;
}
return null;
} 調用get方法時，我們根據key的hashcode計算它對應的index，然後直接去table中的對應位置查找即可，如果有鍊表就遍歷。
remove方法
@Override
public V remove(K k) {
int index = k.hashCode() % table.length;
Entry current = table[index];
// 如果直接匹配第一個節點
if(current.k == k){
table[index] = null;
size--;
return current.v;
}
// 在鍊表中刪除節點
while(current.next != null){
if(current.next.k == k){
V oldValue = current.next.v;
current.next = current.next.next;
size--;
return oldValue;
}
current = current.next;
}
return null;
} 移除某個節點時，如果該key對應的index處沒有形成鍊表，那麼直接置為null。如果存在鍊表，我們需要將目標節點的前驅節點的next引用指向目標節點的後繼節點。由於我們的Entry節點沒有previous引用，因此我們要基於目標節點的前驅節點進行操作，即：
current.next = current.next.next;current代表我們要刪除的節點的前驅節點。
還有一些簡單的size()、isEmpty()等方法都很簡單，這裡就不再贅述。現在，我們自定義的MyHashMap基本可以使用了。
最後
關於HashMap的實現，還有幾點我們沒有解決：
NullPointerException
相信大家自己完成了對HashMap的實現之後，對它的原理一定會有更深刻的認識，本文如果有錯誤或是不嚴謹的地方也歡迎大家指出。上述的問題我們接下來再逐步解決，至於紅黑樹，我也不會（攤手）。