Java 集合系列之 HashMap詳細介紹(源碼解析)和使用示例

Java 集合系列之 HashMap詳細介紹(源碼解析)和使用示例

概要

這一章，我們對HashMap進行學習。

我們先對HashMap有個整體認識，然後再學習它的源碼，最後再通過執行個體來學會使用HashMap。内容包括：

第1部分 HashMap介紹

第2部分 HashMap資料結構

第3部分 HashMap源碼解析(基于JDK1.6.0_45)

    第3.1部分 HashMap的“拉鍊法”相關内容

    第3.2部分 HashMap的構造函數

    第3.3部分 HashMap的主要對外接口

    第3.4部分 HashMap實作的Cloneable接口

    第3.5部分 HashMap實作的Serializable接口

第4部分 HashMap周遊方式

第5部分 HashMap示例

第1部分 HashMap介紹

HashMap簡介

HashMap 是一個散清單，它存儲的内容是鍵值對(key-value)映射。

HashMap 繼承于AbstractMap，實作了Map、Cloneable、java.io.Serializable接口。

HashMap 的實作不是同步的，這意味着它不是線程安全的。它的key、value都可以為null。此外，HashMap中的映射不是有序的。

HashMap 的執行個體有兩個參數影響其性能：“初始容量” 和 “加載因子”。容量 是哈希表中桶的數量，初始容量 隻是哈希表在建立時的容量。加載因子 是哈希表在其容量自動增加之前可以達到多滿的一種尺度。當哈希表中的條目數超出了加載因子與目前容量的乘積時，則要對該哈希表進行 rehash 操作（即重建内部資料結構），進而哈希表将具有大約兩倍的桶數。

通常，預設加載因子是 0.75, 這是在時間和空間成本上尋求一種折衷。加載因子過高雖然減少了空間開銷，但同時也增加了查詢成本（在大多數 HashMap 類的操作中，包括 get 和 put 操作，都反映了這一點）。在設定初始容量時應該考慮到映射中所需的條目數及其加載因子，以便最大限度地減少 rehash 操作次數。如果初始容量大于最大條目數除以加載因子，則不會發生 rehash 操作。

HashMap的構造函數

HashMap共有4個構造函數,如下：

// 預設構造函數。
HashMap()

// 指定“容量大小”的構造函數
HashMap(int capacity)

// 指定“容量大小”和“加載因子”的構造函數
HashMap(int capacity, float loadFactor)

// 包含“子Map”的構造函數
HashMap(Map<? extends K, ? extends V> map)
           

HashMap的API

void                 clear()
Object               clone()
boolean              containsKey(Object key)
boolean              containsValue(Object value)
Set<Entry<K, V>>     entrySet()
V                    get(Object key)
boolean              isEmpty()
Set<K>               keySet()
V                    put(K key, V value)
void                 putAll(Map<? extends K, ? extends V> map)
V                    remove(Object key)
int                  size()
Collection<V>        values()
           

第2部分 HashMap資料結構

HashMap的繼承關系

java.lang.Object
   ↳     java.util.AbstractMap<K, V>
         ↳     java.util.HashMap<K, V>

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable { }
           

HashMap與Map關系如下圖：

從圖中可以看出： 

(01) HashMap繼承于AbstractMap類，實作了Map接口。Map是"key-value鍵值對"接口，AbstractMap實作了"鍵值對"的通用函數接口。 

(02) HashMap是通過"拉鍊法"實作的哈希表。它包括幾個重要的成員變量：table, size, threshold, loadFactor, modCount。

　　table是一個Entry[]數組類型，而Entry實際上就是一個單向連結清單。哈希表的"key-value鍵值對"都是存儲在Entry數組中的。 

　　size是HashMap的大小，它是HashMap儲存的鍵值對的數量。 

　　threshold是HashMap的門檻值，用于判斷是否需要調整HashMap的容量。threshold的值="容量*加載因子"，當HashMap中存儲資料的數量達到threshold時，就需要将HashMap的容量加倍。

　　loadFactor就是加載因子。 

　　modCount是用來實作fail-fast機制的。

第3部分 HashMap源碼解析(基于JDK1.6.0_45)

