Map接口
Map是一個將鍵映射為值的對象。一個映射不能包含重復鍵：每個鍵最多能映射一個值。Map接口如下所示:
public interface Map {
// Basic Operations
Object put(Object key, Object value);
Object get(Object key);
Object remove(Object key);
boolean containsKey(Object key);
boolean containsValue(Object value);
int size();
boolean isEmpty();
// Bulk Operations
void putAll(Map t);
void clear();
// Collection Views
public Set keySet();
public Collection values();
public Set entrySet();
// Interface for entrySet element
public interface Entry {
Object getKey();
Object getValue();
Object setValue(Object value);
}
}
JDK包含兩個新的通用Map實現，一個是HashMap, 它將它的項存儲在一個哈希表中，是一種最好的實現；另一個是TreeMap, 它將它的項存儲在一個紅-黑樹上，它可保證迭代的順序。另外， Hashtable已被改進以實現Map。
與哈希表的比較
如果你使用過Hashtable, 你應該已經熟悉了Map的一般風格(當然Map是一個接口，而Hashtable是一個具體的實現)。以下是它們的主要區別:
Map提供Collection視圖，作為Enumeration對象的替代直接支持迭代過程。Collection視圖 極大地提高了接口的可表達性，正如後續課程將講到的。
Map允許你在鍵、值或鍵-值對上進行迭代；Hashtable則不提供第三個選項。
Map提供了在迭代過程中刪除項的安全途徑；Hashtable則不能。
進一步講，Map修補了Hashtable接口上的某些小缺陷。Hashtable具有一個稱作contains的方法，如果Hashtable包含一個給定值，它將返回true。從它的名字上理解， 你可能期望如果Hashtable包含一個給定的key, 這個方法也會返回一個true ，因為鍵是一個Hashtable的主要存取機制。Map接口通過將這個方法重新命名為containsValue，從而消除了引起混亂的來源；同時也改善了接口的一致性: containsValue與containsKey可很好地對應並行。
基本操作
基本操作 (put, get, remove, containsKey, containsValue, s , a和isEmpty) 的功能與它們在Hashtable中的對等物非常相似。下面的簡單程序針對參數列表中的詞匯生成一個頻率表。頻率表將每個詞和它在參數列表中所出現的次數相映射。
import java.util.*;
public class Freq { private static final Integer ONE = new Integer(1);
public static void main(String args[]) {
Map m = new HashMap();
// Initialize frequency table from command line
for (int i=0; i$#@60; args.length; i++) {
Integer freq = (Integer) m.get(args[i]);
m.put(args[i], (freq==null ? ONE :
new Integer(freq.intValue() + 1)));
}
System.out.println(m.size()+" distinct words detected:");
System.out.println(m);
}
}
有關這個程序的一個小技巧是put語句的第二個參數。這是一個條件表達式，它的效果是如果這個詞匯以前從未被看到過，則將頻率設置為one，如果這個詞匯已經被看到，則設置為當前值加1 。讓我們來運行這個程序:
% java Freq if it is to be it is up to me to delegate
8 distinct words detected:
{to=3, me=1, delegate=1, it=2, is=2, if=1, be=1, up=1}
假設你更喜歡以字母順序排列的頻率表，那麼所有你要做的工作就是將Map的實現類型從HashMap改變為TreeMap. 這四個字母的改變，使該程序從相同的命令行生成了如下輸出:
8 distinct words detected:
{be=1, delegate=1, if=1, is=2, it=2, me=1, to=3, up=1}
這個接口"酷"嗎？怎麼樣？
正如Set和List接口一樣, Map加強了對equals和hashCode方法的要求, 於是, 兩個Map對象可做邏輯等同性比較而不必考慮它們的實現類型。如果它們顯示了相等的鍵-值映射, 則兩個Map對象是相等的。
按慣例, 所有的Map實現可提供構造函數; 該構造函數提取一個Map對象並將這個新的Map初始化, 使之包含特定Map中的所有鍵-值映射。這個標准Map構造函數是為Collection實現而設計的標准對象集 構造函數的完全對等物。它允許調用者創建一個期望的實現類型的Map ; 該實現類型初始包含另一個Map的所有映射。而不考慮其它Map的實現類型。例如,假設你有一個命名為ｍ的Map, 則下列一行代碼創建了一個新的HashMap, 它初始包含所有與m相同的鍵-值映射:
Map copy = new HashMap(m);
批量操作(Bulk Operations)
clear操作所完成的工作正象其詞義上所表達的那樣: 它從Map 中刪除所有映射。putAll操作是Collection接口中的addAll操作的Map對等物; 它可將一個Map轉儲至另一個, 除此之外, 它還有一個更微妙的用處。假設一個Map被用來表示屬性-值對(attribute-value pairs ) ; putAll操作將與標准Map構造函數一起提供一種用默認值創建屬性表的簡捷方法。以下是一個可演示此種技術的靜態方法:
static Map newAttributeMap(Map defaults, Map overrides) {
Map result = new HashMap(defaults);
result.putAll(overrides);
return result;
}
Collection視圖
Collection視圖 方法允許以三種方式將一個Map作為一個Collection來視圖:
keySet: 包含在Map中的鍵的Set。
values: 包含在Map中的值的Collection。該Collection不是一個Set, 因為多個鍵可映射相同的值。
entrySet: 包含在Map中的鍵-值對的Set 。Map接口提供了一個小的被稱作Map.Entry的嵌套接口，它是在這個Set中的元素的類型。
Collection視圖提供了在Map上進行迭代的唯一方法。下面的例子給出了在一個Map上迭代鍵的標准慣用程序：
for (Iterator i=m.keySet().iterator(); i.hasNext(); )
System.out.println(i.next());
對值進行迭代的慣用程序是類似的。這是迭代鍵-值對的慣用程序：
for (Iterator i=m.entrySet().iterator(); i.hasNext(); ) {
Map.Entry e = (Map.Entry) i.next();
System.out.println(e.getKey() + ": " + e.getValue());
}
第一次提交這些慣用程序時，許多人考慮到每次調用一個Collection視圖時，Map都必須創建一個新的Collection對象，因而擔心其速度慢。請放心：這是不可能的。如果每次一個Map被要求給出一個特定的Collection視圖時，沒有道理Map不能總是返回相同的對象。這恰恰是所有JDK的Map實現所要作的事。
用所有三個Collection視圖, 調用一個Iterator的remove的操作可從後備Map中刪除相關項(假設該Map支持刪除)。用entrySet視圖, 通過在迭代過程中調用一個Map.Entry的setValue方法 (再一次假設該Map支持值的更改)，也可能改變與一個鍵相關的值。請注意這是在迭代過程中更改一個Map的唯一安全途徑。
Collection視圖支持它的所有形式的元素刪除：remove, removeAll, retainAll, 和clear操作, 以及Iterator.remove操作 (然而，這是建立在假設後備Map支持元素刪除的基礎之上)。
Collection視圖在任何情況下都不支持元素增加。對keySet和values視圖這是無意義的，而對entrySet視
Collection視圖的奇特用法: Map代數
在應用Collection視圖時，批量操作 (containsAll, removeAll和retainAll) 是一個驚人的有力工具。假設你要了解一個Map是否是另一個的子映射（submap），也就是說，第一個Map是否包含第二個的全部鍵-值映射，請看下面慣用程序的小技巧：
if (m1.entrySet().containsAll(m2.entrySet())) {
..
}
對照類似行，假設你要了解兩個Map對象是否包含所有所有相同鍵的映射：
if (m1.keySet().equals(m2.keySet())) {
...
}
圖來說，這是沒必要的，因為後備Map的put和putAll提供了相同的功能。
假設你具有一個映射，代表一個屬性-值對集合；以及兩個sets, 表示要求的屬性和允許的屬性（允許的屬性包括要求的屬性）。下列代碼可判定該屬性映射是否符合那些限定條件，如果不符合，則打印詳細的出錯消息:
boolean valid = true;
Set attributes = attributeMap.keySet();
if(!attributes.containsAll(requiredAttributes)) {
Set missing = new HashSet(requiredAttributes);
missing.removeAll(attributes);
System.out.println("Missing required attributes: "+missing);
valid = false;
}
if (!permissibleAttributes.containsAll(attributes)) {
Set illegal = new HashSet(attributes);
illegal.removeAll(permissibleAttributes);
System.out.println("Contains illegal attributes: "+illegal);
valid = false;
}
if (valid)
System.out.println("OK");
假設你想了解由兩個Map對象公用的所有鍵:
Set commonKeys = new HashSet(a.keySet());
commonKeys.retainAll(b.keySet());
類似的慣用程序使你可以獲得公共值以及公共鍵-值對。要獲得公共鍵-值對，則需格外小心； 因為結果Set的元素（即Map.Entry對象）在Map被更改後，可能是無效的。到目前為止，所有慣用程序都是"非破壞性的"：它們不更改後備Map。下面是一些更改後備Map的例子。假設你要刪除一個Map與另一個Map所共有的所有鍵-值對:
m1.entrySet().removeAll(m2.entrySet());
假設你要從一個Map中刪除所有在另一個Map中具有映射的鍵:
m1.keySet().removeAll(m2.keySet());
當你在同樣的批量操作中開始混合鍵和值時，發生了什麼事情呢？假設你有一個稱作managers的Map， 它將公司中的每個雇員與該雇員的經理相映射。我們對鍵和值對象的類型是不清楚的。這不要緊， 只要它們是相同的類型就可以了。現在，假設你要知道全部的"個體貢獻者"是誰？ (這是為不是經理的雇員所用的公司語言)。下面的一行程序准確地告訴你所要了解的東西:
Set individualContributors = new HashSet(managers.keySet());
individualContributors.removeAll(managers.values());
假設你要辭退直接向某些經理報告的雇員（我們稱他為herbert）:
Employee herbert = ... ;
managers.values().removeAll(Collections.singleton(herbert));
請注意，這個慣用程序利用了Collections.singleton, 它是一個靜態方法，可返回一個永恆的帶有單一特定元素的Set。
一旦完成了這些工作，你就可能有了一幫雇員，他們的經理不再為公司工作（如果任何herbert的直接報告是他們自己的經理）。下列代碼告訴你所有的他們的經理不再為公司工作的雇員:
Map m = new HashMap(managers);
m.values().removeAll(managers.keySet());
Set slackers = m.keySet();
這個例子是一個小的技巧。首先，它作了一個Map的臨時拷貝，然後又從這個臨時拷貝中刪除所有的經理值是初始Map中的鍵的項。記住這個初始Map包含一個為每一個雇員准備的項。於是，在臨時Map中保留的項包含了初始Map中的經理值不再是雇員。在臨時拷貝中的鍵則恰恰表示了我們正在尋找的雇員的所有項。如果你把這個例子多看看，你就應該全清楚了。如果還不清楚，該去拿一杯熱氣騰騰剛釀好的Java飲料了。
還有許多與本章中的慣用程序類似的例子，但要把它們全列出來則過於煩瑣，也是不實際的，一旦你掌握了它的用法，你就很容易在你需要它的時候拿出正確的解決方案。多重映射（Multimaps）一個multimap與一個map類似, 只是它可以將每個鍵映射為多個值。Collections Framework不包括多重映射接口，因為它們不是很普遍地被使用。將一個其值為List對象的Map當作多重映射來使用則是相當簡單的事情。這個技術在下一個代碼舉例中將被演示，這個例子是閱讀每行（全部小寫）一個單詞的一部詞典並打印所有滿足尺寸標准的permutation groups（排列組）。一個排列組是一組單詞，它們包含完全相同的字母，但字母順序不同。這個程序在命令行中使用了兩個參數：詞典文件名和要打印的排列組的尺寸；排列組包含的單詞如果少於指定的最小值，則該排列組不被打印。
有一個查找排列組的標准技巧：將詞典中的每個詞的字母按字母順序進行排列（即將一個詞的字母按字母順序記錄下來）並將一個項放入一個多重映射，將經過字母排序的單詞映射到原來的單詞。例如，單詞"bad" 導致一個項映射 "abd" 至 "bad" 被放入多重映射。一個瞬間的反射將顯示任何給定的鍵映射到所有單詞形成一個排列組。在一個多重映射中迭代鍵以及打印滿足尺寸條件的每一個排列組是一個簡單的事情。
下列程序是這個技術的一個直接的實現。僅有的技巧部分是alphabetize方法，它返回一個串，這個串包含與它的參數相同的字符，並按字母順序排列。這個例程（它與Collections Framework無關) 實現一個巧妙的桶式分類。它假定按字母順序排列的單詞完全由小寫字母組成。
import java.util.*;
import java.io.*;
public class Perm {
public static void main(String[] args) {
int minGroupSize = Integer.parseInt(args[1]);
// Read words from file and put into simulated multimap
Map m = new HashMap();
try {
BufferedReader in =
new BufferedReader(new FileReader(args[0]));
String word;
while((word = in.readLine()) != null) {
String alpha = alphabetize(word);
List l = (List) m.get(alpha);
if (l==null)
m.put(alpha, l=new ArrayList());
l.add(word);
}
} catch(IOException e) {
System.err.println(e);
System.exit(1);
}
// Print all permutation groups above size threshold
for (Iterator i = m.values().iterator(); i.hasNext(); ) {
List l = (List) i.next();
if (l.size() $#@62; = minGroupSize)
System.out.println(l.size() + ": " + l);
}
}
private static String alphabetize(String s) {
int count[] = new int[256];
int len = s.length();
for (int i=0; i$#@60; len; i++)
count[s.charAt(i)]++;
StringBuffer result = new StringBuffer(len);
for (char c="a"; c$#@60; ="z"; c++)
for (int i=0; i$#@60; count[c]; i++)
result.append(c);
return result.toString();
}
}
在一台老式UltraSparc 1上運行一個有80,000個單詞的詞典用了大約16秒；最小排列組尺寸為8 。它生成了下列輸出
% java Perm dictionary.txt 8
9: [estrin, inerts, insert, inters, niters, nitres, sinter,
triens, trines]
8: [carets, cartes, caster, caters, crates, reacts, recast, traces]
9: [capers, crapes, escarp, pacers, parsec, recaps, scrape, secpar,
spacer]
8: [ates, east, eats, etas, sate, seat, seta, teas]
12: [apers, apres, asper, pares, parse, pears, prase, presa, rapes,
reaps, spare, spear]
9: [anestri, antsier, nastier, ratines, retains, retinas, retsina,
stainer, stearin]
10: [least, setal, slate, stale, steal, stela, taels, tales, teals,
tesla]
8: [arles, earls, lares, laser, lears, rales, reals, seral]
8: [lapse, leaps, pales, peals, pleas, salep, sepal, spale]
8: [aspers, parses, passer, prases, repass, spares, sparse, spears]
8: [earings, erasing, gainers, reagins, regains, reginas, searing,
seringa]
11: [alerts, alters, artels, estral, laster, ratels, salter, slater,
staler, stelar, talers]
9: [palest, palets, pastel, petals, plates, pleats, septal, staple,
tepals]
8: [enters, nester, renest, rentes, resent, tenser, ternes, treens]
8: [peris, piers, pries, prise, ripes, speir, spier, spire]
對象排序
一個 List l 可能被做如下排序:
Collections.sort(l);
如果這個 list 由 String 元素所組成, 那麼它將按詞典排序法(按字母順序)進行排序; 如果它是由 Date 元素所組成, 那麼它將按年代順序來排序。Java 怎麼會知道該怎麼做呢? 這一定是個魔術! 其實不然。實際上, String 和 Date 均實現了Comparable接口。Comparable 接口為一個類提供一個 自然排序( natural ordering), 它允許那個類的對象被自動排序。下表列出了實現了Comparable 的JDK類:
類 自然排序
Byte 帶符號的數字排序
Character 不帶符號的數字排序
Long 帶符號的數字排序
Integer 帶符號的數字排序
Short 帶符號的數字排序
Double 帶符號的數字排序
Float 帶符號的數字排序
BigInteger 帶符號的數字排序
BigDecimal 帶符號的數字排序
File 依賴系統的按路徑名字母順序排序
String 按字母順序排序
Date 按年代順序排序
CollationKey 特定字符集按字母順序排序
如果你要為一個其元素沒有實現 Comparable的列表排序，Collections.sort(list) 將扔出一個 ClassCastException。類似的，如果你要為一個其元素沒有作相互比較的列表進行排序， Collections.sort 將扔出一個 ClassCastException. 能夠被相互比較的元素被稱作 mutually comparable（可相互比較的）。雖然不同類型的元素有可能被相互比較，但以上列出的任何JDK類型都不允許在類之間的比較 （inter-class comparison）。
如果你只是要為可比較的元素的列表進行排序，或為它們創建排序的對象集, 則這就是你實際需要了解的全部有關 Comparable 接口的內容。如果你要實現你自己的 Comparable 類型，則下一節將會引起你的興趣。
