【Guava 教學】（6）不可變群集

不可變（Immutability）是函數式程式設計（Functional programming）的基本特性之一。有不少說法是這麼描述：純函數式語言中的變數（Variable）是不可變（Immutable）。是這樣的嗎？基本上沒錯，不過嚴格來說，這樣的說法，是從計算機科學來解釋「變數」這個詞，就如同維基百科上計算機科學上對變數的條目說明是：

可視為在電腦記憶體裏可修改的、存在值的命名空間。

然而，在純函數式語言中對「變數」這個詞，要從數學上來解釋，就如同維基百科上數學上對變數的修目說明是：

用於開放句子，表示尚未清楚的值（即未知數），或一個可代入的值。

在純函數式語言中，當你說 x = 1，那麼說 x 就是 1，不會再是別的，從計算機科學角度來看，就像是不可變的變數，以 Java 為例的話，就像是變數被加上 final 修飾。
如果變數不可變，那設計出來的函數或物件方法就不會有副作用（Side effect），若物件的方法不會有副作用，那麼物件狀態也會是不可變，不可變物件（Immutable object）有許多好處，像是在並行（Concurrent）程式設計時，就不用擔心那些執行緒共用競爭的問題；在面對資料處理問題若需要一些群集（Collection）物件，像是有序的清單（List）、收集不重複物件的集合（Set）等，如果這些群集物件不可變，那麼就有可能共用資料結構，達到節省時間及空間之目的。
Java 在設計群集框架時，並沒有為不可變群集物件設計專用型態，看看 Collection 介面就知道了，那些 add、remove 等方法就直接定義在上頭。有趣的是，在 Collections Framework Overview 中談到了，有些方法操作都是選用的（Optional），如果不打算提供實作的方法，可以丟出 UnsupportedOperationException，實作物件必須在文件上指明，支援哪些操作。
在這樣的聲明下，如果你原本有個群集已收集了一些物件，現在打算傳遞這個群集，而且不希望拿到這個群集的任何一方對它做出修改（Modify）操作，那麼可以使用 Collections 上提供的 unmodifiableXXX 方法，那些方法會將群集包裹，對於查詢方法，會委託原群集，對於會修改群集的 add、remove 等方法，則丟出 UnsupportedOperationException。例如 unmodifiableCollection 方法的實作是這樣的：

...
    public static  Collection unmodifiableCollection(Collection<? extends T> c) {
        return new UnmodifiableCollection<>(c);
    }
    static class UnmodifiableCollection implements Collection, Serializable {
        private static final long serialVersionUID = 1820017752578914078L;

        final Collection<? extends E> c;

        UnmodifiableCollection(Collection<? extends E> c) {
            if (c==null)
                throw new NullPointerException();
            this.c = c;
        }

        public int size()                   {return c.size();}
        public boolean isEmpty()            {return c.isEmpty();}
        public boolean contains(Object o)   {return c.contains(o);}
        public Object[] toArray()           {return c.toArray();}
        public  T[] toArray(T[] a)       {return c.toArray(a);}
        public String toString()            {return c.toString();}

        public Iterator iterator() {
            return new Iterator() {
                private final Iterator<? extends E> i = c.iterator();

                public boolean hasNext() {return i.hasNext();}
                public E next()          {return i.next();}
                public void remove() {
                    throw new UnsupportedOperationException();
                }
            };
        }

        public boolean add(E e) {
            throw new UnsupportedOperationException();
        }
        public boolean remove(Object o) {
            throw new UnsupportedOperationException();
        }

        public boolean containsAll(Collection<?> coll) {
            return c.containsAll(coll);
        }

        public boolean addAll(Collection<? extends E> coll) {
            throw new UnsupportedOperationException();
        }
        public boolean removeAll(Collection<?> coll) {
            throw new UnsupportedOperationException();
        }
        public boolean retainAll(Collection<?> coll) {
            throw new UnsupportedOperationException();
        }
        public void clear() {
            throw new UnsupportedOperationException();
        }
    }
...

那麼，透過 unmodifiableXXX 方法傳回的群集是不可變嗎？不是！傳回的物件只是無法修改（Unmodifiable），也就是僅僅不支援修改操作罷了，在 Collections Framework Overview 中就講了：

Collections that do not support modification operations (such as add, remove and clear) are referred to as unmodifiable.

這是什麼意思？簡單來說，如果你有個 List 的實作物件被 list 參考的話，那麼 Collections.unmodifiableList(list) 傳回的物件是無法修改，但卻是可變的（Muttable）！嗯？怎麼變？透過 list.add(...) 等修改操作就可變了！，在 Collections Framework Overview 中也講了：

Collections that additionally guarantee that no change in the Collection object will be visible are referred to as immutable.

所以，不可變從來也沒在 Collections 上那些 unmodifiableXXX 方法的保證中，畢竟名稱上也指出了，傳回的物件是 unmodifiable，不是 immutable。無論這是不是在玩文字遊戲，如果你要的是不可變群集，那麼就不能使用 Collections 上那些 unmodifiableXXX 方法。
Guava 對 JDK 的 Collection、List、Set 等，分別提供了 ImmutableCollection、ImmutableList、ImmutableSet 等實作類別，這些類別的實例是不可變。建立它們的方式之一使透過 static 的 of 方法。例如：

