/* HashMap.java -- a class providing a basic hashtable data structure,   mapping Object --> Object   Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005  Free Software Foundation, Inc.This file is part of GNU Classpath.GNU Classpath is free software; you can redistribute it and/or modifyit under the terms of the GNU General Public License as published bythe Free Software Foundation; either version 2, or (at your option)any later version.GNU Classpath is distributed in the hope that it will be useful, butWITHOUT ANY WARRANTY; without even the implied warranty ofMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNUGeneral Public License for more details.You should have received a copy of the GNU General Public Licensealong with GNU Classpath; see the file COPYING.  If not, write to theFree Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA02110-1301 USA.Linking this library statically or dynamically with other modules ismaking a combined work based on this library.  Thus, the terms andconditions of the GNU General Public License cover the wholecombination.As a special exception, the copyright holders of this library give youpermission to link this library with independent modules to produce anexecutable, regardless of the license terms of these independentmodules, and to copy and distribute the resulting executable underterms of your choice, provided that you also meet, for each linkedindependent module, the terms and conditions of the license of thatmodule.  An independent module is a module which is not derived fromor based on this library.  If you modify this library, you may extendthis exception to your version of the library, but you are notobligated to do so.  If you do not wish to do so, delete thisexception statement from your version. */package java.util;import java.io.IOException;import java.io.ObjectInputStream;import java.io.ObjectOutputStream;import java.io.Serializable;// NOTE: This implementation is very similar to that of Hashtable. If you fix// a bug in here, chances are you should make a similar change to the Hashtable// code.// NOTE: This implementation has some nasty coding style in order to// support LinkedHashMap, which extends this./** * This class provides a hashtable-backed implementation of the * Map interface. * <p> * * It uses a hash-bucket approach; that is, hash collisions are handled * by linking the new node off of the pre-existing node (or list of * nodes).  In this manner, techniques such as linear probing (which * can cause primary clustering) and rehashing (which does not fit very * well with Java's method of precomputing hash codes) are avoided. * <p> * * Under ideal circumstances (no collisions), HashMap offers O(1) * performance on most operations (<code>containsValue()</code> is, * of course, O(n)).  In the worst case (all keys map to the same * hash code -- very unlikely), most operations are O(n). * <p> * * HashMap is part of the JDK1.2 Collections API.  It differs from * Hashtable in that it accepts the null key and null values, and it * does not support "Enumeration views." Also, it is not synchronized; * if you plan to use it in multiple threads, consider using:<br> * <code>Map m = Collections.synchronizedMap(new HashMap(...));</code> * <p> * * The iterators are <i>fail-fast</i>, meaning that any structural * modification, except for <code>remove()</code> called on the iterator * itself, cause the iterator to throw a * <code>ConcurrentModificationException</code> rather than exhibit * non-deterministic behavior. * * @author Jon Zeppieri * @author Jochen Hoenicke * @author Bryce McKinlay * @author Eric Blake (ebb9@email.byu.edu) * @see Object#hashCode() * @see Collection * @see Map * @see TreeMap * @see LinkedHashMap * @see IdentityHashMap * @see Hashtable * @since 1.2 * @status updated to 1.4 */public class HashMap extends AbstractMap  implements Map, Cloneable, Serializable{  /**   * Default number of buckets. This is the value the JDK 1.3 uses. Some   * early documentation specified this value as 101. That is incorrect.   * Package visible for use by HashSet.   */  static final int DEFAULT_CAPACITY = 11;  /**   * The default load factor; this is explicitly specified by the spec.   * Package visible for use by HashSet.   */  static final float DEFAULT_LOAD_FACTOR = 0.75f;  /**   * Compatible with JDK 1.2.   */  private static final long serialVersionUID = 362498820763181265L;  /**   * The rounded product of the capacity and the load factor; when the number   * of elements exceeds the threshold, the HashMap calls   * <code>rehash()</code>.   * @serial the threshold for rehashing   */  private int threshold;  /**   * Load factor of this HashMap:  used in computing the threshold.   * Package visible for use by HashSet.   * @serial the load factor   */  final float loadFactor;  /**   * Array containing the actual key-value mappings.   * Package visible for use by nested and subclasses.   */  transient HashEntry[] buckets;  /**   * Counts the number of modifications this HashMap has undergone, used   * by Iterators to know when to throw ConcurrentModificationExceptions.   * Package visible for use by nested and subclasses.   */  transient int modCount;  /**   * The size of this HashMap:  denotes the number of key-value pairs.   * Package visible for use by nested and subclasses.   */  transient int size;  /**   * The cache for {@link #entrySet()}.   */  private transient Set entries;  /**   * Class to represent an entry in the hash table. Holds a single key-value   * pair. Package visible for use by subclass.   *   * @author Eric Blake (ebb9@email.byu.edu)   */  static class HashEntry extends AbstractMap.BasicMapEntry  {    /**     * The next entry in the linked list. Package visible for use by subclass.     */    HashEntry next;    /**     * Simple constructor.     * @param key the key     * @param value the value     */    HashEntry(Object key, Object value)    {      super(key, value);    }    /**     * Called when this entry is accessed via {@link #put(Object, Object)}.     * This version does nothing, but in LinkedHashMap, it must do some     * bookkeeping for access-traversal mode.     */    void access()    {    }    /**     * Called when this entry is removed from the map. This version simply     * returns the value, but in LinkedHashMap, it must also do bookkeeping.     *     * @return the value of this key as it is removed     */    Object cleanup()    {      return value;    }  }  /**   * Construct a new HashMap with the default capacity (11) and the default   * load factor (0.75).   */  public HashMap()  {    this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);  }  /**   * Construct a new HashMap from the given Map, with initial capacity   * the greater of the size of <code>m</code> or the default of 11.   * <p>   *   * Every element in Map m will be put into this new HashMap.   *   * @param m a Map whose key / value pairs will be put into the new HashMap.   *        <b>NOTE: key / value pairs are not cloned in this constructor.</b>   * @throws NullPointerException if m is null   */  public HashMap(Map m)  {    this(Math.max(m.size() * 2, DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR);    putAll(m);  }  /**   * Construct a new HashMap with a specific inital capacity and   * default load factor of 0.75.   *   * @param initialCapacity the initial capacity of this HashMap (&gt;=0)   * @throws IllegalArgumentException if (initialCapacity &lt; 0)   */  public HashMap(int initialCapacity)  {    this(initialCapacity, DEFAULT_LOAD_FACTOR);  }  /**   * Construct a new HashMap with a specific inital capacity and load factor.   *   * @param initialCapacity the initial capacity (&gt;=0)   * @param loadFactor the load factor (&gt; 0, not NaN)   * @throws IllegalArgumentException if (initialCapacity &lt; 0) ||   *                                     ! (loadFactor &gt; 0.0)   */  public HashMap(int initialCapacity, float loadFactor)  {    if (initialCapacity < 0)      throw new IllegalArgumentException("Illegal Capacity: "                                         + initialCapacity);    if (! (loadFactor > 0)) // check for NaN too      throw new IllegalArgumentException("Illegal Load: " + loadFactor);    if (initialCapacity == 0)      initialCapacity = 1;    buckets = new HashEntry[initialCapacity];    this.loadFactor = loadFactor;    threshold = (int) (initialCapacity * loadFactor);  }  /**   * Returns the number of kay-value mappings currently in this Map.   *   * @return the size   */  public int size()  {    return size;  }  /**   * Returns true if there are no key-value mappings currently in this Map.   *   * @return <code>size() == 0</code>   */  public boolean isEmpty()  {    return size == 0;  }  /**   * Return the value in this HashMap associated with the supplied key,   * or <code>null</code> if the key maps to nothing.  NOTE: Since the value   * could also be null, you must use containsKey to see if this key   * actually maps to something.   *   * @param key the key for which to fetch an associated value   * @return what the key maps to, if present   * @see #put(Object, Object)   * @see #containsKey(Object)   */  public Object get(Object key)  {    int idx = hash(key);    HashEntry e = buckets[idx];    while (e != null)      {        if (equals(key, e.key))          return e.value;        e = e.next;      }    return null;  }  /**   * Returns true if the supplied object <code>equals()</code> a key   * in this HashMap.   *   * @param key the key to search for in this HashMap   * @return true if the key is in the table   * @see #containsValue(Object)   */  public boolean containsKey(Object key)  {    int idx = hash(key);    HashEntry e = buckets[idx];    while (e != null)      {        if (equals(key, e.key))          return true;        e = e.next;      }    return false;  }  /**   * Puts the supplied value into the Map, mapped by the supplied key.   * The value may be retrieved by any object which <code>equals()</code>   * this key. NOTE: Since the prior value could also be null, you must   * first use containsKey if you want to see if you are replacing the   * key's mapping.   *   * @param key the key used to locate the value   * @param value the value to be stored in the HashMap   * @return the prior mapping of the key, or null if there was none   * @see #get(Object)   * @see Object#equals(Object)   */  public Object put(Object key, Object value)  {    int idx = hash(key);    HashEntry e = buckets[idx];    while (e != null)      {        if (equals(key, e.key))          {            e.access(); // Must call this for bookkeeping in LinkedHashMap.            Object r = e.value;            e.value = value;            return r;          }        else          e = e.next;      }    // At this point, we know we need to add a new entry.    modCount++;    if (++size > threshold)      {        rehash();        // Need a new hash value to suit the bigger table.        idx = hash(key);      }    // LinkedHashMap cannot override put(), hence this call.    addEntry(key, value, idx, true);    return null;  }  /**   * Copies all elements of the given map into this hashtable.  If this table   * already has a mapping for a key, the new mapping replaces the current   * one.   *   * @param m the map to be hashed into this   */  public void putAll(Map m)  {    Iterator itr = m.entrySet().iterator();    while (itr.hasNext())      {        Map.Entry e = (Map.Entry) itr.next();        // Optimize in case the Entry is one of our own.        if (e instanceof AbstractMap.BasicMapEntry)          {            AbstractMap.BasicMapEntry entry = (AbstractMap.BasicMapEntry) e;            put(entry.key, entry.value);          }        else          put(e.getKey(), e.getValue());      }  }    /**   * Removes from the HashMap and returns the value which is mapped by the   * supplied key. If the key maps to nothing, then the HashMap remains   * unchanged, and <code>null</code> is returned. NOTE: Since the value   * could also be null, you must use containsKey to see if you are   * actually removing a mapping.   *   * @param key the key used to locate the value to remove   * @return whatever the key mapped to, if present   */  public Object remove(Object key)  {    int idx = hash(key);    HashEntry e = buckets[idx];    HashEntry last = null;    while (e != null)      {        if (equals(key, e.key))          {            modCount++;            if (last == null)              buckets[idx] = e.next;            else              last.next = e.next;            size--;            // Method call necessary for LinkedHashMap to work correctly.            return e.cleanup();          }        last = e;        e = e.next;      }    return null;  }  /**   * Clears the Map so it has no keys. This is O(1).   */  public void clear()  {    if (size != 0)      {        modCount++;        Arrays.fill(buckets, null);        size = 0;      }  }  /**   * Returns true if this HashMap contains a value <code>o</code>, such that   * <code>o.equals(value)</code>.   *   * @param value the value to search for in this HashMap   * @return true if at least one key maps to the value   * @see #containsKey(Object)   */  public boolean containsValue(Object value)