【Guava 教學】（7）Multiset、Multimap 與 BiMap

如果有個清單，想要取得清單中不重複的元素，最快的方式就是使用 JDK 中的 Set。例如：

List<String> words = Arrays.asList("one", "two", "three", "one", "three");
Set<String> wordSet = new HashSet<>(words);
out.println(wordSet); // [two, one, three]

如果不單只是想取得清單中不重複元素，也想要知道清單中重複元素個數，那麼你也許會這麼撰寫：

List<String> words = Arrays.asList("one", "two", "three", "one", "three");
Map<String, Integer> counts = new HashMap<>();
for(String word : words) {
    Integer count = counts.get(word);
    counts.put(word, count == null ? 1 : count + 1); 
}
out.println(counts); // {two=1, one=2, three=2}

如果不單只是計數，在後續迭代時也想要取得重複元素呢？你可能會如此撰寫：

List<String> words = Arrays.asList("one", "two", "three", "one", "three");
Map<String, List<String>> wordBag = new HashMap<>();
for(String word : words) {
    List<String> repeatedWds = wordBag.get(word);
    if(repeatedWds == null) {
       repeatedWds = new ArrayList<>();
       wordBag.put(word, repeatedWds);
    }
    repeatedWds.add(word);
}

透過 repeatedWds 的 entrySet 取得 Map.Entry<String, List<String>>，就可以迭代所有元素。實際上，因為元素相同，使用 List 逐一保留重複的元素沒有必要，可以直接使用先前第二個程式片段中的 Map<String, Integer> 的 count。例如：

for(Map.Entry<String, Integer> entry : counts.entrySet()) {
    int count = entry.getValue();
    for(int c = 0; c < count; c++) {
        String word = entry.getKey();
        用迭代的 word 做些事 ...
    }
}

這些程式碼當然都可以自己撰寫，只不過 Guava 的 Multiset 實作將這些細節都封裝起來了，你可以這麼使用：

List<String> words = Arrays.asList("one", "two", "three", "one", "three");
Multiset<String> wordBag = HashMultiset.create(words);
out.println(wordBag); // [two, one x 2, three x 2]
for(String word : wordBag) {
    用迭代的 word 做些事 ...
}

多重集合（Multiset）是集合（Set）概念的推廣（Generalization），集合中相同元素只能出現一次，元素在集合中只是有或無兩個屬性，多重集合則允許相同元素出現多次，元素在集合中具有重複次數（Occurrence）的概念，多重集合又稱為集合包（Bag）。
Guava 的 Multiset 實作是基於 Map，像是 HashMultiset、TreeMultiset 等，不過 Multiset 不是 Map，Multiset 介面直接繼承了 Collection，跟 Set 也沒有任何繼承關係。在 Multiset 的實作中加入的物件若重複，並不會再加以收集，而是利用一個 Count 物件來記錄物件重複次數。在迭代時，會根據 Count 的重複次數資訊來物件要迭代幾次，size 方法傳回的是所有物件重複次數之總和。
Multiset 繼承自 Collection，並擴充了一些操作重複次數的方法，像是 add(E, int)、remove(E, int)、setCount(E, int) 等，Multiset 不單只是元素有或無的集合概念（這是 Collection 的 contains 職責），因此對於詢問元素重複次數，提供了 count(E) 方法。
在資料結構上，Multiset 實作多重集合時，僅實作了對相同（Identical）物件加以計數的概念，實際上還有另一個應用場合，某個物件符合某個相等（Equivalent）定義時，確實地將物件儲存下來。例如 Letter 物件具有 zipCode 及其它屬性時，若 zipCode 值相同，則 zipCode 與 Letter 資訊都要成對儲存下來：

List<Letter> letters = ...;
Map<Integer, List<Letter>> letterBag = new HashMap<>();
for (Letter letter : letters) {
    Integer zipCode = letter.getZipCode();
    List<Letter> sameZipLetters = letterBag.get(zipCode);
    if (sameZipLetters == null) {
        sameZipLetters = new ArrayList<>();
        letterBag.put(zipCode, sameZipLetters);
    }
    sameZipLetters.add(letter);
}
// {106=[Letter(106, adr1), Letter(106, adr2)], 804=[Letter(804, adr3), Letter(804, ..)]}
out.println(letterBag);

對這樣的需求，單純使用 Guava 的 Multiset 沒辦法達成，Guava 定義這類的需求可使用 Multimap 來解決。

List<Letter> letters = ...;
Multimap<Integer, Letter> letterBag = HashMultimap.create();
for(Letter letter : letters) {
    letterBag.put(letter.getZipCode(), letter);
}
// {106=[Letter(106, adr1), Letter(106, adr2)], 804=[Letter(804, adr3), Letter(804, ..)]}
out.println(letterBag);

JDK 的 Map 一個鍵只會有一個對應值，put 時給定相同的鍵，則先前的值會被覆蓋；Guava 的 Multimap 一個鍵允許有多個對應值，put 時給定相同的鍵，先前的值不會被覆蓋，而是收集在鍵對應的 Collection 中，get 方法指定鍵時，傳回的會是鍵對應的 Collection。
選用 Multimap 實作時要考慮的是，鍵對應的 Collection 之行為，以先前第三個程式片段目的而言，如果 word 重複了，也想要分別收集起來，那麼可以使用 ArrayListMultimap。例如：

List<String> words = Arrays.asList("one", "two", "three", "one", "three");
Multimap<String, String> wordBag = ArrayListMultimap.create();
for(String word : words) {
    wordBag.put(word, word);
}

如此重複的字串，才會被個別收集起來，如果你選用了 HashMultimap，那麼值的部份是使用 HashSet 來儲存，結果就是重複的字串並不會被個別收集起來，最後的行為又有點像是 Multiset 了。
要注意的是，Multimap 並不是 Map，它是一個獨立定義的介面，沒有繼承自任何父介面。倒是 Guava 的 BiMap 就真的是 Map 了，它是 Map 的子介面，BiMap 是指雙向對應（Bidirectional map），鍵可以對應至值，值也可以對應至鍵。舉例而言，如果沒有 BiMap，而只是有個 Map，現在有個值要找出它對應的鍵，那麼可能會寫成：

public static Integer getId(Map<Integer, String> users, String name) {
    for(Map.Entry<Integer, String> userEntry : users.entrySet()) {
        if(name.equals(userEntry.getValue())) {
            return userEntry.getKey();
        }
    }
    return null;
}

使用 BiMap 的話，你可以寫成：

public static Integer getId(Map<Integer, String> users, String name) {
    BiMap<Integer, String> userBiMap = HashBiMap.create(users);
    return userBiMap.inverse().get(name);
}

為了要能夠達到從值取鍵的這個目的，BiMap 的值不能是重複的，因而也成了 BiMap 的一個作用，確保值的獨特性，如果建立 BiMap 時給的 Map 值有重複，或者是使用 BiMap 時加入的值有重複，就會引發 IllegalArgumentException。