From d9fd7154ec7908eff8bbbce75651eccf51064ac1 Mon Sep 17 00:00:00 2001 From: Bryce McKinlay Date: Sat, 15 Dec 2001 07:47:03 +0000 Subject: Collections drop from Classpath: 2001-12-15 Bryce McKinlay * java/util/BitSet.java (and): Fix off-by-one bug, don't skip part of the bitset. (andNot): Likewise. (xor): Likewise. 2001-12-15 Bryce McKinlay * java/util/LinkedList.java (LinkedListItr.add): Don't skip the next entry. 2001-12-15 Eric Blake * java/util/TreeMap.java (removeNode): Fix bug in node removal. 2001-12-15 Bryce McKinlay * java/util/AbstractCollection.java (containsAll): Use size of the correct collection for loop bound. * java/util/AbstractList.java (iterator.next): Increment pos after calling get on backing list. (listIterator.next): Likewise. * java/util/LinkedList.java (addLastEntry): Don't increment size before checking for size == 0. (addFirstEntry): Rearrange to match addLastEntry. (add): Do not increment size before inserting the new entry. * java/util/AbstractCollection.java (addAll): Use size of the correct collection for loop bound. 2001-12-15 Bryce McKinlay * java/util/AbstractSet.java (removeAll): Fix scoping thinko. * java/util/HashMap.java (putAllInternal): Set size here. * java/util/Hashtable.java (putAllInternal): New method. Copy contents of a map efficiently without calling put() or putAll(). (Hashtable (map)): Use putAllInternal. (clone): Likewise. 2001-12-15 Eric Blake * java/util/Collections.java: * java/util/Vector.java: * java/util/WeakHashMap.java: Fix spelling errors. 2001-12-15 Eric Blake * java/util/AbstractCollection.java (removeAllInternal), (retainAllInternal): Add hooks for use by ArrayList. * java/util/AbstractList.java: Minor code updates. Fix some scoping. * java/util/AbstractMap.java: ditto * java/util/ArrayList.java (readObject, writeObject): ditto (removeAllInternal, retainAllInternal): Optimize. * java/util/Arrays.java: ditto * java/util/Collections.java: ditto. Change order of parameters to equals(Object, Object) to match specs. * java/util/Dictionary.java: Improve javadoc. (Dictionary): Add explicit constructor. * java/util/HashMap.java: Improve javadoc. Rearrange methods to follow order in JDK. Cleanups related to recent code migration to AbstractMap. Fix some scoping. (entrySet): Cache the result. (modCount): Ensure that this is updated correctly. * java/util/HashSet.java: Improve javadoc. Fix some scoping. (init): Add hooks for LinkedHashSet. (map): Use "" instead of Boolean.TRUE in backing map. Use package-private API where possible for less overhead. (readObject, writeObject): Fix serialization. * java/util/Hashtable.java: Improve javadoc. Fix some scoping. (entrySet, keySet, values): Cache the result. (modCount): Ensure that this is updated correctly. (contains, remove): Fix NullPointer checking to match specs. (class Enumeration): Make more like HashIterator. * java/util/IdentityHashMap.java: Minor code updates. (modCount): Ensure that this is updated correctly. (readObject, writeObject): Fix serialization. * java/util/LinkedHashMap.java: Minor code updates. Cleanups related to recent code migration to AbstractMap. * java/util/LinkedHashSet.java: New file. * java/util/LinkedList.java: (readObject, writeObject): Fix serialization. * java/util/Makefile.am: List recently added files. * java/util/Stack.java: Minor code updates. * java/util/TreeMap.java: Improve javadoc. Overhaul the class to be more efficient. Fix some scoping. Rearrange the methods. (nil): Ensure that this can be thread-safe, and make it a static final. Initialize it to be more useful as a sentinal node. (Node): Specify color in constructor. (deleteFixup, insertFixup): Improve comments and algorithm. (fabricateTree): Redesign with less overhead. (lowestGreaterThan): Add parameter first to make SubMap easier. (removeNode): Patch hole where nil was being modified. Choose predecessor instead of successor so in-place swap works. (class VerifyResult, verifyTree, verifySub, verifyError): Remove this dead code after verifying the class works. (class SubMap): Rewrite several algorithms to avoid problems with comparing nil. * java/util/TreeSet.java: Improve javadoc. Fix some scoping. (clone): Fix ClassCastException when cloning subSet(). (readObject, writeObject): Fix serialization. * java/util/WeakHashMap.java: Improve javadoc. Fix some scoping. (NULL_KEY): Make it compare as null, for ease elsewhere. (Class WeakEntry): Rename from Entry, to avoid shadowing Map.Entry. Add missing toString. (modCount): Ensure that this is updated correctly. (clear, containsValue, keySet, putAll, values, WeakHashMap(Map)): Add missing methods and constructor. 2001-12-15 Eric Blake * java/util/ArrayList.java (checkBoundExclusive), (checkBoundInclusive): Rename from range??clusive, to match AbstractList. * java/util/LinkedList.java (checkBoundsExclusive), (checkBoundsInclusive): ditto * java/util/Vector.java (checkBoundExclusive), (checkBoundInclusive): Move bounds checking into common methods. 2001-12-15 Eric Blake * java/util/AbstractList.java: (modCount): Make sure it is updated in all needed places. * java/util/ArrayList.java: Improve javadoc. Implements RandomAccess. Add serialVersionUID. Reorder methods. (modCount): Make sure it is updated in all needed places. (rangeExclusive, rangeInclusive): Add common methods for bounds check. (isEmpty): Add missing method. * java/util/Collections.java: (class SynchronizedList): Make package visible. * java/util/ConcurrentModificationException.java: Improve javadoc. * java/util/EmptyStackException.java: Improve javadoc. * java/util/LinkedList.java: Improve javadoc. (modCount): Make sure it is updated in all needed places. (rangeExclusive, rangeInclusive): Add common methods for bounds check. * java/util/NoSuchElementException.java: Improve javadoc. * java/util/Stack.java: Improve javadoc. Fix synchronization issues. (modCount): Make sure it is updated in all needed places. * java/util/Vector.java: Improve javadoc. Fix synchronization issues. Implements RandomAccess. Reorder methods. (modCount): Make sure it is updated in all needed places. (setSize): Fix according to specifications: this does not dictate the backing array size. (removeAll, retainAll): Faster implementations. 2001-12-15 Eric Blake * java/util/BitSet.java: Improve javadoc. (cardinality(), clear(), clear(int, int), flip(int)), (flip(int, int), get(int, int), intersects(BitSet), isEmpty()), (nextClearBit(int), nextSetBit(int), set(int, boolean)), (set(int, int), set(int, int, boolean)): Add new JDK 1.4 methods. (clone): Fix so subclasses clone correctly. 2001-12-15 Eric Blake * java/util/AbstractCollection.java: Improve javadoc. (AbstractCollection()): Make constructor protected. (equals(Object, Object), hashCode(Object)): Add utility methods. * java/util/AbstractList.java: Improve javadoc. (AbstractList()): Make constructor protected. (indexOf(Object)): Call listIterator(), not listIterator(int). (iterator()): Follow Sun's requirement to not use listIterator(0). (listIterator(int)): Make AbstractListItr anonymous. (subList(int, int)): Add support for RandomAccess. (SubList.add(int, Object), SubList.remove(Object)): Fix bug with modCount tracking. (SubList.addAll(Collection)): Add missing method. (SubList.listIterator(int)): Fix bugs in indexing, modCount tracking. (class RandomAccessSubList): Add new class. * java/util/AbstractMap.java: Improve javadoc. (keys, values, KEYS, VALUES, ENTRIES): Consolidate common map fields. (AbstractMap()): Make constructor protected. (equals(Object, Object), hashCode(Object)): Add utility methods. (equals(Object)): Change algorithm to entrySet().equals(m.entrySet()), as documented by Sun. (keySet(), values()): Cache the collections. * java/util/AbstractSequentialList.java: Improve javadoc. (AbstractSequentialList()): Make constructor protected. * java/util/AbstractSet.java: Improve javadoc. (AbstractSet()): Make constructor protected. (removeAll(Collection)): Add missing method. * java/util/Arrays.java: Improve javadoc, rearrange method orders. (defaultComparator): Remove, in favor of Collections.compare(Object, Object, Comparator). (binarySearch, equals, sort): Fix natural order comparison of floats and doubles. Also improve Object comparison - when comparator is null, use natural order. (fill, sort): Add missing checks for IllegalArgumentException. (sort, qsort): Fix sorting bugs, rework the code for more legibility. (mergeSort): Inline into sort(Object[], int, int, Comparator). (class ArrayList): Rename from ListImpl, and make compatible with JDK serialization. Add methods which more efficiently override those of AbstractList. * java/util/Collections: Improve javadoc. (isSequential(List)): Add and use a method for deciding between RandomAccess and sequential algorithms on lists. (class Empty*, class Synchronized*, class Unmodifiable*): Make compliant with JDK serializability. (class Singleton*, class CopiesList, class RevereseComparator), (class UnmodifiableMap.UnmodifiableEntrySet), (class *RandomAccessList): New classes for serial compatibility. (class Empty*, class Singleton*, class CopiesList): Add methods which more efficiently override those of Abstract*. (search): Inline into binarySearch(List, Object, Comparator). (binarySearch): Make sequential search only do log(n) comparisons, instead of n. (copy(List, List)): Do bounds checking before starting. (indexOfSubList, lastIndexOfSubList, list, replaceAll, rotate), (swap): Add new JDK 1.4 methods. (binarySearch, max, min, sort): Allow null comparator to represent natural ordering. (reverse(List)): Avoid unnecessary swap. (shuffle(List, Random)): Do shuffle in-place for RandomAccess lists. (SingletonList.get): Fix logic bug. (SingletonMap.entrySet): Make the entry immutable, and cache the returned set. (SynchronizedCollection, SynchronizedMap, UnmodifiableCollection), (UnmodifiableMap): Detect null pointer in construction. (SynchronizedMap, UnmodifiableMap): Cache collection views. * java/util/BasicMapEntry: Improve javadoc. From-SVN: r48035 --- libjava/java/util/HashMap.java | 525 ++++++++++++++++++++++------------------- 1 file changed, 277 insertions(+), 248 deletions(-) (limited to 'libjava/java/util/HashMap.java') diff --git a/libjava/java/util/HashMap.java b/libjava/java/util/HashMap.java index 3b351058a95..dcf7e7e340b 100644 --- a/libjava/java/util/HashMap.java +++ b/libjava/java/util/HashMap.java @@ -53,14 +53,16 @@ import java.io.ObjectOutputStream; *

