知識星球（點選上方公眾號，可快速關註）
來源：五月的倉頡 ，
www.cnblogs.com/xrq730/p/5030920.html
初識HashMap
之前的List，講了ArrayList、LinkedList，最後講到了CopyOnWriteArrayList，就前兩者而言，反映的是兩種思想：
（1）ArrayList以陣列形式實現，順序插入、查詢快，插入、刪除較慢
（2）LinkedList以連結串列形式實現，順序插入、查詢較慢，插入、刪除方便
那麼是否有一種資料結構能夠結合上面兩種的優點呢？有，答案就是HashMap。
HashMap是一種非常常見、方便和有用的集合，是一種鍵值對（K-V）形式的儲存結構，下麵將還是用圖示的方式解讀HashMap的實現原理。
四個關註點在HashMap上的答案
新增資料
首先看一下HashMap的一個儲存單元Entry：
static class Entry
implements Map.Entry { final K key;
V value;
Entry
next; int hash;
…
}
之前一篇寫LinkedList的文章，裡面寫到LinkedList是一個雙向連結串列，從HashMap的Entry看得出，Entry組成的是一個單向連結串列，因為裡面只有Entry的後繼Entry，而沒有Entry的前驅Entry。用圖表示應該是這麼一個資料結構：
接下來，假設我有這麼一段程式碼：
public static void main(String[] args)
{
Map
map = new HashMap (); map.put(“111”, “111”);
map.put(“222”, “222”);
}
看一下做了什麼。首先從第3行開始，new了一個HashMap出來：
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
註意一下第5行的init()是個空方法，它是HashMap的子類比如LinkedHashMap構造的時候使用的。DEFAULT_INITIAL_CAPACITY為16，也就是說，HashMap在new的時候構造出了一個大小為16的Entry陣列，Entry內所有資料都取預設值，如圖示為：
看到new出了一個大小為16的Entry陣列來。接著第4行，put了一個Key和Value同為111的字串，看一下put的時候底層做了什麼：
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry
e = table[i]; e != null; e = e.next) { Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
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);
}
static int indexFor(int h, int length) {
return h & (length-1);
}
看一下put方法的幾個步驟：
1、第2行~第3行就是HashMap允許Key值為空的原因，空的Key會預設放在第0位的陣列位置上
2、第4行拿到Key值的HashCode，由於HashCode是Object的方法，因此每個物件都有一個HashCode，對這個HashCode做一次hash計算。按照JDK原始碼註釋的說法，這次hash的作用是根據給定的HashCode對它做一次打亂的操作，防止一些糟糕的Hash演演算法產生的糟糕的Hash值，至於為什麼要防止糟糕的Hash值，HashMap新增元素的最後會講到
3、第5行根據重新計算的HashCode，對Entry陣列的大小取模得到一個Entry陣列的位置。看到這裡使用了&，移位加快一點程式碼執行效率。另外，這個取模操作的正確性依賴於length必須是2的N次冪，這個熟悉二進位制的朋友一定理解，因此註意HashMap建構式中，如果你指定HashMap初始陣列的大小initialCapacity，如果initialCapacity不是2的N次冪，HashMap會算出大於initialCapacity的最小2的N次冪的值，作為Entry陣列的初始化大小。這裡為了講解方便，我們假定字串111和字串222算出來的i都是1
4、第6行~第14行會先判斷一下原資料結構中是否存在相同的Key值，存在則改寫並傳回，不執行後面的程式碼。註意一下recordAccess這個方法，它也是HashMap的子類比如LinkedHashMap用的，HashMap中這個方法為空。另外，註意一點，對比Key是否相同，是先比HashCode是否相同，HashCode相同再判斷equals是否為true，這樣大大增加了HashMap的效率，對HashCode不熟悉的朋友可以看一下我的這篇文章講講HashCode的作用
5、第16行的modeCount++是用於fail-fast機制的，每次修改HashMap資料結構的時候都會自增一次這個值
然後就到了關鍵的addEntry方法了：
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry
e = table[bucketIndex]; table[bucketIndex] = new Entry
(hash, key, value, e); if (size++ >= threshold)
resize(2 * table.length);
}
Entry(int h, K k, V v, Entry
n) { value = v;
next = n;
key = k;
hash = h;
}
假設new出來的Entry地址為0×00000001，那麼，put(“111″, “111″)用圖表示應該是這樣的：
每一個新增的Entry都位於table[1]上，另外，裡面的hash是rehash之後的hash而不是Key最原始的hash。看到table[1]上存放了111—->111這個鍵值對，它持有原table[1]的取用地址，因此可以定址到原table[1]，這就是單向連結串列。 再看一下put(“222″, “222″)做了什麼，一張圖就可以理解了：
新的Entry再次佔據table[1]的位置，並且持有原table[1]，也就是111—->111這個鍵值對。
至此，HashMap進行put資料的過程就呈現清楚了。不過還有一個問題，就是HashMap如何進行擴容，再看一下addEntry方法：
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry
e = table[bucketIndex]; table[bucketIndex] = new Entry
(hash, key, value, e); if (size++ >= threshold)
resize(2 * table.length);
}
看到第4行~第5行，也就是說在每次放置完Entry之後都會判斷是否需要擴容。這裡不講擴容是因為HashMap擴容在不正確的使用場景下將會導致死迴圈，這是一個值得探討的話題，也是我工作中實際遇到過的一個問題，因此下一篇文章將會詳細說明為什麼不正確地使用HashMap會導致死迴圈。
刪除資料
有一段程式碼：
public static void main(String[] args)
{
Map
map = new HashMap (); map.put(“111”, “111”);
map.put(“222”, “222”);
map.remove(“111”);
}
第6行刪除元素，看一下刪除元素的時候做了什麼，第4行~第5行添加了兩個鍵值對就沿用上面的圖，HashMap刪除指定鍵值對的原始碼是：
public V remove(Object key) {
Entry
e = removeEntryForKey(key); return (e == null ? null : e.value);
}
final Entry
removeEntryForKey(Object key) { int hash = (key == null) ? 0 : hash(key.hashCode());
int i = indexFor(hash, table.length);
Entry
prev = table[i]; Entry
e = prev;
while (e != null) {
Entry
next = e.next; Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size–;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
分析一下remove元素的時候做了幾步：
1、根據key的hash找到待刪除的鍵值對位於table的哪個位置上
2、記錄一個prev表示待刪除的Entry的前一個位置Entry，e可以認為是當前位置
3、從table[i]開始遍歷連結串列，假如找到了匹配的Entry，要做一個判斷，這個Entry是不是table[i]：
（1）是的話，也就是第14行~第15行，table[i]就直接是table[i]的下一個節點，後面的都不需要動
（2）不是的話，也就是第16行~第17行，e的前一個Entry也就是prev，prev的next指向e的後一個節點，也就是next，這樣，e所代表的Entry就被踢出了，e的前後Entry就連起來了
remove(“111″)用圖表示就是：
整個過程只需要修改一個節點的next的值即可，非常方便。
修改資料
修改元素也是put，看一下原始碼：
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry
e = table[i]; e != null; e = e.next) { Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
這個其實前面已經提到過了，第6行~第14行就是修改元素的邏輯，如果某個Key已經在資料結構中存在的話，那麼就會改寫原value，也就是第10行的程式碼。
插入資料
所謂”插入元素”，在我的理解裡，一定是基於資料結構是有序的前提下的。像ArrayList、LinkedList，再遠點說就是資料庫，一條一條都是有序的。
而HashMap，它的順序是基於HashCode，HashCode是一個隨機性很強的數字，所以HashMap中的Entry完全是隨機存放的。HashMap又不像LinkedHashMap這樣維護了插入元素的順序，所以對HashMap這個資料結構談插入元素是沒有意義的。
所以，HashMap並沒有插入的概念。
再談HashCode的重要性
前面講到了，HashMap中對Key的HashCode要做一次rehash，防止一些糟糕的Hash演演算法生成的糟糕的HashCode，那麼為什麼要防止糟糕的HashCode？
糟糕的HashCode意味著的是Hash衝突，即多個不同的Key可能得到的是同一個HashCode，糟糕的Hash演演算法意味著的就是Hash衝突的機率增大，這意味著HashMap的效能將下降，表現在兩方面：
1、有10個Key，可能6個Key的HashCode都相同，另外四個Key所在的Entry均勻分佈在table的位置上，而某一個位置上卻連線了6個Entry。這就失去了HashMap的意義，HashMap這種資料結構性高效能的前提是，Entry均勻地分佈在table位置上，但現在確是1 1 1 1 6的分佈。所以，我們要求HashCode有很強的隨機性，這樣就盡可能地可以保證了Entry分佈的隨機性，提升了HashMap的效率。
2、HashMap在一個某個table位置上遍歷連結串列的時候的程式碼：
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
看到，由於採用了”&&”運運算元，因此先比較HashCode，HashCode都不相同就直接pass了，不會再進行equals比較了。HashCode因為是int值，比較速度非常快，而equals方法往往會對比一系列的內容，速度會慢一些。Hash衝突的機率大，意味著equals比較的次數勢必增多，必然降低了HashMap的效率了。
HashMap的table為什麼是transient的
一個非常細節的地方：
transient Entry[] table;
看到table用了transient修飾，也就是說table裡面的內容全都不會被序列化，不知道大家有沒有想過這麼寫的原因？
在我看來，這麼寫是非常必要的。因為HashMap是基於HashCode的，HashCode作為Object的方法，是native的：
public native int hashCode();
這意味著的是：HashCode和底層實現相關，不同的虛擬機器可能有不同的HashCode演演算法。再進一步說得明白些就是，可能同一個Key在虛擬機器A上的HashCode=1，在虛擬機器B上的HashCode=2，在虛擬機器C上的HashCode=3。
這就有問題了，Java自誕生以來，就以跨平臺性作為最大賣點，好了，如果table不被transient修飾，在虛擬機器A上可以用的程式到虛擬機器B上可以用的程式就不能用了，失去了跨平臺性，因為：
1、Key在虛擬機器A上的HashCode=100，連在table[4]上
2、Key在虛擬機器B上的HashCode=101，這樣，就去table[5]上找Key，明顯找不到
整個程式碼就出問題了。因此，為了避免這一點，Java採取了重寫自己序列化table的方法，在writeObject選擇將key和value追加到序列化的檔案最後面：
private void writeObject(java.io.ObjectOutputStream s)
throws IOException
{
Iterator
> i = (size > 0) ? entrySet0().iterator() : null;
// Write out the threshold, loadfactor, and any hidden stuff
s.defaultWriteObject();
// Write out number of buckets
s.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
e = i.next(); s.writeObject(e.getKey());
s.writeObject(e.getValue());
}
}
}
而在readObject的時候重構HashMap資料結構：
private void readObject(java.io.ObjectInputStream s)
throws IOException, ClassNotFoundException
{
// Read in the threshold, loadfactor, and any hidden stuff
s.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 HashMap
for (int i=0; i
K key = (K) s.readObject();
V value = (V) s.readObject();
putForCreate(key, value);
}
}
一種麻煩的方式，但卻保證了跨平臺性。
這個例子也告訴了我們：儘管使用的虛擬機器大多數情況下都是HotSpot，但是也不能對其它虛擬機器不管不顧，有跨平臺的思想是一件好事。
HashMap和Hashtable的區別
HashMap和Hashtable是一組相似的鍵值對集合，它們的區別也是面試常被問的問題之一，我這裡簡單總結一下HashMap和Hashtable的區別：
1、Hashtable是執行緒安全的，Hashtable所有對外提供的方法都使用了synchronized，也就是同步，而HashMap則是執行緒非安全的
2、Hashtable不允許空的value，空的value將導致空指標異常，而HashMap則無所謂，沒有這方面的限制
3、上面兩個缺點是最主要的區別，另外一個區別無關緊要，我只是提一下，就是兩個的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方法產生的。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);
}
看完本文有收穫？請轉發分享給更多人
關註「ImportNew」，提升Java技能
