Merlin的魔力: 維護插入順序

J2SE 1.4 為 Java Collections Framework 引入了兩個新實現， LinkedHashSet 和 LinkedHashMap 。添加這兩個新實現的好處是散列集合現在可以維護貫穿其元素的兩條路徑。除標准的散列關系之外，現在還有一個可遍歷整個集合的鏈表。正常情況下，這個新的第二路徑會遵循插入順序，這意味著集合的迭代器將按照元素的插入順序返回元素（而不按它們的散列碼將其組合成一個集合的順序），但 LinkedHashMap 支持第二種排序選項：按存取順序而非插入順序維護鏈表。

我們來看一下這些新類是如何工作的。

開始

開始使用這些新類非常容易。 只需導入 java.util 包並找到一組要使用的項目。在我們的示例中，我們將使用日歷表的月份。在使用集時我們將使用英語月份名稱，在使用映射表時用英語和意大利語的月份名稱。

清單 1. 開始定義類

import java.util.*;
public class OrderedAccess {
　 public static void main(String args[]) {
　　 String months[] =
　　　 new DateFormatSymbols().getMonths();
　　 String italianMonths[] =
　　　 new DateFormatSymbols(Locale.ITALIAN).getMonths();
　 }
}

我將假定您已經知道了英語月份的名稱和順序。對於那些不熟悉意大利語月份名稱的人們，它們是：Gennaio、Febbraio、Marzo、Aprile、Maggio、Giugno、Luglio、Agosto、Settembre、Ottobre、Novembre 和 Dicembre， 雖然由於某些原因 getMonths() 返回的名稱不是大寫的。

使用新 HashSet

LinkedHashSet 是基本 HashSet 類的一個子類。因此， 凡是 HashSet 能做的工作， LinkedHashSet 也能做到。 類中沒有新方法。您能得到的只有 4 個構造函數：

LinkedHashSet()

　　 LinkedHashSet(Collection c)

　　 LinkedHashSet(int initialCapacity)

　　 LinkedHashSet(int initialCapacity, float loadFactor)

要向集中添加元素，我們可以為每個元素調用 add() ，或創建一個 Collection 並將它傳遞到構造函數。因為數組中已經有了元素，所以最簡單的機制就是使用 Arrays.asList() ，它會返回一個包裝成 List 中的數組，同時維持原始數組的順序。通過將 list 傳遞到構造函數，我們可以很輕松地將相同的 list 添加到 LinkedHashSet 和簡單的 HashSet 中。

清單 2. 填充集

List list = Arrays.asList(months);
　 Set orderedSet = new LinkedHashSet(list);
　 Set unorderedSet = new HashSet(list);

在填滿了集之後，我們可以檢查它們的元素，看看鏈接的集是否按插入順序維護其元素， 然後與標准散列集比較結果。您可以通過集的 iterator() 手工迭代每個集的各個元素，或只調用 toString() 方法（隱式地），實際上就是它為我們做了那些工作。

清單 3. 顯示集結果　

System.out.println("Ordered:　 " + orderedSet);
　 System.out.println("Unordered: " + unorderedSet);

已排序的集顯示如下：

清單 4. 顯示已排序的集結果Ordered:　 [January, February, March, April, May, June, July, August,

September, October, November, December, ]

而未排序的集顯示如下：

清單 5. 顯示未排序的集結果Unordered: [March, April, November, October, January, July, September,

February, December, May, June, August, ]

使用新 HashMap

LinkedHashMap 的工作原理與 LinkedHashSet 本質相同， 但對每個元素都需要一個鍵和值。它也是原始類，在本例中是 HashMap ，的一個子類，但現在有 5 個構造函數：

LinkedHashMap()

　　 LinkedHashMap(int initialCapacity)

　　 LinkedHashMap(int initialCapacity, float loadFactor)

　　 LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

　　 LinkedHashMap(Map)

添加的構造函數處理存取順序選項。把 false 存取順序作為缺省值， 要獲得一個存取順序的列表，您必須傳入一個 true ；也即映射表的頭部是使用時間距今最遠的映射表條目。

常規 HashMap 的子類 LinkedHashMap 的一個優點是迭代次數不受映射表容量的影響。使用 LinkedHashMap 時，選擇大容量對迭代遍歷次數沒有任何影響， 但使用常規 HashMap 時要影響到性能。

向映射表添加元素要比向集添加元素更加棘手一些，只是因為我們不得不單獨 put() 每一對元素。下面的代碼並沒有什麼特別之處， 只是我們要循環遍歷月份名稱，而不是只向構造函數傳遞一個 Map 。

清單 6. 填充映射表

Map orderedMap = new LinkedHashMap();
　 Map unorderedMap = new HashMap();
　 for (int i=0, n=months.length; i < n; i++) {
　　 orderedMap.put(months[i], italianMonths[i]);
　　 unorderedMap.put(months[i], italianMonths[i]);
　 }

