jaroslav@557: /*
jaroslav@557:  * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved.
jaroslav@557:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
jaroslav@557:  *
jaroslav@557:  * This code is free software; you can redistribute it and/or modify it
jaroslav@557:  * under the terms of the GNU General Public License version 2 only, as
jaroslav@557:  * published by the Free Software Foundation.  Oracle designates this
jaroslav@557:  * particular file as subject to the "Classpath" exception as provided
jaroslav@557:  * by Oracle in the LICENSE file that accompanied this code.
jaroslav@557:  *
jaroslav@557:  * This code is distributed in the hope that it will be useful, but WITHOUT
jaroslav@557:  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
jaroslav@557:  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
jaroslav@557:  * version 2 for more details (a copy is included in the LICENSE file that
jaroslav@557:  * accompanied this code).
jaroslav@557:  *
jaroslav@557:  * You should have received a copy of the GNU General Public License version
jaroslav@557:  * 2 along with this work; if not, write to the Free Software Foundation,
jaroslav@557:  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
jaroslav@557:  *
jaroslav@557:  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
jaroslav@557:  * or visit www.oracle.com if you need additional information or have any
jaroslav@557:  * questions.
jaroslav@557:  */
jaroslav@557: 
jaroslav@557: package java.util;
jaroslav@557: import java.io.*;
jaroslav@557: 
jaroslav@557: /**
jaroslav@557:  * Hash table based implementation of the <tt>Map</tt> interface.  This
jaroslav@557:  * implementation provides all of the optional map operations, and permits
jaroslav@557:  * <tt>null</tt> values and the <tt>null</tt> key.  (The <tt>HashMap</tt>
jaroslav@557:  * class is roughly equivalent to <tt>Hashtable</tt>, except that it is
jaroslav@557:  * unsynchronized and permits nulls.)  This class makes no guarantees as to
jaroslav@557:  * the order of the map; in particular, it does not guarantee that the order
jaroslav@557:  * will remain constant over time.
jaroslav@557:  *
jaroslav@557:  * <p>This implementation provides constant-time performance for the basic
jaroslav@557:  * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function
jaroslav@557:  * disperses the elements properly among the buckets.  Iteration over
jaroslav@557:  * collection views requires time proportional to the "capacity" of the
jaroslav@557:  * <tt>HashMap</tt> instance (the number of buckets) plus its size (the number
jaroslav@557:  * of key-value mappings).  Thus, it's very important not to set the initial
jaroslav@557:  * capacity too high (or the load factor too low) if iteration performance is
jaroslav@557:  * important.
jaroslav@557:  *
jaroslav@557:  * <p>An instance of <tt>HashMap</tt> has two parameters that affect its
jaroslav@557:  * performance: <i>initial capacity</i> and <i>load factor</i>.  The
jaroslav@557:  * <i>capacity</i> is the number of buckets in the hash table, and the initial
jaroslav@557:  * capacity is simply the capacity at the time the hash table is created.  The
jaroslav@557:  * <i>load factor</i> is a measure of how full the hash table is allowed to
jaroslav@557:  * get before its capacity is automatically increased.  When the number of
jaroslav@557:  * entries in the hash table exceeds the product of the load factor and the
jaroslav@557:  * current capacity, the hash table is <i>rehashed</i> (that is, internal data
jaroslav@557:  * structures are rebuilt) so that the hash table has approximately twice the
jaroslav@557:  * number of buckets.
jaroslav@557:  *
jaroslav@557:  * <p>As a general rule, the default load factor (.75) offers a good tradeoff
jaroslav@557:  * between time and space costs.  Higher values decrease the space overhead
jaroslav@557:  * but increase the lookup cost (reflected in most of the operations of the
jaroslav@557:  * <tt>HashMap</tt> class, including <tt>get</tt> and <tt>put</tt>).  The
jaroslav@557:  * expected number of entries in the map and its load factor should be taken
jaroslav@557:  * into account when setting its initial capacity, so as to minimize the
jaroslav@557:  * number of rehash operations.  If the initial capacity is greater
jaroslav@557:  * than the maximum number of entries divided by the load factor, no
jaroslav@557:  * rehash operations will ever occur.
jaroslav@557:  *
jaroslav@557:  * <p>If many mappings are to be stored in a <tt>HashMap</tt> instance,
jaroslav@557:  * creating it with a sufficiently large capacity will allow the mappings to
jaroslav@557:  * be stored more efficiently than letting it perform automatic rehashing as
jaroslav@557:  * needed to grow the table.
jaroslav@557:  *
jaroslav@557:  * <p><strong>Note that this implementation is not synchronized.</strong>
jaroslav@557:  * If multiple threads access a hash map concurrently, and at least one of
jaroslav@557:  * the threads modifies the map structurally, it <i>must</i> be
jaroslav@557:  * synchronized externally.  (A structural modification is any operation
jaroslav@557:  * that adds or deletes one or more mappings; merely changing the value
jaroslav@557:  * associated with a key that an instance already contains is not a
jaroslav@557:  * structural modification.)  This is typically accomplished by
jaroslav@557:  * synchronizing on some object that naturally encapsulates the map.
jaroslav@557:  *
jaroslav@557:  * If no such object exists, the map should be "wrapped" using the
jaroslav@557:  * {@link Collections#synchronizedMap Collections.synchronizedMap}
jaroslav@557:  * method.  This is best done at creation time, to prevent accidental
jaroslav@557:  * unsynchronized access to the map:<pre>
jaroslav@557:  *   Map m = Collections.synchronizedMap(new HashMap(...));</pre>
jaroslav@557:  *
jaroslav@557:  * <p>The iterators returned by all of this class's "collection view methods"
jaroslav@557:  * are <i>fail-fast</i>: if the map is structurally modified at any time after
jaroslav@557:  * the iterator is created, in any way except through the iterator's own
jaroslav@557:  * <tt>remove</tt> method, the iterator will throw a
jaroslav@557:  * {@link ConcurrentModificationException}.  Thus, in the face of concurrent
jaroslav@557:  * modification, the iterator fails quickly and cleanly, rather than risking
jaroslav@557:  * arbitrary, non-deterministic behavior at an undetermined time in the
jaroslav@557:  * future.
jaroslav@557:  *
jaroslav@557:  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
jaroslav@557:  * as it is, generally speaking, impossible to make any hard guarantees in the
jaroslav@557:  * presence of unsynchronized concurrent modification.  Fail-fast iterators
jaroslav@557:  * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
jaroslav@557:  * Therefore, it would be wrong to write a program that depended on this
jaroslav@557:  * exception for its correctness: <i>the fail-fast behavior of iterators
jaroslav@557:  * should be used only to detect bugs.</i>
jaroslav@557:  *
jaroslav@557:  * <p>This class is a member of the
jaroslav@557:  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
jaroslav@557:  * Java Collections Framework</a>.
jaroslav@557:  *
jaroslav@557:  * @param <K> the type of keys maintained by this map
jaroslav@557:  * @param <V> the type of mapped values
jaroslav@557:  *
jaroslav@557:  * @author  Doug Lea
jaroslav@557:  * @author  Josh Bloch
jaroslav@557:  * @author  Arthur van Hoff
jaroslav@557:  * @author  Neal Gafter
jaroslav@557:  * @see     Object#hashCode()
jaroslav@557:  * @see     Collection
jaroslav@557:  * @see     Map
jaroslav@557:  * @see     TreeMap
jaroslav@557:  * @see     Hashtable
jaroslav@557:  * @since   1.2
jaroslav@557:  */
jaroslav@557: 
jaroslav@557: public class HashMap<K,V>
jaroslav@557:     extends AbstractMap<K,V>
jaroslav@557:     implements Map<K,V>, Cloneable, Serializable
jaroslav@557: {
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * The default initial capacity - MUST be a power of two.
jaroslav@557:      */
jaroslav@557:     static final int DEFAULT_INITIAL_CAPACITY = 16;
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * The maximum capacity, used if a higher value is implicitly specified
jaroslav@557:      * by either of the constructors with arguments.
jaroslav@557:      * MUST be a power of two <= 1<<30.
jaroslav@557:      */
jaroslav@557:     static final int MAXIMUM_CAPACITY = 1 << 30;
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * The load factor used when none specified in constructor.
jaroslav@557:      */
jaroslav@557:     static final float DEFAULT_LOAD_FACTOR = 0.75f;
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * The table, resized as necessary. Length MUST Always be a power of two.
jaroslav@557:      */
jaroslav@557:     transient Entry[] table;
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * The number of key-value mappings contained in this map.
jaroslav@557:      */
jaroslav@557:     transient int size;
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * The next size value at which to resize (capacity * load factor).
jaroslav@557:      * @serial
jaroslav@557:      */
jaroslav@557:     int threshold;
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * The load factor for the hash table.
jaroslav@557:      *
jaroslav@557:      * @serial
jaroslav@557:      */
jaroslav@557:     final float loadFactor;
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * The number of times this HashMap has been structurally modified
jaroslav@557:      * Structural modifications are those that change the number of mappings in
jaroslav@557:      * the HashMap or otherwise modify its internal structure (e.g.,
jaroslav@557:      * rehash).  This field is used to make iterators on Collection-views of
jaroslav@557:      * the HashMap fail-fast.  (See ConcurrentModificationException).
jaroslav@557:      */
jaroslav@557:     transient int modCount;
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Constructs an empty <tt>HashMap</tt> with the specified initial
jaroslav@557:      * capacity and load factor.
jaroslav@557:      *
jaroslav@557:      * @param  initialCapacity the initial capacity
jaroslav@557:      * @param  loadFactor      the load factor
jaroslav@557:      * @throws IllegalArgumentException if the initial capacity is negative
jaroslav@557:      *         or the load factor is nonpositive
jaroslav@557:      */
jaroslav@557:     public HashMap(int initialCapacity, float loadFactor) {
jaroslav@557:         if (initialCapacity < 0)
jaroslav@557:             throw new IllegalArgumentException("Illegal initial capacity: " +
jaroslav@557:                                                initialCapacity);
jaroslav@557:         if (initialCapacity > MAXIMUM_CAPACITY)
jaroslav@557:             initialCapacity = MAXIMUM_CAPACITY;
jaroslav@557:         if (loadFactor <= 0 || Float.isNaN(loadFactor))
jaroslav@557:             throw new IllegalArgumentException("Illegal load factor: " +
jaroslav@557:                                                loadFactor);
jaroslav@557: 
jaroslav@557:         // Find a power of 2 >= initialCapacity
jaroslav@557:         int capacity = 1;
jaroslav@557:         while (capacity < initialCapacity)
jaroslav@557:             capacity <<= 1;
jaroslav@557: 
jaroslav@557:         this.loadFactor = loadFactor;
jaroslav@557:         threshold = (int)(capacity * loadFactor);
jaroslav@557:         table = new Entry[capacity];
jaroslav@557:         init();
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Constructs an empty <tt>HashMap</tt> with the specified initial
jaroslav@557:      * capacity and the default load factor (0.75).
jaroslav@557:      *
jaroslav@557:      * @param  initialCapacity the initial capacity.
jaroslav@557:      * @throws IllegalArgumentException if the initial capacity is negative.
jaroslav@557:      */
jaroslav@557:     public HashMap(int initialCapacity) {
jaroslav@557:         this(initialCapacity, DEFAULT_LOAD_FACTOR);
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Constructs an empty <tt>HashMap</tt> with the default initial capacity
jaroslav@557:      * (16) and the default load factor (0.75).
jaroslav@557:      */
jaroslav@557:     public HashMap() {
jaroslav@557:         this.loadFactor = DEFAULT_LOAD_FACTOR;
jaroslav@557:         threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
jaroslav@557:         table = new Entry[DEFAULT_INITIAL_CAPACITY];
jaroslav@557:         init();
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Constructs a new <tt>HashMap</tt> with the same mappings as the
jaroslav@557:      * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
jaroslav@557:      * default load factor (0.75) and an initial capacity sufficient to
jaroslav@557:      * hold the mappings in the specified <tt>Map</tt>.
jaroslav@557:      *
jaroslav@557:      * @param   m the map whose mappings are to be placed in this map
jaroslav@557:      * @throws  NullPointerException if the specified map is null
jaroslav@557:      */
jaroslav@557:     public HashMap(Map<? extends K, ? extends V> m) {
jaroslav@557:         this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
jaroslav@557:                       DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
jaroslav@557:         putAllForCreate(m);
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     // internal utilities
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Initialization hook for subclasses. This method is called
jaroslav@557:      * in all constructors and pseudo-constructors (clone, readObject)
jaroslav@557:      * after HashMap has been initialized but before any entries have
jaroslav@557:      * been inserted.  (In the absence of this method, readObject would
jaroslav@557:      * require explicit knowledge of subclasses.)
jaroslav@557:      */
jaroslav@557:     void init() {
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Applies a supplemental hash function to a given hashCode, which
jaroslav@557:      * defends against poor quality hash functions.  This is critical
jaroslav@557:      * because HashMap uses power-of-two length hash tables, that
jaroslav@557:      * otherwise encounter collisions for hashCodes that do not differ
jaroslav@557:      * in lower bits. Note: Null keys always map to hash 0, thus index 0.
jaroslav@557:      */
jaroslav@557:     static int hash(int h) {
jaroslav@557:         // This function ensures that hashCodes that differ only by
jaroslav@557:         // constant multiples at each bit position have a bounded
jaroslav@557:         // number of collisions (approximately 8 at default load factor).
jaroslav@557:         h ^= (h >>> 20) ^ (h >>> 12);
jaroslav@557:         return h ^ (h >>> 7) ^ (h >>> 4);
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Returns index for hash code h.
jaroslav@557:      */
jaroslav@557:     static int indexFor(int h, int length) {
jaroslav@557:         return h & (length-1);
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Returns the number of key-value mappings in this map.
jaroslav@557:      *
jaroslav@557:      * @return the number of key-value mappings in this map
jaroslav@557:      */
jaroslav@557:     public int size() {
jaroslav@557:         return size;
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Returns <tt>true</tt> if this map contains no key-value mappings.
jaroslav@557:      *
jaroslav@557:      * @return <tt>true</tt> if this map contains no key-value mappings
jaroslav@557:      */
jaroslav@557:     public boolean isEmpty() {
jaroslav@557:         return size == 0;
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Returns the value to which the specified key is mapped,
jaroslav@557:      * or {@code null} if this map contains no mapping for the key.
jaroslav@557:      *
jaroslav@557:      * <p>More formally, if this map contains a mapping from a key
jaroslav@557:      * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
jaroslav@557:      * key.equals(k))}, then this method returns {@code v}; otherwise
jaroslav@557:      * it returns {@code null}.  (There can be at most one such mapping.)
jaroslav@557:      *
jaroslav@557:      * <p>A return value of {@code null} does not <i>necessarily</i>
jaroslav@557:      * indicate that the map contains no mapping for the key; it's also
jaroslav@557:      * possible that the map explicitly maps the key to {@code null}.
jaroslav@557:      * The {@link #containsKey containsKey} operation may be used to
jaroslav@557:      * distinguish these two cases.
jaroslav@557:      *
jaroslav@557:      * @see #put(Object, Object)
jaroslav@557:      */
jaroslav@557:     public V get(Object key) {
jaroslav@557:         if (key == null)
jaroslav@557:             return getForNullKey();
jaroslav@557:         int hash = hash(key.hashCode());
jaroslav@557:         for (Entry<K,V> e = table[indexFor(hash, table.length)];
jaroslav@557:              e != null;
jaroslav@557:              e = e.next) {
jaroslav@557:             Object k;
jaroslav@557:             if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
jaroslav@557:                 return e.value;
jaroslav@557:         }
jaroslav@557:         return null;
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Offloaded version of get() to look up null keys.  Null keys map
jaroslav@557:      * to index 0.  This null case is split out into separate methods
jaroslav@557:      * for the sake of performance in the two most commonly used
jaroslav@557:      * operations (get and put), but incorporated with conditionals in
jaroslav@557:      * others.
jaroslav@557:      */
jaroslav@557:     private V getForNullKey() {
jaroslav@557:         for (Entry<K,V> e = table[0]; e != null; e = e.next) {
jaroslav@557:             if (e.key == null)
jaroslav@557:                 return e.value;
jaroslav@557:         }
jaroslav@557:         return null;
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Returns <tt>true</tt> if this map contains a mapping for the
jaroslav@557:      * specified key.
jaroslav@557:      *
jaroslav@557:      * @param   key   The key whose presence in this map is to be tested
jaroslav@557:      * @return <tt>true</tt> if this map contains a mapping for the specified
jaroslav@557:      * key.
jaroslav@557:      */
jaroslav@557:     public boolean containsKey(Object key) {
jaroslav@557:         return getEntry(key) != null;
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Returns the entry associated with the specified key in the
jaroslav@557:      * HashMap.  Returns null if the HashMap contains no mapping
jaroslav@557:      * for the key.
jaroslav@557:      */
jaroslav@557:     final Entry<K,V> getEntry(Object key) {
jaroslav@557:         int hash = (key == null) ? 0 : hash(key.hashCode());
jaroslav@557:         for (Entry<K,V> e = table[indexFor(hash, table.length)];
jaroslav@557:              e != null;
jaroslav@557:              e = e.next) {
jaroslav@557:             Object k;
jaroslav@557:             if (e.hash == hash &&
jaroslav@557:                 ((k = e.key) == key || (key != null && key.equals(k))))
jaroslav@557:                 return e;
jaroslav@557:         }
jaroslav@557:         return null;
jaroslav@557:     }
jaroslav@557: 
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Associates the specified value with the specified key in this map.
jaroslav@557:      * If the map previously contained a mapping for the key, the old
jaroslav@557:      * value is replaced.
jaroslav@557:      *
jaroslav@557:      * @param key key with which the specified value is to be associated
jaroslav@557:      * @param value value to be associated with the specified key
jaroslav@557:      * @return the previous value associated with <tt>key</tt>, or
jaroslav@557:      *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
jaroslav@557:      *         (A <tt>null</tt> return can also indicate that the map
jaroslav@557:      *         previously associated <tt>null</tt> with <tt>key</tt>.)
jaroslav@557:      */
jaroslav@557:     public V put(K key, V value) {
jaroslav@557:         if (key == null)
jaroslav@557:             return putForNullKey(value);
jaroslav@557:         int hash = hash(key.hashCode());
jaroslav@557:         int i = indexFor(hash, table.length);
jaroslav@557:         for (Entry<K,V> e = table[i]; e != null; e = e.next) {
jaroslav@557:             Object k;
jaroslav@557:             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
jaroslav@557:                 V oldValue = e.value;
jaroslav@557:                 e.value = value;
jaroslav@557:                 e.recordAccess(this);
jaroslav@557:                 return oldValue;
jaroslav@557:             }
jaroslav@557:         }
jaroslav@557: 
jaroslav@557:         modCount++;
jaroslav@557:         addEntry(hash, key, value, i);
jaroslav@557:         return null;
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Offloaded version of put for null keys
jaroslav@557:      */
jaroslav@557:     private V putForNullKey(V value) {
jaroslav@557:         for (Entry<K,V> e = table[0]; e != null; e = e.next) {
jaroslav@557:             if (e.key == null) {
jaroslav@557:                 V oldValue = e.value;
jaroslav@557:                 e.value = value;
jaroslav@557:                 e.recordAccess(this);
jaroslav@557:                 return oldValue;
jaroslav@557:             }
jaroslav@557:         }
jaroslav@557:         modCount++;
jaroslav@557:         addEntry(0, null, value, 0);
jaroslav@557:         return null;
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * This method is used instead of put by constructors and
jaroslav@557:      * pseudoconstructors (clone, readObject).  It does not resize the table,
jaroslav@557:      * check for comodification, etc.  It calls createEntry rather than
jaroslav@557:      * addEntry.
jaroslav@557:      */
jaroslav@557:     private void putForCreate(K key, V value) {
jaroslav@557:         int hash = (key == null) ? 0 : hash(key.hashCode());
jaroslav@557:         int i = indexFor(hash, table.length);
jaroslav@557: 
jaroslav@557:         /**
jaroslav@557:          * Look for preexisting entry for key.  This will never happen for
jaroslav@557:          * clone or deserialize.  It will only happen for construction if the
jaroslav@557:          * input Map is a sorted map whose ordering is inconsistent w/ equals.
jaroslav@557:          */
jaroslav@557:         for (Entry<K,V> e = table[i]; e != null; e = e.next) {
jaroslav@557:             Object k;
jaroslav@557:             if (e.hash == hash &&
jaroslav@557:                 ((k = e.key) == key || (key != null && key.equals(k)))) {
jaroslav@557:                 e.value = value;
jaroslav@557:                 return;
jaroslav@557:             }
jaroslav@557:         }
jaroslav@557: 
jaroslav@557:         createEntry(hash, key, value, i);
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     private void putAllForCreate(Map<? extends K, ? extends V> m) {
jaroslav@557:         for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
jaroslav@557:             putForCreate(e.getKey(), e.getValue());
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Rehashes the contents of this map into a new array with a
jaroslav@557:      * larger capacity.  This method is called automatically when the
jaroslav@557:      * number of keys in this map reaches its threshold.
jaroslav@557:      *
jaroslav@557:      * If current capacity is MAXIMUM_CAPACITY, this method does not
jaroslav@557:      * resize the map, but sets threshold to Integer.MAX_VALUE.
jaroslav@557:      * This has the effect of preventing future calls.
jaroslav@557:      *
jaroslav@557:      * @param newCapacity the new capacity, MUST be a power of two;
jaroslav@557:      *        must be greater than current capacity unless current
jaroslav@557:      *        capacity is MAXIMUM_CAPACITY (in which case value
jaroslav@557:      *        is irrelevant).
jaroslav@557:      */
jaroslav@557:     void resize(int newCapacity) {
jaroslav@557:         Entry[] oldTable = table;
jaroslav@557:         int oldCapacity = oldTable.length;
jaroslav@557:         if (oldCapacity == MAXIMUM_CAPACITY) {
jaroslav@557:             threshold = Integer.MAX_VALUE;
jaroslav@557:             return;
jaroslav@557:         }
jaroslav@557: 
jaroslav@557:         Entry[] newTable = new Entry[newCapacity];
jaroslav@557:         transfer(newTable);
jaroslav@557:         table = newTable;
jaroslav@557:         threshold = (int)(newCapacity * loadFactor);
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Transfers all entries from current table to newTable.
jaroslav@557:      */
jaroslav@557:     void transfer(Entry[] newTable) {
jaroslav@557:         Entry[] src = table;
jaroslav@557:         int newCapacity = newTable.length;
jaroslav@557:         for (int j = 0; j < src.length; j++) {
jaroslav@557:             Entry<K,V> e = src[j];
jaroslav@557:             if (e != null) {
jaroslav@557:                 src[j] = null;
jaroslav@557:                 do {
jaroslav@557:                     Entry<K,V> next = e.next;
jaroslav@557:                     int i = indexFor(e.hash, newCapacity);
jaroslav@557:                     e.next = newTable[i];
jaroslav@557:                     newTable[i] = e;
jaroslav@557:                     e = next;
jaroslav@557:                 } while (e != null);
jaroslav@557:             }
jaroslav@557:         }
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Copies all of the mappings from the specified map to this map.
jaroslav@557:      * These mappings will replace any mappings that this map had for
jaroslav@557:      * any of the keys currently in the specified map.
jaroslav@557:      *
jaroslav@557:      * @param m mappings to be stored in this map
jaroslav@557:      * @throws NullPointerException if the specified map is null
jaroslav@557:      */
jaroslav@557:     public void putAll(Map<? extends K, ? extends V> m) {
jaroslav@557:         int numKeysToBeAdded = m.size();
jaroslav@557:         if (numKeysToBeAdded == 0)
jaroslav@557:             return;
jaroslav@557: 
jaroslav@557:         /*
jaroslav@557:          * Expand the map if the map if the number of mappings to be added
jaroslav@557:          * is greater than or equal to threshold.  This is conservative; the
jaroslav@557:          * obvious condition is (m.size() + size) >= threshold, but this
jaroslav@557:          * condition could result in a map with twice the appropriate capacity,
jaroslav@557:          * if the keys to be added overlap with the keys already in this map.
jaroslav@557:          * By using the conservative calculation, we subject ourself
jaroslav@557:          * to at most one extra resize.
jaroslav@557:          */
jaroslav@557:         if (numKeysToBeAdded > threshold) {
jaroslav@557:             int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
jaroslav@557:             if (targetCapacity > MAXIMUM_CAPACITY)
jaroslav@557:                 targetCapacity = MAXIMUM_CAPACITY;
jaroslav@557:             int newCapacity = table.length;
jaroslav@557:             while (newCapacity < targetCapacity)
jaroslav@557:                 newCapacity <<= 1;
jaroslav@557:             if (newCapacity > table.length)
jaroslav@557:                 resize(newCapacity);
jaroslav@557:         }
jaroslav@557: 
jaroslav@557:         for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
jaroslav@557:             put(e.getKey(), e.getValue());
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Removes the mapping for the specified key from this map if present.
jaroslav@557:      *
jaroslav@557:      * @param  key key whose mapping is to be removed from the map
jaroslav@557:      * @return the previous value associated with <tt>key</tt>, or
jaroslav@557:      *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
jaroslav@557:      *         (A <tt>null</tt> return can also indicate that the map
jaroslav@557:      *         previously associated <tt>null</tt> with <tt>key</tt>.)
jaroslav@557:      */
jaroslav@557:     public V remove(Object key) {
jaroslav@557:         Entry<K,V> e = removeEntryForKey(key);
jaroslav@557:         return (e == null ? null : e.value);
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Removes and returns the entry associated with the specified key
jaroslav@557:      * in the HashMap.  Returns null if the HashMap contains no mapping
jaroslav@557:      * for this key.
jaroslav@557:      */
jaroslav@557:     final Entry<K,V> removeEntryForKey(Object key) {
jaroslav@557:         int hash = (key == null) ? 0 : hash(key.hashCode());
jaroslav@557:         int i = indexFor(hash, table.length);
jaroslav@557:         Entry<K,V> prev = table[i];
jaroslav@557:         Entry<K,V> e = prev;
jaroslav@557: 
jaroslav@557:         while (e != null) {
jaroslav@557:             Entry<K,V> next = e.next;
jaroslav@557:             Object k;
jaroslav@557:             if (e.hash == hash &&
jaroslav@557:                 ((k = e.key) == key || (key != null && key.equals(k)))) {
jaroslav@557:                 modCount++;
jaroslav@557:                 size--;
jaroslav@557:                 if (prev == e)
jaroslav@557:                     table[i] = next;
jaroslav@557:                 else
jaroslav@557:                     prev.next = next;
jaroslav@557:                 e.recordRemoval(this);
jaroslav@557:                 return e;
jaroslav@557:             }
jaroslav@557:             prev = e;
jaroslav@557:             e = next;
jaroslav@557:         }
jaroslav@557: 
jaroslav@557:         return e;
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Special version of remove for EntrySet.
jaroslav@557:      */
jaroslav@557:     final Entry<K,V> removeMapping(Object o) {
jaroslav@557:         if (!(o instanceof Map.Entry))
jaroslav@557:             return null;
jaroslav@557: 
jaroslav@557:         Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
jaroslav@557:         Object key = entry.getKey();
jaroslav@557:         int hash = (key == null) ? 0 : hash(key.hashCode());
jaroslav@557:         int i = indexFor(hash, table.length);
jaroslav@557:         Entry<K,V> prev = table[i];
jaroslav@557:         Entry<K,V> e = prev;
jaroslav@557: 
jaroslav@557:         while (e != null) {
jaroslav@557:             Entry<K,V> next = e.next;
jaroslav@557:             if (e.hash == hash && e.equals(entry)) {
jaroslav@557:                 modCount++;
jaroslav@557:                 size--;
jaroslav@557:                 if (prev == e)
jaroslav@557:                     table[i] = next;
jaroslav@557:                 else
jaroslav@557:                     prev.next = next;
jaroslav@557:                 e.recordRemoval(this);
jaroslav@557:                 return e;
jaroslav@557:             }
jaroslav@557:             prev = e;
jaroslav@557:             e = next;
jaroslav@557:         }
jaroslav@557: 
jaroslav@557:         return e;
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Removes all of the mappings from this map.
jaroslav@557:      * The map will be empty after this call returns.
jaroslav@557:      */
jaroslav@557:     public void clear() {
jaroslav@557:         modCount++;
jaroslav@557:         Entry[] tab = table;
jaroslav@557:         for (int i = 0; i < tab.length; i++)
jaroslav@557:             tab[i] = null;
jaroslav@557:         size = 0;
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Returns <tt>true</tt> if this map maps one or more keys to the
jaroslav@557:      * specified value.
jaroslav@557:      *
jaroslav@557:      * @param value value whose presence in this map is to be tested
jaroslav@557:      * @return <tt>true</tt> if this map maps one or more keys to the
jaroslav@557:      *         specified value
jaroslav@557:      */
jaroslav@557:     public boolean containsValue(Object value) {
jaroslav@557:         if (value == null)
jaroslav@557:             return containsNullValue();
jaroslav@557: 
jaroslav@557:         Entry[] tab = table;
jaroslav@557:         for (int i = 0; i < tab.length ; i++)
jaroslav@557:             for (Entry e = tab[i] ; e != null ; e = e.next)
jaroslav@557:                 if (value.equals(e.value))
jaroslav@557:                     return true;
jaroslav@557:         return false;
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Special-case code for containsValue with null argument
jaroslav@557:      */
jaroslav@557:     private boolean containsNullValue() {
jaroslav@557:         Entry[] tab = table;
jaroslav@557:         for (int i = 0; i < tab.length ; i++)
jaroslav@557:             for (Entry e = tab[i] ; e != null ; e = e.next)
jaroslav@557:                 if (e.value == null)
jaroslav@557:                     return true;
jaroslav@557:         return false;
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
jaroslav@557:      * values themselves are not cloned.
jaroslav@557:      *
jaroslav@557:      * @return a shallow copy of this map
jaroslav@557:      */
jaroslav@557:     public Object clone() {
jaroslav@557:         HashMap<K,V> result = null;
jaroslav@557:         try {
jaroslav@557:             result = (HashMap<K,V>)super.clone();
jaroslav@557:         } catch (CloneNotSupportedException e) {
jaroslav@557:             // assert false;
jaroslav@557:         }
jaroslav@557:         result.table = new Entry[table.length];
jaroslav@557:         result.entrySet = null;
jaroslav@557:         result.modCount = 0;
jaroslav@557:         result.size = 0;
jaroslav@557:         result.init();
jaroslav@557:         result.putAllForCreate(this);
jaroslav@557: 
jaroslav@557:         return result;
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     static class Entry<K,V> implements Map.Entry<K,V> {
jaroslav@557:         final K key;
jaroslav@557:         V value;
jaroslav@557:         Entry<K,V> next;
jaroslav@557:         final int hash;
jaroslav@557: 
jaroslav@557:         /**
jaroslav@557:          * Creates new entry.
jaroslav@557:          */
jaroslav@557:         Entry(int h, K k, V v, Entry<K,V> n) {
jaroslav@557:             value = v;
jaroslav@557:             next = n;
jaroslav@557:             key = k;
jaroslav@557:             hash = h;
jaroslav@557:         }
jaroslav@557: 
jaroslav@557:         public final K getKey() {
jaroslav@557:             return key;
jaroslav@557:         }
jaroslav@557: 
jaroslav@557:         public final V getValue() {
jaroslav@557:             return value;
jaroslav@557:         }
jaroslav@557: 
jaroslav@557:         public final V setValue(V newValue) {
jaroslav@557:             V oldValue = value;
jaroslav@557:             value = newValue;
jaroslav@557:             return oldValue;
jaroslav@557:         }
jaroslav@557: 
jaroslav@557:         public final boolean equals(Object o) {
jaroslav@557:             if (!(o instanceof Map.Entry))
jaroslav@557:                 return false;
jaroslav@557:             Map.Entry e = (Map.Entry)o;
jaroslav@557:             Object k1 = getKey();
jaroslav@557:             Object k2 = e.getKey();
jaroslav@557:             if (k1 == k2 || (k1 != null && k1.equals(k2))) {
jaroslav@557:                 Object v1 = getValue();
jaroslav@557:                 Object v2 = e.getValue();
jaroslav@557:                 if (v1 == v2 || (v1 != null && v1.equals(v2)))
jaroslav@557:                     return true;
jaroslav@557:             }
jaroslav@557:             return false;
jaroslav@557:         }
jaroslav@557: 
jaroslav@557:         public final int hashCode() {
jaroslav@557:             return (key==null   ? 0 : key.hashCode()) ^
jaroslav@557:                    (value==null ? 0 : value.hashCode());
jaroslav@557:         }
jaroslav@557: 
jaroslav@557:         public final String toString() {
jaroslav@557:             return getKey() + "=" + getValue();
jaroslav@557:         }
jaroslav@557: 
jaroslav@557:         /**
jaroslav@557:          * This method is invoked whenever the value in an entry is
jaroslav@557:          * overwritten by an invocation of put(k,v) for a key k that's already
jaroslav@557:          * in the HashMap.
jaroslav@557:          */
jaroslav@557:         void recordAccess(HashMap<K,V> m) {
jaroslav@557:         }
jaroslav@557: 
jaroslav@557:         /**
jaroslav@557:          * This method is invoked whenever the entry is
jaroslav@557:          * removed from the table.
jaroslav@557:          */
jaroslav@557:         void recordRemoval(HashMap<K,V> m) {
jaroslav@557:         }
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Adds a new entry with the specified key, value and hash code to
jaroslav@557:      * the specified bucket.  It is the responsibility of this
jaroslav@557:      * method to resize the table if appropriate.
jaroslav@557:      *
jaroslav@557:      * Subclass overrides this to alter the behavior of put method.
jaroslav@557:      */
jaroslav@557:     void addEntry(int hash, K key, V value, int bucketIndex) {
jaroslav@557:         Entry<K,V> e = table[bucketIndex];
jaroslav@557:         table[bucketIndex] = new Entry<>(hash, key, value, e);
jaroslav@557:         if (size++ >= threshold)
jaroslav@557:             resize(2 * table.length);
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Like addEntry except that this version is used when creating entries
jaroslav@557:      * as part of Map construction or "pseudo-construction" (cloning,
jaroslav@557:      * deserialization).  This version needn't worry about resizing the table.
jaroslav@557:      *
jaroslav@557:      * Subclass overrides this to alter the behavior of HashMap(Map),
jaroslav@557:      * clone, and readObject.
jaroslav@557:      */
jaroslav@557:     void createEntry(int hash, K key, V value, int bucketIndex) {
jaroslav@557:         Entry<K,V> e = table[bucketIndex];
jaroslav@557:         table[bucketIndex] = new Entry<>(hash, key, value, e);
jaroslav@557:         size++;
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     private abstract class HashIterator<E> implements Iterator<E> {
jaroslav@557:         Entry<K,V> next;        // next entry to return
jaroslav@557:         int expectedModCount;   // For fast-fail
jaroslav@557:         int index;              // current slot
jaroslav@557:         Entry<K,V> current;     // current entry
jaroslav@557: 
jaroslav@557:         HashIterator() {
jaroslav@557:             expectedModCount = modCount;
jaroslav@557:             if (size > 0) { // advance to first entry
jaroslav@557:                 Entry[] t = table;
jaroslav@557:                 while (index < t.length && (next = t[index++]) == null)
jaroslav@557:                     ;
jaroslav@557:             }
jaroslav@557:         }
jaroslav@557: 
jaroslav@557:         public final boolean hasNext() {
jaroslav@557:             return next != null;
jaroslav@557:         }
jaroslav@557: 
jaroslav@557:         final Entry<K,V> nextEntry() {
jaroslav@557:             if (modCount != expectedModCount)
jaroslav@557:                 throw new ConcurrentModificationException();
jaroslav@557:             Entry<K,V> e = next;
jaroslav@557:             if (e == null)
jaroslav@557:                 throw new NoSuchElementException();
jaroslav@557: 
jaroslav@557:             if ((next = e.next) == null) {
jaroslav@557:                 Entry[] t = table;
jaroslav@557:                 while (index < t.length && (next = t[index++]) == null)
jaroslav@557:                     ;
jaroslav@557:             }
jaroslav@557:             current = e;
jaroslav@557:             return e;
jaroslav@557:         }
jaroslav@557: 
jaroslav@557:         public void remove() {
jaroslav@557:             if (current == null)
jaroslav@557:                 throw new IllegalStateException();
jaroslav@557:             if (modCount != expectedModCount)
jaroslav@557:                 throw new ConcurrentModificationException();
jaroslav@557:             Object k = current.key;
jaroslav@557:             current = null;
jaroslav@557:             HashMap.this.removeEntryForKey(k);
jaroslav@557:             expectedModCount = modCount;
jaroslav@557:         }
jaroslav@557: 
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     private final class ValueIterator extends HashIterator<V> {
jaroslav@557:         public V next() {
jaroslav@557:             return nextEntry().value;
jaroslav@557:         }
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     private final class KeyIterator extends HashIterator<K> {
jaroslav@557:         public K next() {
jaroslav@557:             return nextEntry().getKey();
jaroslav@557:         }
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
jaroslav@557:         public Map.Entry<K,V> next() {
jaroslav@557:             return nextEntry();
jaroslav@557:         }
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     // Subclass overrides these to alter behavior of views' iterator() method
jaroslav@557:     Iterator<K> newKeyIterator()   {
jaroslav@557:         return new KeyIterator();
jaroslav@557:     }
jaroslav@557:     Iterator<V> newValueIterator()   {
jaroslav@557:         return new ValueIterator();
jaroslav@557:     }
jaroslav@557:     Iterator<Map.Entry<K,V>> newEntryIterator()   {
jaroslav@557:         return new EntryIterator();
jaroslav@557:     }
jaroslav@557: 
jaroslav@557: 
jaroslav@557:     // Views
jaroslav@557: 
jaroslav@557:     private transient Set<Map.Entry<K,V>> entrySet = null;
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Returns a {@link Set} view of the keys contained in this map.
jaroslav@557:      * The set is backed by the map, so changes to the map are
jaroslav@557:      * reflected in the set, and vice-versa.  If the map is modified
jaroslav@557:      * while an iteration over the set is in progress (except through
jaroslav@557:      * the iterator's own <tt>remove</tt> operation), the results of
jaroslav@557:      * the iteration are undefined.  The set supports element removal,
jaroslav@557:      * which removes the corresponding mapping from the map, via the
jaroslav@557:      * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
jaroslav@557:      * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
jaroslav@557:      * operations.  It does not support the <tt>add</tt> or <tt>addAll</tt>
jaroslav@557:      * operations.
jaroslav@557:      */
jaroslav@557:     public Set<K> keySet() {
jaroslav@557:         Set<K> ks = keySet;
jaroslav@557:         return (ks != null ? ks : (keySet = new KeySet()));
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     private final class KeySet extends AbstractSet<K> {
jaroslav@557:         public Iterator<K> iterator() {
jaroslav@557:             return newKeyIterator();
jaroslav@557:         }
jaroslav@557:         public int size() {
jaroslav@557:             return size;
jaroslav@557:         }
jaroslav@557:         public boolean contains(Object o) {
jaroslav@557:             return containsKey(o);
jaroslav@557:         }
jaroslav@557:         public boolean remove(Object o) {
jaroslav@557:             return HashMap.this.removeEntryForKey(o) != null;
jaroslav@557:         }
jaroslav@557:         public void clear() {
jaroslav@557:             HashMap.this.clear();
jaroslav@557:         }
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Returns a {@link Collection} view of the values contained in this map.
jaroslav@557:      * The collection is backed by the map, so changes to the map are
jaroslav@557:      * reflected in the collection, and vice-versa.  If the map is
jaroslav@557:      * modified while an iteration over the collection is in progress
jaroslav@557:      * (except through the iterator's own <tt>remove</tt> operation),
jaroslav@557:      * the results of the iteration are undefined.  The collection
jaroslav@557:      * supports element removal, which removes the corresponding
jaroslav@557:      * mapping from the map, via the <tt>Iterator.remove</tt>,
jaroslav@557:      * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
jaroslav@557:      * <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
jaroslav@557:      * support the <tt>add</tt> or <tt>addAll</tt> operations.
jaroslav@557:      */
jaroslav@557:     public Collection<V> values() {
jaroslav@557:         Collection<V> vs = values;
jaroslav@557:         return (vs != null ? vs : (values = new Values()));
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     private final class Values extends AbstractCollection<V> {
jaroslav@557:         public Iterator<V> iterator() {
jaroslav@557:             return newValueIterator();
jaroslav@557:         }
jaroslav@557:         public int size() {
jaroslav@557:             return size;
jaroslav@557:         }
jaroslav@557:         public boolean contains(Object o) {
jaroslav@557:             return containsValue(o);
jaroslav@557:         }
jaroslav@557:         public void clear() {
jaroslav@557:             HashMap.this.clear();
jaroslav@557:         }
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Returns a {@link Set} view of the mappings contained in this map.
jaroslav@557:      * The set is backed by the map, so changes to the map are
jaroslav@557:      * reflected in the set, and vice-versa.  If the map is modified
jaroslav@557:      * while an iteration over the set is in progress (except through
jaroslav@557:      * the iterator's own <tt>remove</tt> operation, or through the
jaroslav@557:      * <tt>setValue</tt> operation on a map entry returned by the
jaroslav@557:      * iterator) the results of the iteration are undefined.  The set
jaroslav@557:      * supports element removal, which removes the corresponding
jaroslav@557:      * mapping from the map, via the <tt>Iterator.remove</tt>,
jaroslav@557:      * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
jaroslav@557:      * <tt>clear</tt> operations.  It does not support the
jaroslav@557:      * <tt>add</tt> or <tt>addAll</tt> operations.
jaroslav@557:      *
jaroslav@557:      * @return a set view of the mappings contained in this map
jaroslav@557:      */
jaroslav@557:     public Set<Map.Entry<K,V>> entrySet() {
jaroslav@557:         return entrySet0();
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     private Set<Map.Entry<K,V>> entrySet0() {
jaroslav@557:         Set<Map.Entry<K,V>> es = entrySet;
jaroslav@557:         return es != null ? es : (entrySet = new EntrySet());
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
jaroslav@557:         public Iterator<Map.Entry<K,V>> iterator() {
jaroslav@557:             return newEntryIterator();
jaroslav@557:         }
jaroslav@557:         public boolean contains(Object o) {
jaroslav@557:             if (!(o instanceof Map.Entry))
jaroslav@557:                 return false;
jaroslav@557:             Map.Entry<K,V> e = (Map.Entry<K,V>) o;
jaroslav@557:             Entry<K,V> candidate = getEntry(e.getKey());
jaroslav@557:             return candidate != null && candidate.equals(e);
jaroslav@557:         }
jaroslav@557:         public boolean remove(Object o) {
jaroslav@557:             return removeMapping(o) != null;
jaroslav@557:         }
jaroslav@557:         public int size() {
jaroslav@557:             return size;
jaroslav@557:         }
jaroslav@557:         public void clear() {
jaroslav@557:             HashMap.this.clear();
jaroslav@557:         }
jaroslav@557:     }
jaroslav@557: 
jaroslav@557: 
jaroslav@557:     private static final long serialVersionUID = 362498820763181265L;
jaroslav@557: 
jaroslav@557: 
jaroslav@557:     // These methods are used when serializing HashSets
jaroslav@557:     int   capacity()     { return table.length; }
jaroslav@557:     float loadFactor()   { return loadFactor;   }
jaroslav@557: }