{    for (int i = buckets.length - 1; i >= 0; i--)      {        HashEntry e = buckets[i];        while (e != null)          {            if (equals(value, e.value))              return true;            e = e.next;          }      }    return false;  }  /**   * Returns a shallow clone of this HashMap. The Map itself is cloned,   * but its contents are not.  This is O(n).   *   * @return the clone   */  public Object clone()  {    HashMap copy = null;    try      {        copy = (HashMap) super.clone();      }    catch (CloneNotSupportedException x)      {        // This is impossible.      }    copy.buckets = new HashEntry[buckets.length];    copy.putAllInternal(this);    // Clear the entry cache. AbstractMap.clone() does the others.    copy.entries = null;    return copy;  }  /**   * Returns a "set view" of this HashMap's keys. The set is backed by the   * HashMap, so changes in one show up in the other.  The set supports   * element removal, but not element addition.   *   * @return a set view of the keys   * @see #values()   * @see #entrySet()   */  public Set keySet()  {    if (keys == null)      // Create an AbstractSet with custom implementations of those methods      // that can be overridden easily and efficiently.      keys = new AbstractSet()      {        public int size()        {          return size;        }        public Iterator iterator()        {          // Cannot create the iterator directly, because of LinkedHashMap.          return HashMap.this.iterator(KEYS);        }        public void clear()        {          HashMap.this.clear();        }        public boolean contains(Object o)        {          return containsKey(o);        }        public boolean remove(Object o)        {          // Test against the size of the HashMap to determine if anything          // really got removed. This is necessary because the return value          // of HashMap.remove() is ambiguous in the null case.          int oldsize = size;          HashMap.this.remove(o);          return oldsize != size;        }      };    return keys;  }  /**   * Returns a "collection view" (or "bag view") of this HashMap's values.   * The collection is backed by the HashMap, so changes in one show up   * in the other.  The collection supports element removal, but not element   * addition.   *   * @return a bag view of the values   * @see #keySet()   * @see #entrySet()   */  public Collection values()  {    if (values == null)      // We don't bother overriding many of the optional methods, as doing so      // wouldn't provide any significant performance advantage.      values = new AbstractCollection()      {        public int size()        {          return size;        }        public Iterator iterator()        {          // Cannot create the iterator directly, because of LinkedHashMap.          return HashMap.this.iterator(VALUES);        }        public void clear()        {          HashMap.this.clear();        }      };    return values;  }  /**   * Returns a "set view" of this HashMap's entries. The set is backed by   * the HashMap, so changes in one show up in the other.  The set supports   * element removal, but not element addition.<p>   *   * Note that the iterators for all three views, from keySet(), entrySet(),   * and values(), traverse the HashMap in the same sequence.   *   * @return a set view of the entries   * @see #keySet()   * @see #values()   * @see Map.Entry   */  public Set entrySet()  {    if (entries == null)      // Create an AbstractSet with custom implementations of those methods      // that can be overridden easily and efficiently.      entries = new AbstractSet()      {        public int size()        {          return size;        }        public Iterator iterator()        {          // Cannot create the iterator directly, because of LinkedHashMap.          return HashMap.this.iterator(ENTRIES);        }        public void clear()        {          HashMap.this.clear();        }        public boolean contains(Object o)        {          return getEntry(o) != null;        }        public boolean remove(Object o)        {          HashEntry e = getEntry(o);          if (e != null)            {              HashMap.this.remove(e.key);              return true;            }          return false;        }      };    return entries;  }  /**   * Helper method for put, that creates and adds a new Entry.  This is   * overridden in LinkedHashMap for bookkeeping purposes.   *   * @param key the key of the new Entry   * @param value the value   * @param idx the index in buckets where the new Entry belongs   * @param callRemove whether to call the removeEldestEntry method   * @see #put(Object, Object)   */  void addEntry(Object key, Object value, int idx, boolean callRemove)  {    HashEntry e = new HashEntry(key, value);    e.next = buckets[idx];    buckets[idx] = e;  }  /**   * Helper method for entrySet(), which matches both key and value   * simultaneously.   *   * @param o the entry to match   * @return the matching entry, if found, or null   * @see #entrySet()   */  // Package visible, for use in nested classes.  final HashEntry getEntry(Object o)  {    if (! (o instanceof Map.Entry))      return null;    Map.Entry me = (Map.Entry) o;    Object key = me.getKey();    int idx = hash(key);    HashEntry e = buckets[idx];    while (e != null)      {        if (equals(e.key, key))          return equals(e.value, me.getValue()) ? e : null;        e = e.next;      }    return null;  }  /**   * Helper method that returns an index in the buckets array for `key'   * based on its hashCode().  Package visible for use by subclasses.   *   * @param key the key   * @return the bucket number   */  final int hash(Object key)  {    return key == null ? 0 : Math.abs(key.hashCode() % buckets.length);  }  /**   * Generates a parameterized iterator.  Must be overrideable, since   * LinkedHashMap iterates in a different order.   *   * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}   * @return the appropriate iterator   */  Iterator iterator(int type)  {    return new HashIterator(type);  }  /**   * A simplified, more efficient internal implementation of putAll(). clone()    * should not call putAll or put, in order to be compatible with the JDK    * implementation with respect to subclasses.   *   * @param m the map to initialize this from   */  void putAllInternal(Map m)  {    Iterator itr = m.entrySet().iterator();    size = 0;    while (itr.hasNext())      {        size++;	Map.Entry e = (Map.Entry) itr.next();	Object key = e.getKey();	int idx = hash(key);	addEntry(key, e.getValue(), idx, false);      }  }  /**   * Increases the size of the HashMap and rehashes all keys to new   * array indices; this is called when the addition of a new value   * would cause size() &gt; threshold. Note that the existing Entry   * objects are reused in the new hash table.   *   * <p>This is not specified, but the new size is twice the current size   * plus one; this number is not always prime, unfortunately.   */  private void rehash()  {    HashEntry[] oldBuckets = buckets;    int newcapacity = (buckets.length * 2) + 1;    threshold = (int) (newcapacity * loadFactor);    buckets = new HashEntry[newcapacity];    for (int i = oldBuckets.length - 1; i >= 0; i--)      {        HashEntry e = oldBuckets[i];        while (e != null)          {            int idx = hash(e.key);            HashEntry dest = buckets[idx];            HashEntry next = e.next;            e.next = buckets[idx];            buckets[idx] = e;            e = next;          }      }  }  /**   * Serializes this object to the given stream.   *   * @param s the stream to write to   * @throws IOException if the underlying stream fails   * @serialData the <i>capacity</i>(int) that is the length of the   *             bucket array, the <i>size</i>(int) of the hash map   *             are emitted first.  They are followed by size entries,   *             each consisting of a key (Object) and a value (Object).   */  private void writeObject(ObjectOutputStream s) throws IOException  {    // Write the threshold and loadFactor fields.    s.defaultWriteObject();    s.writeInt(buckets.length);    s.writeInt(size);    // Avoid creating a wasted Set by creating the iterator directly.    Iterator it = iterator(ENTRIES);    while (it.hasNext())      {        HashEntry entry = (HashEntry) it.next();        s.writeObject(entry.key);        s.writeObject(entry.value);      }  }  /**   * Deserializes this object from the given stream.   *   * @param s the stream to read from   * @throws ClassNotFoundException if the underlying stream fails   * @throws IOException if the underlying stream fails   * @serialData the <i>capacity</i>(int) that is the length of the   *             bucket array, the <i>size</i>(int) of the hash map   *             are emitted first.  They are followed by size entries,   *             each consisting of a key (Object) and a value (Object).   */  private void readObject(ObjectInputStream s)    throws IOException, ClassNotFoundException  {    // Read the threshold and loadFactor fields.    s.defaultReadObject();    // Read and use capacity, followed by key/value pairs.    buckets = new HashEntry[s.readInt()];    int len = s.readInt();    size = len;    while (len-- > 0)      {        Object key = s.readObject();        addEntry(key, s.readObject(), hash(key), false);      }  }  /**   * Iterate over HashMap's entries.   * This implementation is parameterized to give a sequential view of   * keys, values, or entries.   *   * @author Jon Zeppieri   */  private final class HashIterator implements Iterator  {    /**     * The type of this Iterator: {@link #KEYS}, {@link #VALUES},     * or {@link #ENTRIES}.     */    private final int type;    /**     * The number of modifications to the backing HashMap that we know about.     */    private int knownMod = modCount;    /** The number of elements remaining to be returned by next(). */    private int count = size;    /** Current index in the physical hash table. */    private int idx = buckets.length;    /** The last Entry returned by a next() call. */    private HashEntry last;    /**     * The next entry that should be returned by next(). It is set to something     * if we're iterating through a bucket that contains multiple linked     * entries. It is null if next() needs to find a new bucket.     */    private HashEntry next;    /**     * Construct a new HashIterator with the supplied type.     * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}     */    HashIterator(int type)    {      this.type = type;    }    /**     * Returns true if the Iterator has more elements.     * @return true if there are more elements     * @throws ConcurrentModificationException if the HashMap was modified     */    public boolean hasNext()    {      if (knownMod != modCount)        throw new ConcurrentModificationException();      return count > 0;    }    /**     * Returns the next element in the Iterator's sequential view.     * @return the next element     * @throws ConcurrentModificationException if the HashMap was modified     * @throws NoSuchElementException if there is none     */    public Object next()    {      if (knownMod != modCount)        throw new ConcurrentModificationException();      if (count == 0)        throw new NoSuchElementException();      count--;      HashEntry e = next;      while (e == null)        e = buckets[--idx];      next = e.next;      last = e;      if (type == VALUES)        return e.value;      if (type == KEYS)        return e.key;      return e;    }    /**     * Removes from the backing HashMap the last element which was fetched     * with the <code>next()</code> method.     * @throws ConcurrentModificationException if the HashMap was modified     * @throws IllegalStateException if called when there is no last element     */    public void remove()    {      if (knownMod != modCount)        throw new ConcurrentModificationException();      if (last == null)        throw new IllegalStateException();      HashMap.this.remove(last.key);      last = null;      knownMod++;    }  }}