來源:http://whu241.blogspot.tw/2013/12/map.html
Map又稱關聯式陣列(Associative Array)，為一種使用key-value pair的方式來存取資料的資料結構。在Java Collection Framework中，java.util.Map只是一個Interface，當中定義了一個map所該具有的基本操作；而實作Map介面的類別至少就超過了15個，從這我們也可看出map的重要性了！
不同的實作，由於其針對的面向不一樣，其使用效率及能解決的問題就各自不同，以下筆者描述一些較常見的map class其特點及用法。
HashMap
為以Hash Table為base所發展出來的類別，基本上在使用map時，若無其它考量，則我們應該優先使用HashMap，因其存取資料的時間複雜度可以達到常數時間，非常地快。另外我們也能在HashMap的建構子設定其Capacity，及loading factor。 若我們使用自訂物件作為HashMap的Key，則此時一定要注意是否正確地覆寫了equals()及hashcode()，否則在使用以雜湊函式為基底的類別及函式時，很可能會出現非開發者預期的結果。另外較特別的是HashMap允許鍵值(key)為null喔。
建構函式
[code lang="java"]
//無引數建構子，表採用預設的capacity(16)，及load factor(0.75)
Map<String, String> hm0 = new HashMap<String, String> ();
//指定capacity為32，load factor仍為預設的0.75
Map<String, String> hm1 = new HashMap<String, String> (32);
//指定capacity為32，load factor為0.8
Map<String, String> hm2 = new HashMap<String, String> (32,(float) 0.8);
[/code]
不保證順序
[code lang="java"]
public class MapSorting {
public static void main(String[] args) {
//iterate時，不保證順序
Map<String, String> hm = new HashMap<String, String> ();
hm.put("J", "John");
hm.put("M", "Mary");
hm.put("B", "Bill");
hm.put("C", "Christine");
hm.put("A", "Ariel");
printMap(hm);
}
public static void printMap(Map<String,String> map) {
for (Map.Entry<String,String> entry:map.entrySet()) {
System.out.println(entry.getKey()+" "+entry.getValue());
}
}
}
[/code]
Output從輸出結果中我們可以看到，hashMap輸出key時，並沒有依照插入時的順序，也沒有依照Natural Ordering(M在J前面)，所以我們若需要有排序功能的map時，不能選擇HashMap。
[code lang="text"]
A Ariel
B Bill
C Christine
M Mary
J John
[/code]
為了精簡起見，以下的程式碼例子便不再列出main()及printMap函式。
LinkedHashMap
見文生義，LinkedHashMap內部是用linked list來維護其順序性，所以在iterate時其結果乃是依照元素的插入順序或最近最少使用(least-recently-used)順序。在使用上其與hashmap相似，速度只稍差些；但在iterate時卻是比hashmap還來得快喔^^ 而實務上我們也常用其來實作LRU Cache。
[code lang="java"]
//iterate時，保證其順序為插入順序或最近最少使用(least-recently-used,LRU)的順序
Map<String, String> lhm = new LinkedHashMap<String, String> ();
lhm.put("J", "John");
lhm.put("M", "Mary");
lhm.put("B", "Bill");
lhm.put("C", "Christine");
lhm.put("A", "Ariel");
printMap(lhm);
[/code]
Output
我們可以看到輸出結果與元素插入時的順序一致。
[code lang="text"]
J John
M Mary
B Bill
C Christine
A Ariel
[/code]
TreeMap
紅黑樹(red-black tree)的一個實作品，其特點是其key set或key-value pair是有順序性的，而順序為natual ordering或是由所傳入的comparator來決定。另外TreeMap也是唯一一個提供submap()函式的map。
[code lang="java"]
//iterate時，保證其順序為Natural Ordering或Comparator來決定
Map<String, String> tm = new TreeMap<String, String> ();
tm.put("J", "John");
tm.put("M", "Mary");
tm.put("B", "Bill");
tm.put("C", "Christine");
tm.put("A", "Ariel");
printMap(tm);
System.out.println("----------by comparator");
//sort by comparator
tm = new TreeMap<String,String> (new Comparator<String>() {
public int compare(String o1, String o2) {
return o2.compareTo(o1);
}
});
tm.put("J", "John");
tm.put("M", "Mary");
tm.put("B", "Bill");
tm.put("C", "Christine");
tm.put("A", "Ariel");
printMap(tm);
[/code]
Output
[code lang="plain"]
A Ariel
B Bill
C Christine
J John
M Mary
----------by comparator
M Mary
J John
C Christine
B Bill
A Ariel
[/code]
EnumMap
也為Map的一個實作，其特別之處在於只接受列舉(Enumeration)為Key，也因其只接受列舉為key，不像HashMap能接受各種型態的物件作為key，故在實作上能特地為此種情況最佳化。
EnumMap的好處可以從效率上及使用上來描述：技術上，由於EnumMap內部使用Array來實作；另外因不需用呼叫hashcode函式，故其也不會產生collision的問題；所以在同是key為enum的情況下，EnumMap的效能是好過HashMap的。而在使用上，以列舉作為key便不怕有打錯字的情況了，這個特性，筆者非常地喜歡!
特色：
1. 不接受null為key。
2. 以Natural Ordering的方式來儲存Key。
3. 效能比HashMap稍好些。
[code lang="java"]
import java.util.EnumMap;
import java.util.Map;
enum Keys {
A(1), B(2), C(3), J(4), M(5);
private int code;
private Keys(int code) {
this.code = code;
}
public int getCode() {
return this.code;
}
}
ublic class EnumTest {
public static void main(String[] args) {
Map<Keys, String> enumMap = new EnumMap<Keys, String> (Keys.class);
enumMap.put(Keys.J, "John");
enumMap.put(Keys.M, "Mary");
enumMap.put(Keys.B, "Bill");
enumMap.put(Keys.C, "Christine");
enumMap.put(Keys.A, "Ariel");
for (Map.Entry<Keys, String> entry: enumMap.entrySet()) {
System.out.println(entry.getKey()+" "+entry.getKey().getCode()+" "+entry.getValue());
}
}
}
[/code]
Output
我們可看到輸出的順序為key按照Natural Ordering的排序。
[code lang="plain"]
A 1 Ariel
B 2 Bill
C 3 Christine
J 4 John
M 5 Mary
[/code]
WeakHashMap
WeakHashMap在設計上使用canonicalized mappings來節省儲存空間，而其也能讓GC自動地回收key-value pair，讓使用者不用自行清理。 一般而言，一個物件若有reference指向它時，其是不會被GC回收掉的。如hashMap.put("a",Object A)，由於key "a"指向Object A，所以就算key a己沒有被其它程式使用到，key "a"及其value仍不會被回收掉，開發者需手動呼叫remove()，才能避免空間的浪費。而WeakHashMap中的的key若沒被其它程式reference時，這對key-value pair便會自動被GC回收掉。
[code lang="java"]
import java.util.HashMap;
import java.util.Map;
import java.util.WeakHashMap;
public class WeakHashMapTest {
public static void main(String[] args) {
String hashKey = new String("5566");
String weakHashKey = new String("8899");
ap<String,String> hashMap = new HashMap<String,String>();
Map<String,String> weakHashMap = new WeakHashMap<String,String>();
hashMap.put(hashKey, "I'm sad!");
weakHashMap.put(weakHashKey, "Apple");
System.out.printf("value in HashMap: %s \n",hashMap.get(hashKey));
System.out.printf("value in WeakHashMap: %s \n",weakHashMap.get(weakHashKey));
//將兩個map的鍵值設為null
hashKey = null;
weakHashKey = null;
//建議啟動Garbage Collection
System.gc();
System.out.println("-----after Garbage Collection------");
System.out.printf(" HashMap--> size: %d , ",hashMap.size());
for (String str:hashMap.values()){
System.out.printf("value: %s \n",str);
}
System.out.printf("WeakHashMap--> size: %d , ",weakHashMap.size());
for (String str:weakHashMap.values()) {
System.out.printf(" value: %s \n", str); //key-value entry己被清掉，迴圈己進不來了
}
}
}
[/code]
Output
[code lang="plain"]
value in HashMap: I'm sad!
value in WeakHashMap: Apple
-----after Garbage Collection------
HashMap--> size: 1 , value: I'm sad!
WeakHashMap--> size: 0 ,
[/code]
ConcurrentHashMap
雖然HashMap很好用，但是其並非thread-safe的。當有多個執行緒同時對HashMap進行讀取及修改的動作時，便可能產生「ConcurrentModificationException」；而在JDK 1.5之前，只有HashTable及利用Collections.synchronizedMap()才能保証map在多執行緒環境下的安全，但這兩個方式採用的方法為鎖住整個map，這會造成效能的顯著下降。所以在Sun在1.5時加入了ConcurrentHashMap類別，它能保證thread-safe且效能也不錯。嗯這是怎麼做到的呢？讓我們繼續看下去^^ (為了方便，以下用chm來簡稱ConcurrentHashMap)
為了讓同一個map可以被很多個執行緒同時又讀又寫，chm的作法是只鎖住部份的map!其藉由使用ConcurrencyLevel的值(可在建構子中指定，預設值為16)來將map切成很多塊，。每一塊皆能由不同的執行緒來使用，所以使用不同塊的執行緒並不會互相干擾，而用到同一塊map的執行緒們的溝通則還是藉由lock的機制來保護。
特色
1. 不會丟出ConcurrentModificationException.
2. 有個特別的putIfAbsent(key, value)函式。
3. 不允許鍵值為null。
多執行緒同時存取HashMap
[code lang="java"]
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
public class NotThreadSafeMap implements Runnable {
private String name;
private static Map<Integer, String> map = new HashMap<Integer,String>();
public NotThreadSafeMap(Integer number, String name) {
this.name = name;
map.put(number, name);
}
public void run() {
try{
Iterator<Integer> it = map.keySet().iterator();
while(it.hasNext()) {
Integer key = it.next();
map.put(key+1, name);
}
System.out.println(name+ " inserted");
} catch(Exception e) {
e.printStackTrace();
} finally {
}
}
public static void main(String[] args) {
NotThreadSafeMap not1 = new NotThreadSafeMap(1,"Apple");
NotThreadSafeMap not2 = new NotThreadSafeMap(2,"Beagle");
ExecutorService executor = Executors.newCachedThreadPool();
executor.execute(not1);
executor.execute(not2);
for (Entry<Integer, String> entry: map.entrySet()) {
System.out.println("Key:" + entry.getKey() + " Value:" + entry.getValue());
}
executor.shutdownNow();
}
}
[/code]
Output
產生了exception@@
[code lang="plain"]
Key:1 Value:Apple
Beagle inserted
Apple inserted
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.HashMap$HashIterator.nextEntry(HashMap.java:894)
at java.util.HashMap$EntryIterator.next(HashMap.java:934)
at java.util.HashMap$EntryIterator.next(HashMap.java:932)
at fun.practice.map.NotThreadSafeMap.main(NotThreadSafeMap.java:41)
[/code]
多執行緒同時存取CHM
[code lang="java"]
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
public class ThreadSafeMap implements Runnable {
private String name;
private static Map<Integer, String> map = new ConcurrentHashMap<Integer,String>();
public ThreadSafeMap(Integer number, String name) {
this.name = name;
map.put(number, name);
}
public void run() {
try{
Iterator<Integer> it = map.keySet().iterator();
while(it.hasNext()) {
Integer key = it.next();
map.put(key+1, name);
}
System.out.println(name+ " inserted");
} catch(Exception e) {
e.printStackTrace();
} finally{
}
}
public static void main(String[] args) {
ThreadSafeMap not1 = new ThreadSafeMap(1,"Apple");
ThreadSafeMap not2 = new ThreadSafeMap(2,"Beagle");
ExecutorService executor = Executors.newCachedThreadPool();
executor.execute(not1);
executor.execute(not2);
for (Entry<Integer, String> entry: map.entrySet()) {
System.out.println("Key:" + entry.getKey() + " Value:" + entry.getValue());
}
executor.shutdownNow();
}
}
[/code]
Output
結果正常，不會產生Exception。
[code lang="lang"]
Apple inserted
Key:2 Value:Apple
Key:1 Value:Apple
Key:3 Value:Beagle
Key:4 Value:Beagle
Beagle inserted
[/code]
IdentityHashMap
HashMap在判斷一個鍵值(key)是否己存在時，會呼叫key物件的equals()方法來辨別，任何物件預設的equals()方法都是用物件預設的reference來比較，被覆寫後就是依照此物件的邏輯來比了。IdentityHashMap則是使用"=="，也就是利用reference來比較兩個物件是否相等，不管此物件的equals()有無被覆寫；而其是利用System.identityHashCode(object)來產生hashcode，所以也不會受到mutable object的影響。
IdentityHashMap之所以會存在主要是為了解決使用可變物件(mutable object)為key時，hashmap可能會遇到的困擾。如下例中筆者自行定義了一個Person物件，有name及age兩個屬性。另外筆者覆寫了equals()，以name及age來判斷兩個person物件是否一樣；程式一開始用hashmap來存放person與職稱的對應，在放入了一個person物件為key後，我們改變了此person物件的age，由於age會被equals()使用到，當呼叫containsKey()時其結果會變得不可預測，另外此例中age也會影響到hashcode的計算，所以當拿改變過後的person物件，想取出對應的職稱時，hashmap也可能會找不到原本其應該mapping到的value。
而若我們使用IdentityHashMap來存mutable object時，不管此物件在被放入map之後經過了多少的改變，由於是使用reference來判斷key是否相等，所以containsKey()傳回來的結果總是一致的，另外在getValue(key)時，其傳回的hashCode也不會收到物件改變的影響。
[code lang="java"]
import java.util.HashMap;
import java.util.IdentityHashMap;
import java.util.Map;
import static java.lang.System.out;
class Person {
private String name;
private Integer age;
public Person (String name,Integer age) {
this.name = name;
this.age = age;
}
public void setName(String name) {
this.name = name;
}
public void setAge(Integer age) {
this.age = age;
}
@Override
public boolean equals(Object obj) {
if (obj instanceof Person) {
Person person2 = (Person) obj;
if (this.name.equals(person2.name) && this.age == person2.age) {
return true;
}
}
return false;
}
@Override
public int hashCode() {
return this.age * 47;
}
}
public class IdentityMapTest {
public static void main(String... args) {
Person p = new Person("Wallace",31);
out.println("Mutable object in Hashmap:");
Map<Person, String> hashMap = new HashMap<Person, String>();
hashMap.put(p, "Engineer");
out.println("titleBeforeChange:"+hashMap.get(p));
p.setAge(99);
out.println("title1AfterChange:"+hashMap.get(p));
out.println("\nMutable object in IdentityHashmap:");
p = new Person("Wallace",31);
Map<Person, String> iHashMap = new IdentityHashMap<Person, String>();
iHashMap.put(p, "Engineer");
out.println("titleBeforeChange:"+iHashMap.get(p));
p.setAge(99);
out.println("title1AfterChange:"+iHashMap.get(p));
}
}
[/code]
Output
我們可以看到第3行的取出結果為null，這便是問題所在了。
[code lang="plain"]
Mutable object in Hashmap:
titleBeforeChange:Engineer
title1AfterChange:null
Mutable object in IdentityHashmap:
titleBeforeChange:Engineer
title1AfterChange:Engineer
[/code]
Reference
1. Thinking In Java, 4e.
2. http://java.dzone.com/articles/difference-between-hashmap-and