為了更了解HashMap的原理，下面對HashMap源碼代碼作出分析。

在閱讀源碼時，建議參考後面的說明來建立對HashMap的整體認識，這樣更容易了解HashMap。

 View Code

說明:

在詳細介紹HashMap的代碼之前，我們需要了解：HashMap就是一個散清單，它是通過“拉鍊法”解決哈希沖突的。

還需要再補充說明的一點是影響HashMap性能的有兩個參數：初始容量(initialCapacity) 和加載因子(loadFactor)。容量 是哈希表中桶的數量，初始容量隻是哈希表在建立時的容量。加載因子 是哈希表在其容量自動增加之前可以達到多滿的一種尺度。當哈希表中的條目數超出了加載因子與目前容量的乘積時，則要對該哈希表進行 rehash 操作（即重建内部資料結構），進而哈希表将具有大約兩倍的桶數。

第3.1部分 HashMap的“拉鍊法”相關内容

3.1.1 HashMap資料存儲數組

transient Entry[] table;
           

HashMap中的key-value都是存儲在Entry數組中的。

3.1.2 資料節點Entry的資料結構

 View Code

從中，我們可以看出 Entry 實際上就是一個單向連結清單。這也是為什麼我們說HashMap是通過拉鍊法解決哈希沖突的。

Entry 實作了Map.Entry 接口，即實作getKey(), getValue(), setValue(V value), equals(Object o), hashCode()這些函數。這些都是基本的讀取/修改key、value值的函數。

第3.2部分 HashMap的構造函數

HashMap共包括4個構造函數

 View Code

第3.3部分 HashMap的主要對外接口

3.3.1 clear()

clear() 的作用是清空HashMap。它是通過将所有的元素設為null來實作的。

 View Code

3.3.2 containsKey()

containsKey() 的作用是判斷HashMap是否包含key。

public boolean containsKey(Object key) {
    return getEntry(key) != null;
}
           

containsKey() 首先通過getEntry(key)擷取key對應的Entry，然後判斷該Entry是否為null。

getEntry()的源碼如下：

 View Code

getEntry() 的作用就是傳回“鍵為key”的鍵值對，它的實作源碼中已經進行了說明。

這裡需要強調的是：HashMap将“key為null”的元素都放在table的位置0處，即table[0]中；“key不為null”的放在table的其餘位置！

3.3.3 containsValue()

containsValue() 的作用是判斷HashMap是否包含“值為value”的元素。

 View Code

從中，我們可以看出containsNullValue()分為兩步進行處理：第一，若“value為null”，則調用containsNullValue()。第二，若“value不為null”，則查找HashMap中是否有值為value的節點。

containsNullValue() 的作用判斷HashMap中是否包含“值為null”的元素。

 View Code

3.3.4 entrySet()、values()、keySet()

它們3個的原理類似，這裡以entrySet()為例來說明。

entrySet()的作用是傳回“HashMap中所有Entry的集合”，它是一個集合。實作代碼如下：

 View Code

HashMap是通過拉鍊法實作的散清單。表現在HashMap包括許多的Entry，而每一個Entry本質上又是一個單向連結清單。那麼HashMap周遊key-value鍵值對的時候，是如何逐個去周遊的呢？

下面我們就看看HashMap是如何通過entrySet()周遊的。

entrySet()實際上是通過newEntryIterator()實作的。 下面我們看看它的代碼：

 View Code

當我們通過entrySet()擷取到的Iterator的next()方法去周遊HashMap時，實際上調用的是 nextEntry() 。而nextEntry()的實作方式，先周遊Entry(根據Entry在table中的序号，從小到大的周遊)；然後對每個Entry(即每個單向連結清單)，逐個周遊。

3.3.5 get()

get() 的作用是擷取key對應的value，它的實作代碼如下：

 View Code

3.3.6 put()

put() 的作用是對外提供接口，讓HashMap對象可以通過put()将“key-value”添加到HashMap中。

 View Code

若要添加到HashMap中的鍵值對對應的key已經存在HashMap中，則找到該鍵值對；然後新的value取代舊的value，并退出！

若要添加到HashMap中的鍵值對對應的key不在HashMap中，則将其添加到該哈希值對應的連結清單中，并調用addEntry()。

