Collection集合框架集

java培訓(xùn)之Collection集合框架集

Map

Map概述

• Map與Collection并列存在。用于保存具有映射關(guān)系的數(shù)據(jù):Key-Value
• Map 中的 key 和 value 都可以是任何引用類型的數(shù)據(jù)
• Map 中的 key 不允許重復(fù)
• key 和 value 之間存在單向一對(duì)一關(guān)系，即通過指定的 key 總能找到唯一的、確定的 value。
• Map接口的常用實(shí)現(xiàn)類：HashMap、TreeMap、linkedHashMap和Properties。
• HashMap是 Map 接口使用頻率最高的實(shí)現(xiàn)類。
• 允許使用null鍵和null值，與HashSet一樣，不保證映射的順序。

Map的常用方法：

1、添加、刪除操作：

• Object put(Object key,Object value)
• Object remove(Object key)
• void putAll(Map t)
• void clear()

2、元素查詢的操作：

• Object get(Object key)
• boolean containsKey(Object key)
• boolean containsValue(Object value)
• int size()
• boolean isEmpty()

3、元視圖操作的方法：

• Set keySet()
• Collection values()
• Set entrySet()

Map的遍歷

Collection集合的遍歷：（1）foreach（2）通過Iterator對(duì)象遍歷

Map的遍歷，不能支持foreach

（1）分開遍歷：單獨(dú)遍歷所有key，還可以根據(jù)key獲取對(duì)應(yīng)value

單獨(dú)遍歷所有value

（2）成對(duì)遍歷：遍歷的是映射關(guān)系Map.Entry

Map.Entry是Map接口的內(nèi)部接口。每一種Map內(nèi)部有自己的Map.Entry的實(shí)現(xiàn)類

在Map中存儲(chǔ)數(shù)據(jù)，實(shí)際上是將Key—->value的數(shù)據(jù)存儲(chǔ)在Map.Entry接口的實(shí)例中，再在Map集合中插入Map.Entry的實(shí)例化對(duì)象，如圖示：

public static void main(String[] args) {

Map map = new HashMap();
map.put(“邢濤”, 60);
map.put(“林明明”, 70);
map.put(“田杰”, 80);
map.put(“李鎧”, 90);
map.put(“李信”, 60);
System.out.println(“map的所有key:”);
Set keys = map.keySet();//HashSet
for(Object key : keys){
System.out.println(key+”->”+map.get(key));
}
System.out.println(“map的所有的value：”);
Collection values = map.values();
Iterator iter = values.iterator();
while(iter.hasNext()){
System.out.println(iter.next());
}
System.out.println(“map所有的映射關(guān)系：”);
//映射關(guān)系的類型是Map.Entry類型，它是Map接口的內(nèi)部接口
Set mappings = map.entrySet();
for(Object mapping : mappings){
//System.out.println(mapping);
Map.Entry entry = (Map.Entry)mapping;
System.out.println(“key是：”+ entry.getKey()+ “，value是：”+entry.getValue());
}
}

Map的實(shí)現(xiàn)類

1、HashMap

HashMap 判斷兩個(gè) key 相等的標(biāo)準(zhǔn)是：兩個(gè) key 通過 equals() 方法返回 true，hashCode 值也相等。

HashMap 判斷兩個(gè) value相等的標(biāo)準(zhǔn)是：兩個(gè) value 通過 equals() 方法返回 true。

HashMap線程不安全

JDK1.8之前：

HashMap的內(nèi)部存儲(chǔ)結(jié)構(gòu)其實(shí)是數(shù)組和鏈表的結(jié)合。當(dāng)實(shí)例化一個(gè)HashMap時(shí)，系統(tǒng)會(huì)創(chuàng)建一個(gè)長度為Capacity的Entry數(shù)組，這個(gè)長度在哈希表中被稱為容量(Capacity)，在這個(gè)數(shù)組中可以存放元素的位置我們稱之為“桶”(bucket)，每個(gè)bucket都有自己的索引，系統(tǒng)可以根據(jù)索引快速的查找bucket中的元素。

