diff options
Diffstat (limited to 'libjava/java/util/HashMap.java')
| -rw-r--r-- | libjava/java/util/HashMap.java | 812 |
1 files changed, 483 insertions, 329 deletions
diff --git a/libjava/java/util/HashMap.java b/libjava/java/util/HashMap.java index 4bc88b7..b75718f 100644 --- a/libjava/java/util/HashMap.java +++ b/libjava/java/util/HashMap.java @@ -1,6 +1,6 @@ /* HashMap.java -- a class providing a basic hashtable data structure, mapping Object --> Object - Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc. + Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc. This file is part of GNU Classpath. @@ -37,83 +37,137 @@ import java.io.ObjectOutputStream; // 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. + * 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 casue primary clustering) and - * rehashing (which does not fit very well with Java's method of - * precomputing hash codes) are avoided. + * 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) + * Under ideal circumstances (no collisions), HashMap offers O(1) * performance on most operations (<pre>containsValue()</pre> is, - * of course, O(n)). In the worst case (all keys map to the same + * 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 + * 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." + * <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 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 */ 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. */ - private static final int DEFAULT_CAPACITY = 11; - /** The defaulty load factor; this is explicitly specified by the spec. */ - private static final float DEFAULT_LOAD_FACTOR = 0.75f; + /** + * Default number of buckets. This is the value the JDK 1.3 uses. Some + * early documentation specified this value as 101. That is incorrect. + */ + static final int DEFAULT_CAPACITY = 11; + + /** + * The default load factor; this is explicitly specified by the spec. + */ + static final float DEFAULT_LOAD_FACTOR = 0.75f; + + /** "enum" of iterator types. */ + static final int KEYS = 0, + VALUES = 1, + ENTRIES = 2; + /** + * Compatible with JDK 1.2. + */ private static final long serialVersionUID = 362498820763181265L; - /** - * The rounded product of the capacity and the load factor; when the number + /** + * The rounded product of the capacity and the load factor; when the number * of elements exceeds the threshold, the HashMap calls <pre>rehash()</pre>. * @serial */ int threshold; - /** Load factor of this HashMap: used in computing the threshold. + /** + * Load factor of this HashMap: used in computing the threshold. * @serial */ - float loadFactor = DEFAULT_LOAD_FACTOR; + final float loadFactor; - /** - * Array containing the actual key-value mappings + /** + * Array containing the actual key-value mappings. */ - transient Entry[] buckets; + transient HashEntry[] buckets; - /** - * counts the number of modifications this HashMap has undergone, used + /** + * Counts the number of modifications this HashMap has undergone, used * by Iterators to know when to throw ConcurrentModificationExceptions. */ transient int modCount; - /** the size of this HashMap: denotes the number of key-value pairs */ + /** + * The size of this HashMap: denotes the number of key-value pairs. + */ transient int size; /** * Class to represent an entry in the hash table. Holds a single key-value - * pair. + * pair. This is extended again in LinkedHashMap. See {@link clone()} + * for why this must be Cloneable. */ - static class Entry extends BasicMapEntry + static class HashEntry extends BasicMapEntry implements Cloneable { - Entry next; - - Entry(Object key, Object value) + /** The next entry in the linked list. */ + 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 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 + * Construct a new HashMap with the default capacity (11) and the default * load factor (0.75). */ public HashMap() @@ -122,237 +176,279 @@ public class HashMap extends AbstractMap } /** - * construct a new HashMap from the given Map - * - * every element in Map t will be put into this new HashMap + * 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> * - * @param t 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> + * 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) { - int size = Math.max(m.size() * 2, DEFAULT_CAPACITY); - buckets = new Entry[size]; - threshold = (int) (size * loadFactor); - putAll(m); + this(Math.max(m.size() * 2, DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR); + putAllInternal(m); } /** - * construct a new HashMap with a specific inital capacity - * - * @param initialCapacity the initial capacity of this HashMap (>=0) + * Construct a new HashMap with a specific inital capacity and + * default load factor of 0.75. * - * @throws IllegalArgumentException if (initialCapacity < 0) + * @param initialCapacity the initial capacity of this HashMap (>=0) + * @throws IllegalArgumentException if (initialCapacity < 0) */ - public HashMap(int initialCapacity) throws IllegalArgumentException + public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } /** - * construct a new HashMap with a specific inital capacity and load factor + * Construct a new HashMap with a specific inital capacity and load factor. * - * @param initialCapacity the initial capacity (>=0) - * @param loadFactor the load factor - * - * @throws IllegalArgumentException if (initialCapacity < 0) || - * (loadFactor <= 0) + * @param initialCapacity the initial capacity (>=0) + * @param loadFactor the load factor (>0, not NaN) + * @throws IllegalArgumentException if (initialCapacity < 0) || + * ! (loadFactor > 0.0) */ public HashMap(int initialCapacity, float loadFactor) - throws IllegalArgumentException { if (initialCapacity < 0) - throw new IllegalArgumentException("Illegal Initial Capacity: " - + initialCapacity); - if (loadFactor <= 0) - throw new IllegalArgumentException("Illegal Load Factor: " + loadFactor); + 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 Entry[initialCapacity]; + buckets = new HashEntry[initialCapacity]; this.loadFactor = loadFactor; - this.threshold = (int) (initialCapacity * loadFactor); + threshold = (int) (initialCapacity * loadFactor); } - /** returns the number of kay-value mappings currently in this Map */ + /** + * 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 */ + /** + * Returns true if there are no key-value mappings currently in this Map + * @return <code>size() == 0</code> + */ public boolean isEmpty() { return size == 0; } /** - * returns true if this HashMap contains a value <pre>o</pre>, such that + * Returns true if this HashMap contains a value <pre>o</pre>, such that * <pre>o.equals(value)</pre>. * - * @param value the value to search for in this Hashtable + * @param value the value to search for in this HashMap + * @return true if at least one key maps to the value */ public boolean containsValue(Object value) { - for (int i = 0; i < buckets.length; i++) + for (int i = buckets.length - 1; i >= 0; i--) { - Entry e = buckets[i]; - while (e != null) - { - if (value == null ? e.value == null : value.equals(e.value)) - return true; - e = e.next; - } + HashEntry e = buckets[i]; + while (e != null) + { + if (value == null ? e.value == null : value.equals(e.value)) + return true; + e = e.next; + } } return false; } - /** - * returns true if the supplied object equals (<pre>equals()</pre>) a key - * in this HashMap + /** + * Returns true if the supplied object <pre>equals()</pre> a key + * in this HashMap. * - * @param key the key to search for 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); - Entry e = buckets[idx]; + HashEntry e = buckets[idx]; while (e != null) { if (key == null ? e.key == null : key.equals(e.key)) - return true; - e = e.next; + return true; + e = e.next; } return false; } /** - * return the value in this Hashtable associated with the supplied key, or <pre>null</pre> - * if the key maps to nothing + * Return the value in this HashMap associated with the supplied key, + * or <pre>null</pre> 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 + * @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); - Entry e = buckets[idx]; + HashEntry e = buckets[idx]; while (e != null) { if (key == null ? e.key == null : key.equals(e.key)) - return e.value; - e = e.next; + return e.value; + e = e.next; } return null; } /** - * puts the supplied value into the Map, mapped by the supplied key + * 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 HashMap key used to locate the value - * @param value the value to be stored in the HashMap + * @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) { modCount++; int idx = hash(key); - Entry e = buckets[idx]; - + HashEntry e = buckets[idx]; + while (e != null) { if (key == null ? e.key == null : key.equals(e.key)) - { - Object r = e.value; - e.value = value; - return r; - } - else - { - e = e.next; - } + // Must use this method for necessary bookkeeping in LinkedHashMap. + return e.setValue(value); + else + e = e.next; } - + // At this point, we know we need to add a new entry. if (++size > threshold) { - rehash(); - // Need a new hash value to suit the bigger table. - idx = hash(key); + rehash(); + // Need a new hash value to suit the bigger table. + idx = hash(key); } - e = new Entry(key, value); - + // LinkedHashMap cannot override put(), hence this call. + addEntry(key, value, idx, true); + return null; + } + + /** + * 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; - - return null; } /** - * 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 <pre>null</pre> is returned + * 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 <pre>null</pre> 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 from the HashMap + * @param key the key used to locate the value to remove + * @return whatever the key mapped to, if present */ public Object remove(Object key) { modCount++; int idx = hash(key); - Entry e = buckets[idx]; - Entry last = null; + HashEntry e = buckets[idx]; + HashEntry last = null; while (e != null) { if (key == null ? e.key == null : key.equals(e.key)) - { - if (last == null) - buckets[idx] = e.next; - else - last.next = e.next; - size--; - return e.value; - } - last = e; - e = e.next; + { + 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; } + /** + * 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) { - int msize = m.size(); Iterator itr = m.entrySet().iterator(); - - for (int i=0; i < msize; i++) + + for (int msize = m.size(); msize > 0; msize--) { Map.Entry e = (Map.Entry) itr.next(); - // Optimize in case the Entry is one of our own. - if (e instanceof BasicMapEntry) - { - BasicMapEntry entry = (BasicMapEntry) e; - put(entry.key, entry.value); - } - else - { + // Optimize in case the Entry is one of our own. + if (e instanceof BasicMapEntry) + { + BasicMapEntry entry = (BasicMapEntry) e; + put(entry.key, entry.value); + } + else + { put(e.getKey(), e.getValue()); - } + } } } + /** + * Clears the Map so it has no keys. This is O(1). + */ public void clear() { modCount++; - for (int i=0; i < buckets.length; i++) - { - buckets[i] = null; - } + Arrays.fill(buckets, null); size = 0; } - /** - * returns a shallow clone of this HashMap (i.e. the Map itself is cloned, but - * its contents are not) + /** + * 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() { @@ -363,49 +459,39 @@ public class HashMap extends AbstractMap } catch (CloneNotSupportedException x) { + // This is impossible. } - copy.buckets = new Entry[buckets.length]; - - for (int i=0; i < buckets.length; i++) - { - Entry e = buckets[i]; - Entry last = null; - - while (e != null) - { - if (last == null) - { - copy.buckets[i] = new Entry(e.key, e.value); - last = copy.buckets[i]; - } - else - { - last.next = new Entry(e.key, e.value); - last = last.next; - } - e = e.next; - } - } + copy.buckets = new HashEntry[buckets.length]; + copy.putAllInternal(this); return copy; } - /** returns a "set view" of this HashMap's keys */ + /** + * 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() { - // Create an AbstractSet with custom implementations of those methods that - // can be overriden easily and efficiently. + // Create an AbstractSet with custom implementations of those methods that + // can be overridden easily and efficiently. return new AbstractSet() { public int size() { return size; } - + public Iterator iterator() { - return new HashIterator(HashIterator.KEYS); + // Cannot create the iterator directly, because of LinkedHashMap. + return HashMap.this.iterator(KEYS); } - + public void clear() { HashMap.this.clear(); @@ -415,20 +501,29 @@ public class HashMap extends AbstractMap { return HashMap.this.containsKey(o); } - + public boolean remove(Object o) { // Test against the size of the HashMap to determine if anything - // really got removed. This is neccessary because the return value of - // HashMap.remove() is ambiguous in the null case. + // really got removed. This is neccessary because the return value of + // HashMap.remove() is ambiguous in the null case. int oldsize = size; HashMap.this.remove(o); - return (oldsize != size); + return (oldsize != size); } }; } - - /** Returns a "collection view" (or "bag view") of this HashMap's values. */ + + /** + * 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() { // We don't bother overriding many of the optional methods, as doing so @@ -439,12 +534,13 @@ public class HashMap extends AbstractMap { return size; } - + public Iterator iterator() { - return new HashIterator(HashIterator.VALUES); + // Cannot create the iterator directly, because of LinkedHashMap. + return HashMap.this.iterator(VALUES); } - + public void clear() { HashMap.this.clear(); @@ -452,23 +548,37 @@ public class HashMap extends AbstractMap }; } - /** Returns a "set view" of this HashMap's entries. */ + /** + * 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() { - // Create an AbstractSet with custom implementations of those methods that - // can be overriden easily and efficiently. + // Create an AbstractSet with custom implementations of those methods that + // can be overridden easily and efficiently. return new AbstractSet() { public int size() { return size; } - + public Iterator iterator() { - return new HashIterator(HashIterator.ENTRIES); + // Cannot create the iterator directly, because of LinkedHashMap. + return HashMap.this.iterator(ENTRIES); } - + public void clear() { HashMap.this.clear(); @@ -476,143 +586,184 @@ public class HashMap extends AbstractMap public boolean contains(Object o) { - if (!(o instanceof Map.Entry)) - return false; - Map.Entry me = (Map.Entry) o; - Entry e = getEntry(me); - return (e != null); + return getEntry(o) != null; } - + public boolean remove(Object o) { - if (!(o instanceof Map.Entry)) - return false; - Map.Entry me = (Map.Entry) o; - Entry e = getEntry(me); - if (e != null) - { - HashMap.this.remove(e.key); - return true; - } - return false; + HashEntry e = getEntry(o); + if (e != null) + { + HashMap.this.remove(e.key); + return true; + } + return false; } }; } - - /** Return an index in the buckets array for `key' based on its hashCode() */ - private int hash(Object key) + + /** Helper method that returns an index in the buckets array for `key; + * based on its hashCode(). + * + * @param key the key + * @return the bucket number + */ + int hash(Object key) { - if (key == null) - return 0; - else - return Math.abs(key.hashCode() % buckets.length); + return (key == null) ? 0 : Math.abs(key.hashCode() % buckets.length); } - /** Return an Entry who's key and value equal the supplied Map.Entry. - * This is used by entrySet's contains() and remove() methods. They can't - * use contains(key) and remove(key) directly because that would result - * in entries with the same key but a different value being matched. */ - private Entry getEntry(Map.Entry me) + /** + * 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() + */ + private HashEntry getEntry(Object o) { + if (!(o instanceof Map.Entry)) + return null; + Map.Entry me = (Map.Entry) o; int idx = hash(me.getKey()); - Entry e = buckets[idx]; + HashEntry e = buckets[idx]; while (e != null) { if (e.equals(me)) - return e; - e = e.next; + return e; + e = e.next; } return null; } - - /** - * 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() > threshold. Note that the existing Entry objects are reused in + + /** + * 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() > 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() { - Entry[] oldBuckets = buckets; - + HashEntry[] oldBuckets = buckets; + int newcapacity = (buckets.length * 2) + 1; threshold = (int) (newcapacity * loadFactor); - buckets = new Entry[newcapacity]; - - for (int i = 0; i < oldBuckets.length; i++) + buckets = new HashEntry[newcapacity]; + + for (int i = oldBuckets.length - 1; i >= 0; i--) { - Entry e = oldBuckets[i]; + HashEntry e = oldBuckets[i]; while (e != null) - { - int idx = hash(e.key); - Entry dest = buckets[idx]; - - if (dest != null) - { - while (dest.next != null) - dest = dest.next; - dest.next = e; - } - else - { - buckets[idx] = e; - } - - Entry next = e.next; - e.next = null; - e = next; - } + { + int idx = hash(e.key); + HashEntry dest = buckets[idx]; + + if (dest != null) + { + while (dest.next != null) + dest = dest.next; + dest.next = e; + } + else + { + buckets[idx] = e; + } + + HashEntry next = e.next; + e.next = null; + e = next; + } + } + } + + /** + * 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(). The + * Map constructor and clone() should not call putAll or put, in order to + * be compatible with the JDK implementation with respect to subclasses. + */ + void putAllInternal(Map m) + { + Iterator itr = m.entrySet().iterator(); + + for (int msize = m.size(); msize > 0; msize--) + { + Map.Entry e = (Map.Entry) itr.next(); + Object key = e.getKey(); + int idx = hash(key); + addEntry(key, e.getValue(), idx, false); } } /** * Serializes this object to the given stream. - * @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). + * + * @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 { - // the threshold and loadFactor fields + // Write the threshold and loadFactor fields. s.defaultWriteObject(); s.writeInt(buckets.length); s.writeInt(size); - Iterator it = entrySet().iterator(); + // Avoid creating a wasted Set by creating the iterator directly. + Iterator it = iterator(ENTRIES); while (it.hasNext()) { - Map.Entry entry = (Map.Entry) it.next(); - s.writeObject(entry.getKey()); - s.writeObject(entry.getValue()); + HashEntry entry = (HashEntry) it.next(); + s.writeObject(entry.key); + s.writeObject(entry.value); } } /** * Deserializes this object from the given stream. - * @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). + * + * @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 { - // the threshold and loadFactor fields + // Read the threshold and loadFactor fields. s.defaultReadObject(); - int capacity = s.readInt(); + // Read and use capacity. + buckets = new HashEntry[s.readInt()]; int len = s.readInt(); - size = 0; - modCount = 0; - buckets = new Entry[capacity]; + // Already happens automatically. + // size = 0; + // modCount = 0; - for (int i = 0; i < len; i++) - { - Object key = s.readObject(); - Object value = s.readObject(); - put(key, value); - } + // Read and use key/value pairs. + for ( ; len > 0; len--) + put(s.readObject(), s.readObject()); } /** @@ -620,64 +771,70 @@ public class HashMap extends AbstractMap * This implementation is parameterized to give a sequential view of * keys, values, or entries. * - * @author Jon Zeppieri + * @author Jon Zeppieri */ class HashIterator implements Iterator { - static final int KEYS = 0, - VALUES = 1, - ENTRIES = 2; - - // the type of this Iterator: KEYS, VALUES, or ENTRIES. - int type; - // the number of modifications to the backing Hashtable that we know about. - int knownMod; - // The total number of elements returned by next(). Used to determine if - // there are more elements remaining. - int count; - // Current index in the physical hash table. - int idx; - // The last Entry returned by a next() call. - Entry 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. - Entry next; - - /* construct a new HashtableIterator with the supllied type: - KEYS, VALUES, or ENTRIES */ + /** + * The type of this Iterator: {@link #KEYS}, {@link #VALUES}, + * or {@link #ENTRIES}. + */ + final int type; + /** + * The number of modifications to the backing HashMap that we know about. + */ + int knownMod = modCount; + /** The number of elements remaining to be returned by next(). */ + int count = size; + /** Current index in the physical hash table. */ + int idx = buckets.length; + /** The last Entry returned by a next() call. */ + 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. + */ + 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; - knownMod = HashMap.this.modCount; - count = 0; - idx = buckets.length; } - /** returns true if the Iterator has more elements */ + /** + * 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 != HashMap.this.modCount) - throw new ConcurrentModificationException(); - return count < size; + if (knownMod != modCount) + throw new ConcurrentModificationException(); + return count > 0; } - /** returns the next element in the Iterator's sequential view */ + /** + * 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 != HashMap.this.modCount) - throw new ConcurrentModificationException(); - if (count == size) + if (knownMod != modCount) + throw new ConcurrentModificationException(); + if (count == 0) throw new NoSuchElementException(); - count++; - Entry e = null; - if (next != null) - e = next; + count--; + HashEntry e = next; while (e == null) - { - e = buckets[--idx]; - } + e = buckets[--idx]; next = e.next; last = e; @@ -688,25 +845,22 @@ public class HashMap extends AbstractMap return e; } - /** - * removes from the backing HashMap the last element which was fetched with the - * <pre>next()</pre> method + /** + * Removes from the backing HashMap the last element which was fetched + * with the <pre>next()</pre> method. + * @throws ConcurrentModificationException if the HashMap was modified + * @throws IllegalStateException if called when there is no last element */ public void remove() { - if (knownMod != HashMap.this.modCount) - throw new ConcurrentModificationException(); + if (knownMod != modCount) + throw new ConcurrentModificationException(); if (last == null) - { - throw new IllegalStateException(); - } - else - { - HashMap.this.remove(last.key); - knownMod++; - count--; - last = null; - } + throw new IllegalStateException(); + + HashMap.this.remove(last.key); + knownMod++; + last = null; } } } |