android/guava/src/com/google/common/collect/RegularImmutableMap.java - platform/external/guava - Git at Google

 /*
  * Copyright (C) 2008 The Guava Authors
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  * http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 package com.google.common.collect;

 import static com.google.common.base.Preconditions.checkElementIndex;
 import static com.google.common.base.Preconditions.checkPositionIndex;
 import static com.google.common.collect.CollectPreconditions.checkEntryNotNull;
 import static java.util.Objects.requireNonNull;

 import com.google.common.annotations.GwtCompatible;
 import com.google.common.annotations.VisibleForTesting;
 import java.util.AbstractMap;
 import java.util.Arrays;
 import java.util.Map.Entry;
 import javax.annotation.CheckForNull;
 import org.checkerframework.checker.nullness.qual.Nullable;

 /**
  * A hash-based implementation of {@link ImmutableMap}.
  *
  * @author Louis Wasserman
  */
 @GwtCompatible(serializable = true, emulated = true)
 @ElementTypesAreNonnullByDefault
 final class RegularImmutableMap<K, V> extends ImmutableMap<K, V> {
   private static final byte ABSENT = -1;

   // Max size is halved due to indexing into double-sized alternatingKeysAndValues
   private static final int BYTE_MAX_SIZE = 1 << (Byte.SIZE - 1); // 2^7 = 128
   private static final int SHORT_MAX_SIZE = 1 << (Short.SIZE - 1); // 2^15 = 32_768

   private static final int BYTE_MASK = (1 << Byte.SIZE) - 1; // 2^8 - 1 = 255
   private static final int SHORT_MASK = (1 << Short.SIZE) - 1; // 2^16 - 1 = 65_535

   @SuppressWarnings("unchecked")
   static final ImmutableMap<Object, Object> EMPTY =
       new RegularImmutableMap<>(null, new Object[0], 0);

   /*
    * This is an implementation of ImmutableMap optimized especially for Android, which does not like
    * objects per entry.  Instead we use an open-addressed hash table.  This design is basically
    * equivalent to RegularImmutableSet, save that instead of having a hash table containing the
    * elements directly and null for empty positions, we store indices of the keys in the hash table,
    * and ABSENT for empty positions.  We then look up the keys in alternatingKeysAndValues.
    *
    * (The index actually stored is the index of the key in alternatingKeysAndValues, which is
    * double the index of the entry in entrySet.asList.)
    *
    * The basic data structure is described in https://en.wikipedia.org/wiki/Open_addressing.
    * The pointer to a key is stored in hashTable[Hashing.smear(key.hashCode()) % table.length],
    * save that if that location is already full, we try the next index, and the next, until we
    * find an empty table position.  Since the table has a power-of-two size, we use
    * & (table.length - 1) instead of % table.length, though.
    */

   @CheckForNull private final transient Object hashTable;
   @VisibleForTesting final transient @Nullable Object[] alternatingKeysAndValues;
   private final transient int size;

   /*
    * We have some considerable complexity in these create methods because of
    * Builder.buildKeepingLast(). The same Builder might be called with buildKeepingLast() and then
    * buildOrThrow(), or vice versa. So in particular, if we modify alternatingKeysAndValues to
    * eliminate duplicate keys (for buildKeepingLast()) then we have to ensure that a later call to
    * buildOrThrow() will still throw as if the duplicates had not been eliminated. And the exception
    * message must mention two values that were associated with the duplicate key in two different
    * calls to Builder.put (though we don't really care *which* two values if there were more than
    * two). These considerations lead us to have a field of type DuplicateKey in the Builder, which
    * will remember the first duplicate key we encountered. All later calls to buildOrThrow() can
    * mention that key with its values. Further duplicates might be added in the meantime but since
    * builders only ever accumulate entries it will always be valid to throw from buildOrThrow() with
    * the first duplicate.
    */

   // This entry point is for callers other than ImmutableMap.Builder.
   static <K, V> RegularImmutableMap<K, V> create(
       int n, @Nullable Object[] alternatingKeysAndValues) {
     return create(n, alternatingKeysAndValues, /* builder= */ null);
   }

   // This entry point is used by the other create method but also directly by
   // ImmutableMap.Builder, so that it can remember any DuplicateKey encountered and produce an
   // exception for a later buildOrThrow(). If builder is null that means that a duplicate
   // key will lead to an immediate exception. If it is not null then a duplicate key will instead be
   // stored in the builder, which may use it to throw an exception later.
   static <K, V> RegularImmutableMap<K, V> create(
       int n, @Nullable Object[] alternatingKeysAndValues, @Nullable Builder<K, V> builder) {
     if (n == 0) {
       @SuppressWarnings("unchecked")
       RegularImmutableMap<K, V> empty = (RegularImmutableMap<K, V>) EMPTY;
       return empty;
     } else if (n == 1) {
       // requireNonNull is safe because the first `2*n` elements have been filled in.
       checkEntryNotNull(
           requireNonNull(alternatingKeysAndValues[0]), requireNonNull(alternatingKeysAndValues[1]));
       return new RegularImmutableMap<K, V>(null, alternatingKeysAndValues, 1);
     }
     checkPositionIndex(n, alternatingKeysAndValues.length >> 1);
     int tableSize = ImmutableSet.chooseTableSize(n);
     // If there are no duplicate keys, hashTablePlus is the final hashTable value. If there *are*
     // duplicate keys, hashTablePlus consists of 3 elements: [0] the hashTable; [1] the number of
     // entries in alternatingKeysAndValues that are still valid after rewriting to remove
     // duplicates; [2] a Builder.DuplicateKey that records the first duplicate key we encountered
     // for possible later use in exceptions, perhaps straight away.
     Object hashTablePlus = createHashTable(alternatingKeysAndValues, n, tableSize, 0);
     Object hashTable;
     if (hashTablePlus instanceof Object[]) {
       Object[] hashTableAndSizeAndDuplicate = (Object[]) hashTablePlus;
       Builder.DuplicateKey duplicateKey = (Builder.DuplicateKey) hashTableAndSizeAndDuplicate[2];
       if (builder == null) {
         throw duplicateKey.exception();
       }
       builder.duplicateKey = duplicateKey;
       hashTable = hashTableAndSizeAndDuplicate[0];
       n = (Integer) hashTableAndSizeAndDuplicate[1];
       alternatingKeysAndValues = Arrays.copyOf(alternatingKeysAndValues, n * 2);
     } else {
       hashTable = hashTablePlus;
     }
     return new RegularImmutableMap<K, V>(hashTable, alternatingKeysAndValues, n);
   }

   /**
    * Returns a hash table for the specified keys and values, and ensures that neither keys nor
    * values are null. This method may update {@code alternatingKeysAndValues} if there are duplicate
    * keys. If so, the return value will indicate how many entries are still valid, and will also
    * include a {@link Builder.DuplicateKey} in case duplicate keys are not allowed now or will not
    * be allowed on a later {@link Builder#buildOrThrow()} call.
    *
    * @param keyOffset 1 if this is the reverse direction of a BiMap, 0 otherwise.
    * @return an {@code Object} that is a {@code byte[]}, {@code short[]}, or {@code int[]}, the
    *     smallest possible to fit {@code tableSize}; or an {@code Object[]} where [0] is one of
    *     these; [1] indicates how many element pairs in {@code alternatingKeysAndValues} are valid;
    *     and [2] is a {@link Builder.DuplicateKey} for the first duplicate key encountered.
    */
   @CheckForNull
   private static Object createHashTable(
       @Nullable Object[] alternatingKeysAndValues, int n, int tableSize, int keyOffset) {
     if (n == 1) {
       // for n=1 we don't create a hash table, but we need to do the checkEntryNotNull check!
       // requireNonNull is safe because the first `2*n` elements have been filled in.
       checkEntryNotNull(
           requireNonNull(alternatingKeysAndValues[keyOffset]),
           requireNonNull(alternatingKeysAndValues[keyOffset ^ 1]));
       return null;
     }
     int mask = tableSize - 1;
     Builder.DuplicateKey duplicateKey = null;
     if (tableSize <= BYTE_MAX_SIZE) {
       /*
        * Use 8 bits per entry. The value is unsigned to allow use up to a size of 2^8.
        *
        * The absent indicator of -1 signed becomes 2^8 - 1 unsigned, which reduces the actual max
        * size to 2^8 - 1. However, due to a load factor < 1 the limit is never approached.
        */
       byte[] hashTable = new byte[tableSize];
       Arrays.fill(hashTable, ABSENT);

       int outI = 0;
       entries:
       for (int i = 0; i < n; i++) {
         int keyIndex = 2 * i + keyOffset;
         int outKeyIndex = 2 * outI + keyOffset;
         // requireNonNull is safe because the first `2*n` elements have been filled in.
         Object key = requireNonNull(alternatingKeysAndValues[keyIndex]);
         Object value = requireNonNull(alternatingKeysAndValues[keyIndex ^ 1]);
         checkEntryNotNull(key, value);
         for (int h = Hashing.smear(key.hashCode()); ; h++) {
           h &= mask;
           int previousKeyIndex = hashTable[h] & BYTE_MASK; // unsigned read
           if (previousKeyIndex == BYTE_MASK) { // -1 signed becomes 255 unsigned
             hashTable[h] = (byte) outKeyIndex;
             break;
           } else if (key.equals(alternatingKeysAndValues[previousKeyIndex])) {
             duplicateKey =
                 new Builder.DuplicateKey(
                     key, value, requireNonNull(alternatingKeysAndValues[previousKeyIndex ^ 1]));
             alternatingKeysAndValues[previousKeyIndex ^ 1] = value;
             continue entries;
           }
         }
         if (outI < i) { // if outI == i don't bother writing the values back where they came from
           alternatingKeysAndValues[outKeyIndex] = key;
           alternatingKeysAndValues[outKeyIndex ^ 1] = value;
         }
         outI++;
       }
       return outI == n ? hashTable : new Object[] {hashTable, outI, duplicateKey};
     } else if (tableSize <= SHORT_MAX_SIZE) {
       /*
        * Use 16 bits per entry. The value is unsigned to allow use up to a size of 2^16.
        *
        * The absent indicator of -1 signed becomes 2^16 - 1 unsigned, which reduces the actual max
        * size to 2^16 - 1. However, due to a load factor < 1 the limit is never approached.
        */
       short[] hashTable = new short[tableSize];
       Arrays.fill(hashTable, ABSENT);

       int outI = 0;
       entries:
       for (int i = 0; i < n; i++) {
         int keyIndex = 2 * i + keyOffset;
         int outKeyIndex = 2 * outI + keyOffset;
         // requireNonNull is safe because the first `2*n` elements have been filled in.
         Object key = requireNonNull(alternatingKeysAndValues[keyIndex]);
         Object value = requireNonNull(alternatingKeysAndValues[keyIndex ^ 1]);
         checkEntryNotNull(key, value);
         for (int h = Hashing.smear(key.hashCode()); ; h++) {
           h &= mask;
           int previousKeyIndex = hashTable[h] & SHORT_MASK; // unsigned read
           if (previousKeyIndex == SHORT_MASK) { // -1 signed becomes 65_535 unsigned
             hashTable[h] = (short) outKeyIndex;
             break;
           } else if (key.equals(alternatingKeysAndValues[previousKeyIndex])) {
             duplicateKey =
                 new Builder.DuplicateKey(
                     key, value, requireNonNull(alternatingKeysAndValues[previousKeyIndex ^ 1]));
             alternatingKeysAndValues[previousKeyIndex ^ 1] = value;
             continue entries;
           }
         }
         if (outI < i) { // if outI == i don't bother writing the values back where they came from
           alternatingKeysAndValues[outKeyIndex] = key;
           alternatingKeysAndValues[outKeyIndex ^ 1] = value;
         }
         outI++;
       }
       return outI == n ? hashTable : new Object[] {hashTable, outI, duplicateKey};
     } else {
       /*
        * Use 32 bits per entry.
        */
       int[] hashTable = new int[tableSize];
       Arrays.fill(hashTable, ABSENT);

       int outI = 0;
       entries:
       for (int i = 0; i < n; i++) {
         int keyIndex = 2 * i + keyOffset;
         int outKeyIndex = 2 * outI + keyOffset;
         // requireNonNull is safe because the first `2*n` elements have been filled in.
         Object key = requireNonNull(alternatingKeysAndValues[keyIndex]);
         Object value = requireNonNull(alternatingKeysAndValues[keyIndex ^ 1]);
         checkEntryNotNull(key, value);
         for (int h = Hashing.smear(key.hashCode()); ; h++) {
           h &= mask;
           int previousKeyIndex = hashTable[h];
           if (previousKeyIndex == ABSENT) {
             hashTable[h] = outKeyIndex;
             break;
           } else if (key.equals(alternatingKeysAndValues[previousKeyIndex])) {
             duplicateKey =
                 new Builder.DuplicateKey(
                     key, value, requireNonNull(alternatingKeysAndValues[previousKeyIndex ^ 1]));
             alternatingKeysAndValues[previousKeyIndex ^ 1] = value;
             continue entries;
           }
         }
         if (outI < i) { // if outI == i don't bother writing the values back where they came from
           alternatingKeysAndValues[outKeyIndex] = key;
           alternatingKeysAndValues[outKeyIndex ^ 1] = value;
         }
         outI++;
       }
       return outI == n ? hashTable : new Object[] {hashTable, outI, duplicateKey};
     }
   }

   @CheckForNull
   static Object createHashTableOrThrow(
       @Nullable Object[] alternatingKeysAndValues, int n, int tableSize, int keyOffset) {
     Object hashTablePlus = createHashTable(alternatingKeysAndValues, n, tableSize, keyOffset);
     if (hashTablePlus instanceof Object[]) {
       Object[] hashTableAndSizeAndDuplicate = (Object[]) hashTablePlus;
       Builder.DuplicateKey duplicateKey = (Builder.DuplicateKey) hashTableAndSizeAndDuplicate[2];
       throw duplicateKey.exception();
     }
     return hashTablePlus;
   }

   private RegularImmutableMap(
       @CheckForNull Object hashTable, @Nullable Object[] alternatingKeysAndValues, int size) {
     this.hashTable = hashTable;
     this.alternatingKeysAndValues = alternatingKeysAndValues;
     this.size = size;
   }

   @Override
   public int size() {
     return size;
   }

   @SuppressWarnings("unchecked")
   @Override
   @CheckForNull
   public V get(@CheckForNull Object key) {
     Object result = get(hashTable, alternatingKeysAndValues, size, 0, key);
     /*
      * We can't simply cast the result of `RegularImmutableMap.get` to V because of a bug in our
      * nullness checker (resulting from https://github.com/jspecify/checker-framework/issues/8).
      */
     if (result == null) {
       return null;
     } else {
       return (V) result;
     }
   }

   @CheckForNull
   static Object get(
       @CheckForNull Object hashTableObject,
       @Nullable Object[] alternatingKeysAndValues,
       int size,
       int keyOffset,
       @CheckForNull Object key) {
     if (key == null) {
       return null;
     } else if (size == 1) {
       // requireNonNull is safe because the first 2 elements have been filled in.
       return requireNonNull(alternatingKeysAndValues[keyOffset]).equals(key)
           ? requireNonNull(alternatingKeysAndValues[keyOffset ^ 1])
           : null;
     } else if (hashTableObject == null) {
       return null;
     }
     if (hashTableObject instanceof byte[]) {
       byte[] hashTable = (byte[]) hashTableObject;
       int mask = hashTable.length - 1;
       for (int h = Hashing.smear(key.hashCode()); ; h++) {
         h &= mask;
         int keyIndex = hashTable[h] & BYTE_MASK; // unsigned read
         if (keyIndex == BYTE_MASK) { // -1 signed becomes 255 unsigned
           return null;
         } else if (key.equals(alternatingKeysAndValues[keyIndex])) {
           return alternatingKeysAndValues[keyIndex ^ 1];
         }
       }
     } else if (hashTableObject instanceof short[]) {
       short[] hashTable = (short[]) hashTableObject;
       int mask = hashTable.length - 1;
       for (int h = Hashing.smear(key.hashCode()); ; h++) {
         h &= mask;
         int keyIndex = hashTable[h] & SHORT_MASK; // unsigned read
         if (keyIndex == SHORT_MASK) { // -1 signed becomes 65_535 unsigned
           return null;
         } else if (key.equals(alternatingKeysAndValues[keyIndex])) {
           return alternatingKeysAndValues[keyIndex ^ 1];
         }
       }
     } else {
       int[] hashTable = (int[]) hashTableObject;
       int mask = hashTable.length - 1;
       for (int h = Hashing.smear(key.hashCode()); ; h++) {
         h &= mask;
         int keyIndex = hashTable[h];
         if (keyIndex == ABSENT) {
           return null;
         } else if (key.equals(alternatingKeysAndValues[keyIndex])) {
           return alternatingKeysAndValues[keyIndex ^ 1];
         }
       }
     }
   }

   @Override
   ImmutableSet<Entry<K, V>> createEntrySet() {
     return new EntrySet<>(this, alternatingKeysAndValues, 0, size);
   }

   static class EntrySet<K, V> extends ImmutableSet<Entry<K, V>> {
     private final transient ImmutableMap<K, V> map;
     private final transient @Nullable Object[] alternatingKeysAndValues;
     private final transient int keyOffset;
     private final transient int size;

     EntrySet(
         ImmutableMap<K, V> map,
         @Nullable Object[] alternatingKeysAndValues,
         int keyOffset,
         int size) {
       this.map = map;
       this.alternatingKeysAndValues = alternatingKeysAndValues;
       this.keyOffset = keyOffset;
       this.size = size;
     }

     @Override
     public UnmodifiableIterator<Entry<K, V>> iterator() {
       return asList().iterator();
     }

     @Override
     int copyIntoArray(Object[] dst, int offset) {
       return asList().copyIntoArray(dst, offset);
     }

     @Override
     ImmutableList<Entry<K, V>> createAsList() {
       return new ImmutableList<Entry<K, V>>() {
         @Override
         public Entry<K, V> get(int index) {
           checkElementIndex(index, size);
           /*
            * requireNonNull is safe because the first `2*(size+keyOffset)` elements have been filled
            * in.
            */
           @SuppressWarnings("unchecked")
           K key = (K) requireNonNull(alternatingKeysAndValues[2 * index + keyOffset]);
           @SuppressWarnings("unchecked")
           V value = (V) requireNonNull(alternatingKeysAndValues[2 * index + (keyOffset ^ 1)]);
           return new AbstractMap.SimpleImmutableEntry<K, V>(key, value);
         }

         @Override
         public int size() {
           return size;
         }

         @Override
         public boolean isPartialView() {
           return true;
         }
       };
     }

     @Override
     public boolean contains(@CheckForNull Object object) {
       if (object instanceof Entry) {
         Entry<?, ?> entry = (Entry<?, ?>) object;
         Object k = entry.getKey();
         Object v = entry.getValue();
         return v != null && v.equals(map.get(k));
       }
       return false;
     }

     @Override
     boolean isPartialView() {
       return true;
     }

     @Override
     public int size() {
       return size;
     }
   }

   @Override
   ImmutableSet<K> createKeySet() {
     @SuppressWarnings("unchecked")
     ImmutableList<K> keyList =
         (ImmutableList<K>) new KeysOrValuesAsList(alternatingKeysAndValues, 0, size);
     return new KeySet<K>(this, keyList);
   }

   static final class KeysOrValuesAsList extends ImmutableList<Object> {
     private final transient @Nullable Object[] alternatingKeysAndValues;
     private final transient int offset;
     private final transient int size;

     KeysOrValuesAsList(@Nullable Object[] alternatingKeysAndValues, int offset, int size) {
       this.alternatingKeysAndValues = alternatingKeysAndValues;
       this.offset = offset;
       this.size = size;
     }

     @Override
     public Object get(int index) {
       checkElementIndex(index, size);
       // requireNonNull is safe because the first `2*(size+offset)` elements have been filled in.
       return requireNonNull(alternatingKeysAndValues[2 * index + offset]);
     }

     @Override
     boolean isPartialView() {
       return true;
     }

     @Override
     public int size() {
       return size;
     }
   }

   static final class KeySet<K> extends ImmutableSet<K> {
     private final transient ImmutableMap<K, ?> map;
     private final transient ImmutableList<K> list;

     KeySet(ImmutableMap<K, ?> map, ImmutableList<K> list) {
       this.map = map;
       this.list = list;
     }

     @Override
     public UnmodifiableIterator<K> iterator() {
       return asList().iterator();
     }

     @Override
     int copyIntoArray(Object[] dst, int offset) {
       return asList().copyIntoArray(dst, offset);
     }

     @Override
     public ImmutableList<K> asList() {
       return list;
     }

     @Override
     public boolean contains(@CheckForNull Object object) {
       return map.get(object) != null;
     }

     @Override
     boolean isPartialView() {
       return true;
     }

     @Override
     public int size() {
       return map.size();
     }
   }

   @SuppressWarnings("unchecked")
   @Override
   ImmutableCollection<V> createValues() {
     return (ImmutableList<V>) new KeysOrValuesAsList(alternatingKeysAndValues, 1, size);
   }

   @Override
   boolean isPartialView() {
     return false;
   }

   // This class is never actually serialized directly, but we have to make the
   // warning go away (and suppressing would suppress for all nested classes too)
   private static final long serialVersionUID = 0;
 }
	/*
	* Copyright (C) 2008 The Guava Authors
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	package com.google.common.collect;

	import static com.google.common.base.Preconditions.checkElementIndex;
	import static com.google.common.base.Preconditions.checkPositionIndex;
	import static com.google.common.collect.CollectPreconditions.checkEntryNotNull;
	import static java.util.Objects.requireNonNull;

	import com.google.common.annotations.GwtCompatible;
	import com.google.common.annotations.VisibleForTesting;
	import java.util.AbstractMap;
	import java.util.Arrays;
	import java.util.Map.Entry;
	import javax.annotation.CheckForNull;
	import org.checkerframework.checker.nullness.qual.Nullable;

	/**
	* A hash-based implementation of {@link ImmutableMap}.
	*
	* @author Louis Wasserman
	*/
	@GwtCompatible(serializable = true, emulated = true)
	@ElementTypesAreNonnullByDefault
	final class RegularImmutableMap<K, V> extends ImmutableMap<K, V> {
	private static final byte ABSENT = -1;

	// Max size is halved due to indexing into double-sized alternatingKeysAndValues
	private static final int BYTE_MAX_SIZE = 1 << (Byte.SIZE - 1); // 2^7 = 128
	private static final int SHORT_MAX_SIZE = 1 << (Short.SIZE - 1); // 2^15 = 32_768

	private static final int BYTE_MASK = (1 << Byte.SIZE) - 1; // 2^8 - 1 = 255
	private static final int SHORT_MASK = (1 << Short.SIZE) - 1; // 2^16 - 1 = 65_535

	@SuppressWarnings("unchecked")
	static final ImmutableMap<Object, Object> EMPTY =
	new RegularImmutableMap<>(null, new Object[0], 0);

	/*
	* This is an implementation of ImmutableMap optimized especially for Android, which does not like
	* objects per entry. Instead we use an open-addressed hash table. This design is basically
	* equivalent to RegularImmutableSet, save that instead of having a hash table containing the
	* elements directly and null for empty positions, we store indices of the keys in the hash table,
	* and ABSENT for empty positions. We then look up the keys in alternatingKeysAndValues.
	*
	* (The index actually stored is the index of the key in alternatingKeysAndValues, which is
	* double the index of the entry in entrySet.asList.)
	*
	* The basic data structure is described in https://en.wikipedia.org/wiki/Open_addressing.
	* The pointer to a key is stored in hashTable[Hashing.smear(key.hashCode()) % table.length],
	* save that if that location is already full, we try the next index, and the next, until we
	* find an empty table position. Since the table has a power-of-two size, we use
	* & (table.length - 1) instead of % table.length, though.
	*/

	@CheckForNull private final transient Object hashTable;
	@VisibleForTesting final transient @Nullable Object[] alternatingKeysAndValues;
	private final transient int size;

	/*
	* We have some considerable complexity in these create methods because of
	* Builder.buildKeepingLast(). The same Builder might be called with buildKeepingLast() and then
	* buildOrThrow(), or vice versa. So in particular, if we modify alternatingKeysAndValues to
	* eliminate duplicate keys (for buildKeepingLast()) then we have to ensure that a later call to
	* buildOrThrow() will still throw as if the duplicates had not been eliminated. And the exception
	* message must mention two values that were associated with the duplicate key in two different
	* calls to Builder.put (though we don't really care which two values if there were more than
	* two). These considerations lead us to have a field of type DuplicateKey in the Builder, which
	* will remember the first duplicate key we encountered. All later calls to buildOrThrow() can
	* mention that key with its values. Further duplicates might be added in the meantime but since
	* builders only ever accumulate entries it will always be valid to throw from buildOrThrow() with
	* the first duplicate.
	*/

	// This entry point is for callers other than ImmutableMap.Builder.
	static <K, V> RegularImmutableMap<K, V> create(
	int n, @Nullable Object[] alternatingKeysAndValues) {
	return create(n, alternatingKeysAndValues, /* builder= */ null);
	}

	// This entry point is used by the other create method but also directly by
	// ImmutableMap.Builder, so that it can remember any DuplicateKey encountered and produce an
	// exception for a later buildOrThrow(). If builder is null that means that a duplicate
	// key will lead to an immediate exception. If it is not null then a duplicate key will instead be
	// stored in the builder, which may use it to throw an exception later.
	static <K, V> RegularImmutableMap<K, V> create(
	int n, @Nullable Object[] alternatingKeysAndValues, @Nullable Builder<K, V> builder) {
	if (n == 0) {
	@SuppressWarnings("unchecked")
	RegularImmutableMap<K, V> empty = (RegularImmutableMap<K, V>) EMPTY;
	return empty;
	} else if (n == 1) {
	// requireNonNull is safe because the first `2*n` elements have been filled in.
	checkEntryNotNull(
	requireNonNull(alternatingKeysAndValues[0]), requireNonNull(alternatingKeysAndValues[1]));
	return new RegularImmutableMap<K, V>(null, alternatingKeysAndValues, 1);
	}
	checkPositionIndex(n, alternatingKeysAndValues.length >> 1);
	int tableSize = ImmutableSet.chooseTableSize(n);
	// If there are no duplicate keys, hashTablePlus is the final hashTable value. If there are
	// duplicate keys, hashTablePlus consists of 3 elements: [0] the hashTable; [1] the number of
	// entries in alternatingKeysAndValues that are still valid after rewriting to remove
	// duplicates; [2] a Builder.DuplicateKey that records the first duplicate key we encountered
	// for possible later use in exceptions, perhaps straight away.
	Object hashTablePlus = createHashTable(alternatingKeysAndValues, n, tableSize, 0);
	Object hashTable;
	if (hashTablePlus instanceof Object[]) {
	Object[] hashTableAndSizeAndDuplicate = (Object[]) hashTablePlus;
	Builder.DuplicateKey duplicateKey = (Builder.DuplicateKey) hashTableAndSizeAndDuplicate[2];
	if (builder == null) {
	throw duplicateKey.exception();
	}
	builder.duplicateKey = duplicateKey;
	hashTable = hashTableAndSizeAndDuplicate[0];
	n = (Integer) hashTableAndSizeAndDuplicate[1];
	alternatingKeysAndValues = Arrays.copyOf(alternatingKeysAndValues, n * 2);
	} else {
	hashTable = hashTablePlus;
	}
	return new RegularImmutableMap<K, V>(hashTable, alternatingKeysAndValues, n);
	}

	/**
	* Returns a hash table for the specified keys and values, and ensures that neither keys nor
	* values are null. This method may update {@code alternatingKeysAndValues} if there are duplicate
	* keys. If so, the return value will indicate how many entries are still valid, and will also
	* include a {@link Builder.DuplicateKey} in case duplicate keys are not allowed now or will not
	* be allowed on a later {@link Builder#buildOrThrow()} call.
	*
	* @param keyOffset 1 if this is the reverse direction of a BiMap, 0 otherwise.
	* @return an {@code Object} that is a {@code byte[]}, {@code short[]}, or {@code int[]}, the
	* smallest possible to fit {@code tableSize}; or an {@code Object[]} where [0] is one of
	* these; [1] indicates how many element pairs in {@code alternatingKeysAndValues} are valid;
	* and [2] is a {@link Builder.DuplicateKey} for the first duplicate key encountered.
	*/
	@CheckForNull
	private static Object createHashTable(
	@Nullable Object[] alternatingKeysAndValues, int n, int tableSize, int keyOffset) {
	if (n == 1) {
	// for n=1 we don't create a hash table, but we need to do the checkEntryNotNull check!
	// requireNonNull is safe because the first `2*n` elements have been filled in.
	checkEntryNotNull(
	requireNonNull(alternatingKeysAndValues[keyOffset]),
	requireNonNull(alternatingKeysAndValues[keyOffset ^ 1]));
	return null;
	}
	int mask = tableSize - 1;
	Builder.DuplicateKey duplicateKey = null;
	if (tableSize <= BYTE_MAX_SIZE) {
	/*
	* Use 8 bits per entry. The value is unsigned to allow use up to a size of 2^8.
	*
	* The absent indicator of -1 signed becomes 2^8 - 1 unsigned, which reduces the actual max
	* size to 2^8 - 1. However, due to a load factor < 1 the limit is never approached.
	*/
	byte[] hashTable = new byte[tableSize];
	Arrays.fill(hashTable, ABSENT);

	int outI = 0;
	entries:
	for (int i = 0; i < n; i++) {
	int keyIndex = 2 * i + keyOffset;
	int outKeyIndex = 2 * outI + keyOffset;
	// requireNonNull is safe because the first `2*n` elements have been filled in.
	Object key = requireNonNull(alternatingKeysAndValues[keyIndex]);
	Object value = requireNonNull(alternatingKeysAndValues[keyIndex ^ 1]);
	checkEntryNotNull(key, value);
	for (int h = Hashing.smear(key.hashCode()); ; h++) {
	h &= mask;
	int previousKeyIndex = hashTable[h] & BYTE_MASK; // unsigned read
	if (previousKeyIndex == BYTE_MASK) { // -1 signed becomes 255 unsigned
	hashTable[h] = (byte) outKeyIndex;
	break;
	} else if (key.equals(alternatingKeysAndValues[previousKeyIndex])) {
	duplicateKey =
	new Builder.DuplicateKey(
	key, value, requireNonNull(alternatingKeysAndValues[previousKeyIndex ^ 1]));
	alternatingKeysAndValues[previousKeyIndex ^ 1] = value;
	continue entries;
	}
	}
	if (outI < i) { // if outI == i don't bother writing the values back where they came from
	alternatingKeysAndValues[outKeyIndex] = key;
	alternatingKeysAndValues[outKeyIndex ^ 1] = value;
	}
	outI++;
	}
	return outI == n ? hashTable : new Object[] {hashTable, outI, duplicateKey};
	} else if (tableSize <= SHORT_MAX_SIZE) {
	/*
	* Use 16 bits per entry. The value is unsigned to allow use up to a size of 2^16.
	*
	* The absent indicator of -1 signed becomes 2^16 - 1 unsigned, which reduces the actual max
	* size to 2^16 - 1. However, due to a load factor < 1 the limit is never approached.
	*/
	short[] hashTable = new short[tableSize];
	Arrays.fill(hashTable, ABSENT);

	int outI = 0;
	entries:
	for (int i = 0; i < n; i++) {
	int keyIndex = 2 * i + keyOffset;
	int outKeyIndex = 2 * outI + keyOffset;
	// requireNonNull is safe because the first `2*n` elements have been filled in.
	Object key = requireNonNull(alternatingKeysAndValues[keyIndex]);
	Object value = requireNonNull(alternatingKeysAndValues[keyIndex ^ 1]);
	checkEntryNotNull(key, value);
	for (int h = Hashing.smear(key.hashCode()); ; h++) {
	h &= mask;
	int previousKeyIndex = hashTable[h] & SHORT_MASK; // unsigned read
	if (previousKeyIndex == SHORT_MASK) { // -1 signed becomes 65_535 unsigned
	hashTable[h] = (short) outKeyIndex;
	break;
	} else if (key.equals(alternatingKeysAndValues[previousKeyIndex])) {
	duplicateKey =
	new Builder.DuplicateKey(
	key, value, requireNonNull(alternatingKeysAndValues[previousKeyIndex ^ 1]));
	alternatingKeysAndValues[previousKeyIndex ^ 1] = value;
	continue entries;
	}
	}
	if (outI < i) { // if outI == i don't bother writing the values back where they came from
	alternatingKeysAndValues[outKeyIndex] = key;
	alternatingKeysAndValues[outKeyIndex ^ 1] = value;
	}
	outI++;
	}
	return outI == n ? hashTable : new Object[] {hashTable, outI, duplicateKey};
	} else {
	/*
	* Use 32 bits per entry.
	*/
	int[] hashTable = new int[tableSize];
	Arrays.fill(hashTable, ABSENT);

	int outI = 0;
	entries:
	for (int i = 0; i < n; i++) {
	int keyIndex = 2 * i + keyOffset;
	int outKeyIndex = 2 * outI + keyOffset;
	// requireNonNull is safe because the first `2*n` elements have been filled in.
	Object key = requireNonNull(alternatingKeysAndValues[keyIndex]);
	Object value = requireNonNull(alternatingKeysAndValues[keyIndex ^ 1]);
	checkEntryNotNull(key, value);
	for (int h = Hashing.smear(key.hashCode()); ; h++) {
	h &= mask;
	int previousKeyIndex = hashTable[h];
	if (previousKeyIndex == ABSENT) {
	hashTable[h] = outKeyIndex;
	break;
	} else if (key.equals(alternatingKeysAndValues[previousKeyIndex])) {
	duplicateKey =
	new Builder.DuplicateKey(
	key, value, requireNonNull(alternatingKeysAndValues[previousKeyIndex ^ 1]));
	alternatingKeysAndValues[previousKeyIndex ^ 1] = value;
	continue entries;
	}
	}
	if (outI < i) { // if outI == i don't bother writing the values back where they came from
	alternatingKeysAndValues[outKeyIndex] = key;
	alternatingKeysAndValues[outKeyIndex ^ 1] = value;
	}
	outI++;
	}
	return outI == n ? hashTable : new Object[] {hashTable, outI, duplicateKey};
	}
	}

	@CheckForNull
	static Object createHashTableOrThrow(
	@Nullable Object[] alternatingKeysAndValues, int n, int tableSize, int keyOffset) {
	Object hashTablePlus = createHashTable(alternatingKeysAndValues, n, tableSize, keyOffset);
	if (hashTablePlus instanceof Object[]) {
	Object[] hashTableAndSizeAndDuplicate = (Object[]) hashTablePlus;
	Builder.DuplicateKey duplicateKey = (Builder.DuplicateKey) hashTableAndSizeAndDuplicate[2];
	throw duplicateKey.exception();
	}
	return hashTablePlus;
	}

	private RegularImmutableMap(
	@CheckForNull Object hashTable, @Nullable Object[] alternatingKeysAndValues, int size) {
	this.hashTable = hashTable;
	this.alternatingKeysAndValues = alternatingKeysAndValues;
	this.size = size;
	}

	@Override
	public int size() {
	return size;
	}

	@SuppressWarnings("unchecked")
	@Override
	@CheckForNull
	public V get(@CheckForNull Object key) {
	Object result = get(hashTable, alternatingKeysAndValues, size, 0, key);
	/*
	* We can't simply cast the result of `RegularImmutableMap.get` to V because of a bug in our
	* nullness checker (resulting from https://github.com/jspecify/checker-framework/issues/8).
	*/
	if (result == null) {
	return null;
	} else {
	return (V) result;
	}
	}

	@CheckForNull
	static Object get(
	@CheckForNull Object hashTableObject,
	@Nullable Object[] alternatingKeysAndValues,
	int size,
	int keyOffset,
	@CheckForNull Object key) {
	if (key == null) {
	return null;
	} else if (size == 1) {
	// requireNonNull is safe because the first 2 elements have been filled in.
	return requireNonNull(alternatingKeysAndValues[keyOffset]).equals(key)
	? requireNonNull(alternatingKeysAndValues[keyOffset ^ 1])
	: null;
	} else if (hashTableObject == null) {
	return null;
	}
	if (hashTableObject instanceof byte[]) {
	byte[] hashTable = (byte[]) hashTableObject;
	int mask = hashTable.length - 1;
	for (int h = Hashing.smear(key.hashCode()); ; h++) {
	h &= mask;
	int keyIndex = hashTable[h] & BYTE_MASK; // unsigned read
	if (keyIndex == BYTE_MASK) { // -1 signed becomes 255 unsigned
	return null;
	} else if (key.equals(alternatingKeysAndValues[keyIndex])) {
	return alternatingKeysAndValues[keyIndex ^ 1];
	}
	}
	} else if (hashTableObject instanceof short[]) {
	short[] hashTable = (short[]) hashTableObject;
	int mask = hashTable.length - 1;
	for (int h = Hashing.smear(key.hashCode()); ; h++) {
	h &= mask;
	int keyIndex = hashTable[h] & SHORT_MASK; // unsigned read
	if (keyIndex == SHORT_MASK) { // -1 signed becomes 65_535 unsigned
	return null;
	} else if (key.equals(alternatingKeysAndValues[keyIndex])) {
	return alternatingKeysAndValues[keyIndex ^ 1];
	}
	}
	} else {
	int[] hashTable = (int[]) hashTableObject;
	int mask = hashTable.length - 1;
	for (int h = Hashing.smear(key.hashCode()); ; h++) {
	h &= mask;
	int keyIndex = hashTable[h];
	if (keyIndex == ABSENT) {
	return null;
	} else if (key.equals(alternatingKeysAndValues[keyIndex])) {
	return alternatingKeysAndValues[keyIndex ^ 1];
	}
	}
	}
	}

	@Override
	ImmutableSet<Entry<K, V>> createEntrySet() {
	return new EntrySet<>(this, alternatingKeysAndValues, 0, size);
	}

	static class EntrySet<K, V> extends ImmutableSet<Entry<K, V>> {
	private final transient ImmutableMap<K, V> map;
	private final transient @Nullable Object[] alternatingKeysAndValues;
	private final transient int keyOffset;
	private final transient int size;

	EntrySet(
	ImmutableMap<K, V> map,
	@Nullable Object[] alternatingKeysAndValues,
	int keyOffset,
	int size) {
	this.map = map;
	this.alternatingKeysAndValues = alternatingKeysAndValues;
	this.keyOffset = keyOffset;
	this.size = size;
	}

	@Override
	public UnmodifiableIterator<Entry<K, V>> iterator() {
	return asList().iterator();
	}

	@Override
	int copyIntoArray(Object[] dst, int offset) {
	return asList().copyIntoArray(dst, offset);
	}

	@Override
	ImmutableList<Entry<K, V>> createAsList() {
	return new ImmutableList<Entry<K, V>>() {
	@Override
	public Entry<K, V> get(int index) {
	checkElementIndex(index, size);
	/*
	* requireNonNull is safe because the first `2*(size+keyOffset)` elements have been filled
	* in.
	*/
	@SuppressWarnings("unchecked")
	K key = (K) requireNonNull(alternatingKeysAndValues[2 * index + keyOffset]);
	@SuppressWarnings("unchecked")
	V value = (V) requireNonNull(alternatingKeysAndValues[2 * index + (keyOffset ^ 1)]);
	return new AbstractMap.SimpleImmutableEntry<K, V>(key, value);
	}

	@Override
	public int size() {
	return size;
	}

	@Override
	public boolean isPartialView() {
	return true;
	}
	};
	}

	@Override
	public boolean contains(@CheckForNull Object object) {
	if (object instanceof Entry) {
	Entry<?, ?> entry = (Entry<?, ?>) object;
	Object k = entry.getKey();
	Object v = entry.getValue();
	return v != null && v.equals(map.get(k));
	}
	return false;
	}

	@Override
	boolean isPartialView() {
	return true;
	}

	@Override
	public int size() {
	return size;
	}
	}

	@Override
	ImmutableSet<K> createKeySet() {
	@SuppressWarnings("unchecked")
	ImmutableList<K> keyList =
	(ImmutableList<K>) new KeysOrValuesAsList(alternatingKeysAndValues, 0, size);
	return new KeySet<K>(this, keyList);
	}

	static final class KeysOrValuesAsList extends ImmutableList<Object> {
	private final transient @Nullable Object[] alternatingKeysAndValues;
	private final transient int offset;
	private final transient int size;

	KeysOrValuesAsList(@Nullable Object[] alternatingKeysAndValues, int offset, int size) {
	this.alternatingKeysAndValues = alternatingKeysAndValues;
	this.offset = offset;
	this.size = size;
	}

	@Override
	public Object get(int index) {
	checkElementIndex(index, size);
	// requireNonNull is safe because the first `2*(size+offset)` elements have been filled in.
	return requireNonNull(alternatingKeysAndValues[2 * index + offset]);
	}

	@Override
	boolean isPartialView() {
	return true;
	}

	@Override
	public int size() {
	return size;
	}
	}

	static final class KeySet<K> extends ImmutableSet<K> {
	private final transient ImmutableMap<K, ?> map;
	private final transient ImmutableList<K> list;

	KeySet(ImmutableMap<K, ?> map, ImmutableList<K> list) {
	this.map = map;
	this.list = list;
	}

	@Override
	public UnmodifiableIterator<K> iterator() {
	return asList().iterator();
	}

	@Override
	int copyIntoArray(Object[] dst, int offset) {
	return asList().copyIntoArray(dst, offset);
	}

	@Override
	public ImmutableList<K> asList() {
	return list;
	}

	@Override
	public boolean contains(@CheckForNull Object object) {
	return map.get(object) != null;
	}

	@Override
	boolean isPartialView() {
	return true;
	}

	@Override
	public int size() {
	return map.size();
	}
	}

	@SuppressWarnings("unchecked")
	@Override
	ImmutableCollection<V> createValues() {
	return (ImmutableList<V>) new KeysOrValuesAsList(alternatingKeysAndValues, 1, size);
	}

	@Override
	boolean isPartialView() {
	return false;
	}

	// This class is never actually serialized directly, but we have to make the
	// warning go away (and suppressing would suppress for all nested classes too)
	private static final long serialVersionUID = 0;
	}