每個(gè)bucket中存儲(chǔ)一個(gè)元素，即一個(gè)Entry對(duì)象，但每一個(gè)Entry對(duì)象可以帶一個(gè)引用變量，用于指向下一個(gè)元素，因此，在一個(gè)桶中，就有可能生成一個(gè)Entry鏈。而且新添加的元素作為鏈表的head。

HashMap的擴(kuò)容

當(dāng)HashMap中的元素越來越多的時(shí)候，hash沖突的幾率也就越來越高，因?yàn)閿?shù)組的長度是固定的。所以為了提高查詢的效率，就要對(duì)HashMap的數(shù)組進(jìn)行擴(kuò)容，而在HashMap數(shù)組擴(kuò)容之后，最消耗性能的點(diǎn)就出現(xiàn)了：原數(shù)組中的數(shù)據(jù)必須重新計(jì)算其在新數(shù)組中的位置，并放進(jìn)去，這就是resize。

那么HashMap什么時(shí)候進(jìn)行擴(kuò)容呢？

當(dāng)HashMap中的元素個(gè)數(shù)超過數(shù)組大小(數(shù)組總大小length,不是數(shù)組中個(gè)數(shù)size)*loadFactor時(shí)，就會(huì)進(jìn)行數(shù)組擴(kuò)容，loadFactor的默認(rèn)值為0.75，這是一個(gè)折中的取值。也就是說，默認(rèn)情況下，數(shù)組大小為16，那么當(dāng)HashMap中元素個(gè)數(shù)超過16*0.75=12（這個(gè)值就是代碼中的threshold值，也叫做臨界值）的時(shí)候，就把數(shù)組的大小擴(kuò)展為 2*16=32，即擴(kuò)大一倍，然后重新計(jì)算每個(gè)元素在數(shù)組中的位置，而這是一個(gè)非常消耗性能的操作，所以如果我們已經(jīng)預(yù)知HashMap中元素的個(gè)數(shù)，那么預(yù)設(shè)元素的個(gè)數(shù)能夠有效的提高HashMap的性能。

JDK1.8之后：

HashMap的內(nèi)部存儲(chǔ)結(jié)構(gòu)其實(shí)是數(shù)組和鏈表/樹的結(jié)合。當(dāng)實(shí)例化一個(gè)HashMap時(shí)，會(huì)初始化initialCapacity和loadFactor，在put第一對(duì)映射關(guān)系時(shí)，系統(tǒng)會(huì)創(chuàng)建一個(gè)長度為initialCapacity的Node數(shù)組，這個(gè)長度在哈希表中被稱為容量(Capacity)，在這個(gè)數(shù)組中可以存放元素的位置我們稱之為“桶”(bucket)，每個(gè)bucket都有自己的索引，系統(tǒng)可以根據(jù)索引快速的查找bucket中的元素。

每個(gè)bucket中存儲(chǔ)一個(gè)元素，即一個(gè)Node對(duì)象，但每一個(gè)Node對(duì)象可以帶一個(gè)引用變量next，用于指向下一個(gè)元素，因此，在一個(gè)桶中，就有可能生成一個(gè)Node鏈。也可能是一個(gè)一個(gè)TreeNode對(duì)象，每一個(gè)TreeNode對(duì)象可以有兩個(gè)葉子結(jié)點(diǎn)left和right，因此，在一個(gè)桶中，就有可能生成一個(gè)TreeNode樹。而新添加的元素作為鏈表的last,或樹的葉子結(jié)點(diǎn)。（七上八下）

那么HashMap什么時(shí)候進(jìn)行擴(kuò)容和樹形化呢？

當(dāng)HashMap中的元素個(gè)數(shù)超過數(shù)組大小(數(shù)組總大小length,不是數(shù)組中個(gè)數(shù)size)*loadFactor時(shí)，就會(huì)進(jìn)行數(shù)組擴(kuò)容，loadFactor的默認(rèn)值為0.75，這是一個(gè)折中的取值。也就是說，默認(rèn)情況下，數(shù)組大小為16，那么當(dāng)HashMap中元素個(gè)數(shù)超過16*0.75=12（這個(gè)值就是代碼中的threshold值，也叫做臨界值）的時(shí)候，就把數(shù)組的大小擴(kuò)展為 2*16=32，即擴(kuò)大一倍，然后重新計(jì)算每個(gè)元素在數(shù)組中的位置，而這是一個(gè)非常消耗性能的操作，所以如果我們已經(jīng)預(yù)知HashMap中元素的個(gè)數(shù)，那么預(yù)設(shè)元素的個(gè)數(shù)能夠有效的提高HashMap的性能。

