歡迎光臨
每天分享高質量文章

圖解集合 HashMap

(點擊上方公眾號,可快速關註)


來源:五月的倉頡 ,

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技能

赞(0)

分享創造快樂