手寫HashMap，手撕面試官
前言
今天去面試啊，聊得差不多的時(shí)候面試官突然問(wèn)我會(huì)手寫HashMap嗎？這我哪能慫啊，好死不死的面試之前我還真手寫過(guò)一個(gè)簡(jiǎn)單的HashMap，所以我不過(guò)花了5分鐘便弄出來(lái)了，面試官直呼內(nèi)行。
相信大家關(guān)于HashMap的面試題刷的也不少了，源碼應(yīng)該也看了很多遍，大部分人可以說(shuō)是非常熟悉了，但是如果面試官突然給你們整這么一手，我相信很多人還是會(huì)表示懵逼的。所以今天給大伙捋一捋，掌握手寫HashMap之后都給我去手撕面試官。
HashMap是Java中一中非常常用的數(shù)據(jù)結(jié)構(gòu)，也基本是面試中的“必考題”。它實(shí)現(xiàn)了基于“K-V”形式的鍵值對(duì)的高效存取。JDK1.7之前，HashMap是基于數(shù)組+鏈表實(shí)現(xiàn)的，1.8以后，HashMap的底層實(shí)現(xiàn)中加入了紅黑樹(shù)用于提升查找效率。
HashMap根據(jù)存入的鍵值對(duì)中的key計(jì)算對(duì)應(yīng)的index，也就是它在數(shù)組中的存儲(chǔ)位置。當(dāng)發(fā)生哈希沖突時(shí)，即不同的key計(jì)算出了相同的index，HashMap就會(huì)在對(duì)應(yīng)位置生成鏈表。當(dāng)鏈表的長(zhǎng)度超過(guò)8時(shí)，鏈表就會(huì)轉(zhuǎn)化為紅黑樹(shù)。
手寫HashMap之前，我們討論一個(gè)小問(wèn)題：當(dāng)我們?cè)贖ashMap中根據(jù)key查找value時(shí)，在數(shù)組、鏈表、紅黑樹(shù)三種情況下，平均要做多少次比較？
在數(shù)組中查找時(shí)，我們可以通過(guò)key的hashcode直接計(jì)算它在數(shù)組中的位置，比較次數(shù)為1
在鏈表中查找時(shí)，根據(jù)next引用依次比較各個(gè)節(jié)點(diǎn)的key，長(zhǎng)度為n的鏈表節(jié)點(diǎn)平均比較次數(shù)為n/2
在紅黑樹(shù)中查找時(shí)，由于紅黑樹(shù)的特性，節(jié)點(diǎn)數(shù)為n的紅黑樹(shù)平均比較次數(shù)為log(n)
前面我們提到，鏈表長(zhǎng)度超過(guò)8時(shí)樹(shù)化（TREEIFY），正是因?yàn)閚=8，就是log(n) < n/2的閾值。而n<6時(shí)，log(n) > n/2，紅黑樹(shù)解除樹(shù)化（UNTREEIFY）。另外我們可以看到，想要提高HashMap的效率，最重要的就是盡量避免生成鏈表，或者說(shuō)盡量減少鏈表的長(zhǎng)度，避免哈希沖突，降低key的比較次數(shù)。
手寫HashMap
定義一個(gè)Map接口
也可以使用Java中的java.util.Map
public interface MyMap<K,V> {
V put(K k, V v);
V get(K k);
int size();
V remove(K k);
boolean isEmpty();
void clear();
}
然后編寫一個(gè)MyHashMap類，實(shí)現(xiàn)這個(gè)接口，并實(shí)現(xiàn)里面的方法。
成員變量
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, V>{
K k;
V v;
Entry next;
public Entry(K k, V v, Entry next){
this.k = k;
this.v = v;
this.next = next;
}
}
我們參照HashMap設(shè)置一個(gè)默認(rèn)的容量capacity和默認(rèn)的加載因子loadFactor，table就是底層數(shù)組，Entry類保存了"K-V"數(shù)據(jù)，next字段表明它可能會(huì)是一個(gè)鏈表節(jié)點(diǎn)。
構(gòu)造方法
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中，開(kāi)發(fā)者采用了更精妙的位運(yùn)算的方式完成了這個(gè)功能，效率比這種方式要更高。
private static int upperMinPowerOf2(int n){
int power = 1;
while(power <= n){
power *= 2;
}
return power;
}
為什么HashMap的capacity一定要是2次冪呢？這是為了方便HashMap中的數(shù)組擴(kuò)容時(shí)已存在元素的重新哈希（rehash）考慮的。
put方法
@Override
public V put(K k, V v) {
// 通過(guò)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;
}
// 沒(méi)有則使用頭插法
table[index] = new Entry(k, v, table[index]);
size++;
return null;
}
// table[index]為空 直接賦值
table[index] = new Entry(k, v, null);
size++;
return null;
}
put方法中，我們通過(guò)傳入的K-V值構(gòu)建一個(gè)Entry對(duì)象，然后判斷它應(yīng)該被放在數(shù)組的那個(gè)位置?；叵胛覀冎暗恼摂啵?/p>
想要提高HashMap的效率，最重要的就是盡量避免生成鏈表，或者說(shuō)盡量減少鏈表的長(zhǎng)度
想要達(dá)到這一點(diǎn)，我們需要Entry對(duì)象盡可能均勻地散布在數(shù)組table中，且index不能超過(guò)table的長(zhǎng)度，很明顯，取模運(yùn)算很符合我們的需求int index = k.hashCode() % table.length。關(guān)于這一點(diǎn)，HashMap中也使用了一種效率更高的方法——通過(guò)&運(yùn)算完成key的散列，有興趣的同學(xué)可以查看HashMap的源碼。
如果table[index]處已存在元素，說(shuō)明將要形成鏈表。我們首先遍歷這個(gè)鏈表（長(zhǎng)度為1也視作鏈表），如果存在key與我們存入的key相等，則替換并返回舊值；如果不存在，則將新節(jié)點(diǎn)插入鏈表。插入鏈表又有兩種做法：頭插法和尾插法。如果使用尾插法，我們需要遍歷這個(gè)鏈表，將新節(jié)點(diǎn)插入末尾；如果使用頭插法，我們只需要將table[index]的引用指向新節(jié)點(diǎn)，然后將新節(jié)點(diǎn)的next引用指向原來(lái)table[index]位置的節(jié)點(diǎn)即可，這也是HashMap中的做法。
如果table[index]處為空，將新的Entry對(duì)象直接插入即可。
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;
}
調(diào)用get方法時(shí)，我們根據(jù)key的hashcode計(jì)算它對(duì)應(yīng)的index，然后直接去table中的對(duì)應(yīng)位置查找即可，如果有鏈表就遍歷。
remove方法
@Override
public V remove(K k) {
int index = k.hashCode() % table.length;
Entry current = table[index];
// 如果直接匹配第一個(gè)節(jié)點(diǎn)
if(current.k == k){
table[index] = null;
size--;
return current.v;
}
// 在鏈表中刪除節(jié)點(diǎn)
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;
}
移除某個(gè)節(jié)點(diǎn)時(shí)，如果該key對(duì)應(yīng)的index處沒(méi)有形成鏈表，那么直接置為null。如果存在鏈表，我們需要將目標(biāo)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)的next引用指向目標(biāo)節(jié)點(diǎn)的后繼節(jié)點(diǎn)。由于我們的Entry節(jié)點(diǎn)沒(méi)有previous引用，因此我們要基于目標(biāo)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)進(jìn)行操作，即：
current.next = current.next.next;
current代表我們要?jiǎng)h除的節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)。
還有一些簡(jiǎn)單的size()、isEmpty()等方法都很簡(jiǎn)單，這里就不再贅述?，F(xiàn)在，我們自定義的MyHashMap基本可以使用了。
最后
關(guān)于HashMap的實(shí)現(xiàn)，還有幾點(diǎn)我們沒(méi)有解決：
擴(kuò)容問(wèn)題。在HashMap中，當(dāng)存儲(chǔ)的元素?cái)?shù)量超過(guò)閾值（threshold = capacity * loadFactor）時(shí)，HashMap就會(huì)發(fā)生擴(kuò)容（resize）,然后將內(nèi)部的所有元素進(jìn)行rehash，使hash沖突盡可能減少。在我們的MyHashMap中，雖然定義了加載因子，但是并沒(méi)有使用它，capacity是固定的，雖然由于鏈表的存在，仍然可以一直存入數(shù)據(jù)，但是數(shù)據(jù)量增大時(shí)，查詢效率將急劇下降。
樹(shù)化問(wèn)題（treeify）。我們之前講過(guò)，鏈表節(jié)點(diǎn)數(shù)量超過(guò)8時(shí)，為了更高的查詢效率，鏈表將轉(zhuǎn)化為紅黑樹(shù)。但是我們的代碼中并沒(méi)有實(shí)現(xiàn)這個(gè)功能。
null值的判斷。HashMap中是允許存null值的key的，key為null時(shí)，HashMap中的hash()方法會(huì)固定返回0，即key為null的值固定存在table[0]處。這個(gè)實(shí)現(xiàn)起來(lái)很簡(jiǎn)單，不實(shí)現(xiàn)的情況下MyHashMap中如果存入null值會(huì)直接報(bào)
NullPointerException異常。一些其他問(wèn)題。
相信大家自己完成了對(duì)HashMap的實(shí)現(xiàn)之后，對(duì)它的原理一定會(huì)有更深刻的認(rèn)識(shí)，本文如果有錯(cuò)誤或是不嚴(yán)謹(jǐn)?shù)牡胤揭矚g迎大家指出。上述的問(wèn)題我們接下來(lái)再逐步解決。
作者：編程十二
鏈接：https://www.jianshu.com/p/1be0e957baf2