/* * Licensed to the Apache Software Foundation (ASF) under one or more * contributor license agreements. See the NOTICE file distributed with * this work for additional information regarding copyright ownership. * The ASF licenses this file to You 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 java.util; /** * LinkedHashMap is an implementation of {@link Map} that guarantees iteration order. * All optional operations are supported. * *

All elements are permitted as keys or values, including null. * *

Entries are kept in a doubly-linked list. The iteration order is, by default, the * order in which keys were inserted. Reinserting an already-present key doesn't change the * order. If the three argument constructor is used, and {@code accessOrder} is specified as * {@code true}, the iteration will be in the order that entries were accessed. * The access order is affected by {@code put}, {@code get}, and {@code putAll} operations, * but not by operations on the collection views. * *

Note: the implementation of {@code LinkedHashMap} is not synchronized. * If one thread of several threads accessing an instance modifies the map * structurally, access to the map needs to be synchronized. For * insertion-ordered instances a structural modification is an operation that * removes or adds an entry. Access-ordered instances also are structurally * modified by {@code put}, {@code get}, and {@code putAll} since these methods * change the order of the entries. Changes in the value of an entry are not structural changes. * *

The {@code Iterator} created by calling the {@code iterator} method * may throw a {@code ConcurrentModificationException} if the map is structurally * changed while an iterator is used to iterate over the elements. Only the * {@code remove} method that is provided by the iterator allows for removal of * elements during iteration. It is not possible to guarantee that this * mechanism works in all cases of unsynchronized concurrent modification. It * should only be used for debugging purposes. */ public class LinkedHashMap extends HashMap { /** * A dummy entry in the circular linked list of entries in the map. * The first real entry is header.nxt, and the last is header.prv. * If the map is empty, header.nxt == header && header.prv == header. */ transient LinkedEntry header; /** * True if access ordered, false if insertion ordered. */ private final boolean accessOrder; /** * Constructs a new empty {@code LinkedHashMap} instance. */ public LinkedHashMap() { init(); accessOrder = false; } /** * Constructs a new {@code LinkedHashMap} instance with the specified * capacity. * * @param initialCapacity * the initial capacity of this map. * @throws IllegalArgumentException * when the capacity is less than zero. */ public LinkedHashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } /** * Constructs a new {@code LinkedHashMap} instance with the specified * capacity and load factor. * * @param initialCapacity * the initial capacity of this map. * @param loadFactor * the initial load factor. * @throws IllegalArgumentException * when the capacity is less than zero or the load factor is * less or equal to zero. */ public LinkedHashMap(int initialCapacity, float loadFactor) { this(initialCapacity, loadFactor, false); } /** * Constructs a new {@code LinkedHashMap} instance with the specified * capacity, load factor and a flag specifying the ordering behavior. * * @param initialCapacity * the initial capacity of this hash map. * @param loadFactor * the initial load factor. * @param accessOrder * {@code true} if the ordering should be done based on the last * access (from least-recently accessed to most-recently * accessed), and {@code false} if the ordering should be the * order in which the entries were inserted. * @throws IllegalArgumentException * when the capacity is less than zero or the load factor is * less or equal to zero. */ public LinkedHashMap( int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); init(); this.accessOrder = accessOrder; } /** * Constructs a new {@code LinkedHashMap} instance containing the mappings * from the specified map. The order of the elements is preserved. * * @param map * the mappings to add. */ public LinkedHashMap(Map map) { this(capacityForInitSize(map.size())); constructorPutAll(map); } @Override void init() { header = new LinkedEntry(); } /** * LinkedEntry adds nxt/prv double-links to plain HashMapEntry. */ static class LinkedEntry extends HashMapEntry { LinkedEntry nxt; LinkedEntry prv; /** Create the header entry */ LinkedEntry() { super(null, null, 0, null); nxt = prv = this; } /** Create a normal entry */ LinkedEntry(K key, V value, int hash, HashMapEntry next, LinkedEntry nxt, LinkedEntry prv) { super(key, value, hash, next); this.nxt = nxt; this.prv = prv; } } /** * Returns the eldest entry in the map, or {@code null} if the map is empty. * @hide */ public Entry eldest() { LinkedEntry eldest = header.nxt; return eldest != header ? eldest : null; } /** * Evicts eldest entry if instructed, creates a new entry and links it in * as head of linked list. This method should call constructorNewEntry * (instead of duplicating code) if the performance of your VM permits. * *

It may seem strange that this method is tasked with adding the entry * to the hash table (which is properly the province of our superclass). * The alternative of passing the "next" link in to this method and * returning the newly created element does not work! If we remove an * (eldest) entry that happens to be the first entry in the same bucket * as the newly created entry, the "next" link would become invalid, and * the resulting hash table corrupt. */ @Override void addNewEntry(K key, V value, int hash, int index) { LinkedEntry header = this.header; // Remove eldest entry if instructed to do so. LinkedEntry eldest = header.nxt; if (eldest != header && removeEldestEntry(eldest)) { remove(eldest.key); } // Create new entry, link it on to list, and put it into table LinkedEntry oldTail = header.prv; LinkedEntry newTail = new LinkedEntry( key, value, hash, table[index], header, oldTail); table[index] = oldTail.nxt = header.prv = newTail; } @Override void addNewEntryForNullKey(V value) { LinkedEntry header = this.header; // Remove eldest entry if instructed to do so. LinkedEntry eldest = header.nxt; if (eldest != header && removeEldestEntry(eldest)) { remove(eldest.key); } // Create new entry, link it on to list, and put it into table LinkedEntry oldTail = header.prv; LinkedEntry newTail = new LinkedEntry( null, value, 0, null, header, oldTail); entryForNullKey = oldTail.nxt = header.prv = newTail; } /** * As above, but without eviction. */ @Override HashMapEntry constructorNewEntry( K key, V value, int hash, HashMapEntry next) { LinkedEntry header = this.header; LinkedEntry oldTail = header.prv; LinkedEntry newTail = new LinkedEntry(key, value, hash, next, header, oldTail); return oldTail.nxt = header.prv = newTail; } /** * Returns the value of the mapping with the specified key. * * @param key * the key. * @return the value of the mapping with the specified key, or {@code null} * if no mapping for the specified key is found. */ @Override public V get(Object key) { /* * This method is overridden to eliminate the need for a polymorphic * invocation in superclass at the expense of code duplication. */ if (key == null) { HashMapEntry e = entryForNullKey; if (e == null) return null; if (accessOrder) makeTail((LinkedEntry) e); return e.value; } int hash = Collections.secondaryHash(key); HashMapEntry[] tab = table; for (HashMapEntry e = tab[hash & (tab.length - 1)]; e != null; e = e.next) { K eKey = e.key; if (eKey == key || (e.hash == hash && key.equals(eKey))) { if (accessOrder) makeTail((LinkedEntry) e); return e.value; } } return null; } /** * Relinks the given entry to the tail of the list. Under access ordering, * this method is invoked whenever the value of a pre-existing entry is * read by Map.get or modified by Map.put. */ private void makeTail(LinkedEntry e) { // Unlink e e.prv.nxt = e.nxt; e.nxt.prv = e.prv; // Relink e as tail LinkedEntry header = this.header; LinkedEntry oldTail = header.prv; e.nxt = header; e.prv = oldTail; oldTail.nxt = header.prv = e; modCount++; } @Override void preModify(HashMapEntry e) { if (accessOrder) { makeTail((LinkedEntry) e); } } @Override void postRemove(HashMapEntry e) { LinkedEntry le = (LinkedEntry) e; le.prv.nxt = le.nxt; le.nxt.prv = le.prv; le.nxt = le.prv = null; // Help the GC (for performance) } /** * This override is done for LinkedHashMap performance: iteration is cheaper * via LinkedHashMap nxt links. */ @Override public boolean containsValue(Object value) { if (value == null) { for (LinkedEntry header = this.header, e = header.nxt; e != header; e = e.nxt) { if (e.value == null) { return true; } } return false; } // value is non-null for (LinkedEntry header = this.header, e = header.nxt; e != header; e = e.nxt) { if (value.equals(e.value)) { return true; } } return false; } public void clear() { super.clear(); // Clear all links to help GC LinkedEntry header = this.header; for (LinkedEntry e = header.nxt; e != header; ) { LinkedEntry nxt = e.nxt; e.nxt = e.prv = null; e = nxt; } header.nxt = header.prv = header; } private abstract class LinkedHashIterator implements Iterator { LinkedEntry next = header.nxt; LinkedEntry lastReturned = null; int expectedModCount = modCount; public final boolean hasNext() { return next != header; } final LinkedEntry nextEntry() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); LinkedEntry e = next; if (e == header) throw new NoSuchElementException(); next = e.nxt; return lastReturned = e; } public final void remove() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (lastReturned == null) throw new IllegalStateException(); LinkedHashMap.this.remove(lastReturned.key); lastReturned = null; expectedModCount = modCount; } } private final class KeyIterator extends LinkedHashIterator { public final K next() { return nextEntry().key; } } private final class ValueIterator extends LinkedHashIterator { public final V next() { return nextEntry().value; } } private final class EntryIterator extends LinkedHashIterator> { public final Map.Entry next() { return nextEntry(); } } // Override view iterator methods to generate correct iteration order @Override Iterator newKeyIterator() { return new KeyIterator(); } @Override Iterator newValueIterator() { return new ValueIterator(); } @Override Iterator> newEntryIterator() { return new EntryIterator(); } protected boolean removeEldestEntry(Map.Entry eldest) { return false; } private static final long serialVersionUID = 3801124242820219131L; }