「 深入淺出 」集合Map

前面已經介紹完了Collection接口下的集合實作類，今天我們來介紹Map接口下的幾個重要的集合實作類HashMap,Hashtable,LinkedHashMap,TreeMap。

HashMap

(最常用,随機通路速度快,無序,可存一個Null key,多個Null value,非同步)

HashMap是最常用的Map，它根據鍵的HashCode值存儲資料，根據鍵可以直接擷取它的值，具有很快的通路速度，周遊時，取得資料的順序是完全随機的。因為鍵對象不可以重複，是以HashMap最多隻允許一條記錄的鍵為Null，允許多條記錄的值為Null，是非同步的

Hashtable

(HashMap線程安全版,效率低,key和value都不能為null,同步)

Hashtable與HashMap類似，是HashMap的線程安全版，它支援線程同步，即任一時刻隻有一個線程能寫Hashtable，是以也導緻了Hashtale在寫入時會比較慢，它繼承自Dictionary類，不同的是它不允許記錄的鍵或者值為null，同時效率較低。

LinkedHashMap

(有序,周遊性能好,可存一個Null key,多個Null值,非同步)

LinkedHashMap是由散清單+循環雙向連結清單實作的。LinkedHashMap需要維護元素的插入順序，是以性能略低于HashMap的性能；但是因為它以連結清單來維護内部順序，是以在疊代通路Map裡的全部元素時有較好的性能。疊代輸出LinkedHashMap的元素時，将會按照添加key-value對的順序輸出,有HashMap的全部特性。

TreeMap

(有序,可自定義排序,key不能為空,非同步)

TreeMap 是一個有序的key-value集合，它是通過紅黑樹實作的，每個key-value對即作為紅黑樹的一個節點。能夠把它儲存的記錄根據鍵排序，預設是按鍵值的升序排序（自然順序），也可以指定排序的比較器，不允許key值為空，非同步的。

HashMap的實作

下面具體說說hashMap的實作原理(基于jdk1.7)

HashMap的構造函數

//内部數組的預設初始容量，作為hashmap的初始容量     //2的4次方，2的n次方的作用是減少hash沖突     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;     //預設的最大容量     static final int MAXIMUM_CAPACITY = 1 << 30;     //預設負載因子，當容器使用率達到這個75%的時候就擴容     static final float DEFAULT_LOAD_FACTOR = 0.75f;     //當數組表還沒擴容的時候，一個共享的空表對象     static final Entry<?,?>[] EMPTY_TABLE = {};     //内部數組表，用來裝entry，大小隻能是2的n次方。     transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;     // 預設構造函數。     HashMap()     // 指定“容量大小”的構造函數     HashMap(int capacity)     // 指定“容量大小”和“加載因子”的構造函數     HashMap(int capacity, float loadFactor)     // 包含“子Map”的構造函數     HashMap(Map<? extends K, ? extends V> map)           

HashMap有以上4種構造方法,其中HashMap(int capacity)和HashMap(int capacity, float loadFactor)可以指定容量或加載因子。

容量即是HashMap所能存儲的"最大"容量(注意:最大加了雙引号,因為hashMap會做擴容)

加載因子是HashMap在其容量做擴容前可以達到多滿的程度。當容量超出了加載因子與目前容量的乘積時，hashMap會進行擴容達到原來的2倍容量。

當使用預設構造函數HashMap()建構時，會使用預設的容量

DEFAULT_INITIAL_CAPACITY = 1 << 4

(即是16)和預設加載因子

DEFAULT_LOAD_FACTOR = 0.75f

注意

:使用HashMap時,盡量指定它的初始容量,因為擴容是按1倍擴充的,如果頻繁的擴容會導緻性能下降,記憶體的消耗。

底層存儲Entry

上次文中錯誤是這一塊内容,jdk7中低層存儲是Entry,jdk8中低層存儲是Node

HashMap是通過"拉鍊法"實作的哈希表。其底層存儲結構是Entry數組,Entry實際上就是一個單向連結清單,哈希表的"key-value鍵值對"都是存儲在Entry中的。

Entry是HashMap的内部類,如下

