Guava源码分析——Immutable Collections(4)

Immutable的集合体系，还有中很重要的集合没有介绍，就是ImmutableMap，通过UML图，可以看出ImmutableMap的结构体系。

首先来看一下ImmutableBiMap，因为普通ImmutableMap的实现依赖于它。ImmutableBiMap在ImmutableMap的基础上，加入inverse()等方法，可以使键值反转。ImmutableBiMap的构造，也是根据元素个数的不同，使用不同的实现（0-->EmptyImmutablBiMap，1-->SingletonImmutablBiMap，n(n>=2)-->RegularImmubtalMap），代码如下所示：

public abstract class ImmutableBiMap<K, V> extends ImmutableMap<K, V> implements BiMap<K, V> {    public static <K, V> ImmutableBiMap<K, V> of() {   //Empty元素内部，不维护存储结构，inverse()方法直接返回this   return (ImmutableBiMap<K, V>) EmptyImmutableBiMap.INSTANCE;  }  public static <K, V> ImmutableBiMap<K, V> of(K k1, V v1) {   //单个元素构造时，返回此类，内部维护两个元素K,V，inverse()时，返回V,K的SingletonImmutableBiMap   return new SingletonImmutableBiMap<K, V>(k1, v1);  }  public static <K, V> ImmutableBiMap<K, V> of(K k1, V v1, K k2, V v2) {   //多个元素构造是，返回此类，内部维护两个Entry[]集合，一个以key作为hashbucket的位置，
  //另一个以value作为hashbucket的位置，用于inverse()的时候，key-value的反转   return new RegularImmutableBiMap<K, V>(entryOf(k1, v1), entryOf(k2, v2));  } } 

copyOf()方法，在ImmutableCollections中实现的原则就是，如果copyOf()的还是一份ImmutableCollections集合，那么只是进行引用的赋值，因为集合本身不可变。

看过ImmutableBiMap之后，在回头看ImmutableMap就简单了很多，只是在ImmutableBiMap基础上去除了inverse()方法，并在内部为户单一数组（hashbucket）

不需要维护反转的数组。在无元素和单一元素构造的时候，直接调用ImmutableBiMap.of()和ImmutableBiMap.of(K,V)方法，代码如下所示：

public abstract class ImmutableMap<K, V> implements Map<K, V>, Serializable {    /**    * Returns the empty map. This map behaves and performs comparably to    * {@link Collections#emptyMap}, and is preferable mainly for consistency    * and maintainability of your code.    */   public static <K, V> ImmutableMap<K, V> of() {     return ImmutableBiMap.of();   }    /**    * Returns an immutable map containing a single entry. This map behaves and    * performs comparably to {@link Collections#singletonMap} but will not accept    * a null key or value. It is preferable mainly for consistency and    * maintainability of your code.    */   public static <K, V> ImmutableMap<K, V> of(K k1, V v1) {     return ImmutableBiMap.of(k1, v1);   } }

多个元素构造的时候，返回RegularImmubtalMap，与RegularImmutableBiMap内部实现大同小异，去除对反转（值-键）的数组维护，去除inverse()等方法。

最后简单的阐述一下ImmutableSortedMap的实现，ImmutableMap单一元素和空元素的实现，就不详细说了，有兴趣的读者可以自己看看。多元素实现的时候，

ImmutableSortedMap的具体实现类是RegularImmutableSortedMap，有意思的是，它的内部维护key和value的数据结构是两个List，那么可想而知，排序早在构造的时候就已经完成了，而事实确实是这样，具体代码如下所示：

@SuppressWarnings("unchecked")  public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {        //将排序器和entires传入fromEntries方法        return fromEntries(Ordering.natural(), false, 4, entryOf(k1, v1), entryOf(k2, v2),                 entryOf(k3, v3), entryOf(k4, v4));  }

static <K, V> ImmutableSortedMap<K, V> fromEntries(  Comparator<? super K> comparator, boolean sameComparator, int size, Entry<K, V>... entries) {  for (int i = 0; i < size; i++) {      Entry<K, V> entry = entries[i];      entries[i] = entryOf(entry.getKey(), entry.getValue());  }  if (!sameComparator) {      sortEntries(comparator, size, entries);//遍历entries排序      validateEntries(size, entries, comparator);  }  return fromSortedEntries(comparator, size, entries);     } 

static <K, V> ImmutableSortedMap<K, V> fromSortedEntries( Comparator<? super K> comparator,int size,Entry<K, V>[] entries) {   if (size == 0) {    return emptyMap(comparator);   }   //遍历排序之后的entries，分开key和value，分别组成各自的List   ImmutableList.Builder<K> keyBuilder = ImmutableList.builder();   ImmutableList.Builder<V> valueBuilder = ImmutableList.builder();   for (int i = 0; i < size; i++) {    Entry<K, V> entry = entries[i];    keyBuilder.add(entry.getKey());    valueBuilder.add(entry.getValue());   }   return new RegularImmutableSortedMap<K, V>(     new RegularImmutableSortedSet<K>(keyBuilder.build(), comparator),     valueBuilder.build()); } 

ImmutableMap中的Entry，也是被Guava重新实现，增加了bucket的计算逻辑，如下图UML：

AbstractMapEntry在原有Map.entry基础上，将写操作，置为直接抛异常，ImmutableEntry实现getKey()和getValue()，ImmutableMapEntry再加入bucket的计算和维护方法(链表)，最终反映到NonTerminalMapEntry和TerminalEntry，对于这两个类，TerminalEntry为bucket链表的尾结点，所以实现如下：

static final class TerminalEntry<K, V> extends ImmutableMapEntry<K, V> {  TerminalEntry(ImmutableMapEntry<K, V> contents) {   super(contents);  }  TerminalEntry(K key, V value) {   super(key, value);  }  @Override  @Nullable  ImmutableMapEntry<K, V> getNextInKeyBucket() {   //尾节点，所以没有nuext   return null;  }  @Override  @Nullable  ImmutableMapEntry<K, V> getNextInValueBucket() {   //尾节点，所以没有nuext   return null;  } } 

而NonTerminalMapEntry的构造则需要传入下一个Entry

private static final class NonTerminalMapEntry<K, V> extends ImmutableMapEntry<K, V> {   private final ImmutableMapEntry<K, V> nextInKeyBucket;    NonTerminalMapEntry(K key, V value, ImmutableMapEntry<K, V> nextInKeyBucket) {     super(key, value);     this.nextInKeyBucket = nextInKeyBucket;   }    NonTerminalMapEntry(ImmutableMapEntry<K, V> contents, ImmutableMapEntry<K, V> nextInKeyBucket) {     super(contents);     this.nextInKeyBucket = nextInKeyBucket;   }    @Override   ImmutableMapEntry<K, V> getNextInKeyBucket() {     //同一个bucket中的下一个Entry     return nextInKeyBucket;   }    @Override   @Nullable   ImmutableMapEntry<K, V> getNextInValueBucket() {     //BiMap才会维护Value的Bucket     return null;   } } 

那么在构造的时候，如果产生hash冲突，就是用nonTerminalMapEntry，代码如下所示：

RegularImmutableMap(Entry<?, ?>[] theEntries) {   int size = theEntries.length;   entries = createEntryArray(size);   int tableSize = Hashing.closedTableSize(size, MAX_LOAD_FACTOR);   table = createEntryArray(tableSize);   mask = tableSize - 1;   for (int entryIndex = 0; entryIndex < size; entryIndex++) {     @SuppressWarnings("unchecked") // all our callers carefully put in only Entry<K, V>s     Entry<K, V> entry = (Entry<K, V>) theEntries[entryIndex];     K key = entry.getKey();     V value = entry.getValue();     checkEntryNotNull(key, value);     int tableIndex = Hashing.smear(key.hashCode()) & mask;     @Nullable ImmutableMapEntry<K, V> existing = table[tableIndex];     // prepend, not append, so the entries can be immutable     //在构造是，如果产生hash冲突，那么直接的append到terminal的前面     ImmutableMapEntry<K, V> newEntry = (existing == null)         ? new TerminalEntry<K, V>(key, value)         : new NonTerminalMapEntry<K, V>(key, value, existing);     table[tableIndex] = newEntry;     entries[entryIndex] = newEntry;     checkNoConflictInBucket(key, newEntry, existing);   } }