Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
   * 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
  * 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.
 import static;
Implementation of ImmutableMap with two or more entries.

Jesse Wilson
Kevin Bourrillion
Gregory Kick
 @GwtCompatible(serializable = true, emulated = true)
 final class RegularImmutableMap<K, V> extends ImmutableMap<K, V> {
   // entries in insertion order
   private final transient LinkedEntry<K, V>[] entries;
   // array of linked lists of entries
   private final transient LinkedEntry<K, V>[] table;
   // 'and' with an int to get a table index
   private final transient int mask;
   private final transient int keySetHashCode;
   // TODO(gak): investigate avoiding the creation of ImmutableEntries since we
   // re-copy them anyway.
   RegularImmutableMap(Entry<?, ?>... immutableEntries) {
     int size = immutableEntries.length;
      = createEntryArray(size);
     int tableSize = chooseTableSize(size);
      = createEntryArray(tableSize);
      = tableSize - 1;
     int keySetHashCodeMutable = 0;
     for (int entryIndex = 0; entryIndex < sizeentryIndex++) {
       // each of our 6 callers carefully put only Entry<K, V>s into the array!
       Entry<K, V> entry = (Entry<K, V>) immutableEntries[entryIndex];
       K key = entry.getKey();
       int keyHashCode = key.hashCode();
       keySetHashCodeMutable += keyHashCode;
       int tableIndex = Hashing.smear(keyHashCode) & ;
       @Nullable LinkedEntry<K, V> existing = [tableIndex];
       // prepend, not append, so the entries can be immutable
       LinkedEntry<K, V> linkedEntry =
           newLinkedEntry(keyentry.getValue(), existing);
       [tableIndex] = linkedEntry;
       [entryIndex] = linkedEntry;
       while (existing != null) {
         checkArgument(!key.equals(existing.getKey()), "duplicate key: %s"key);
         existing =;
      = keySetHashCodeMutable;
   private static int chooseTableSize(int size) {
     // least power of 2 greater than size
     int tableSize = Integer.highestOneBit(size) << 1;
     checkArgument(tableSize > 0, "table too large: %s"size);
     return tableSize;

Creates a RegularImmutableMap.LinkedEntry array to hold parameterized entries. The result must never be upcast back to LinkedEntry[] (or Object[], etc.), or allowed to escape the class.
   @SuppressWarnings("unchecked"// Safe as long as the javadocs are followed
   private LinkedEntry<K, V>[] createEntryArray(int size) {
     return new LinkedEntry[size];
   private static <K, V> LinkedEntry<K, V> newLinkedEntry(K key, V value,
       @Nullable LinkedEntry<K, V> next) {
     return (next == null)
         ? new TerminalEntry<K, V>(keyvalue)
         : new NonTerminalEntry<K, V>(keyvaluenext);
  private interface LinkedEntry<K, V> extends Entry<K, V> {
Returns the next entry in the list or null if none exists.
    @Nullable LinkedEntry<K, V> next();

LinkedEntry implementation that has a next value.
  @SuppressWarnings("serial"// this class is never serialized
  private static final class NonTerminalEntry<K, V>
      extends ImmutableEntry<K, V> implements LinkedEntry<K, V> {
    final LinkedEntry<K, V> next;
    NonTerminalEntry(K key, V valueLinkedEntry<K, V> next) {
      this. = next;
    @Override public LinkedEntry<K, V> next() {
      return ;

LinkedEntry implementation that serves as the last entry in the list. I.e. no next entry
  @SuppressWarnings("serial"// this class is never serialized
  private static final class TerminalEntry<K, V> extends ImmutableEntry<K, V>
      implements LinkedEntry<K, V> {
    TerminalEntry(K key, V value) {
    @Nullable @Override public LinkedEntry<K, V> next() {
      return null;
  @Override public V get(@Nullable Object key) {
    if (key == null) {
      return null;
    int index = Hashing.smear(key.hashCode()) & ;
    for (LinkedEntry<K, V> entry = [index];
        entry != null;
        entry = {
      K candidateKey = entry.getKey();
       * Assume that equals uses the == optimization when appropriate, and that
       * it would check hash codes as an optimization when appropriate. If we
       * did these things, it would just make things worse for the most
       * performance-conscious users.
      if (key.equals(candidateKey)) {
        return entry.getValue();
    return null;
  public int size() {
    return .;
  @Override public boolean isEmpty() {
    return false;
  @Override public boolean containsValue(@Nullable Object value) {
    if (value == null) {
      return false;
    for (Entry<K, V> entry : ) {
      if (entry.getValue().equals(value)) {
        return true;
    return false;
  @Override boolean isPartialView() {
    return false;
    return new EntrySet();
  @SuppressWarnings("serial"// uses writeReplace(), not default serialization
  private class EntrySet extends ImmutableMap<K, V>.EntrySet {
    public UnmodifiableIterator<Entry<K, V>> iterator() {
      return asList().iterator();
    ImmutableList<Entry<K, V>> createAsList() {
      // TODO(user): make this delegate contains calls to the EntrySet
      return new RegularImmutableList<Entry<K, V>>();
    return new KeySet();
  @Override public String toString() {
    StringBuilder result
        = Collections2.newStringBuilderForCollection(size()).append('{');
    return result.append('}').toString();
  // 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;
New to GrepCode? Check out our FAQ X