/**     * 内部類     * hashmap中每一個鍵值對都是存在Entry對象中，entry還存儲了自己的hash值等資訊     * Entry被儲存在hashmap的内部數組中。     * @param <K> 鍵值名key     * @param <V> 鍵值value     */     static class Entry<K,V> implements Map.Entry<K,V> {             //鍵對象，final修飾，不可變             final K key;             //值對象             V value;             //下一個鍵值對Entry對象             Entry<K,V> next;             //鍵對象的哈希值             int hash;             //提供了一個有參構造方法             Entry(int h, K k, V v, Entry<K,V> n) {                 value = v;                 next = n;                 key = k;                 hash = h;             }            ...         }           

Java中資料存儲方式最底層的兩種結構:數組和連結清單。

數組的特點：連續空間，尋址迅速，但是在刪除或者添加元素的時候需要有較大幅度的移動，是以查詢速度快，增刪較慢。

而連結清單正好相反，由于空間不連續，尋址困難，增刪元素隻需修改指針，是以查詢速度慢、增刪快。

有沒有一種數組結構來綜合一下數組和連結清單，以便發揮它們各自的優勢？答案是肯定的！就是：哈希表（HashMap）。

哈希表具有較快（常量級）的查詢速度，及相對較快的增刪速度，是以很适合在海量資料的環境中使用。一般實作哈希表的方法采用“拉鍊法”，我們可以了解為“連結清單的數組”，如下圖：

從圖中，我們可清楚地看出哈希表是由數組+連結清單組成的，一個長度為16的數組中，每個元素存儲的是一個連結清單的頭結點。

通過hash(key)方法判斷出元素的存儲位置，如果hash(key)值相等，則都存入該hash值所對應的連結清單中。

這個hash(key)方法是HashMap的一個方法,與Object類的hashCode()是有所差別的,hash(key)在hashCode()方法的基礎做一些修改。

HashMap周遊

有3種周遊方式,map.keySet()、map.values()、Map.Entry,例子代碼如下

public class Demo2 {         public static void main(String[] args) {             Map<Integer, String> map = new HashMap<Integer, String>();             map.put(1, "aaaa");             map.put(2, "bbbb");             map.put(3, "cccc");             System.out.println(map);             // 第一種方式: 使用keySet             // 需要分别擷取key和value，沒有面向對象的思想             // Set<K> keySet() 傳回所有的key對象的Set集合             Set<Integer> ks = map.keySet();             Iterator<Integer> it = ks.iterator();             while (it.hasNext()) {                 Integer key = it.next();                 String value = map.get(key);                 System.out.println("key=" + key + " value=" + value);             }             // 第二種方式：map.values()             // 通過values 擷取所有值,不能擷取到key對象             // Collection<V> values()             Collection<String> vs = map.values();             Iterator<String> it = vs.iterator();             while (it.hasNext()) {                 String value = it.next();                 System.out.println(" value=" + value);                     }             // 第三種方式： Map.Entry對象 推薦使用 重點             // Set<Map.Entry<K,V>> entrySet()             // 傳回的Map.Entry對象的Set集合 Map.Entry包含了key和value對象             Set<Map.Entry<Integer, String>> es = map.entrySet();             Iterator<Map.Entry<Integer, String>> it = es.iterator();             while (it.hasNext()) {                 // 傳回的是封裝了key和value對象的Map.Entry對象                 Map.Entry<Integer, String> en = it.next();                 // 擷取Map.Entry對象中封裝的key和value對象                 Integer key = en.getKey();                 String value = en.getValue();                 System.out.println("key=" + key + " value=" + value);               }         }     }           

性能分析及适用場景

• HashMap與Hashtable實作機制幾乎一樣，但是HashMap比Hashtable性能更好些。
• LinkedHashMap比HashMap慢一點，因為它需要維護一個雙向連結清單。
• TreeMap比HashMap與Hashtable慢（尤其在插入、删除key-value時更慢），因為TreeMap底層采用紅黑樹來管理鍵值對。

适用場景：

• 一般的應用場景，盡可能多考慮使用HashMap，因為其為快速查詢設計的。
• 如需特定的排序時，考慮使用TreeMap。
• 如僅僅需要插入的順序時，考慮使用LinkedHashMap。

集合篇系列上講完了,Queue就不講了,實在是很少用到,請自行學習哈~