2362N/A * Copyright (c) 1998, 2000, Oracle and/or its affiliates. All rights reserved. 0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 0N/A * This code is free software; you can redistribute it and/or modify it 0N/A * under the terms of the GNU General Public License version 2 only, as 2362N/A * published by the Free Software Foundation. Oracle designates this 0N/A * particular file as subject to the "Classpath" exception as provided 2362N/A * by Oracle in the LICENSE file that accompanied this code. 0N/A * This code is distributed in the hope that it will be useful, but WITHOUT 0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 0N/A * version 2 for more details (a copy is included in the LICENSE file that 0N/A * accompanied this code). 0N/A * You should have received a copy of the GNU General Public License version 0N/A * 2 along with this work; if not, write to the Free Software Foundation, 0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 2362N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 2362N/A * or visit www.oracle.com if you need additional information or have any 0N/A * Hash table based implementation of the Map interface. This implementation 0N/A * provides all of the optional Map operations, and permits null values and 0N/A * the null key. (HashMap is roughly equivalent to Hashtable, except that it 0N/A * is unsynchronized and permits nulls.) In addition, elements in the map are 0N/A * ordered and doubly linked together. 0N/A * This implementation provides constant-time performance for the basic 0N/A * operations (get and put), assuming the the hash function disperses the 0N/A * elements properly among the buckets. Iteration over Collection views 0N/A * requires time proportional to its size (the number of key-value mappings) 0N/A * and returns elements in the order they are linked. In a HashMap the 0N/A * iteration would require time proportional to the capacity of the map 0N/A * plus the map size. 0N/A * An instance of LinkedHashMap has two parameters that affect its efficiency: 0N/A * its <i>capacity</i> and its <i>load factor</i>. The load factor should be 0N/A * between 0.0 and 1.0. When the number of mappings in the LinkedHashMap exceeds 0N/A * the product of the load factor and the current capacity, the capacity is 0N/A * increased by calling the rehash method which requires time proportional 0N/A * to the number of key-value mappings in the map. Larger load factors 0N/A * use memory more efficiently, at the expense of larger expected time per 0N/A * If many mappings are to be stored in a LinkedHashMap, creating it with a 0N/A * sufficiently large capacity will allow the mappings to be stored more 0N/A * efficiently than letting it perform automatic rehashing as needed to grow 0N/A * <strong>Note that this implementation is not synchronized.</strong> If 0N/A * multiple threads access a LinkedHashMap concurrently, and at least one of the 0N/A * threads modifies the LinkedHashMap structurally, it <em>must</em> be 0N/A * synchronized externally. (A structural modification is any operation that 0N/A * adds or deletes one or more mappings; merely changing the value associated 0N/A * with a key that is already contained in the Table is not a structural 0N/A * modification.) This is typically accomplished by synchronizing on some 0N/A * object that naturally encapsulates the LinkedHashMap. If no such object 0N/A * exists, the LinkedHashMap should be "wrapped" using the 0N/A * Collections.synchronizedSet method. This is best done at creation time, to 0N/A * prevent accidental unsynchronized access to the LinkedHashMap: 0N/A * Map m = Collections.synchronizedMap(new LinkedHashMap(...)); 0N/A * The Iterators returned by the iterator methods of the Collections returned 0N/A * by all of LinkedHashMap's "collection view methods" are <em>fail-fast</em>: 0N/A * if the LinkedHashMap is structurally modified at any time after the Iterator 0N/A * is created, in any way except through the Iterator's own remove or add 0N/A * methods, the Iterator will throw a ConcurrentModificationException. Thus, 0N/A * in the face of concurrent modification, the Iterator fails quickly and 0N/A * cleanly, rather than risking arbitrary, non-deterministic behavior at an 0N/A * undetermined time in the future. 0N/A * @author Josh Bloch 0N/A * @author Arthur van Hoff 0N/A * @author Zhenghua Li 0N/A * @see Object#hashCode() 0N/A * @see java.util.Collection 0N/A * @see java.util.Map 0N/A * @see java.util.TreeMap 0N/A * @see java.util.Hashtable 0N/A * @see java.util.HashMap 0N/A * The hash table data. 0N/A * The head of the double linked list. 0N/A * The total number of mappings in the hash table. 0N/A * Rehashes the table when count exceeds this threshold. 0N/A * The load factor for the LinkedHashMap. 0N/A * The number of times this LinkedHashMap has been structurally modified 0N/A * Structural modifications are those that change the number of mappings in 0N/A * the LinkedHashMap or otherwise modify its internal structure (e.g., 0N/A * rehash). This field is used to make iterators on Collection-views of 0N/A * the LinkedHashMap fail-fast. (See ConcurrentModificationException). 0N/A * Constructs a new, empty LinkedHashMap with the specified initial 0N/A * capacity and the specified load factor. 0N/A * @param initialCapacity the initial capacity of the LinkedHashMap. 0N/A * @param loadFactor a number between 0.0 and 1.0. 0N/A * @exception IllegalArgumentException if the initial capacity is less 0N/A * than or equal to zero, or if the load factor is less than 0N/A * Constructs a new, empty LinkedHashMap with the specified initial capacity 0N/A * and default load factor. 0N/A * @param initialCapacity the initial capacity of the LinkedHashMap. 0N/A * Constructs a new, empty LinkedHashMap with a default capacity and load 0N/A * Constructs a new LinkedHashMap with the same mappings as the given 0N/A * Map. The LinkedHashMap is created with a capacity of thrice the number 0N/A * of mappings in the given Map or 11 (whichever is greater), and a 0N/A * default load factor. 0N/A * Returns the number of key-value mappings in this Map. 0N/A * Returns true if this Map contains no key-value mappings. 0N/A * Returns true if this LinkedHashMap maps one or more keys to the specified 0N/A * @param value value whose presence in this Map is to be tested. 0N/A * Returns true if this LinkedHashMap contains a mapping for the specified 0N/A * @param key key whose presence in this Map is to be tested. 0N/A * Returns the value to which this LinkedHashMap maps the specified key. 0N/A * Returns null if the LinkedHashMap contains no mapping for this key. 0N/A * A return value of null does not <em>necessarily</em> indicate that the 0N/A * LinkedHashMap contains no mapping for the key; it's also possible that 0N/A * the LinkedHashMap explicitly maps the key to null. The containsKey 0N/A * operation may be used to distinguish these two cases. 0N/A * @param key key whose associated value is to be returned. 0N/A * Returns the entry associated with the specified key in the LinkedHashMap. 0N/A * Returns null if the LinkedHashMap contains no mapping for this key. 0N/A * Rehashes the contents of the LinkedHashMap into a LinkedHashMap with a 0N/A * larger capacity. This method is called automatically when the 0N/A * number of keys in the LinkedHashMap exceeds this LinkedHashMap's capacity 0N/A * Remove an entry from the linked list. 0N/A * Add the specified entry before the specified existing entry to 0N/A * Returns the position of the mapping for the specified key 0N/A * in the ordered map. 0N/A * @param key the specified key. 0N/A * @return index of the key mapping. 0N/A * Associates the specified value with the specified key in this 0N/A * LinkedHashMap. If the LinkedHashMap previously contained a mapping for 0N/A * this key, the old value is replaced and the position of this mapping 0N/A * entry in the double linked list remains the same. Otherwise, a new 0N/A * mapping entry is created and inserted into the list before the specified 0N/A * existing mapping entry. The method returns the previous value associated 0N/A * with the specified key, or null if there was no mapping for key. A null 0N/A * return can also indicate that the LinkedHashMap previously associated 0N/A * null with the specified key. 0N/A // Makes sure the key is not already in the LinkedHashMap. 0N/A // Rehash the table if the threshold is exceeded 0N/A // Creates the new entry. 0N/A * Associates the specified value with the specified key in this 0N/A * LinkedHashMap and position the mapping at the specified index. 0N/A * If the LinkedHashMap previously contained a mapping for this key, 0N/A * the old value is replaced and the position of this mapping entry 0N/A * in the double linked list remains the same. Otherwise, a new mapping 0N/A * entry is created and inserted into the list at the specified 0N/A * @param index the position to put the key-value mapping. 0N/A * @param key key with which the specified value is to be associated. 0N/A * @param value value to be associated with the specified key. 0N/A * @return previous value associated with specified key, or null if there 0N/A * was no mapping for key. A null return can also indicate that 0N/A * the LinkedHashMap previously associated null with the specified 0N/A * Associates the specified value with the specified key in this 0N/A * LinkedHashMap. If the LinkedHashMap previously contained a mapping for 0N/A * this key, the old value is replaced. The mapping entry is also appended 0N/A * to the end of the ordered linked list. 0N/A * @param key key with which the specified value is to be associated. 0N/A * @param value value to be associated with the specified key. 0N/A * @return previous value associated with specified key, or null if there 0N/A * was no mapping for key. A null return can also indicate that 0N/A * the LinkedHashMap previously associated null with the specified 0N/A * Removes the mapping for this key from this LinkedHashMap if present. 0N/A * The mapping would also be removed from the double linked list. 0N/A * @param key key whose mapping is to be removed from the Map. 0N/A * @return previous value associated with specified key, or null if there 0N/A * was no mapping for key. A null return can also indicate that 0N/A * the LinkedHashMap previously associated null with the specified 0N/A * Copies all of the mappings from the specified Map to this LinkedHashMap 0N/A * These mappings will replace any mappings that this LinkedHashMap had for 0N/A * any of the keys currently in the specified Map. 0N/A * @param t Mappings to be stored in this Map. 0N/A * Removes all mappings from this LinkedHashMap. 0N/A * Returns a shallow copy of this LinkedHashMap. The keys and values 0N/A * themselves are not cloned. 0N/A * Returns a Set view of the keys contained in this LinkedHashMap. The Set 0N/A * is backed by the LinkedHashMap, so changes to the LinkedHashMap are 0N/A * reflected in the Set, and vice-versa. The Set supports element removal, 0N/A * which removes the corresponding mapping from the LinkedHashMap, via the 0N/A * Iterator.remove, Set.remove, removeAll retainAll, and clear operations. 0N/A * It does not support the add or addAll operations. 0N/A * Returns a Collection view of the values contained in this LinkedHashMap. 0N/A * The Collection is backed by the LinkedHashMap, so changes to the 0N/A * LinkedHashMap are reflected in the Collection, and vice-versa. The 0N/A * Collection supports element removal, which removes the corresponding 0N/A * mapping from the LinkedHashMap, via the Iterator.remove, 0N/A * Collection.remove, removeAll, retainAll and clear operations. It does 0N/A * not support the add or addAll operations. 0N/A * Returns a Collection view of the mappings contained in this 0N/A * LinkedHashMap. Each element in the returned collection is a Map.Entry. 0N/A * The Collection is backed by the LinkedHashMap, so changes to the 0N/A * LinkedHashMap are reflected in the Collection, and vice-versa. The 0N/A * Collection supports element removal, which removes the corresponding 0N/A * mapping from the LinkedHashMap, via the Iterator.remove, 0N/A * Collection.remove, removeAll, retainAll and clear operations. It does 0N/A * not support the add or addAll operations. 0N/A * @see java.util.Map.Entry 0N/A * Compares the specified Object with this Map for equality. 0N/A * Returns true if the given object is also a LinkedHashMap and the two 0N/A * Maps represent the same mappings in the same order. More formally, 0N/A * two Maps <code>t1</code> and <code>t2</code> represent the same mappings 0N/A * if <code>t1.keySet().equals(t2.keySet())</code> and for every 0N/A * key <code>k</code> in <code>t1.keySet()</code>, <code> 0N/A * (t1.get(k)==null ? t2.get(k)==null : t1.get(k).equals(t2.get(k))) 0N/A * This implementation first checks if the specified Object is this Map; 0N/A * if so it returns true. Then, it checks if the specified Object is 0N/A * a Map whose size is identical to the size of this Set; if not, it 0N/A * it returns false. If so, it iterates over this Map and the specified 0N/A * Map's entrySet() Collection, and checks that the specified Map contains 0N/A * each mapping that this Map contains at the same position. If the 0N/A * specified Map fails to contain such a mapping in the right order, false 0N/A * is returned. If the iteration completes, true is returned. 0N/A * @param o Object to be compared for equality with this Map. 0N/A * @return true if the specified Object is equal to this Map. 0N/A * LinkedHashMap collision list entry. 0N/A // These fields comprise the doubly linked list that is used for 0N/A // Types of Iterators 0N/A * The modCount value that the iterator believes that the backing 0N/A * List should have. If this expectation is violated, the iterator 0N/A * has detected concurrent modification. 0N/A * Save the state of the LinkedHashMap to a stream (i.e., serialize it). 0N/A * The objects will be written out in the order they are linked 0N/A // Write out the threshold, loadfactor, and any hidden stuff 0N/A // Write out number of buckets 0N/A // Write out size (number of Mappings) 0N/A // Write out keys and values (alternating) 0N/A * Reconstitute the LinkedHashMap from a stream (i.e., deserialize it). 0N/A // Read in the threshold, loadfactor, and any hidden stuff 0N/A // Read in number of buckets and allocate the bucket array; 0N/A // Read in size (number of Mappings) 0N/A // Read the keys and values, and put the mappings in the LinkedHashMap