Map

什麼是map

是一種鍵值（key-value）映射表的資料結構

實作類

1. HashMap Map主要實作類 線程不安全 效率高 可存儲 null的key value

   • LinkedHashMap 保證在周遊map時 可以按照添加的順序實作

     在原有hashMap的基礎上 添加了一對指針 指向前一個元素 和 後一個元素

     對于頻繁的周遊操作 LinkedHashMap 執行效率 高于 HashMap

   • 底層結構: 數組 + 連結清單（JDK7及之前） 數組 + 連結清單 + 紅黑樹(JDK8)

2. TreeMap 排序 周遊

   底層使用紅黑樹

3. Hashtable 線程安全 效率低 不能存儲null的key value
   • Properties 常用來處理配置檔案 key value都是String類型

Map特點

1. key 無序 不可重複 跟set類似 key所在的類 要重寫hashCode() 和 equals()方法 (HashMap舉例)
2. value無序 但是可以重複 使用Collection來存儲所有value value所在的類需要重寫equals()方法
3. 一個key-value構成了一個Entry對象
4. Map中的entry：無序的 不可重複 使用Set去存儲所有的entry

HashMap實作原理

JDK7

HashMap map = new HashMap();

	執行個體化後 底層建立了長度是16的一維數組Entry[] table

	map.put(key1,value1);

	首先 調用key1所在類的hashCode方法 此哈希值經過某種計算後 得到在數組的位置 

		如果該位置沒有資料 `map.put(key1,value1);`添加成功
	
		如果該位置有資料(最少有一個資料的存在) 比較key1和其他資料的哈希值是否相同
	
			如果不相同 `map.put(key1,value1);`添加成功		情況2
		
			如果和某個資料key2-value2相同 則比較key1 所在類的equals(key2)方法
		
				如果傳回值為false `map.put(key1,value1);`添加成功		情況3
			
				如果傳回值為true value1的值替換value2
			
	情況2 和 情況3 此時的key1-value1和已經存在的資料以連結清單的方式進行存儲
	
	最後 在不斷的擴容過程中 預設擴充為原來數組長度的兩倍 将原來的資料 copy 過來
           

jdk8相比較于jdk7

new HashMap() 底層沒有建立一個長度 16的數組

底層數組是Node[] 不是Entry[]

首次調用Put方法 建立長度為16的數組

當數組上某一索引的元素以連結清單的形式存在的資料個數 > 8 且目前數組長度 > 64時

此索引位置上的存儲資料結構改為 `紅黑樹`存儲
           

重要常量

1. DEFAULT_INITIAL_CAPACITY

   預設容量 16

2. MAXIMUM_CAPACITY

   最大容量 230

3. DEFAULT_LOAD_FACTOR

   HashMap預設加載因子 0.75f

4. threshold

   臨界值 = 預設容量 * 加載因子

5. TREEIFY_THRESHOLD

   連結清單長度大于 此值時 轉化為 紅黑樹 8

6. MIN_TREEIFY_CAPACITY

   被轉化成紅黑樹最小數組大小 64

即使再小的帆也能遠航