HashMap

HashMap
- 1、存儲結構
- 2、HashCode計算
- 3、HashMap參數以及擴容機制
- 4、get源碼
- 5、put源碼
- 6、JDK 1.8中的優化(HashMap)
- 7、常見問題

本文主要參考了Java Collection Framework 源碼剖析這位部落客的專欄，寫的很好，感興趣的可以去看一下！

TreeMap：基于紅黑樹實作;
HashMap：基于哈希表實作;
HashTable：和 HashMap 類似，但它是線程安全的，這意味着同一時刻多個線程可以同時寫入 HashTable 并且不會導緻資料不一緻。它是遺留類，不應該去使用它。現在可以使用 ConcurrentHashMap 來支援線程安全，并且 ConcurrentHashMap 的效率會更高，因為 ConcurrentHashMap 引入了分段鎖;
LinkedHashMap：使用雙向連結清單來維護元素的順序，順序為插入順序或者最近最少使用（LRU）順序;

容器中主要包括 Collection 和 Map 兩種，Collection 存儲着對象的集合，而 Map 存儲着鍵值對（兩個對象）的映射表；

Java容器源碼分析——HashMapHashMap

HashMap

1、存儲結構

Entry 是構成哈希表的基石，是哈希表所存儲的元素的具體形式内部包含了一個Entry類型的數組table;

Entry内部存儲着鍵值對，包含了四個字段，從next字段可以看出Entry是一個連結清單;

即數組中的每個位置被當成一個桶，一個桶存放一個連結清單。HashMap 使用拉鍊法來解決沖突，同一個連結清單中存放哈希值和散列桶取模運算結果相同的 Entry;

Java容器源碼分析——HashMapHashMap

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash; // hash(key.hashCode())方法的傳回值
        final K key;//鍵值對的鍵 
        V value;//鍵值對的值
        Node<K,V> next;//下一個節點

        Node(int hash, K key, V value, Node<K,V> next) { //Node的構造函數
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

2、HashCode計算

在JDK1.8的源碼中，hashcode的計算：高16位異或低16位

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

3、HashMap參數以及擴容機制

設 HashMap 的 table 長度為 M，需要存儲的鍵值對數量為 N，如果哈希函數滿足均勻性的要求，那麼每條連結清單的長度大約為 N/M，是以平均查找次數的複雜度為 O(N/M)；

為了讓查找的成本降低，應該盡可能使得 N/M 盡可能小，是以需要保證 M 盡可能大，也就是說 table 要盡可能大。HashMap 采用動态擴容來根據目前的 N 值來調整 M 值，使得空間效率和時間效率都能得到保證；

HashMap參數：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //預設初始容量是16
static final int MAXIMUM_CAPACITY = 1 << 30;//最大容量是2的30次方
static final float DEFAULT_LOAD_FACTOR = 0.75f;//負載因子是0.75
static final int TREEIFY_THRESHOLD = 8;//這是一個門檻值，當桶(bucket)上的連結清單數大于這個值時會轉成紅黑樹
static final int UNTREEIFY_THRESHOLD = 6;//也是門檻值同上一個相反，當桶(bucket)上的連結清單數小于這個值時樹轉連結清單
static final int MIN_TREEIFY_CAPACITY = 64;//樹的最小的容量

初始容量是16，達到門檻值擴容，門檻值等于最大容量*負載因子，每次擴容2倍，總是2的n次方；

擴容機制：

為了保證HashMap的效率，系統必須要在容量達到threshold進行擴容。擴容操作十分耗時，需要重新計算這些元素在新table數組中的位置并且進行複制處理，看一下源碼中的resize()操作；

void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;

        // 若 oldCapacity 已達到最大值，直接将 threshold 設為 Integer.MAX_VALUE
        if (oldCapacity == MAXIMUM_CAPACITY) {  
            threshold = Integer.MAX_VALUE;
            return;             // 直接傳回
        }

        // 否則，建立一個更大的數組
        Entry[] newTable = new Entry[newCapacity];

        //将每條Entry重新哈希到新的數組中
        transfer(newTable);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);  // 重新設定 threshold
    }

重哈希主要是一個重新計算原HashMap中的元素在新table數組中的位置并進行複制處理的過程

