1/* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18package java.util; 19 20/** 21 * LinkedHashMap is an implementation of {@link Map} that guarantees iteration order. 22 * All optional operations are supported. 23 * 24 * <p>All elements are permitted as keys or values, including null. 25 * 26 * <p>Entries are kept in a doubly-linked list. The iteration order is, by default, the 27 * order in which keys were inserted. Reinserting an already-present key doesn't change the 28 * order. If the three argument constructor is used, and {@code accessOrder} is specified as 29 * {@code true}, the iteration will be in the order that entries were accessed. 30 * The access order is affected by {@code put}, {@code get}, and {@code putAll} operations, 31 * but not by operations on the collection views. 32 * 33 * <p>Note: the implementation of {@code LinkedHashMap} is not synchronized. 34 * If one thread of several threads accessing an instance modifies the map 35 * structurally, access to the map needs to be synchronized. For 36 * insertion-ordered instances a structural modification is an operation that 37 * removes or adds an entry. Access-ordered instances also are structurally 38 * modified by {@code put}, {@code get}, and {@code putAll} since these methods 39 * change the order of the entries. Changes in the value of an entry are not structural changes. 40 * 41 * <p>The {@code Iterator} created by calling the {@code iterator} method 42 * may throw a {@code ConcurrentModificationException} if the map is structurally 43 * changed while an iterator is used to iterate over the elements. Only the 44 * {@code remove} method that is provided by the iterator allows for removal of 45 * elements during iteration. It is not possible to guarantee that this 46 * mechanism works in all cases of unsynchronized concurrent modification. It 47 * should only be used for debugging purposes. 48 */ 49public class LinkedHashMap<K, V> extends HashMap<K, V> { 50 51 /** 52 * A dummy entry in the circular linked list of entries in the map. 53 * The first real entry is header.nxt, and the last is header.prv. 54 * If the map is empty, header.nxt == header && header.prv == header. 55 */ 56 transient LinkedEntry<K, V> header; 57 58 /** 59 * True if access ordered, false if insertion ordered. 60 */ 61 private final boolean accessOrder; 62 63 /** 64 * Constructs a new empty {@code LinkedHashMap} instance. 65 */ 66 public LinkedHashMap() { 67 init(); 68 accessOrder = false; 69 } 70 71 /** 72 * Constructs a new {@code LinkedHashMap} instance with the specified 73 * capacity. 74 * 75 * @param initialCapacity 76 * the initial capacity of this map. 77 * @exception IllegalArgumentException 78 * when the capacity is less than zero. 79 */ 80 public LinkedHashMap(int initialCapacity) { 81 this(initialCapacity, DEFAULT_LOAD_FACTOR); 82 } 83 84 /** 85 * Constructs a new {@code LinkedHashMap} instance with the specified 86 * capacity and load factor. 87 * 88 * @param initialCapacity 89 * the initial capacity of this map. 90 * @param loadFactor 91 * the initial load factor. 92 * @throws IllegalArgumentException 93 * when the capacity is less than zero or the load factor is 94 * less or equal to zero. 95 */ 96 public LinkedHashMap(int initialCapacity, float loadFactor) { 97 this(initialCapacity, loadFactor, false); 98 } 99 100 /** 101 * Constructs a new {@code LinkedHashMap} instance with the specified 102 * capacity, load factor and a flag specifying the ordering behavior. 103 * 104 * @param initialCapacity 105 * the initial capacity of this hash map. 106 * @param loadFactor 107 * the initial load factor. 108 * @param accessOrder 109 * {@code true} if the ordering should be done based on the last 110 * access (from least-recently accessed to most-recently 111 * accessed), and {@code false} if the ordering should be the 112 * order in which the entries were inserted. 113 * @throws IllegalArgumentException 114 * when the capacity is less than zero or the load factor is 115 * less or equal to zero. 116 */ 117 public LinkedHashMap( 118 int initialCapacity, float loadFactor, boolean accessOrder) { 119 super(initialCapacity, loadFactor); 120 init(); 121 this.accessOrder = accessOrder; 122 } 123 124 /** 125 * Constructs a new {@code LinkedHashMap} instance containing the mappings 126 * from the specified map. The order of the elements is preserved. 127 * 128 * @param map 129 * the mappings to add. 130 */ 131 public LinkedHashMap(Map<? extends K, ? extends V> map) { 132 this(capacityForInitSize(map.size())); 133 constructorPutAll(map); 134 } 135 136 @Override void init() { 137 header = new LinkedEntry<K, V>(); 138 } 139 140 /** 141 * LinkedEntry adds nxt/prv double-links to plain HashMapEntry. 142 */ 143 static class LinkedEntry<K, V> extends HashMapEntry<K, V> { 144 LinkedEntry<K, V> nxt; 145 LinkedEntry<K, V> prv; 146 147 /** Create the header entry */ 148 LinkedEntry() { 149 super(null, null, 0, null); 150 nxt = prv = this; 151 } 152 153 /** Create a normal entry */ 154 LinkedEntry(K key, V value, int hash, HashMapEntry<K, V> next, 155 LinkedEntry<K, V> nxt, LinkedEntry<K, V> prv) { 156 super(key, value, hash, next); 157 this.nxt = nxt; 158 this.prv = prv; 159 } 160 } 161 162 /** 163 * Returns the eldest entry in the map, or {@code null} if the map is empty. 164 * @hide 165 */ 166 public Entry<K, V> eldest() { 167 LinkedEntry<K, V> eldest = header.nxt; 168 return eldest != header ? eldest : null; 169 } 170 171 /** 172 * Evicts eldest entry if instructed, creates a new entry and links it in 173 * as head of linked list. This method should call constructorNewEntry 174 * (instead of duplicating code) if the performance of your VM permits. 175 * 176 * <p>It may seem strange that this method is tasked with adding the entry 177 * to the hash table (which is properly the province of our superclass). 178 * The alternative of passing the "next" link in to this method and 179 * returning the newly created element does not work! If we remove an 180 * (eldest) entry that happens to be the first entry in the same bucket 181 * as the newly created entry, the "next" link would become invalid, and 182 * the resulting hash table corrupt. 183 */ 184 @Override void addNewEntry(K key, V value, int hash, int index) { 185 LinkedEntry<K, V> header = this.header; 186 187 // Remove eldest entry if instructed to do so. 188 LinkedEntry<K, V> eldest = header.nxt; 189 if (eldest != header && removeEldestEntry(eldest)) { 190 remove(eldest.key); 191 } 192 193 // Create new entry, link it on to list, and put it into table 194 LinkedEntry<K, V> oldTail = header.prv; 195 LinkedEntry<K, V> newTail = new LinkedEntry<K,V>( 196 key, value, hash, table[index], header, oldTail); 197 table[index] = oldTail.nxt = header.prv = newTail; 198 } 199 200 @Override void addNewEntryForNullKey(V value) { 201 LinkedEntry<K, V> header = this.header; 202 203 // Remove eldest entry if instructed to do so. 204 LinkedEntry<K, V> eldest = header.nxt; 205 if (eldest != header && removeEldestEntry(eldest)) { 206 remove(eldest.key); 207 } 208 209 // Create new entry, link it on to list, and put it into table 210 LinkedEntry<K, V> oldTail = header.prv; 211 LinkedEntry<K, V> newTail = new LinkedEntry<K,V>( 212 null, value, 0, null, header, oldTail); 213 entryForNullKey = oldTail.nxt = header.prv = newTail; 214 } 215 216 /** 217 * As above, but without eviction. 218 */ 219 @Override HashMapEntry<K, V> constructorNewEntry( 220 K key, V value, int hash, HashMapEntry<K, V> next) { 221 LinkedEntry<K, V> header = this.header; 222 LinkedEntry<K, V> oldTail = header.prv; 223 LinkedEntry<K, V> newTail 224 = new LinkedEntry<K,V>(key, value, hash, next, header, oldTail); 225 return oldTail.nxt = header.prv = newTail; 226 } 227 228 /** 229 * Returns the value of the mapping with the specified key. 230 * 231 * @param key 232 * the key. 233 * @return the value of the mapping with the specified key, or {@code null} 234 * if no mapping for the specified key is found. 235 */ 236 @Override public V get(Object key) { 237 /* 238 * This method is overridden to eliminate the need for a polymorphic 239 * invocation in superclass at the expense of code duplication. 240 */ 241 if (key == null) { 242 HashMapEntry<K, V> e = entryForNullKey; 243 if (e == null) 244 return null; 245 if (accessOrder) 246 makeTail((LinkedEntry<K, V>) e); 247 return e.value; 248 } 249 250 // Doug Lea's supplemental secondaryHash function (inlined) 251 int hash = key.hashCode(); 252 hash ^= (hash >>> 20) ^ (hash >>> 12); 253 hash ^= (hash >>> 7) ^ (hash >>> 4); 254 255 HashMapEntry<K, V>[] tab = table; 256 for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)]; 257 e != null; e = e.next) { 258 K eKey = e.key; 259 if (eKey == key || (e.hash == hash && key.equals(eKey))) { 260 if (accessOrder) 261 makeTail((LinkedEntry<K, V>) e); 262 return e.value; 263 } 264 } 265 return null; 266 } 267 268 /** 269 * Relinks the given entry to the tail of the list. Under access ordering, 270 * this method is invoked whenever the value of a pre-existing entry is 271 * read by Map.get or modified by Map.put. 272 */ 273 private void makeTail(LinkedEntry<K, V> e) { 274 // Unlink e 275 e.prv.nxt = e.nxt; 276 e.nxt.prv = e.prv; 277 278 // Relink e as tail 279 LinkedEntry<K, V> header = this.header; 280 LinkedEntry<K, V> oldTail = header.prv; 281 e.nxt = header; 282 e.prv = oldTail; 283 oldTail.nxt = header.prv = e; 284 modCount++; 285 } 286 287 @Override void preModify(HashMapEntry<K, V> e) { 288 if (accessOrder) { 289 makeTail((LinkedEntry<K, V>) e); 290 } 291 } 292 293 @Override void postRemove(HashMapEntry<K, V> e) { 294 LinkedEntry<K, V> le = (LinkedEntry<K, V>) e; 295 le.prv.nxt = le.nxt; 296 le.nxt.prv = le.prv; 297 le.nxt = le.prv = null; // Help the GC (for performance) 298 } 299 300 /** 301 * This override is done for LinkedHashMap performance: iteration is cheaper 302 * via LinkedHashMap nxt links. 303 */ 304 @Override public boolean containsValue(Object value) { 305 if (value == null) { 306 for (LinkedEntry<K, V> header = this.header, e = header.nxt; 307 e != header; e = e.nxt) { 308 if (e.value == null) { 309 return true; 310 } 311 } 312 return false; 313 } 314 315 // value is non-null 316 for (LinkedEntry<K, V> header = this.header, e = header.nxt; 317 e != header; e = e.nxt) { 318 if (value.equals(e.value)) { 319 return true; 320 } 321 } 322 return false; 323 } 324 325 public void clear() { 326 super.clear(); 327 328 // Clear all links to help GC 329 LinkedEntry<K, V> header = this.header; 330 for (LinkedEntry<K, V> e = header.nxt; e != header; ) { 331 LinkedEntry<K, V> nxt = e.nxt; 332 e.nxt = e.prv = null; 333 e = nxt; 334 } 335 336 header.nxt = header.prv = header; 337 } 338 339 private abstract class LinkedHashIterator<T> implements Iterator<T> { 340 LinkedEntry<K, V> next = header.nxt; 341 LinkedEntry<K, V> lastReturned = null; 342 int expectedModCount = modCount; 343 344 public final boolean hasNext() { 345 return next != header; 346 } 347 348 final LinkedEntry<K, V> nextEntry() { 349 if (modCount != expectedModCount) 350 throw new ConcurrentModificationException(); 351 LinkedEntry<K, V> e = next; 352 if (e == header) 353 throw new NoSuchElementException(); 354 next = e.nxt; 355 return lastReturned = e; 356 } 357 358 public final void remove() { 359 if (modCount != expectedModCount) 360 throw new ConcurrentModificationException(); 361 if (lastReturned == null) 362 throw new IllegalStateException(); 363 LinkedHashMap.this.remove(lastReturned.key); 364 lastReturned = null; 365 expectedModCount = modCount; 366 } 367 } 368 369 private final class KeyIterator extends LinkedHashIterator<K> { 370 public final K next() { return nextEntry().key; } 371 } 372 373 private final class ValueIterator extends LinkedHashIterator<V> { 374 public final V next() { return nextEntry().value; } 375 } 376 377 private final class EntryIterator 378 extends LinkedHashIterator<Map.Entry<K, V>> { 379 public final Map.Entry<K, V> next() { return nextEntry(); } 380 } 381 382 // Override view iterator methods to generate correct iteration order 383 @Override Iterator<K> newKeyIterator() { 384 return new KeyIterator(); 385 } 386 @Override Iterator<V> newValueIterator() { 387 return new ValueIterator(); 388 } 389 @Override Iterator<Map.Entry<K, V>> newEntryIterator() { 390 return new EntryIterator(); 391 } 392 393 protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { 394 return false; 395 } 396 397 private static final long serialVersionUID = 3801124242820219131L; 398} 399