001/*
002 * Copyright (C) 2008 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.collect;
018
019import static com.google.common.base.Preconditions.checkNotNull;
020import static com.google.common.base.Preconditions.checkState;
021import static com.google.common.collect.CollectPreconditions.checkEntryNotNull;
022import static com.google.common.collect.CollectPreconditions.checkNonnegative;
023
024import com.google.common.annotations.Beta;
025import com.google.common.annotations.GwtCompatible;
026import com.google.errorprone.annotations.CanIgnoreReturnValue;
027import com.google.errorprone.annotations.concurrent.LazyInit;
028import com.google.j2objc.annotations.RetainedWith;
029import com.google.j2objc.annotations.WeakOuter;
030import java.io.Serializable;
031import java.util.AbstractMap;
032import java.util.Arrays;
033import java.util.Collection;
034import java.util.Collections;
035import java.util.Comparator;
036import java.util.Iterator;
037import java.util.Map;
038import java.util.Map.Entry;
039import java.util.SortedMap;
040import org.checkerframework.checker.nullness.compatqual.MonotonicNonNullDecl;
041import org.checkerframework.checker.nullness.compatqual.NullableDecl;
042
043/**
044 * A {@link Map} whose contents will never change, with many other important properties detailed at
045 * {@link ImmutableCollection}.
046 *
047 * <p>See the Guava User Guide article on <a href=
048 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained"> immutable collections</a>.
049 *
050 * @author Jesse Wilson
051 * @author Kevin Bourrillion
052 * @since 2.0
053 */
054@GwtCompatible(serializable = true, emulated = true)
055@SuppressWarnings("serial") // we're overriding default serialization
056public abstract class ImmutableMap<K, V> implements Map<K, V>, Serializable {
057
058  /**
059   * Returns the empty map. This map behaves and performs comparably to {@link
060   * Collections#emptyMap}, and is preferable mainly for consistency and maintainability of your
061   * code.
062   */
063  @SuppressWarnings("unchecked")
064  public static <K, V> ImmutableMap<K, V> of() {
065    return (ImmutableMap<K, V>) RegularImmutableMap.EMPTY;
066  }
067
068  /**
069   * Returns an immutable map containing a single entry. This map behaves and performs comparably to
070   * {@link Collections#singletonMap} but will not accept a null key or value. It is preferable
071   * mainly for consistency and maintainability of your code.
072   */
073  public static <K, V> ImmutableMap<K, V> of(K k1, V v1) {
074    checkEntryNotNull(k1, v1);
075    return RegularImmutableMap.create(1, new Object[] {k1, v1});
076  }
077
078  /**
079   * Returns an immutable map containing the given entries, in order.
080   *
081   * @throws IllegalArgumentException if duplicate keys are provided
082   */
083  public static <K, V> ImmutableMap<K, V> of(K k1, V v1, K k2, V v2) {
084    checkEntryNotNull(k1, v1);
085    checkEntryNotNull(k2, v2);
086    return RegularImmutableMap.create(2, new Object[] {k1, v1, k2, v2});
087  }
088
089  /**
090   * Returns an immutable map containing the given entries, in order.
091   *
092   * @throws IllegalArgumentException if duplicate keys are provided
093   */
094  public static <K, V> ImmutableMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3) {
095    checkEntryNotNull(k1, v1);
096    checkEntryNotNull(k2, v2);
097    checkEntryNotNull(k3, v3);
098    return RegularImmutableMap.create(3, new Object[] {k1, v1, k2, v2, k3, v3});
099  }
100
101  /**
102   * Returns an immutable map containing the given entries, in order.
103   *
104   * @throws IllegalArgumentException if duplicate keys are provided
105   */
106  public static <K, V> ImmutableMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
107    checkEntryNotNull(k1, v1);
108    checkEntryNotNull(k2, v2);
109    checkEntryNotNull(k3, v3);
110    checkEntryNotNull(k4, v4);
111    return RegularImmutableMap.create(4, new Object[] {k1, v1, k2, v2, k3, v3, k4, v4});
112  }
113
114  /**
115   * Returns an immutable map containing the given entries, in order.
116   *
117   * @throws IllegalArgumentException if duplicate keys are provided
118   */
119  public static <K, V> ImmutableMap<K, V> of(
120      K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
121    checkEntryNotNull(k1, v1);
122    checkEntryNotNull(k2, v2);
123    checkEntryNotNull(k3, v3);
124    checkEntryNotNull(k4, v4);
125    checkEntryNotNull(k5, v5);
126    return RegularImmutableMap.create(5, new Object[] {k1, v1, k2, v2, k3, v3, k4, v4, k5, v5});
127  }
128
129  // looking for of() with > 5 entries? Use the builder instead.
130
131  /**
132   * Verifies that {@code key} and {@code value} are non-null, and returns a new immutable entry
133   * with those values.
134   *
135   * <p>A call to {@link Entry#setValue} on the returned entry will always throw {@link
136   * UnsupportedOperationException}.
137   */
138  static <K, V> Entry<K, V> entryOf(K key, V value) {
139    checkEntryNotNull(key, value);
140    return new AbstractMap.SimpleImmutableEntry<>(key, value);
141  }
142
143  /**
144   * Returns a new builder. The generated builder is equivalent to the builder created by the {@link
145   * Builder} constructor.
146   */
147  public static <K, V> Builder<K, V> builder() {
148    return new Builder<>();
149  }
150
151  /**
152   * Returns a new builder, expecting the specified number of entries to be added.
153   *
154   * <p>If {@code expectedSize} is exactly the number of entries added to the builder before {@link
155   * Builder#build} is called, the builder is likely to perform better than an unsized {@link
156   * #builder()} would have.
157   *
158   * <p>It is not specified if any performance benefits apply if {@code expectedSize} is close to,
159   * but not exactly, the number of entries added to the builder.
160   *
161   * @since 23.1
162   */
163  @Beta
164  public static <K, V> Builder<K, V> builderWithExpectedSize(int expectedSize) {
165    checkNonnegative(expectedSize, "expectedSize");
166    return new Builder<>(expectedSize);
167  }
168
169  static void checkNoConflict(
170      boolean safe, String conflictDescription, Entry<?, ?> entry1, Entry<?, ?> entry2) {
171    if (!safe) {
172      throw conflictException(conflictDescription, entry1, entry2);
173    }
174  }
175
176  static IllegalArgumentException conflictException(
177      String conflictDescription, Object entry1, Object entry2) {
178    return new IllegalArgumentException(
179        "Multiple entries with same " + conflictDescription + ": " + entry1 + " and " + entry2);
180  }
181
182  /**
183   * A builder for creating immutable map instances, especially {@code public static final} maps
184   * ("constant maps"). Example:
185   *
186   * <pre>{@code
187   * static final ImmutableMap<String, Integer> WORD_TO_INT =
188   *     new ImmutableMap.Builder<String, Integer>()
189   *         .put("one", 1)
190   *         .put("two", 2)
191   *         .put("three", 3)
192   *         .build();
193   * }</pre>
194   *
195   * <p>For <i>small</i> immutable maps, the {@code ImmutableMap.of()} methods are even more
196   * convenient.
197   *
198   * <p>By default, a {@code Builder} will generate maps that iterate over entries in the order they
199   * were inserted into the builder, equivalently to {@code LinkedHashMap}. For example, in the
200   * above example, {@code WORD_TO_INT.entrySet()} is guaranteed to iterate over the entries in the
201   * order {@code "one"=1, "two"=2, "three"=3}, and {@code keySet()} and {@code values()} respect
202   * the same order. If you want a different order, consider using {@link ImmutableSortedMap} to
203   * sort by keys, or call {@link #orderEntriesByValue(Comparator)}, which changes this builder to
204   * sort entries by value.
205   *
206   * <p>Builder instances can be reused - it is safe to call {@link #build} multiple times to build
207   * multiple maps in series. Each map is a superset of the maps created before it.
208   *
209   * @since 2.0
210   */
211  public static class Builder<K, V> {
212    @MonotonicNonNullDecl Comparator<? super V> valueComparator;
213    Object[] alternatingKeysAndValues;
214    int size;
215    boolean entriesUsed;
216
217    /**
218     * Creates a new builder. The returned builder is equivalent to the builder generated by {@link
219     * ImmutableMap#builder}.
220     */
221    public Builder() {
222      this(ImmutableCollection.Builder.DEFAULT_INITIAL_CAPACITY);
223    }
224
225    @SuppressWarnings("unchecked")
226    Builder(int initialCapacity) {
227      this.alternatingKeysAndValues = new Object[2 * initialCapacity];
228      this.size = 0;
229      this.entriesUsed = false;
230    }
231
232    private void ensureCapacity(int minCapacity) {
233      if (minCapacity * 2 > alternatingKeysAndValues.length) {
234        alternatingKeysAndValues =
235            Arrays.copyOf(
236                alternatingKeysAndValues,
237                ImmutableCollection.Builder.expandedCapacity(
238                    alternatingKeysAndValues.length, minCapacity * 2));
239        entriesUsed = false;
240      }
241    }
242
243    /**
244     * Associates {@code key} with {@code value} in the built map. Duplicate keys are not allowed,
245     * and will cause {@link #build} to fail.
246     */
247    @CanIgnoreReturnValue
248    public Builder<K, V> put(K key, V value) {
249      ensureCapacity(size + 1);
250      checkEntryNotNull(key, value);
251      alternatingKeysAndValues[2 * size] = key;
252      alternatingKeysAndValues[2 * size + 1] = value;
253      size++;
254      return this;
255    }
256
257    /**
258     * Adds the given {@code entry} to the map, making it immutable if necessary. Duplicate keys are
259     * not allowed, and will cause {@link #build} to fail.
260     *
261     * @since 11.0
262     */
263    @CanIgnoreReturnValue
264    public Builder<K, V> put(Entry<? extends K, ? extends V> entry) {
265      return put(entry.getKey(), entry.getValue());
266    }
267
268    /**
269     * Associates all of the given map's keys and values in the built map. Duplicate keys are not
270     * allowed, and will cause {@link #build} to fail.
271     *
272     * @throws NullPointerException if any key or value in {@code map} is null
273     */
274    @CanIgnoreReturnValue
275    public Builder<K, V> putAll(Map<? extends K, ? extends V> map) {
276      return putAll(map.entrySet());
277    }
278
279    /**
280     * Adds all of the given entries to the built map. Duplicate keys are not allowed, and will
281     * cause {@link #build} to fail.
282     *
283     * @throws NullPointerException if any key, value, or entry is null
284     * @since 19.0
285     */
286    @CanIgnoreReturnValue
287    @Beta
288    public Builder<K, V> putAll(Iterable<? extends Entry<? extends K, ? extends V>> entries) {
289      if (entries instanceof Collection) {
290        ensureCapacity(size + ((Collection<?>) entries).size());
291      }
292      for (Entry<? extends K, ? extends V> entry : entries) {
293        put(entry);
294      }
295      return this;
296    }
297
298    /**
299     * Configures this {@code Builder} to order entries by value according to the specified
300     * comparator.
301     *
302     * <p>The sort order is stable, that is, if two entries have values that compare as equivalent,
303     * the entry that was inserted first will be first in the built map's iteration order.
304     *
305     * @throws IllegalStateException if this method was already called
306     * @since 19.0
307     */
308    @CanIgnoreReturnValue
309    @Beta
310    public Builder<K, V> orderEntriesByValue(Comparator<? super V> valueComparator) {
311      checkState(this.valueComparator == null, "valueComparator was already set");
312      this.valueComparator = checkNotNull(valueComparator, "valueComparator");
313      return this;
314    }
315
316    /*
317     * TODO(kevinb): Should build() and the ImmutableBiMap & ImmutableSortedMap
318     * versions throw an IllegalStateException instead?
319     */
320
321    /**
322     * Returns a newly-created immutable map. The iteration order of the returned map is the order
323     * in which entries were inserted into the builder, unless {@link #orderEntriesByValue} was
324     * called, in which case entries are sorted by value.
325     *
326     * @throws IllegalArgumentException if duplicate keys were added
327     */
328    @SuppressWarnings("unchecked")
329    public ImmutableMap<K, V> build() {
330      /*
331       * If entries is full, then this implementation may end up using the entries array
332       * directly and writing over the entry objects with non-terminal entries, but this is
333       * safe; if this Builder is used further, it will grow the entries array (so it can't
334       * affect the original array), and future build() calls will always copy any entry
335       * objects that cannot be safely reused.
336       */
337      sortEntries();
338      entriesUsed = true;
339      return RegularImmutableMap.create(size, alternatingKeysAndValues);
340    }
341
342    void sortEntries() {
343      if (valueComparator != null) {
344        if (entriesUsed) {
345          alternatingKeysAndValues = Arrays.copyOf(alternatingKeysAndValues, 2 * size);
346        }
347        Entry<K, V>[] entries = new Entry[size];
348        for (int i = 0; i < size; i++) {
349          entries[i] =
350              new AbstractMap.SimpleImmutableEntry<K, V>(
351                  (K) alternatingKeysAndValues[2 * i], (V) alternatingKeysAndValues[2 * i + 1]);
352        }
353        Arrays.sort(
354            entries, 0, size, Ordering.from(valueComparator).onResultOf(Maps.<V>valueFunction()));
355        for (int i = 0; i < size; i++) {
356          alternatingKeysAndValues[2 * i] = entries[i].getKey();
357          alternatingKeysAndValues[2 * i + 1] = entries[i].getValue();
358        }
359      }
360    }
361  }
362
363  /**
364   * Returns an immutable map containing the same entries as {@code map}. The returned map iterates
365   * over entries in the same order as the {@code entrySet} of the original map. If {@code map}
366   * somehow contains entries with duplicate keys (for example, if it is a {@code SortedMap} whose
367   * comparator is not <i>consistent with equals</i>), the results of this method are undefined.
368   *
369   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
370   * safe to do so. The exact circumstances under which a copy will or will not be performed are
371   * undocumented and subject to change.
372   *
373   * @throws NullPointerException if any key or value in {@code map} is null
374   */
375  public static <K, V> ImmutableMap<K, V> copyOf(Map<? extends K, ? extends V> map) {
376    if ((map instanceof ImmutableMap) && !(map instanceof SortedMap)) {
377      @SuppressWarnings("unchecked") // safe since map is not writable
378      ImmutableMap<K, V> kvMap = (ImmutableMap<K, V>) map;
379      if (!kvMap.isPartialView()) {
380        return kvMap;
381      }
382    }
383    return copyOf(map.entrySet());
384  }
385
386  /**
387   * Returns an immutable map containing the specified entries. The returned map iterates over
388   * entries in the same order as the original iterable.
389   *
390   * @throws NullPointerException if any key, value, or entry is null
391   * @throws IllegalArgumentException if two entries have the same key
392   * @since 19.0
393   */
394  @Beta
395  public static <K, V> ImmutableMap<K, V> copyOf(
396      Iterable<? extends Entry<? extends K, ? extends V>> entries) {
397    int initialCapacity =
398        (entries instanceof Collection)
399            ? ((Collection<?>) entries).size()
400            : ImmutableCollection.Builder.DEFAULT_INITIAL_CAPACITY;
401    ImmutableMap.Builder<K, V> builder = new ImmutableMap.Builder<K, V>(initialCapacity);
402    builder.putAll(entries);
403    return builder.build();
404  }
405
406  static final Entry<?, ?>[] EMPTY_ENTRY_ARRAY = new Entry<?, ?>[0];
407
408  abstract static class IteratorBasedImmutableMap<K, V> extends ImmutableMap<K, V> {
409    abstract UnmodifiableIterator<Entry<K, V>> entryIterator();
410
411    @Override
412    ImmutableSet<K> createKeySet() {
413      return new ImmutableMapKeySet<>(this);
414    }
415
416    @Override
417    ImmutableSet<Entry<K, V>> createEntrySet() {
418      @WeakOuter
419      class EntrySetImpl extends ImmutableMapEntrySet<K, V> {
420        @Override
421        ImmutableMap<K, V> map() {
422          return IteratorBasedImmutableMap.this;
423        }
424
425        @Override
426        public UnmodifiableIterator<Entry<K, V>> iterator() {
427          return entryIterator();
428        }
429      }
430      return new EntrySetImpl();
431    }
432
433    @Override
434    ImmutableCollection<V> createValues() {
435      return new ImmutableMapValues<>(this);
436    }
437  }
438
439  ImmutableMap() {}
440
441  /**
442   * Guaranteed to throw an exception and leave the map unmodified.
443   *
444   * @throws UnsupportedOperationException always
445   * @deprecated Unsupported operation.
446   */
447  @CanIgnoreReturnValue
448  @Deprecated
449  @Override
450  public final V put(K k, V v) {
451    throw new UnsupportedOperationException();
452  }
453
454  /**
455   * Guaranteed to throw an exception and leave the map unmodified.
456   *
457   * @throws UnsupportedOperationException always
458   * @deprecated Unsupported operation.
459   */
460  @CanIgnoreReturnValue
461  @Deprecated
462  @Override
463  public final V remove(Object o) {
464    throw new UnsupportedOperationException();
465  }
466
467  /**
468   * Guaranteed to throw an exception and leave the map unmodified.
469   *
470   * @throws UnsupportedOperationException always
471   * @deprecated Unsupported operation.
472   */
473  @Deprecated
474  @Override
475  public final void putAll(Map<? extends K, ? extends V> map) {
476    throw new UnsupportedOperationException();
477  }
478
479  /**
480   * Guaranteed to throw an exception and leave the map unmodified.
481   *
482   * @throws UnsupportedOperationException always
483   * @deprecated Unsupported operation.
484   */
485  @Deprecated
486  @Override
487  public final void clear() {
488    throw new UnsupportedOperationException();
489  }
490
491  @Override
492  public boolean isEmpty() {
493    return size() == 0;
494  }
495
496  @Override
497  public boolean containsKey(@NullableDecl Object key) {
498    return get(key) != null;
499  }
500
501  @Override
502  public boolean containsValue(@NullableDecl Object value) {
503    return values().contains(value);
504  }
505
506  // Overriding to mark it Nullable
507  @Override
508  public abstract V get(@NullableDecl Object key);
509
510  /**
511   * {@inheritDoc}
512   *
513   * <p>See <a
514   * href="https://developer.android.com/reference/java/util/Map.html#getOrDefault%28java.lang.Object,%20V%29">{@code
515   * Map.getOrDefault}</a>.
516   *
517   * @since 23.5 (but since 21.0 in the JRE <a
518   *     href="https://github.com/google/guava#guava-google-core-libraries-for-java">flavor</a>).
519   *     Note that API Level 24 users can call this method with any version of Guava.
520   */
521  // @Override under Java 8 / API Level 24
522  public final V getOrDefault(@NullableDecl Object key, @NullableDecl V defaultValue) {
523    V result = get(key);
524    return (result != null) ? result : defaultValue;
525  }
526
527  @LazyInit private transient ImmutableSet<Entry<K, V>> entrySet;
528
529  /**
530   * Returns an immutable set of the mappings in this map. The iteration order is specified by the
531   * method used to create this map. Typically, this is insertion order.
532   */
533  @Override
534  public ImmutableSet<Entry<K, V>> entrySet() {
535    ImmutableSet<Entry<K, V>> result = entrySet;
536    return (result == null) ? entrySet = createEntrySet() : result;
537  }
538
539  abstract ImmutableSet<Entry<K, V>> createEntrySet();
540
541  @LazyInit @RetainedWith private transient ImmutableSet<K> keySet;
542
543  /**
544   * Returns an immutable set of the keys in this map, in the same order that they appear in {@link
545   * #entrySet}.
546   */
547  @Override
548  public ImmutableSet<K> keySet() {
549    ImmutableSet<K> result = keySet;
550    return (result == null) ? keySet = createKeySet() : result;
551  }
552
553  /*
554   * This could have a good default implementation of return new ImmutableKeySet<K, V>(this),
555   * but ProGuard can't figure out how to eliminate that default when RegularImmutableMap
556   * overrides it.
557   */
558  abstract ImmutableSet<K> createKeySet();
559
560  UnmodifiableIterator<K> keyIterator() {
561    final UnmodifiableIterator<Entry<K, V>> entryIterator = entrySet().iterator();
562    return new UnmodifiableIterator<K>() {
563      @Override
564      public boolean hasNext() {
565        return entryIterator.hasNext();
566      }
567
568      @Override
569      public K next() {
570        return entryIterator.next().getKey();
571      }
572    };
573  }
574
575  @LazyInit @RetainedWith private transient ImmutableCollection<V> values;
576
577  /**
578   * Returns an immutable collection of the values in this map, in the same order that they appear
579   * in {@link #entrySet}.
580   */
581  @Override
582  public ImmutableCollection<V> values() {
583    ImmutableCollection<V> result = values;
584    return (result == null) ? values = createValues() : result;
585  }
586
587  /*
588   * This could have a good default implementation of {@code return new
589   * ImmutableMapValues<K, V>(this)}, but ProGuard can't figure out how to eliminate that default
590   * when RegularImmutableMap overrides it.
591   */
592  abstract ImmutableCollection<V> createValues();
593
594  // cached so that this.multimapView().inverse() only computes inverse once
595  @LazyInit private transient ImmutableSetMultimap<K, V> multimapView;
596
597  /**
598   * Returns a multimap view of the map.
599   *
600   * @since 14.0
601   */
602  public ImmutableSetMultimap<K, V> asMultimap() {
603    if (isEmpty()) {
604      return ImmutableSetMultimap.of();
605    }
606    ImmutableSetMultimap<K, V> result = multimapView;
607    return (result == null)
608        ? (multimapView =
609            new ImmutableSetMultimap<>(new MapViewOfValuesAsSingletonSets(), size(), null))
610        : result;
611  }
612
613  @WeakOuter
614  private final class MapViewOfValuesAsSingletonSets
615      extends IteratorBasedImmutableMap<K, ImmutableSet<V>> {
616
617    @Override
618    public int size() {
619      return ImmutableMap.this.size();
620    }
621
622    @Override
623    ImmutableSet<K> createKeySet() {
624      return ImmutableMap.this.keySet();
625    }
626
627    @Override
628    public boolean containsKey(@NullableDecl Object key) {
629      return ImmutableMap.this.containsKey(key);
630    }
631
632    @Override
633    public ImmutableSet<V> get(@NullableDecl Object key) {
634      V outerValue = ImmutableMap.this.get(key);
635      return (outerValue == null) ? null : ImmutableSet.of(outerValue);
636    }
637
638    @Override
639    boolean isPartialView() {
640      return ImmutableMap.this.isPartialView();
641    }
642
643    @Override
644    public int hashCode() {
645      // ImmutableSet.of(value).hashCode() == value.hashCode(), so the hashes are the same
646      return ImmutableMap.this.hashCode();
647    }
648
649    @Override
650    boolean isHashCodeFast() {
651      return ImmutableMap.this.isHashCodeFast();
652    }
653
654    @Override
655    UnmodifiableIterator<Entry<K, ImmutableSet<V>>> entryIterator() {
656      final Iterator<Entry<K, V>> backingIterator = ImmutableMap.this.entrySet().iterator();
657      return new UnmodifiableIterator<Entry<K, ImmutableSet<V>>>() {
658        @Override
659        public boolean hasNext() {
660          return backingIterator.hasNext();
661        }
662
663        @Override
664        public Entry<K, ImmutableSet<V>> next() {
665          final Entry<K, V> backingEntry = backingIterator.next();
666          return new AbstractMapEntry<K, ImmutableSet<V>>() {
667            @Override
668            public K getKey() {
669              return backingEntry.getKey();
670            }
671
672            @Override
673            public ImmutableSet<V> getValue() {
674              return ImmutableSet.of(backingEntry.getValue());
675            }
676          };
677        }
678      };
679    }
680  }
681
682  @Override
683  public boolean equals(@NullableDecl Object object) {
684    return Maps.equalsImpl(this, object);
685  }
686
687  abstract boolean isPartialView();
688
689  @Override
690  public int hashCode() {
691    return Sets.hashCodeImpl(entrySet());
692  }
693
694  boolean isHashCodeFast() {
695    return false;
696  }
697
698  @Override
699  public String toString() {
700    return Maps.toStringImpl(this);
701  }
702
703  /**
704   * Serialized type for all ImmutableMap instances. It captures the logical contents and they are
705   * reconstructed using public factory methods. This ensures that the implementation types remain
706   * as implementation details.
707   */
708  static class SerializedForm implements Serializable {
709    private final Object[] keys;
710    private final Object[] values;
711
712    SerializedForm(ImmutableMap<?, ?> map) {
713      keys = new Object[map.size()];
714      values = new Object[map.size()];
715      int i = 0;
716      for (Entry<?, ?> entry : map.entrySet()) {
717        keys[i] = entry.getKey();
718        values[i] = entry.getValue();
719        i++;
720      }
721    }
722
723    Object readResolve() {
724      Builder<Object, Object> builder = new Builder<>(keys.length);
725      return createMap(builder);
726    }
727
728    Object createMap(Builder<Object, Object> builder) {
729      for (int i = 0; i < keys.length; i++) {
730        builder.put(keys[i], values[i]);
731      }
732      return builder.build();
733    }
734
735    private static final long serialVersionUID = 0;
736  }
737
738  Object writeReplace() {
739    return new SerializedForm(this);
740  }
741}