當(dāng)HashMap中的其中一個(gè)鏈的對(duì)象個(gè)數(shù)如果達(dá)到了8個(gè)，此時(shí)如果capacity沒有達(dá)到64，那么HashMap會(huì)先擴(kuò)容解決，如果已經(jīng)達(dá)到了64，那么這個(gè)鏈會(huì)變成樹，結(jié)點(diǎn)類型由Node變成TreeNode類型。當(dāng)然，如果當(dāng)映射關(guān)系被移除后，下次resize方法時(shí)判斷樹的結(jié)點(diǎn)個(gè)數(shù)低于6個(gè)，也會(huì)把樹在轉(zhuǎn)為鏈表。

關(guān)于映射關(guān)系的key是否可以修改？

映射關(guān)系存儲(chǔ)到HashMap中會(huì)存儲(chǔ)key的hash值，這樣就不用在每次查找時(shí)重新計(jì)算每一個(gè)Entry或Node（TreeNode）的hash值了，因此如果已經(jīng)put到Map中的映射關(guān)系，再修改key的屬性，而這個(gè)屬性又參與hashcode值的計(jì)算，那么會(huì)導(dǎo)致匹配不上。

HashSet的底層實(shí)現(xiàn)

public class HashSet<E> ……{

private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
public Iterator<E> iterator() {
return map.keySet().iterator();
}
public int size() {
return map.size();
}
public boolean isEmpty() {
return map.isEmpty();

}
public boolean contains(Object o) {
return map.containsKey(o);
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
public void clear() {
map.clear();
}
}

2、linkedHashMap

linkedHashMap 是 HashMap 的子類

與linkedHashSet類似，linkedHashMap 可以維護(hù) Map 的迭代順序：迭代順序與 Key-Value 對(duì)的插入順序一致

3、TreeMap

TreeMap存儲(chǔ) Key-Value 對(duì)時(shí)，需要根據(jù) key進(jìn)行排序。TreeMap 可以保證所有的 Key-Value 對(duì)處于有序狀態(tài)。

TreeMap 的 Key 的排序：

自然排序：TreeMap 的所有的 Key 必須實(shí)現(xiàn) Comparable 接口，而且所有的 Key 應(yīng)該是同一個(gè)類的對(duì)象，否則將會(huì)拋出 ClasssCastException

定制排序：創(chuàng)建 TreeMap 時(shí)，傳入一個(gè) Comparator 對(duì)象，該對(duì)象負(fù)責(zé)對(duì) TreeMap 中的所有 key 進(jìn)行排序。

TreeMap判斷兩個(gè)key相等的標(biāo)準(zhǔn)：兩個(gè)key通過compareTo()方法或者compare()方法返回0。

若使用自定義類作為TreeMap的key，所屬類需要重寫equals()和hashCode()方法，且equals()方法返回true時(shí)，compareTo()方法應(yīng)返回0。

4、Hashtable

Hashtable是個(gè)古老的 Map 實(shí)現(xiàn)類，線程安全。

與HashMap不同，Hashtable 不允許使用 null 作為 key 和 value

與HashMap一樣，Hashtable 也不能保證其中 Key-Value 對(duì)的順序

Hashtable判斷兩個(gè)key相等、兩個(gè)value相等的標(biāo)準(zhǔn)，與hashMap一致。

5、Properties

Properties 類是 Hashtable 的子類，該對(duì)象用于處理屬性文件

由于屬性文件里的 key、value 都是字符串類型，所以 Properties 里的 key 和 value 都是字符串類型

存取數(shù)據(jù)時(shí)，建議使用setProperty(String key,String value)方法和getProperty(String key)方法

Map集合框架集