void transfer(Entry[] newTable) {

        // 将原數組 table 賦給數組 src
        Entry[] src = table;
        int newCapacity = newTable.length;

        // 将數組 src 中的每條鍊重新添加到 newTable 中
        for (int j = 0; j < src.length; j++) {
            Entry<K,V> e = src[j];
            if (e != null) {
                src[j] = null;   // src 回收
                // 将每條鍊的每個元素依次添加到 newTable 中相應的桶中
                do {
                    Entry<K,V> next = e.next;
                    // e.hash指的是 hash(key.hashCode())的傳回值;
                    // 計算在newTable中的位置，注意原來在同一條子鍊上的元素可能被配置設定到不同的子鍊
                    int i = indexFor(e.hash, newCapacity);   
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }

4、get源碼

HashMap隻需要根據key的哈希值定位到table數組的某個特定的桶，查找并傳回該key對應的value即可；

以JDK1.7中的代碼為例
public V get(Object key){
	//若為null,調用getForNullKey方法傳回對應的value;
	if(key==null)
		//從table的第一個桶中尋找key為null的映射；若不存在，直接傳回null;
		return getForNullKey();
	//根據key的hashCode值重新計算它的hash碼
	int hash = hash(key.hashCode());
	//找到table數組内對應的桶；
	for(Entry<K,V> e = table[indexFor(hash,table.length)];
						e!=null;
						e = e.next;){
		Object k;
		//若搜尋的key與查找的key相同，則傳回相應的value
		if(e.hash==hash&&((k==e.key)==key||key.equals(k)))
			return e.value;
	}
	return null;	
}
//針對鍵值為NULL的鍵值對
private V getForNullKey() {
        // 鍵為NULL的鍵值對若存在，則必定在第一個桶中
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        // 鍵為NULL的鍵值對若不存在，則直接傳回 null
        return null;
    }

調用HashMap中的get(Object key)的方法後，若傳回值是NULL,存在以下兩種可能：

該key對應的值就是NULL;
HashMap中不存在該key;

5、put源碼

HashMap儲存資料的過程，先判斷key是否為null,若為null,則直接調用putForNullKey方法；若不為空，則先計算key的hash值，然後根據hash值搜尋在table數組中的索引位置，如果table數組中該位置有元素，查找是否存在相同的key,若存在則覆寫原有key的value，否則将該元素儲存在連結清單頭部(最先儲存的元素放在連結清單尾部)，若table此處沒有元素，則直接儲存；

public v put(K key,V value){
	//當key==null時，調用putForNullKey,并将該鍵值儲存到table上的第一個位置
	if(key==null)
		return putForNullKey(value);
	//根據key的hashCode計算hash值
	int hash = hash(key.hashCode());
	
	//計算該鍵值對在數組中的存儲位置(判斷在哪個桶)
	int i = indexFor(hash,table.length);

	//在table的第i個桶上進行疊代，尋找key儲存的位置
	for(Entry<K,V> e = table[i];e!=null;e=e.next){
		Object k;
		//判斷該條連結清單上是否存在hash值相同且key值相等的映射，若存在，直接覆寫value,并傳回舊value;
		if(e.hash==hash&&((k==e.key)==key||key.equals(k))){
			V oldValue = e.value;
			e.value = value;
			e.recordAccess(this);
			return oldValue;//傳回舊值
		}
	}
	modCount++;//修改次數+1，快速失敗機制
	//原HashMap中無該映射，将其添加至連結清單頭部；
	addEntry(hash,key,value,i);
	return null;	
}

void addEntry(int hash,K key,V value,int bucketIndex){
	//擷取bucketIndex處的連結清單
	Entry<K,V> e = table[bucketIndex];
	//将新建立的 Entry 鍊入 bucketIndex處的連結清單的表頭 	
	table[bucketIndex] = new Entry<K,V>(hash,key,value,e);//參數e,是Entry.next;
	//如果size超過threshold，擴充table大小，再散列
	if(size++>=threshold)
		resize(2*table.length);
}

通過hash()方法取得了Key的hash值，但如何才能保證元素能夠均勻的分不到table的每個桶中？

HashMap采用了indexFor方法處理，簡單高效。

static int indexFor(int h,int length){
	return h&(length-1);//等價于取模運算
}

對NULL鍵的特别處理：putForNullKey()

HashMap 中可以儲存鍵為NULL的鍵值對，且該鍵值對是唯一的。若再次向其中添加鍵為NULL的鍵值對，将覆寫其原值。此外，如果HashMap中存在鍵為NULL的鍵值對，那麼一定在第一個桶中

private v putForNullKey(V value){
	//若key==null,則将其放入table的第一個桶内
	for(Entry<K,V> e = table[0];e != null;e = e.next){
		if(e.key == null){
			//若已經存在key為null的鍵替換其值，并傳回舊值
			V oldValue = e.value;
			e.value = value;
			e.recordAccess(this);
			return oldValue;
		}
	}
	modCount++;
	addEntry(0,null,value,0);//否則将其添加到table[0]桶内
	return null;
}

6、JDK 1.8中的優化(HashMap)

Java8中的改進

HashMap是數組+連結清單+紅黑樹；當連結清單長度>=8時轉化為紅黑樹，利用紅黑樹快速增删改查的特點提高HashMap的性能；
Java8中對于hashMap的擴容不是重新計算所有元素在數組的位置，而是使用2次幂的擴充；元素要麼在原位置，要麼是在原位置再移動2次幂的位置；
HashMap在存放自定義類的時候,需要自定義類中的hashCode和equals,通過hash(hashCode)然後模運算，然後定位在Entry數組的下标，周遊之後的連結清單，通過equals比較有沒有相同的key,有就直接覆寫，沒有就重新建立一個Entry.

7、常見問題

1、HashMap為什麼線程不安全？

主要是由于Hash沖突和擴容導緻的；

HashMap在擴容的時候可能會生成環形連結清單，造成死循環；

HashMap采用連結清單法來解決Hash沖突當A線程和B線程同時對一個數組位置調用addEntry,兩個線程同時得到現在的頭結點，那麼其中一個線程的寫入就會造成另一個線程被覆寫，導緻寫入操作丢失；

當多個線程檢測到總數量超過門檻值執行resize操作，各自生成新的數組并且rehash後給map底層的table,最終隻會有一個線程生成的新數組被賦給table變量，其它線程均會丢失；

要想實作線程安全，就需要使用collections類的靜态方法synchronizeMap()實作；

2、HashMap中的key可以是任意對象或類型嗎？

可以為null,但不能是可變對象，可變對象的屬性改變，HashCode也會發生改變，導緻無法查找到Map中的資料；
保證對于成員變量的改變能夠使得對象的哈希值不變；

3、HashMap為什麼可以插入null值

先判斷key是否為null,若為null,則直接調用putForNullKey方法去周遊table[0]桶内的連結清單，尋找e.key == null,沒有找到就周遊結束；找到了就采用value去覆寫oldValue,并且傳回oldValue;如果在table[0]Entry連結清單中沒有找到就調用addEntry方法添加一個key為null的Entry;

4、HashMap在高并發情況下會出現什麼問題？

擴容問題，上面提到了擴容對于HashMap的影響；

擴容問題會引起資料丢失，也會造成鍊環導緻死循環；

Java容器源碼分析——HashMapHashMap

多線程擴容，如果線程1和線程2都需要進行擴容；

線上程1中，我們發現這三個entry都落到了第二個桶裡面；假設線程1執行到了transfer方法的Entry next = e.next這一句，然後時間片用完了，此時的e = [3,A], next = [7,B]；

線程2被排程執行并且順利完成了resize操作，需要注意的是，此時的[7,B]的next為[3,A]；

此時線程1重新被排程運作，此時的線程1持有的引用是已經被線程2 resize之後的結果；線程1首先将[3,A]遷移到新的數組上，然後再處理[7,B]，而[7,B]被連結到了[3,A]的後面，處理完[7,B]之後，就需要處理[7,B]的next；

通過線程2的resize之後，[7,B]的next變為了[3,A]。此時，[3,A]和[7,B]形成了環形連結清單，在get的時候，如果get的key的桶索引和[3,A]和[7,B]一樣，那麼就會陷入死循環。

5、HashMap和HashSet之間的差別

Java容器源碼分析——HashMapHashMap

HashSet基于HashMap來實作，HashSet中存儲的是一個對象，其中沒有重複的元素；

Hashset 底層是Hashmap 但是存儲的是一個對象，Hashset 實際将該元素e 作為key 放入Hashmap,當key 值(該元素e)相同時，隻是進行更新value，并不會新增加，是以set 中的元素不會進行改變。

Java容器源碼分析——HashMapHashMap

HashMap

HashMap

1、存儲結構

2、HashCode計算

3、HashMap參數以及擴容機制

4、get源碼

5、put源碼

6、JDK 1.8中的優化(HashMap)

7、常見問題

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method