幸運的是，與集相同，您可以只調用映射表的 toString() 方法來獲取按插入順序排列的映射表條目。這種調用將以 key=value 的形式返回每個鍵值對。

清單 7. 顯示映射表結果　System.out.println("Ordered:　 " + orderedMap);

System.out.println("Unordered: " + unorderedMap);

已排序的映射表顯示如下：

清單 8. 顯示已排序的映射表結果

Ordered:

{January=gennaio, February=febbraio, March=marzo, April=aprile,
　 May=maggio, June=giugno, July=luglio, August=agosto, September=settembre,
　 October=ottobre, November=novembre, December=dicembre, =}

而未排序的映射表顯示如下：

清單 9. 顯示未排序的映射表結果

Unordered: {August=agosto, July=luglio, November=novembre, June=giugno,
　 October=ottobre, April=aprile, May=maggio, March=marzo, January=gennaio,
　 February=febbraio, =, December=dicembre, September=settembre}

要自己核對，您可以迭代。所有的迭代器都知道插入順序， 所以在接收到值迭代器 ( values() ) 時，您可以按插入順序遍歷那些值，如下所示：

清單 10. 迭代值　

Collection values = orderedMap.values();
　 for (Iterator i = values.iterator(); i.hasNext();
　　 System.out.println(i.next()));

顯示如下：

清單 11. 顯示已排序的值gennaio

febbraio
marzo
aprile
maggio
giugno
luglio
agosto
settembre
ottobre
novembre
dicembre

按存取順序訪問

我們將要討論的新類的最後一個方面是 LinkedHashMap 的存取順序選項。 將 true 傳遞到 LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) 構造函數使您能夠保持映射表的鏈表的存取順序，從使用時間距今最遠的到最近使用的。換句話說，新項目被添加到尾部，映射表查找操作將項目移到鏈表的尾部。最後一點十分重要。因為映射表的典型的讀存取操作會改變順序，如果多個線程可以從映射表讀取，就應該同步存取操作。

為了演示，我們可以看幾個月份並按新順序打印：

清單 12. 按存取順序訪問元素

Map accessorderedMap =
　　 new LinkedHashMap(20, .80f, true);
　 for (int i=0, n=months.length; i < n; i++) {
　　 accessorderedMap.put(months[i], italianMonths[i]);
　 }
　 accessorderedMap.get("June");
　 accessorderedMap.get("April");
　 accessorderedMap.get("February");
　 System.out.println(accessorderedMap);

因為我們對 3 個月份進行了存取操作，這 3 個月份將被移到列表的尾部，二月在最後，四月在六月的前面：

清單 13. 顯示存取順序結果{January=gennaio, March=marzo, May=maggio, July=luglio, August=agosto,

September=settembre, October=ottobre, November=novembre,

December=dicembre, =, June=giugno, April=aprile, February=febbraio}

注意：您會注意到鏈接的映射表中的額外元素。 = 是一個額外條目， 它是由 getMethods() 方法返回的。由於某些原因， getMonths() 返回 13 個月，而不是 12 個月，其中最後一個月沒有名稱。 出於相同的原因，在鏈接的集示例中有一個逗號，而沒有最後一個月份。

還有一點需要注意： LinkedHashMap 的 1.4 beta 2 版本添加了一個受保護的 removeEldestEntry() 方法。如果需要移去最老的節點，子類可以使該方法返回 true，比如為確保映射表不會獲得多於 n個元素。

完整的示例

下面是完整的示例源代碼。

清單 14. 完整的示例import java.util.*;

import java.text.*;
public class OrderedAccess {
　 public static void main(String args[]) {
　　 String months[] =
　　　 new DateFormatSymbols().getMonths();
　　 String italianMonths[] =
　　　 new DateFormatSymbols(Locale.ITALIAN).getMonths();
　　 List list = Arrays.asList(months);
　　 Set orderedSet = new LinkedHashSet(list);
　　 Set unorderedSet = new HashSet(list);
　　 System.out.println("Ordered:　 " + orderedSet);
　　 System.out.println("Unordered: " + unorderedSet);
　　 Map orderedMap = new LinkedHashMap();
　　 Map unorderedMap = new HashMap();
　　 for (int i=0, n=months.length; i < n; i++) {
　　　 orderedMap.put(months[i], italianMonths[i]);
　　　 unorderedMap.put(months[i], italianMonths[i]);
　　 }
　　 System.out.println("Ordered:　 " + orderedMap);
　　 System.out.println("Unordered: " + unorderedMap);
　　 Collection values = orderedMap.values();
　　 for (Iterator i = values.iterator(); i.hasNext();
　　　 System.out.println(i.next()));
　　 Map accessorderedMap =
　　　 new LinkedHashMap(20, .80f, true);
　　 for (int i=0, n=months.length; i < n; i++) {
　　　 accessorderedMap.put(months[i], italianMonths[i]);
　　 }
　　 accessorderedMap.get("June");
　　 accessorderedMap.get("April");
　　 accessorderedMap.get("February");
　　 System.out.println(accessorderedMap);
　 }
}