List<String> nameList = ImmutableList.of("Duke", "Java", "Oracle");
Set<String> nameSet = ImmutableSet.of("Duke", "Java", "Oracle");

上例傳回的實例分別會是 ImmutableList 及 ImmutableSet 的實例，有趣的是，ImmutableSet 會保留 of 方法傳入的引數順序。對於 Map，Guava 也有 ImmutableMap。例如以下會建立 ImmutableMap 的實例：

Map<String, Integer> userDB = ImmutableMap.of("Duke", 123, "Java", 456);

如果你需要收集資料，最後取得一個 ImmutableXXX，那麼可以使用 builder 方法取得 ImmutableCollection.Builder 實例，由它來收集物件，最後呼叫其 build 方法建造出不可變群集。例如：

ImmutableList.Builder<Integer> builder = ImmutableList.builder();
for(String arg : args) {
    builder.add(Integer.parseInt(arg));
}
List<Integer> numbers = builder.build();

如果你已經有陣列、Iterable、Iterator 或 Collection 實例，想要用他們來得到不可變群集，則可以使用 copyOf 方法。例如：

public static void doSome(Collection<String> names) {
    List<String> immutableNames = ImmutableList.copyOf(names);
    ...
}

正如 copyOf 名稱指出的，他會將物件從來源（淺層）複製出來，而不是單純的包裹來源，因此你對來源加以變動，並不會影響 copyOf 傳回的物件。不過對於參數型態為 Collection 的 copyOf 方法來說，如果實際上傳入的是子類型的 ImmutableXXX，那麼不一定會發生複製，因為群集不可變，所以實際上會有許多共用資料結構的機會。
舉例而言，如果將 ImmutableCollection 傳入 ImmutableList.copyOf，方法內部會呼叫其 asList 方法，如果傳入的物件實際上是 ImmutableList，其 asList 的實作只是直接 return this 罷了；如果傳入的實際上是 ImmutableSet，asList 傳回的 ImmutableList，實際上會與 ImmutableSet 共用一組陣列。
ImmutableCollection 既然定義了 asList 方法，其傳回 ImmutableList 實例，這也就表示，即使是 ImmutableSet，也可以透過來以 List 的方式檢視。
那麼 ImmutableList 實際上內部是什麼資料結構實作呢？既然它是不可變，那麼陣列自然是最理想的結構，畢竟陣列是記憶體的連續空間結構，索引存取是常數時間。
ImmutableList 有 SingletonImmutableList、RegularImmutableList 與 RegularImmutableAsList 等子類別。空的以及兩個元素以上的 ImmutableList 都會是 RegularImmutableList；asList 傳回的則是 RegularImmutableAsList，這兩個類別內部都使用陣列元素；而單一元素的 ImmutableList 則會是 SingletonImmutableList，這個類別內部直接包裹該元素，不使用陣列，呼叫 get 時，就只是傳回包裹的單一元素而已：

...
final class SingletonImmutableList<E> extends ImmutableList<E> {

  final transient E element;

  SingletonImmutableList(E element) {
    this.element = checkNotNull(element);
  }

  @Override
  public E get(int index) {
    Preconditions.checkElementIndex(index, 1);
    return element;
  }
  ...
}

至於 ImmutableSet 也有 RegularImmutableSet、SingletonImmutableSet 等子類別，實際上 RegularImmutableSet 內部實作也是使用陣列保存元素，這也就是為什麼 ImmutableSet 可以保有元素順序的原因，先前提到，如果 ImmutableList.copyOf 方法傳入的實際上是 ImmutableSet，asList 傳回的 ImmutableList，實際上會與 ImmutableSet 共用一組陣列，指的就是 RegularImmutableSet 中的陣列，不過在呼叫 contains 方法時，並不會因此而成為線性時間，RegularImmutableSet 還保存有另一個陣列，可根據物件的 hashCode 方法傳回值來查找物件，這可從 RegularImmutableSet 的 contains 原始碼略知一二：

...
  @Override public boolean contains(Object target) {
    if (target == null) {
      return false;
    }
    for (int i = Hashing.smear(target.hashCode()); true; i++) {
      Object candidate = table[i & mask];
      if (candidate == null) {
        return false;
      }
      if (candidate.equals(target)) {
        return true;
      }
    }
  }
...

這些原始碼的探討，其實在回應本文一開始談到的，群集物件若是不可變，那麼就有可能共用資料結構，達到節省時間及空間之目的。不可變特性並非僅存於函數式程式設計的世界，在命令式程式設計（Imperative programming）世界中，在某些場合若可善用不可變特性，就可避免因狀態可變而帶來的問題。
Guava 並不特別強調函數式的概念，不過實際上它提出不可變群集程式庫，並非只是單純地令群集不可變，在實作上也確實善用了不可變的益處，你可以查找更多 Guava 不可變群集的相關程式碼，藉此就可以看到更多有趣的設計與概念。