RegularImmutableMap.java revision 7dd252788645e940eada959bdde927426e2531c9
1/* 2 * Copyright (C) 2008 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package com.google.common.collect; 18 19import static com.google.common.base.Preconditions.checkArgument; 20 21import com.google.common.annotations.GwtCompatible; 22 23import javax.annotation.Nullable; 24import javax.annotation.concurrent.Immutable; 25 26/** 27 * Implementation of {@link ImmutableMap} with two or more entries. 28 * 29 * @author Jesse Wilson 30 * @author Kevin Bourrillion 31 * @author Gregory Kick 32 */ 33@GwtCompatible(serializable = true, emulated = true) 34final class RegularImmutableMap<K, V> extends ImmutableMap<K, V> { 35 36 // entries in insertion order 37 private final transient LinkedEntry<K, V>[] entries; 38 // array of linked lists of entries 39 private final transient LinkedEntry<K, V>[] table; 40 // 'and' with an int to get a table index 41 private final transient int mask; 42 43 // TODO(gak): investigate avoiding the creation of ImmutableEntries since we 44 // re-copy them anyway. 45 RegularImmutableMap(Entry<?, ?>... immutableEntries) { 46 int size = immutableEntries.length; 47 entries = createEntryArray(size); 48 49 int tableSize = Hashing.closedTableSize(size, MAX_LOAD_FACTOR); 50 table = createEntryArray(tableSize); 51 mask = tableSize - 1; 52 53 for (int entryIndex = 0; entryIndex < size; entryIndex++) { 54 // each of our 6 callers carefully put only Entry<K, V>s into the array! 55 @SuppressWarnings("unchecked") 56 Entry<K, V> entry = (Entry<K, V>) immutableEntries[entryIndex]; 57 K key = entry.getKey(); 58 int keyHashCode = key.hashCode(); 59 int tableIndex = Hashing.smear(keyHashCode) & mask; 60 @Nullable 61 LinkedEntry<K, V> existing = table[tableIndex]; 62 // prepend, not append, so the entries can be immutable 63 LinkedEntry<K, V> linkedEntry = newLinkedEntry(key, entry.getValue(), existing); 64 table[tableIndex] = linkedEntry; 65 entries[entryIndex] = linkedEntry; 66 while (existing != null) { 67 checkArgument(!key.equals(existing.getKey()), "duplicate key: %s", key); 68 existing = existing.next(); 69 } 70 } 71 } 72 73 /** 74 * Closed addressing tends to perform well even with high load factors. 75 * Being conservative here ensures that the table is still likely to be 76 * relatively sparse (hence it misses fast) while saving space. 77 */ 78 private static final double MAX_LOAD_FACTOR = 1.2; 79 80 /** 81 * Creates a {@link LinkedEntry} array to hold parameterized entries. The 82 * result must never be upcast back to LinkedEntry[] (or Object[], etc.), or 83 * allowed to escape the class. 84 */ 85 @SuppressWarnings("unchecked") 86 // Safe as long as the javadocs are followed 87 private LinkedEntry<K, V>[] createEntryArray(int size) { 88 return new LinkedEntry[size]; 89 } 90 91 private static <K, V> LinkedEntry<K, V> newLinkedEntry(K key, V value, 92 @Nullable LinkedEntry<K, V> next) { 93 return (next == null) ? new TerminalEntry<K, V>(key, value) : new NonTerminalEntry<K, V>(key, 94 value, next); 95 } 96 97 private interface LinkedEntry<K, V> extends Entry<K, V> { 98 /** Returns the next entry in the list or {@code null} if none exists. */ 99 @Nullable 100 LinkedEntry<K, V> next(); 101 } 102 103 /** {@code LinkedEntry} implementation that has a next value. */ 104 @Immutable 105 @SuppressWarnings("serial") 106 // this class is never serialized 107 private static final class NonTerminalEntry<K, V> extends ImmutableEntry<K, V> implements 108 LinkedEntry<K, V> { 109 final LinkedEntry<K, V> next; 110 111 NonTerminalEntry(K key, V value, LinkedEntry<K, V> next) { 112 super(key, value); 113 this.next = next; 114 } 115 116 public LinkedEntry<K, V> next() { 117 return next; 118 } 119 } 120 121 /** 122 * {@code LinkedEntry} implementation that serves as the last entry in the 123 * list. I.e. no next entry 124 */ 125 @Immutable 126 @SuppressWarnings("serial") 127 // this class is never serialized 128 private static final class TerminalEntry<K, V> extends ImmutableEntry<K, V> implements 129 LinkedEntry<K, V> { 130 TerminalEntry(K key, V value) { 131 super(key, value); 132 } 133 134 @Nullable 135 public LinkedEntry<K, V> next() { 136 return null; 137 } 138 } 139 140 @Override 141 public V get(@Nullable Object key) { 142 if (key == null) { 143 return null; 144 } 145 int index = Hashing.smear(key.hashCode()) & mask; 146 for (LinkedEntry<K, V> entry = table[index]; entry != null; entry = entry.next()) { 147 K candidateKey = entry.getKey(); 148 149 /* 150 * Assume that equals uses the == optimization when appropriate, and that 151 * it would check hash codes as an optimization when appropriate. If we 152 * did these things, it would just make things worse for the most 153 * performance-conscious users. 154 */ 155 if (key.equals(candidateKey)) { 156 return entry.getValue(); 157 } 158 } 159 return null; 160 } 161 162 public int size() { 163 return entries.length; 164 } 165 166 @Override 167 public boolean isEmpty() { 168 return false; 169 } 170 171 @Override 172 public boolean containsValue(@Nullable Object value) { 173 if (value == null) { 174 return false; 175 } 176 for (Entry<K, V> entry : entries) { 177 if (entry.getValue().equals(value)) { 178 return true; 179 } 180 } 181 return false; 182 } 183 184 @Override 185 boolean isPartialView() { 186 return false; 187 } 188 189 @Override 190 ImmutableSet<Entry<K, V>> createEntrySet() { 191 return new EntrySet(); 192 } 193 194 @SuppressWarnings("serial") 195 // uses writeReplace(), not default serialization 196 private class EntrySet extends ImmutableMapEntrySet<K, V> { 197 @Override 198 ImmutableMap<K, V> map() { 199 return RegularImmutableMap.this; 200 } 201 202 @Override 203 public UnmodifiableIterator<Entry<K, V>> iterator() { 204 return asList().iterator(); 205 } 206 207 @Override 208 ImmutableList<Entry<K, V>> createAsList() { 209 return new RegularImmutableAsList<Entry<K, V>>(this, entries); 210 } 211 } 212 213 // This class is never actually serialized directly, but we have to make the 214 // warning go away (and suppressing would suppress for all nested classes too) 215 private static final long serialVersionUID = 0; 216} 217