Map

Map接口:雙列數據，保存具有映射關係(key-value)成對的物件

結構

key:無序、不可重複的，使用Set儲存。key決定存放位置，key的所在類必須重寫equals()與hashCode()
value:無序，可重複的，使用Collection儲存，value的所在類必須重寫equals()
一對key與value構成一個Entry物件，使用Set儲存，當然也是無序、不可重複的

HashMap源碼分析

以JDK7為例

HashMap map = new HashMap();實例化時，底層創建了一個長度16的一維數組Entry[] table
map.put(key1, value1);:放數據時，調用key1所在類的hashcode()方法算出哈希值，以此哈希值再經過某些位運算，得到在Entry[] table數組中的存放位置，此時:
- 若位置是空的，放入成功
- 若已經有人(可能有一個數據或鏈表)，就來比較key1跟佔位者(可能有多個，全都要比一遍)的哈希值
  - 如果哈希值都不同，添加成功(放成鏈表)
  - 如果key1的哈希值跟已存在的某數據(舉例為key2, value2)哈希值相同，此時再比較key1所在類的equals()方法，根據返回值:
    - 如果equals()返回false，表示key不同只是恰好哈希值一樣，添加成功(放成鏈表)
    - 如果equals()返回true，表示兩者key真的一樣，~~那就進入至尊對決~~，此時把put()方法理解為覆蓋，將舊的value2換成新的value1
  - 所謂放成鏈表跟前面Set提到的一樣，類似於"卜"字的概念，從該位置延伸出去存放新的元素
擴容:超過臨界值(容量*負載因子)且要存的位置非空，就會進行擴容，預設的擴容方式為造一個新的兩倍長數組，然後將原有的複製過來
- 預設容量:16
- 預設負載因子:0.75
- 擴容的邏輯是這樣的，為了減少哈希碰撞(就是不希望分支的鏈表太多太長)，所以不會等他裝到滿才擴容。
- 假如負載因子0.9可能老是撞車導致分支很多，負載因子0.2可能一直在擴容，折衷就定負載因子為0.75效率最高

JDK8的改動

new HashMap():實例化時，底層沒有創建數組，首次調用put()方法才創建，類似懶漢式
底層數組用Node[]取代Entry[]
當數組某一個位置上的元素以鏈表形式存在的數據>8，且當前數組長度>64時，將鏈表改為紅黑樹儲存，提高查找效率
- 白話:分支長度>8且主幹長度>64轉紅黑樹

LinkedHashMap

繼承了HashMap的Node，但又多了before跟after兩個屬性，所以形成雙向鏈表，可以在添加時記錄前後順序

Map常用方法

預設使用一個HashMap的實例物件作為調用的主體演示

Object put(Object key, Object value):添加或修改，並且返回null或被取代的value
void putAll(Map m):將m所有的對都放進去
Object remove(Object key):移除指定key的鍵值對，返回被刪除的value
void clear():清空當前map中所有數據，注意與map=null不同，只是清空數據，本身還在
Object get(Object key):獲取對應的value
boolean containsKey(Object key):是否有此key
boolean containsValue(Object value):是否有此value
int size():返回鍵值對個數
boolean isEmpty():是否size=0
boolean equals(Object key):判斷當前map與obj是否相等

遍歷Map

切出Collection的部分再用Iterator來遍歷

Set keySet():返回所有key構成的Set集合
Collection values():返回所有value構成的Collection集合

Set entrySet():返回所有key-value構成的Set集合，得到的元素每個都是entry，故也能強轉回去Map再進行一些操作，舉例:

HashMap map = new HashMap();
map.put("A", 123);
map.put("B", 1234);
map.put("c", 14564);
Set entrySet = map.entrySet();
Iterator iterator = entrySet.iterator();
while (iterator.hasNext()) {
    Object obj = iterator.next();
    Map.Entry entry = (Map.Entry) obj;
    System.out.println(entry.getKey() + "=>" + entry.getValue());
}

TreeMap

實際發開中非常少用，了解即可

規定了key必須都是同類，單看key其實就是TreeSet，排序的規則都是一樣的必須重寫compareTo()或compare()方法

自然排序:加入的類若實現了Comparable接口，此時比較兩個物件是用重寫的compareTo()方法而非equals()，要注意自己重寫的比較邏輯，否則可能會產生兩個物件被誤認為重複元素的狀況
訂製排序:用自訂的比較器，此時比較兩個物件是用重寫的compare()方法而非equals()，舉例:

Properties

key跟value都是String類型，常用於配置文件
有load(文件流)與getProperty(String)方法，專門用來讀取配置文件的訊息

Collections工具類

雖然叫做Collections，但他能操作Set、List還有Map等集合
既然是工具類，顯然都是靜態方法

常用方法

reverse(List):反轉List中元素的順序
shuffle(List):隨機排序List中的元素
sort(List):按照元素自然排序
sort(List, Comparator):依照指定的Comparator對元素排序
swap(List, int, int):交換索引位置
Object max(Collection):根據自然排序返回最大值；也有min方法
Object max(Collection, Comparator):根據指定的Comparator返回最大值
int frequency(Collection, Object):返回Object出現次數
void copy(List dest, List src):將scr的內容複製到dest中，要注意長度，想被貼上的list長度不能比原來的短，可以新建一個填滿null的等長數組去接，舉例:
```
List list = new ArrayList();
// 對list塞了一些元素後，想作為src複製到新的dest
List dest = Arrays.asList(new Object[list.size()]);
Collections.copy(dest,list);
```
boolean replaceAll(List list, 舊, 新):全替換
synchronizedXXX(xxx):返回一個線程安全的xxx集合

小結

Map:由Set存成key(無序不可重複)，由Collection存成value(無序可重複)，key與value組合成無序不可重複的Entry或說Node結構
HashMap的底層原理:16位長的數組，put元素時拿key跑hashCode()再位移運算得出要放的位置，若已經有東西，再比key的euqals()方法，若false表示哈希值恰好相同，在此處分支成鏈表結構儲存；若euqals()返回true表示key完全相等，則進行覆蓋的操作
Hashtable:古老、線程安全、效率低，過時不用；但其下有Properties常用來存配置，特色是K-V都是String
HashTree:key的部分就是SetTree，要求key都是同類，重寫compareTo()或compare()方法後可以用key排序
遍歷Map，用keySet方法取出key為一個Set就能用Iterator遍歷了，還可以用這個key調用get方法獲取對應的value執行各種操作
Collection是一個抽象接口，其下有List跟Set與對應的實現類用來存取單列數據
Collections是一個工具類，有很多靜態方法去操作List、Set還有Map

上次修改於 2021-12-09

Map

分類

結構