下面看看addEntry()的代碼：

 View Code

addEntry() 的作用是新增Entry。将“key-value”插入指定位置，bucketIndex是位置索引。

說到addEntry()，就不得不說另一個函數createEntry()。createEntry()的代碼如下：

 View Code

它們的作用都是将key、value添加到HashMap中。而且，比較addEntry()和createEntry()的代碼，我們發現addEntry()多了兩句：

if (size++ >= threshold)
    resize(2 * table.length);
           

那它們的差別到底是什麼呢？

閱讀代碼，我們可以發現，它們的使用情景不同。

(01) addEntry()一般用在 新增Entry可能導緻“HashMap的實際容量”超過“門檻值”的情況下。

       例如，我們建立一個HashMap，然後不斷通過put()向HashMap中添加元素；put()是通過addEntry()新增Entry的。

       在這種情況下，我們不知道何時“HashMap的實際容量”會超過“門檻值”；

       是以，需要調用addEntry()

(02) createEntry() 一般用在 新增Entry不會導緻“HashMap的實際容量”超過“門檻值”的情況下。

        例如，我們調用HashMap“帶有Map”的構造函數，它繪将Map的全部元素添加到HashMap中；

       但在添加之前，我們已經計算好“HashMap的容量和門檻值”。也就是，可以确定“即使将Map中的全部元素添加到HashMap中，都不會超過HashMap的門檻值”。

       此時，調用createEntry()即可。

3.3.7 putAll()

putAll() 的作用是将"m"的全部元素都添加到HashMap中，它的代碼如下：

 View Code

3.3.8 remove()

remove() 的作用是删除“鍵為key”元素

 View Code

第3.4部分 HashMap實作的Cloneable接口

HashMap實作了Cloneable接口，即實作了clone()方法。

clone()方法的作用很簡單，就是克隆一個HashMap對象并傳回。

 View Code

第3.5部分 HashMap實作的Serializable接口

HashMap實作java.io.Serializable，分别實作了串行讀取、寫入功能。

串行寫入函數是writeObject()，它的作用是将HashMap的“總的容量，實際容量，所有的Entry”都寫入到輸出流中。

而串行讀取函數是readObject()，它的作用是将HashMap的“總的容量，實際容量，所有的Entry”依次讀出

 View Code

第4部分 HashMap周遊方式

4.1 周遊HashMap的鍵值對

第一步：根據entrySet()擷取HashMap的“鍵值對”的Set集合。

第二步：通過Iterator疊代器周遊“第一步”得到的集合。

// 假設map是HashMap對象
// map中的key是String類型，value是Integer類型
Integer integ = null;
Iterator iter = map.entrySet().iterator();
while(iter.hasNext()) {
    Map.Entry entry = (Map.Entry)iter.next();
    // 擷取key
    key = (String)entry.getKey();
        // 擷取value
    integ = (Integer)entry.getValue();
}
           

4.2 周遊HashMap的鍵

第一步：根據keySet()擷取HashMap的“鍵”的Set集合。

第二步：通過Iterator疊代器周遊“第一步”得到的集合。

// 假設map是HashMap對象
// map中的key是String類型，value是Integer類型
String key = null;
Integer integ = null;
Iterator iter = map.keySet().iterator();
while (iter.hasNext()) {
        // 擷取key
    key = (String)iter.next();
        // 根據key，擷取value
    integ = (Integer)map.get(key);
}
           

4.3 周遊HashMap的值

第一步：根據value()擷取HashMap的“值”的集合。

第二步：通過Iterator疊代器周遊“第一步”得到的集合。

// 假設map是HashMap對象
// map中的key是String類型，value是Integer類型
Integer value = null;
Collection c = map.values();
Iterator iter= c.iterator();
while (iter.hasNext()) {
    value = (Integer)iter.next();
}
           

周遊測試程式如下：

 View Code

第5部分 HashMap示例

下面通過一個執行個體學習如何使用HashMap

 View Code

 (某一次)運作結果： 

map:{two=7, one=9, three=6}
next : two - 7
next : one - 9
next : three - 6
size:3
contains key two : true
contains key five : false
contains value 0 : false
map:{two=7, one=9}
map is empty