/* * @(#)HashMap.java	1.45 06/10/10 * * Copyright  1990-2008 Sun Microsystems, Inc. All Rights Reserved.   * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER   *    * This program is free software; you can redistribute it and/or   * modify it under the terms of the GNU General Public License version   * 2 only, as published by the Free Software Foundation.    *    * This program is distributed in the hope that it will be useful, but   * WITHOUT ANY WARRANTY; without even the implied warranty of   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU   * General Public License version 2 for more details (a copy is   * included at /legal/license.txt).    *    * You should have received a copy of the GNU General Public License   * version 2 along with this work; if not, write to the Free Software   * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA   * 02110-1301 USA    *    * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa   * Clara, CA 95054 or visit www.sun.com if you need additional   * information or have any questions.  * */package java.util;import  java.io.*;/** * Hash table based implementation of the <tt>Map</tt> interface.  This * implementation provides all of the optional map operations, and permits * <tt>null</tt> values and the <tt>null</tt> key.  (The <tt>HashMap</tt> * class is roughly equivalent to <tt>Hashtable</tt>, except that it is * unsynchronized and permits nulls.)  This class makes no guarantees as to * the order of the map; in particular, it does not guarantee that the order * will remain constant over time. * * <p>This implementation provides constant-time performance for the basic * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function * disperses the elements properly among the buckets.  Iteration over * collection views requires time proportional to the "capacity" of the * <tt>HashMap</tt> instance (the number of buckets) plus its size (the number * of key-value mappings).  Thus, it's very important not to set the initial * capacity too high (or the load factor too low) if iteration performance is * important. * * <p>An instance of <tt>HashMap</tt> has two parameters that affect its * performance: <i>initial capacity</i> and <i>load factor</i>.  The * <i>capacity</i> is the number of buckets in the hash table, and the initial * capacity is simply the capacity at the time the hash table is created.  The * <i>load factor</i> is a measure of how full the hash table is allowed to * get before its capacity is automatically increased.  When the number of * entries in the hash table exceeds the product of the load factor and the * current capacity, the capacity is roughly doubled by calling the * <tt>rehash</tt> method. * * <p>As a general rule, the default load factor (.75) offers a good tradeoff * between time and space costs.  Higher values decrease the space overhead * but increase the lookup cost (reflected in most of the operations of the * <tt>HashMap</tt> class, including <tt>get</tt> and <tt>put</tt>).  The * expected number of entries in the map and its load factor should be taken * into account when setting its initial capacity, so as to minimize the * number of <tt>rehash</tt> operations.  If the initial capacity is greater * than the maximum number of entries divided by the load factor, no * <tt>rehash</tt> operations will ever occur. * * <p>If many mappings are to be stored in a <tt>HashMap</tt> instance, * creating it with a sufficiently large capacity will allow the mappings to * be stored more efficiently than letting it perform automatic rehashing as * needed to grow the table. * * <p><b>Note that this implementation is not synchronized.</b> If multiple * threads access this map concurrently, and at least one of the threads * modifies the map structurally, it <i>must</i> be synchronized externally. * (A structural modification is any operation that adds or deletes one or * more mappings; merely changing the value associated with a key that an * instance already contains is not a structural modification.)  This is * typically accomplished by synchronizing on some object that naturally * encapsulates the map.  If no such object exists, the map should be * "wrapped" using the <tt>Collections.synchronizedMap</tt> method.  This is * best done at creation time, to prevent accidental unsynchronized access to * the map: <pre> Map m = Collections.synchronizedMap(new HashMap(...)); * </pre> * * <p>The iterators returned by all of this class's "collection view methods" * are <i>fail-fast</i>: if the map is structurally modified at any time after * the iterator is created, in any way except through the iterator's own * <tt>remove</tt> or <tt>add</tt> methods, the iterator will throw a * <tt>ConcurrentModificationException</tt>.  Thus, in the face of concurrent * modification, the iterator fails quickly and cleanly, rather than risking * arbitrary, non-deterministic behavior at an undetermined time in the * future. * * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed * as it is, generally speaking, impossible to make any hard guarantees in the * presence of unsynchronized concurrent modification.  Fail-fast iterators * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.  * Therefore, it would be wrong to write a program that depended on this * exception for its correctness: <i>the fail-fast behavior of iterators * should be used only to detect bugs.</i> * * <p>This class is a member of the  * <a href="{@docRoot}/../guide/collections/index.html"> * Java Collections Framework</a>. * * @author  Doug Lea * @author  Josh Bloch * @author  Arthur van Hoff * @version 1.38, 02/02/00 * @see     Object#hashCode() * @see     Collection * @see	    Map * @see	    TreeMap * @see	    Hashtable * @since   1.2 */public class HashMap extends AbstractMap implements Map, Cloneable,    Serializable{    /**     * The default initial capacity - MUST be a power of two.     */    static final int DEFAULT_INITIAL_CAPACITY = 16;    /**     * The maximum capacity, used if a higher value is implicitly specified     * by either of the constructors with arguments.     * MUST be a power of two <= 1<<30.     */    static final int MAXIMUM_CAPACITY = 1 << 30;    /**     * The load factor used when none specified in constructor.     **/    static final float DEFAULT_LOAD_FACTOR = 0.75f;    /**     * The table, resized as necessary. Length MUST Always be a power of two.     */    transient Entry[] table;    /**     * The number of key-value mappings contained in this identity hash map.     */    transient int size;      /**     * The next size value at which to resize (capacity * load factor).     * @serial     */    int threshold;      /**     * The load factor for the hash table.     *     * @serial     */    final float loadFactor;    /**     * The number of times this HashMap has been structurally modified     * Structural modifications are those that change the number of mappings in     * the HashMap or otherwise modify its internal structure (e.g.,     * rehash).  This field is used to make iterators on Collection-views of     * the HashMap fail-fast.  (See ConcurrentModificationException).     */    transient volatile int modCount;    /**     * Constructs an empty <tt>HashMap</tt> with the specified initial     * capacity and load factor.     *     * @param  initialCapacity The initial capacity.     * @param  loadFactor      The load factor.     * @throws IllegalArgumentException if the initial capacity is negative     *         or the load factor is nonpositive.     */    public HashMap(int initialCapacity, float loadFactor) {        if (initialCapacity < 0)            throw new IllegalArgumentException("Illegal initial capacity: " +                                               initialCapacity);        if (initialCapacity > MAXIMUM_CAPACITY)            initialCapacity = MAXIMUM_CAPACITY;        if (loadFactor <= 0 || Float.isNaN(loadFactor))            throw new IllegalArgumentException("Illegal load factor: " +                                               loadFactor);        // Find a power of 2 >= initialCapacity        int capacity = 1;        while (capacity < initialCapacity)             capacity <<= 1;            this.loadFactor = loadFactor;        threshold = (int)(capacity * loadFactor);        table = new Entry[capacity];        init();    }      /**     * Constructs an empty <tt>HashMap</tt> with the specified initial     * capacity and the default load factor (0.75).     *     * @param  initialCapacity the initial capacity.     * @throws IllegalArgumentException if the initial capacity is negative.     */    public HashMap(int initialCapacity) {        this(initialCapacity, DEFAULT_LOAD_FACTOR);    }    /**     * Constructs an empty <tt>HashMap</tt> with the default initial capacity     * (16) and the default load factor (0.75).     */    public HashMap() {        this.loadFactor = DEFAULT_LOAD_FACTOR;        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);        table = new Entry[DEFAULT_INITIAL_CAPACITY];        init();    }    /**     * Constructs a new <tt>HashMap</tt> with the same mappings as the     * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with     * default load factor (0.75) and an initial capacity sufficient to     * hold the mappings in the specified <tt>Map</tt>.     *     * @param   m the map whose mappings are to be placed in this map.     * @throws  NullPointerException if the specified map is null.     */    public HashMap(Map m) {        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);        putAllForCreate(m);    }    // internal utilities    /**     * Initialization hook for subclasses. This method is called     * in all constructors and pseudo-constructors (clone, readObject)     * after HashMap has been initialized but before any entries have     * been inserted.  (In the absence of this method, readObject would     * require explicit knowledge of subclasses.)     */    void init() {    }    /**     * Value representing null keys inside tables.     */    static final Object NULL_KEY = new Object();    /**     * Returns internal representation for key. Use NULL_KEY if key is null.     */    static Object maskNull(Object key) {        return (key == null ? NULL_KEY : key);    }    /**     * Returns key represented by specified internal representation.     */    static Object unmaskNull(Object key) {        return (key == NULL_KEY ? null : key);    }    /**     * Returns a hash value for the specified object.  In addition to      * the object's own hashCode, this method applies a "supplemental     * hash function," which defends against poor quality hash functions.     * This is critical because HashMap uses power-of two length      * hash tables.<p>     *     * The shift distances in this function were chosen as the result     * of an automated search over the entire four-dimensional search space.     */    static int hash(Object x) {        int h = x.hashCode();        h += ~(h << 9);        h ^=  (h >>> 14);        h +=  (h << 4);        h ^=  (h >>> 10);        return h;    }    /**      * Check for equality of non-null reference x and possibly-null y.      */    static boolean eq(Object x, Object y) {        return x == y || x.equals(y);    }    /**     * Returns index for hash code h.      */    static int indexFor(int h, int length) {        return h & (length-1);    }     /**     * Returns the number of key-value mappings in this map.     *     * @return the number of key-value mappings in this map.     */    public int size() {        return size;    }      /**     * Returns <tt>true</tt> if this map contains no key-value mappings.     *     * @return <tt>true</tt> if this map contains no key-value mappings.     */    public boolean isEmpty() {        return size == 0;    }    /**     * Returns the value to which the specified key is mapped in this identity     * hash map, or <tt>null</tt> if the map contains no mapping for this key.     * A return value of <tt>null</tt> does not <i>necessarily</i> indicate     * that the map contains no mapping for the key; it is also possible that     * the map explicitly maps the key to <tt>null</tt>. The     * <tt>containsKey</tt> method may be used to distinguish these two cases.     *     * @param   key the key whose associated value is to be returned.     * @return  the value to which this map maps the specified key, or     *          <tt>null</tt> if the map contains no mapping for this key.     * @see #put(Object, Object)     */    public Object get(Object key) {        Object k = maskNull(key);        int hash = hash(k);        int i = indexFor(hash, table.length);        Entry e = table[i];         while (true) {            if (e == null)                return e;            if (e.hash == hash && eq(k, e.key))                 return e.value;            e = e.next;