初識HashMap
之前的List，講了ArrayList、LinkedList，最后講到了CopyOnWriteArrayList，就前兩者而言，反映的是兩種思想：
（1）ArrayList以數(shù)組形式實現(xiàn)，順序插入、查找快，插入、刪除較慢
（2）LinkedList以鏈表形式實現(xiàn)，順序插入、查找較慢，插入、刪除方便
那么是否有一種數(shù)據(jù)結(jié)構(gòu)能夠結(jié)合上面兩種的優(yōu)點呢？有，答案就是HashMap。
HashMap是一種非常常見、方便和有用的集合，是一種鍵值對（K-V）形式的存儲結(jié)構(gòu)，下面將還是用圖示的方式解讀HashMap的實現(xiàn)原理，
四個關(guān)注點在HashMap上的答案
| 關(guān) 注 點 | 結(jié) 論 |
| HashMap是否允許空 | Key和Value都允許為空 |
| HashMap是否允許重復(fù)數(shù)據(jù) | Key重復(fù)會覆蓋、Value允許重復(fù) |
| HashMap是否有序 | 無序，特別說明這個無序指的是遍歷HashMap的時候，得到的元素的順序基本不可能是put的順序 |
| HashMap是否線程安全 | 非線程安全 |
添加數(shù)據(jù)
首先看一下HashMap的一個存儲單元Entry：
static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; int hash; ...}
之前一篇寫LinkedList的文章，里面寫到LinkedList是一個雙向鏈表，從HashMap的Entry看得出，Entry組成的是一個單向鏈表，因為里面只有Entry的后繼Entry，而沒有Entry的前驅(qū)Entry。用圖表示應(yīng)該是這么一個數(shù)據(jù)結(jié)構(gòu)：
接下來，假設(shè)我有這么一段代碼：
1 public static void main(String[] args)2 {3 Map<String, String> map = new HashMap<String, String>();4 map.put("111", "111");5 map.put("222", "222");6 }
看一下做了什么。首先從第3行開始，new了一個HashMap出來：
1 public HashMap() {2 this.loadFactor = DEFAULT_LOAD_FACTOR;3 threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);4 table = new Entry[DEFAULT_INITIAL_CAPACITY];5 init();6 }
注意一下第5行的init()是個空方法，它是HashMap的子類比如LinkedHashMap構(gòu)造的時候使用的。DEFAULT_INITIAL_CAPACITY為16，也就是說，HashMap在new的時候構(gòu)造出了一個大小為16的Entry數(shù)組，Entry內(nèi)所有數(shù)據(jù)都取默認(rèn)值，如圖示為：
看到new出了一個大小為16的Entry數(shù)組來。接著第4行，put了一個Key和Value同為111的字符串，看一下put的時候底層做了什么：
1 public V put(K key, V value) { 2 if (key == null) 3 return putForNullKey(value); 4 int hash = hash(key.hashCode()); 5 int i = indexFor(hash, table.length); 6 for (Entry<K,V> e = table[i]; e != null; e = e.next) { 7 Object k; 8 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 9 V oldValue = e.value;10 e.value = value;11 e.recordaccess(this);12 return oldValue;13 }14 }15 16 modCount++;17 addEntry(hash, key, value, i);18 return null;19 }
1 static int hash(int h) {2 // This function ensures that hashCodes that differ only by3 // constant multiples at each bit position have a bounded4 // number of collisions (apPRoximately 8 at default load factor).5 h ^= (h >>> 20) ^ (h >>> 12);6 return h ^ (h >>> 7) ^ (h >>> 4);7 }
1 static int indexFor(int h, int length) { 2 return h & (length-1); 3 }
看一下put方法的幾個步驟：
1、第2行~第3行就是HashMap允許Key值為空的原因，空的Key會默認(rèn)放在第0位的數(shù)組位置上
2、第4行拿到Key值的HashCode，由于HashCode是Object的方法，因此每個對象都有一個HashCode，對這個HashCode做一次hash計算。按照J(rèn)DK源碼注釋的說法，這次hash的作用是根據(jù)給定的HashCode對它做一次打亂的操作，防止一些糟糕的Hash算法產(chǎn)生的糟糕的Hash值，至于為什么要防止糟糕的Hash值，HashMap添加元素的最后會講到
3、第5行根據(jù)重新計算的HashCode，對Entry數(shù)組的大小取模得到一個Entry數(shù)組的位置。看到這里使用了&，移位加快一點代碼運行效率。另外，這個取模操作的正確性依賴于length必須是2的N次冪，這個熟悉二進(jìn)制的朋友一定理解，因此注意HashMap構(gòu)造函數(shù)中，如果你指定HashMap初始數(shù)組的大小initialCapacity，如果initialCapacity不是2的N次冪，HashMap會算出大于initialCapacity的最小2的N次冪的值，作為Entry數(shù)組的初始化大小。這里為了講解方便，我們假定字符串111和字符串222算出來的i都是1
4、第6行~第14行會先判斷一下原數(shù)據(jù)結(jié)構(gòu)中是否存在相同的Key值，存在則覆蓋并返回，不執(zhí)行后面的代碼。注意一下recordAccess這個方法，它也是HashMap的子類比如LinkedHashMap用的，HashMap中這個方法為空。另外，注意一點，對比Key是否相同，是先比HashCode是否相同，HashCode相同再判斷equals是否為true，這樣大大增加了HashMap的效率，對HashCode不熟悉的朋友可以看一下我的這篇文章講講HashCode的作用
5、第16行的modeCount++是用于fail-fast機(jī)制的，每次修改HashMap數(shù)據(jù)結(jié)構(gòu)的時候都會自增一次這個值
然后就到了關(guān)鍵的addEntry方法了：
void addEntry(int hash, K key, V value, int bucketIndex) {Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<K,V>(hash, key, value, e); if (size++ >= threshold) resize(2 * table.length);}
Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h;}
假設(shè)new出來的Entry地址為0x00000001，那么，put("111", "111")用圖表示應(yīng)該是這樣的：
每一個新增的Entry都位于table[1]上，另外，里面的hash是rehash之后的hash而不是Key最原始的hash。看到table[1]上存放了111---->111這個鍵值對，它持有原table[1]的引用地址，因此可以尋址到原table[1]，這就是單向鏈表。 再看一下put("222", "222")做了什么，一張圖就可以理解了：
新的Entry再次占據(jù)table[1]的位置，并且持有原table[1]，也就是111---->111這個鍵值對。
至此，HashMap進(jìn)行put數(shù)據(jù)的過程就呈現(xiàn)清楚了。不過還有一個問題，就是HashMap如何進(jìn)行擴(kuò)容，再看一下addEntry方法：
1 void addEntry(int hash, K key, V value, int bucketIndex) { 2 Entry<K,V> e = table[bucketIndex]; 3 table[bucketIndex] = new Entry<K,V>(hash, key, value, e); 4 if (size++ >= threshold) 5 resize(2 * table.length); 6 }
看到第4行~第5行，也就是說在每次放置完Entry之后都會判斷是否需要擴(kuò)容。這里不講擴(kuò)容是因為HashMap擴(kuò)容在不正確的使用場景下將會導(dǎo)致死循環(huán)，這是一個值得探討的話題，也是我工作中實際遇到過的一個問題，因此下一篇文章將會詳細(xì)說明為什么不正確地使用HashMap會導(dǎo)致死循環(huán)。
刪除數(shù)據(jù)
有一段代碼：
1 public static void main(String[] args)2 {3 Map<String, String> map = new HashMap<String, String>();4 map.put("111", "111");5 map.put("222", "222");6 map.remove("111");7 }
第6行刪除元素，看一下刪除元素的時候做了什么，第4行~第5行添加了兩個鍵值對就沿用上面的圖，HashMap刪除指定鍵值對的源代碼是：
1 public V remove(Object key) { 2 Entry<K,V> e = removeEntryForKey(key); 3 return (e == null ? null : e.value); 4 }
1 final Entry<K,V> removeEntryForKey(Object key) { 2 int hash = (key == null) ? 0 : hash(key.hashCode()); 3 int i = indexFor(hash, table.length); 4 Entry<K,V> prev = table[i]; 5 Entry<K,V> e = prev; 6 7 while (e != null) { 8 Entry<K,V> next = e.next; 9 Object k;10 if (e.hash == hash &&11 ((k = e.key) == key || (key != null && key.equals(k)))) {12 modCount++;13 size--;14 if (prev == e)15 table[i] = next;16 else17 prev.next = next;18 e.recordRemoval(this);19 return e;20 }21 prev = e;22 e = next;23 }24 25 return e;26 }
分析一下remove元素的時候做了幾步：
1、根據(jù)key的hash找到待刪除的鍵值對位于table的哪個位置上
2、記錄一個prev表示待刪除的Entry的前一個位置Entry，e可以認(rèn)為是當(dāng)前位置
3、從table[i]開始遍歷鏈表，假如找到了匹配的Entry，要做一個判斷，這個Entry是不是table[i]：
（1）是的話，也就是第14行~第15行，table[i]就直接是table[i]的下一個節(jié)點，后面的都不需要動
（2）不是的話，也就是第16行~第17行，e的前一個Entry也就是prev，prev的next指向e的后一個節(jié)點，也就是next，這樣，e所代表的Entry就被踢出了，e的前后Entry就連起來了
remove("111")用圖表示就是：
整個過程只需要修改一個節(jié)點的next的值即可，非常方便。
修改數(shù)據(jù)
修改元素也是put，看一下源代碼：
1 public V put(K key, V value) { 2 if (key == null) 3 return putForNullKey(value); 4 int hash = hash(key.hashCode()); 5 int i = indexFor(hash, table.length); 6 for (Entry<K,V> e = table[i]; e != null; e = e.next) { 7 Object k; 8 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 9 V oldValue = e.value;10 e.value = value;11 e.recordAccess(this);12 return oldValue;13 }14 }15 modCount++;16 addEntry(hash, key, value, i);17 return null;18 }
這個其實前面已經(jīng)提到過了，第6行~第14行就是修改元素的邏輯，如果某個Key已經(jīng)在數(shù)據(jù)結(jié)構(gòu)中存在的話，那么就會覆蓋原value，也就是第10行的代碼。
插入數(shù)據(jù)
所謂"插入元素"，在我的理解里，一定是基于數(shù)據(jù)結(jié)構(gòu)是有序的前提下的。像ArrayList、LinkedList，再遠(yuǎn)點說就是數(shù)據(jù)庫，一條一條都是有序的。
而HashMap，它的順序是基于HashCode，HashCode是一個隨機(jī)性很強的數(shù)字，所以HashMap中的Entry完全是隨機(jī)存放的。HashMap又不像LinkedHashMap這樣維護(hù)了插入元素的順序，所以對HashMap這個數(shù)據(jù)結(jié)構(gòu)談插入元素是沒有意義的。
所以，HashMap并沒有插入的概念。
再談HashCode的重要性
前面講到了，HashMap中對Key的HashCode要做一次rehash，防止一些糟糕的Hash算法生成的糟糕的HashCode，那么為什么要防止糟糕的HashCode？
糟糕的HashCode意味著的是Hash沖突，即多個不同的Key可能得到的是同一個HashCode，糟糕的Hash算法意味著的就是Hash沖突的概率增大，這意味著HashMap的性能將下降，表現(xiàn)在兩方面：
1、有10個Key，可能6個Key的HashCode都相同，另外四個Key所在的Entry均勻分布在table的位置上，而某一個位置上卻連接了6個Entry。這就失去了HashMap的意義，HashMap這種數(shù)據(jù)結(jié)構(gòu)性高性能的前提是，Entry均勻地分布在table位置上，但現(xiàn)在確是1 1 1 1 6的分布。所以，我們要求HashCode有很強的隨機(jī)性，這樣就盡可能地可以保證了Entry分布的隨機(jī)性，提升了HashMap的效率。
2、HashMap在一個某個table位置上遍歷鏈表的時候的代碼：
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
看到，由于采用了"&&"運算符，因此先比較HashCode，HashCode都不相同就直接pass了，不會再進(jìn)行equals比較了。HashCode因為是int值，比較速度非常快，而equals方法往往會對比一系列的內(nèi)容，速度會慢一些。Hash沖突的概率大，意味著equals比較的次數(shù)勢必增多，必然降低了HashMap的效率了。
HashMap的table為什么是transient的
一個非常細(xì)節(jié)的地方：
transient Entry[] table;
看到table用了transient修飾，也就是說table里面的內(nèi)容全都不會被序列化，不知道大家有沒有想過這么寫的原因？
在我看來，這么寫是非常必要的。因為HashMap是基于HashCode的，HashCode作為Object的方法，是native的：
public native int hashCode();
這意味著的是：HashCode和底層實現(xiàn)相關(guān)，不同的虛擬機(jī)可能有不同的HashCode算法。再進(jìn)一步說得明白些就是，可能同一個Key在虛擬機(jī)A上的HashCode=1，在虛擬機(jī)B上的HashCode=2，在虛擬機(jī)C上的HashCode=3。
這就有問題了，java自誕生以來，就以跨平臺性作為最大賣點，好了，如果table不被transient修飾，在虛擬機(jī)A上可以用的程序到虛擬機(jī)B上可以用的程序就不能用了，失去了跨平臺性，因為：
1、Key在虛擬機(jī)A上的HashCode=100，連在table[4]上
2、Key在虛擬機(jī)B上的HashCode=101，這樣，就去table[5]上找Key，明顯找不到
整個代碼就出問題了。因此，為了避免這一點，Java采取了重寫自己序列化table的方法，在writeObject選擇將key和value追加到序列化的文件最后面：
private void writeObject(java.io.ObjectOutputStream s) throws IOException{Iterator<Map.Entry<K,V>> i = (size > 0) ? entrySet0().iterator() : null;// Write out the threshold, loadfactor, and any hidden stuffs.defaultWriteObject();// Write out number of bucketss.writeInt(table.length);// Write out size (number of Mappings)s.writeInt(size); // Write out keys and values (alternating)if (i != null) { while (i.hasNext()) { Map.Entry<K,V> e = i.next(); s.writeObject(e.getKey()); s.writeObject(e.getValue()); } }}
而在readObject的時候重構(gòu)HashMap數(shù)據(jù)結(jié)構(gòu)：
private void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException{// Read in the threshold, loadfactor, and any hidden stuffs.defaultReadObject();// Read in number of buckets and allocate the bucket array;int numBuckets = s.readInt();table = new Entry[numBuckets]; init(); // Give subclass a chance to do its thing.// Read in size (number of Mappings)int size = s.readInt();// Read the keys and values, and put the mappings in the HashMapfor (int i=0; i<size; i++) { K key = (K) s.readObject(); V value = (V) s.readObject(); putForCreate(key, value);}}
一種麻煩的方式，但卻保證了跨平臺性。
這個例子也告訴了我們：盡管使用的虛擬機(jī)大多數(shù)情況下都是HotSpot，但是也不能對其它虛擬機(jī)不管不顧，有跨平臺的思想是一件好事。
HashMap和Hashtable的區(qū)別
HashMap和Hashtable是一組相似的鍵值對集合，它們的區(qū)別也是面試常被問的問題之一，我這里簡單總結(jié)一下HashMap和Hashtable的區(qū)別：
1、Hashtable是線程安全的，Hashtable所有對外提供的方法都使用了synchronized，也就是同步，而HashMap則是線程非安全的
2、Hashtable不允許空的value，空的value將導(dǎo)致空指針異常，而HashMap則無所謂，沒有這方面的限制
3、上面兩個缺點是最主要的區(qū)別，另外一個區(qū)別無關(guān)緊要，我只是提一下，就是兩個的rehash算法不同，Hashtable的是：
private int hash(Object k) { // hashSeed will be zero if alternative hashing is disabled. return hashSeed ^ k.hashCode();}
這個hashSeed是使用sun.misc.Hashing類的randomHashSeed方法產(chǎn)生的。HashMap的rehash算法上面看過了，也就是：
static int hash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4);}
新聞熱點
疑難解答
