HashMap簡(jiǎn)介
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ù)隘竭。
手寫(xiě)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ù)医吊。
手寫(xiě)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();
}
然后編寫(xiě)一個(gè)MyHashMap類(lèi)，實(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<K,V>[] table;
class Entry<K, V>{
K k;
V v;
Entry<K,V> next;
public Entry(K k, V v, Entry<K, V> next){
this.k = k;
this.v = v;
this.next = next;
}
}
我們參照HashMap設(shè)置一個(gè)默認(rèn)的容量capacity和默認(rèn)的加載因子loadFactor，table就是底層數(shù)組，Entry類(lèi)保存了"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<K, V> 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>(k, v, table[index]);
size++;
return null;
}
// table[index]為空 直接賦值
table[index] = new Entry<K, V>(k, v, null);
size++;
return null;
}
put方法中，我們通過(guò)傳入的K-V值構(gòu)建一個(gè)Entry對(duì)象术浪，然后判斷它應(yīng)該被放在數(shù)組的那個(gè)位置瓢对。回想我們之前的論斷：
想要提高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<K, V> 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<K, V> 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)單邀泉，這里就不再贅述。現(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í)，查詢(xún)效率將急劇下降媳维。
- 樹(shù)化問(wèn)題（treeify）酿雪。我們之前講過(guò)，鏈表節(jié)點(diǎn)數(shù)量超過(guò)8時(shí)侄刽，為了更高的查詢(xún)效率执虹，鏈表將轉(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迎大家指出徙垫。