* * Under ideal circumstances (no collisions), HashMap offers O(1) - * performance on most operations (

containsValue()
is, + * performance on most operations (containsValue() is, * of course, O(n)). In the worst case (all keys map to the same * hash code -- very unlikely), most operations are O(n). *

* * 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." + * does not support "Enumeration views." Also, it is not synchronized; + * if you plan to use it in multiple threads, consider using:
+ * Map m = Collections.synchronizedMap(new HashMap(...)); *

* * The iterators are fail-fast, meaning that any structural @@ -81,6 +83,7 @@ import java.io.ObjectOutputStream; * @see IdentityHashMap * @see Hashtable * @since 1.2 + * @status updated to 1.4 */ public class HashMap extends AbstractMap implements Map, Cloneable, Serializable @@ -88,19 +91,16 @@ public class HashMap extends AbstractMap /** * Default number of buckets. This is the value the JDK 1.3 uses. Some * early documentation specified this value as 101. That is incorrect. + * Package visible for use by HashSet. */ static final int DEFAULT_CAPACITY = 11; /** * The default load factor; this is explicitly specified by the spec. + * Package visible for use by HashSet. */ static final float DEFAULT_LOAD_FACTOR = 0.75f; - /** "enum" of iterator types. */ - static final int KEYS = 0, - VALUES = 1, - ENTRIES = 2; - /** * Compatible with JDK 1.2. */ @@ -108,41 +108,54 @@ public class HashMap extends AbstractMap /** * The rounded product of the capacity and the load factor; when the number - * of elements exceeds the threshold, the HashMap calls 

rehash()
. - * @serial + * of elements exceeds the threshold, the HashMap calls + * rehash(). + * @serial the threshold for rehashing */ - int threshold; + private int threshold; /** * Load factor of this HashMap: used in computing the threshold. - * @serial + * Package visible for use by HashSet. + * @serial the load factor */ final float loadFactor; /** * Array containing the actual key-value mappings. + * Package visible for use by nested and subclasses. */ transient HashEntry[] buckets; /** * Counts the number of modifications this HashMap has undergone, used * by Iterators to know when to throw ConcurrentModificationExceptions. + * Package visible for use by nested and subclasses. */ transient int modCount; /** * The size of this HashMap: denotes the number of key-value pairs. + * Package visible for use by nested and subclasses. */ transient int size; + /** + * The cache for {@link #entrySet()}. + */ + private transient Set entries; + /** * Class to represent an entry in the hash table. Holds a single key-value - * pair. This is extended again in LinkedHashMap. See {@link clone()} - * for why this must be Cloneable. + * pair. Package visible for use by subclass. + * + * @author Eric Blake */ - static class HashEntry extends BasicMapEntry implements Cloneable + static class HashEntry extends BasicMapEntry { - /** The next entry in the linked list. */ + /** + * The next entry in the linked list. Package visible for use by subclass. + */ HashEntry next; /** @@ -158,7 +171,8 @@ public class HashMap extends AbstractMap /** * 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. + * + * @return the value of this key as it is removed */ Object cleanup() { @@ -182,9 +196,8 @@ public class HashMap extends AbstractMap * * 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. NOTE: key / value pairs - * are not cloned in this constructor. + * @param m a Map whose key / value pairs will be put into the new HashMap. + * NOTE: key / value pairs are not cloned in this constructor. * @throws NullPointerException if m is null */ public HashMap(Map m) @@ -197,8 +210,8 @@ public class HashMap extends AbstractMap * Construct a new HashMap with a specific inital capacity and * default load factor of 0.75. * - * @param initialCapacity the initial capacity of this HashMap (>=0) - * @throws IllegalArgumentException if (initialCapacity < 0) + * @param initialCapacity the initial capacity of this HashMap (>=0) + * @throws IllegalArgumentException if (initialCapacity < 0) */ public HashMap(int initialCapacity) { @@ -208,10 +221,10 @@ public class HashMap extends AbstractMap /** * Construct a new HashMap with a specific inital capacity and load factor. * - * @param initialCapacity the initial capacity (>=0) - * @param loadFactor the load factor (>0, not NaN) - * @throws IllegalArgumentException if (initialCapacity < 0) || - * ! (loadFactor > 0.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) { @@ -229,7 +242,8 @@ public class HashMap extends AbstractMap } /** - * 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() @@ -238,7 +252,8 @@ public class HashMap extends AbstractMap } /** - * 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 size() == 0 */ public boolean isEmpty() @@ -247,29 +262,31 @@ public class HashMap extends AbstractMap } /** - * Returns true if this HashMap contains a value 
o
, such that - * 
o.equals(value)
. + * Return the value in this HashMap associated with the supplied key, + * or null 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 value the value to search for in this HashMap - * @return true if at least one key maps to the 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 boolean containsValue(Object value) + public Object get(Object key) { - for (int i = buckets.length - 1; i >= 0; i--) + int idx = hash(key); + HashEntry e = buckets[idx]; + while (e != null) { - HashEntry e = buckets[i]; - while (e != null) - { - if (value == null ? e.value == null : value.equals(e.value)) - return true; - e = e.next; - } + if (equals(key, e.key)) + return e.value; + e = e.next; } - return false; + return null; } /** - * Returns true if the supplied object 
equals()
a key + * Returns true if the supplied object equals() a key * in this HashMap. * * @param key the key to search for in this HashMap @@ -282,37 +299,13 @@ public class HashMap extends AbstractMap HashEntry e = buckets[idx]; while (e != null) { - if (key == null ? e.key == null : key.equals(e.key)) + if (equals(key, e.key)) return true; e = e.next; } return false; } - /** - * Return the value in this HashMap associated with the supplied key, - * or 
null
if the key maps to nothing. NOTE: Since the value - * could also be null, you must use containsKey to see if this key - * actually maps to something. - * - * @param key the key for which to fetch an associated value - * @return what the key maps to, if present - * @see #put(Object, Object) - * @see #containsKey(Object) - */ - public Object get(Object key) - { - int idx = hash(key); - HashEntry e = buckets[idx]; - while (e != null) - { - if (key == null ? e.key == null : key.equals(e.key)) - return e.value; - e = e.next; - } - return null; - } - /** * Puts the supplied value into the Map, mapped by the supplied key. * The value may be retrieved by any object which equals() @@ -328,13 +321,12 @@ public class HashMap extends AbstractMap */ public Object put(Object key, Object value) { - modCount++; int idx = hash(key); HashEntry e = buckets[idx]; while (e != null) { - if (key == null ? e.key == null : key.equals(e.key)) + if (equals(key, e.key)) // Must use this method for necessary bookkeeping in LinkedHashMap. return e.setValue(value); else @@ -342,6 +334,7 @@ public class HashMap extends AbstractMap } // At this point, we know we need to add a new entry. + modCount++; if (++size > threshold) { rehash(); @@ -355,27 +348,36 @@ public class HashMap extends AbstractMap } /** - * Helper method for put, that creates and adds a new Entry. This is - * overridden in LinkedHashMap for bookkeeping purposes. + * 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 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) + * @param m the map to be hashed into this */ - void addEntry(Object key, Object value, int idx, boolean callRemove) + public void putAll(Map m) { - HashEntry e = new HashEntry(key, value); + Iterator itr = m.entrySet().iterator(); - e.next = buckets[idx]; - buckets[idx] = e; + 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 + { + put(e.getKey(), e.getValue()); + } + } } - + /** * Removes from the HashMap and returns the value which is mapped by the * supplied key. If the key maps to nothing, then the HashMap remains - * unchanged, and 
null
is returned. NOTE: Since the value + * unchanged, and null is returned. NOTE: Since the value * could also be null, you must use containsKey to see if you are * actually removing a mapping. * @@ -384,15 +386,15 @@ public class HashMap extends AbstractMap */ public Object remove(Object key) { - modCount++; int idx = hash(key); HashEntry e = buckets[idx]; HashEntry last = null; while (e != null) { - if (key == null ? e.key == null : key.equals(e.key)) + if (equals(key, e.key)) { + modCount++; if (last == null) buckets[idx] = e.next; else @@ -408,40 +410,39 @@ public class HashMap extends AbstractMap } /** - * 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 + * Clears the Map so it has no keys. This is O(1). */ - public void putAll(Map m) + public void clear() { - Iterator itr = m.entrySet().iterator(); - - for (int msize = m.size(); msize > 0; msize--) + if (size != 0) { - 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 - { - put(e.getKey(), e.getValue()); - } + modCount++; + Arrays.fill(buckets, null); + size = 0; } } - + /** - * Clears the Map so it has no keys. This is O(1). + * Returns true if this HashMap contains a value o, such that + * o.equals(value). + * + * @param value the value to search for in this HashMap + * @return true if at least one key maps to the value + * @see containsKey(Object) */ - public void clear() + public boolean containsValue(Object value) { - modCount++; - Arrays.fill(buckets, null); - size = 0; + 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; } /** @@ -463,6 +464,8 @@ public class HashMap extends AbstractMap } copy.buckets = new HashEntry[buckets.length]; copy.putAllInternal(this); + // Clear the entry cache. AbstractMap.clone() does the others. + copy.entries = null; return copy; } @@ -477,41 +480,43 @@ public class HashMap extends AbstractMap */ public Set keySet() { - // 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() - { - // 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 HashMap.this.containsKey(o); - } - - public boolean remove(Object o) + if (keys == null) + // Create an AbstractSet with custom implementations of those methods + // that can be overridden easily and efficiently. + keys = new AbstractSet() { - // 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); - } - }; + 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 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 keys; } /** @@ -526,33 +531,34 @@ public class HashMap extends AbstractMap */ public Collection values() { - // We don't bother overriding many of the optional methods, as doing so - // wouldn't provide any significant performance advantage. - return 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() + 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() { - HashMap.this.clear(); - } - }; + 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. - *

+ * element removal, but not element addition.

* * Note that the iterators for all three views, from keySet(), entrySet(), * and values(), traverse the HashMap in the same sequence. @@ -564,53 +570,62 @@ public class HashMap extends AbstractMap */ public Set entrySet() { - // 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() - { - // 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) + if (entries == null) + // Create an AbstractSet with custom implementations of those methods + // that can be overridden easily and efficiently. + entries = new AbstractSet() { - HashEntry e = getEntry(o); - if (e != null) - { - HashMap.this.remove(e.key); - return true; - } - return false; - } - }; + 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 that returns an index in the buckets array for `key; - * based on its hashCode(). + /** + * Helper method for put, that creates and adds a new Entry. This is + * overridden in LinkedHashMap for bookkeeping purposes. * - * @param key the key - * @return the bucket number + * @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) */ - int hash(Object key) + void addEntry(Object key, Object value, int idx, boolean callRemove) { - return (key == null) ? 0 : Math.abs(key.hashCode() % buckets.length); + HashEntry e = new HashEntry(key, value); + + e.next = buckets[idx]; + buckets[idx] = e; } /** @@ -637,6 +652,52 @@ public class HashMap extends AbstractMap 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(). The + * Map constructor and 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(); + int msize = m.size(); + this.size = msize; + + for (; msize > 0; msize--) + { + 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 @@ -681,35 +742,6 @@ public class HashMap extends AbstractMap } } - /** - * 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. * @@ -757,9 +789,6 @@ public class HashMap extends AbstractMap // Read and use capacity. buckets = new HashEntry[s.readInt()]; int len = s.readInt(); - // Already happens automatically. - // size = 0; - // modCount = 0; // Read and use key/value pairs. for ( ; len > 0; len--) @@ -773,29 +802,29 @@ public class HashMap extends AbstractMap * * @author Jon Zeppieri */ - class HashIterator implements Iterator + private final class HashIterator implements Iterator { /** * The type of this Iterator: {@link #KEYS}, {@link #VALUES}, * or {@link #ENTRIES}. */ - final int type; + private final int type; /** * The number of modifications to the backing HashMap that we know about. */ - int knownMod = modCount; + private int knownMod = modCount; /** The number of elements remaining to be returned by next(). */ - int count = size; + private int count = size; /** Current index in the physical hash table. */ - int idx = buckets.length; + private int idx = buckets.length; /** The last Entry returned by a next() call. */ - HashEntry last; + 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. */ - HashEntry next; + private HashEntry next; /** * Construct a new HashIterator with the supplied type. @@ -840,14 +869,14 @@ public class HashMap extends AbstractMap last = e; if (type == VALUES) return e.value; - else if (type == KEYS) + if (type == KEYS) return e.key; return e; } /** * Removes from the backing HashMap the last element which was fetched - * with the 

next()
method. + * with the next() method. * @throws ConcurrentModificationException if the HashMap was modified * @throws IllegalStateException if called when there is no last element */ @@ -859,8 +888,8 @@ public class HashMap extends AbstractMap throw new IllegalStateException(); HashMap.this.remove(last.key); - knownMod++; last = null; + knownMod++; } } } -- cgit v1.2.3