diff options
Diffstat (limited to 'libjava/java/util/HashMap.java')
| -rw-r--r-- | libjava/java/util/HashMap.java | 1411 |
1 files changed, 655 insertions, 756 deletions
diff --git a/libjava/java/util/HashMap.java b/libjava/java/util/HashMap.java index 5d50660..6e5c434 100644 --- a/libjava/java/util/HashMap.java +++ b/libjava/java/util/HashMap.java @@ -8,7 +8,7 @@ GNU Classpath is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) any later version. - + GNU Classpath is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU @@ -32,7 +32,10 @@ import java.io.IOException; import java.io.Serializable; import java.io.ObjectInputStream; import java.io.ObjectOutputStream; -import java.io.ObjectStreamField; + +// NOTE: This implementation is very similar to that of Hashtable. If you fix +// a bug in here, chances are you should make a similar change to the Hashtable +// code. /** * This class provides a hashtable-backed implementation of the @@ -55,804 +58,700 @@ import java.io.ObjectStreamField; * does not support "Enumeration views." * * @author Jon Zeppieri - * @version $Revision: 1.6 $ - * @modified $Id: HashMap.java,v 1.6 2000/03/15 21:59:13 rao Exp $ + * @author Jochen Hoenicke + * @author Bryce McKinlay + * @version $Revision: 1.8 $ + * @modified $Id: HashMap.java,v 1.8 2000/10/26 10:19:00 bryce Exp $ */ -public class HashMap extends AbstractMap - implements Map, Cloneable, Serializable +public class HashMap extends AbstractMap + implements Map, Cloneable, Serializable { - // STATIC (CLASS) VARIABLES ------------------------------------------ - - /** - * the default capacity for an instance of HashMap -- I think this - * is low, and perhaps it shoudl be raised; Sun's documentation mildly - * suggests that this (11) is the correct value, though - */ - private static final int DEFAULT_CAPACITY = 11; - - /** the default load factor of a HashMap */ - private static final float DEFAULT_LOAD_FACTOR = 0.75F; - - /** used internally to represent the null key */ - private static final HashMap.Null NULL_KEY = new HashMap.Null(); - - /** used internally to parameterize the creation of set/collection views */ - private static final int KEYS = 0; - - /** used internally to parameterize the creation of set/collection views */ - private static final int VALUES = 1; - - /** used internally to parameterize the creation of set/collection views */ - private static final int ENTRIES = 2; - - private static final long serialVersionUID = 362498820763181265L; - - // INSTANCE VARIABLES ------------------------------------------------- - - /** the capacity of this HashMap: denotes the size of the bucket array */ - transient int capacity; - - /** the size of this HashMap: denotes the number of key-value pairs */ - private transient int size; - - /** the load factor of this HashMap: used in computing the threshold - * @serial - */ - float loadFactor; - - /* 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 - */ - private int threshold; - - /** - * this data structure contains the actual key-value mappings; a - * <pre>BucketList</pre> is a lightweight linked list of "Buckets", - * which, in turn, are linked nodes containing a key-value mapping - * and a reference to the "next" Bucket in the list - */ - private transient Bucket[] buckets; - - /** - * counts the number of modifications this HashMap has undergone; used by Iterators - * to know when to throw ConcurrentModificationExceptions (idea ripped-off from - * Stuart Ballard's AbstractList implementation) - */ - private transient int modCount; - - - // CONSTRUCTORS --------------------------------------------------------- + /** 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 Sun */ + private static final float DEFAULT_LOAD_FACTOR = 0.75f; + + private static final long serialVersionUID = 362498820763181265L; + + /** + * The rounded product of the capacity and the load factor; when the number + * of elements exceeds the threshold, the HashMap calls <pre>rehash()</pre>. + * @serial + */ + int threshold; + + /** Load factor of this HashMap: used in computing the threshold. + * @serial + */ + float loadFactor = DEFAULT_LOAD_FACTOR; + + /** + * Array containing the actual key-value mappings + */ + transient Entry[] buckets; + + /** + * 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 */ + transient int size; + + /** + * Class to represent an entry in the hash table. Holds a single key-value + * pair. + */ + static class Entry implements Map.Entry + { + Object key; + Object value; + Entry next; - /** - * construct a new HashMap with the default capacity and the default - * load factor - */ - public HashMap() + Entry(Object key, Object value) { - init(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR); + this.key = key; + this.value = value; } - /** - * construct a new HashMap with a specific inital capacity and load factor - * - * @param initialCapacity the initial capacity of this HashMap (>=0) - * @param initialLoadFactor the load factor of this HashMap - * (a misnomer, really, since the load factor of - * a HashMap does not change) - * - * @throws IllegalArgumentException if (initialCapacity < 0) || - * (initialLoadFactor > 1.0) || - * (initialLoadFactor <= 0.0) - */ - public HashMap(int initialCapacity, float initialLoadFactor) - throws IllegalArgumentException + public boolean equals(Object o) { - if (initialCapacity < 0 || initialLoadFactor <= 0 || initialLoadFactor > 1) - throw new IllegalArgumentException(); - else - init(initialCapacity, initialLoadFactor); - } - - /** - * construct a new HashMap with a specific inital capacity - * - * @param initialCapacity the initial capacity of this HashMap (>=0) - * - * @throws IllegalArgumentException if (initialCapacity < 0) - */ - public HashMap(int initialCapacity) - throws IllegalArgumentException - { - if (initialCapacity < 0) - throw new IllegalArgumentException(); - else - init(initialCapacity, DEFAULT_LOAD_FACTOR); - } - - /** - * construct a new HashMap from the given Map - * - * every element in Map t will be put into this new HashMap - * - * @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> - */ - public HashMap(Map t) - { - int mapSize = t.size() * 2; - init(((mapSize > DEFAULT_CAPACITY) ? mapSize : DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR); - putAll(t); - } - - - // PUBLIC METHODS --------------------------------------------------------- - - /** returns the number of kay-value mappings currently in this Map */ - public int size() - { - return size; - } - - /** returns true if there are no key-value mappings currently in this Map */ - public boolean isEmpty() - { - return size == 0; - } - - /** empties this HashMap of all elements */ - public void clear() - { - size = 0; - modCount++; - buckets = new Bucket[capacity]; - } - - /** - * returns a shallow clone of this HashMap (i.e. the Map itself is cloned, but - * its contents are not) - */ - public Object clone() - { - Map.Entry entry; - Iterator it = entrySet().iterator(); - HashMap clone = new HashMap(capacity, loadFactor); - while (it.hasNext()) - { - entry = (Map.Entry) it.next(); - clone.internalPut(entry.getKey(), entry.getValue()); - } - return clone; - } - - /** returns a "set view" of this HashMap's keys */ - public Set keySet() - { - return new HashMapSet(KEYS); - } - - /** returns a "set view" of this HashMap's entries */ - public Set entrySet() - { - return new HashMapSet(ENTRIES); - } - - /** returns a "collection view" (or "bag view") of this HashMap's values */ - public Collection values() - { - return new HashMapCollection(); - } - - /** - * returns true if the supplied object equals (<pre>equals()</pre>) a key - * in this HashMap - * - * @param key the key to search for in this HashMap - */ - public boolean containsKey(Object key) - { - return (internalGet(key) != null); + if (!(o instanceof Map.Entry)) + return false; + Map.Entry e = (Map.Entry) o; + return (key == null ? e.getKey() == null : key.equals(e.getKey()) + && value == null ? e.getValue() == null : + value.equals(e.getValue())); } - /** - * 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 - */ - public boolean containsValue(Object value) + public Object getKey() { - int i; - Bucket list; - - for (i = 0; i < capacity; i++) - { - list = buckets[i]; - if (list != null && list.containsValue(value)) - return true; - } - return false; + return key; } - /* - * return the value in this Hashtable associated with the supplied key, or <pre>null</pre> - * if the key maps to nothing - * - * @param key the key for which to fetch an associated value - */ - public Object get(Object key) + public Object getValue() { - Map.Entry oResult = internalGet(key); - return (oResult == null) ? null : oResult.getValue(); + return value; } - - /** - * puts the supplied value into the Map, mapped by the supplied key - * - * @param key the HashMap key used to locate the value - * @param value the value to be stored in the HashMap - */ - public Object put(Object key, Object value) + + public int hashCode() { - return internalPut(key, value); + int kc = (key == null ? 0 : key.hashCode()); + int vc = (value == null ? 0 : value.hashCode()); + return kc ^ vc; } - - /** - * 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 - * - * @param key the key used to locate the value to remove from the HashMap - */ - public Object remove(Object key) + + public Object setValue(Object newVal) { - Bucket list; - int index; - Object result = null; - if (size > 0) - { - index = hash(((key == null) ? NULL_KEY : key)); - list = buckets[index]; - if (list != null) - { - result = list.removeByKey(key); - if (result != null) - { - size--; - modCount++; - if (list.first == null) - buckets[index] = null; - } - } - } - return result; + Object r = value; + value = newVal; + return r; } - - - // PRIVATE METHODS ----------------------------------------------------------- - - /** - * puts the given key-value pair into this HashMap; a private method is used - * because it is called by the rehash() method as well as the put() method, - * and if a subclass overrides put(), then rehash would do funky things - * if it called put() - * - * @param key the HashMap key used to locate the value - * @param value the value to be stored in the HashMap - */ - private Object internalPut(Object key, Object value) + + public String toString() { - HashMapEntry entry; - Bucket list; - int hashIndex; - Object oResult; - Object oRealKey = ((key == null) ? NULL_KEY : key); - - entry = new HashMapEntry(oRealKey, value); - hashIndex = hash(oRealKey); - list = buckets[hashIndex]; - if (list == null) + return key + "=" + value; + } + } + + /** + * construct a new HashMap with the default capacity (11) and the default + * load factor (0.75). + */ + public HashMap() + { + this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR); + } + + /** + * construct a new HashMap from the given Map + * + * every element in Map t will be put into this new HashMap + * + * @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> + */ + public HashMap(Map m) + { + int size = Math.max(m.size() * 2, DEFAULT_CAPACITY); + buckets = new Entry[size]; + threshold = (int) (size * loadFactor); + putAll(m); + } + + /** + * construct a new HashMap with a specific inital capacity + * + * @param initialCapacity the initial capacity of this HashMap (>=0) + * + * @throws IllegalArgumentException if (initialCapacity < 0) + */ + public HashMap(int initialCapacity) throws IllegalArgumentException + { + this(initialCapacity, DEFAULT_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) || + * (initialLoadFactor > 1.0) || + * (initialLoadFactor <= 0.0) + */ + public HashMap(int initialCapacity, float loadFactor) + throws IllegalArgumentException + { + if (initialCapacity < 0 || loadFactor <= 0 || loadFactor > 1) + throw new IllegalArgumentException(); + + buckets = new Entry[initialCapacity]; + this.loadFactor = loadFactor; + this.threshold = (int) (initialCapacity * loadFactor); + } + + /** returns the number of kay-value mappings currently in this Map */ + public int size() + { + return size; + } + + /** returns true if there are no key-value mappings currently in this Map */ + public boolean isEmpty() + { + return size == 0; + } + + /** + * 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 + */ + public boolean containsValue(Object value) + { + for (int i = 0; i < buckets.length; i++) + { + Entry e = buckets[i]; + while (e != null) { - list = new Bucket(); - buckets[hashIndex] = list; + 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 + * + * @param key the key to search for in this HashMap + */ + public boolean containsKey(Object key) + { + int idx = hash(key); + Entry e = buckets[idx]; + while (e != null) + { + if (key == null ? e.key == null : key.equals(e.key)) + 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 + * + * @param key the key for which to fetch an associated value + */ + public Object get(Object key) + { + int idx = hash(key); + Entry 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 + * + * @param key the HashMap key used to locate the value + * @param value the value to be stored in the HashMap + */ + public Object put(Object key, Object value) + { + modCount++; + int idx = hash(key); + Entry e = buckets[idx]; + Entry last = e; // Final entry in bucket's linked list, if any. + + while (e != null) + { + if (key == null ? e.key == null : key.equals(e.key)) + { + Object r = e.value; + e.value = value; + return r; } - oResult = list.add(entry); - if (oResult == null) - { - modCount++; - if (size++ == threshold) - rehash(); - return null; - } else - { - // SEH: if key already exists, we don't rehash & we don't update the modCount - // because it is not a "structural" modification - return oResult; - } - } - - /** - * a private method, called by all of the constructors to initialize a new HashMap - * - * @param initialCapacity the initial capacity of this HashMap (>=0) - * @param initialLoadFactor the load factor of this HashMap - * (a misnomer, really, since the load factor of - * a HashMap does not change) - */ - private void init(int initialCapacity, float initialLoadFactor) - { - size = 0; - modCount = 0; - capacity = initialCapacity; - loadFactor = initialLoadFactor; - threshold = (int) ((float) capacity * loadFactor); - buckets = new Bucket[capacity]; - } - - /** private -- simply hashes a non-null Object to its array index */ - private int hash(Object key) - { - return Math.abs(key.hashCode() % capacity); - } - - /** - * 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 - */ - private void rehash() - { - int i; - Bucket[] data = buckets; - Bucket.Node node; - - modCount++; - capacity = (capacity * 2) + 1; - size = 0; - threshold = (int) ((float) capacity * loadFactor); - buckets = new Bucket[capacity]; - for (i = 0; i < data.length; i++) - { - if (data[i] != null) - { - node = data[i].first; - while (node != null) - { - internalPut(node.getKey(), node.getValue()); - node = node.next; - } - } - } - } - - /** - * a private method which does the "dirty work" (or some of it anyway) of fetching a value - * with a key - * - * @param key the key for which to fetch an associated value - */ - private Map.Entry internalGet(Object key) - { - Bucket list; - if (size == 0) - { - return null; - } + { + last = e; + 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); + } + + e = new Entry(key, value); + + if (last != null) + last.next = e; + else + 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 + * + * @param key the key used to locate the value to remove from the HashMap + */ + public Object remove(Object key) + { + modCount++; + int idx = hash(key); + Entry e = buckets[idx]; + Entry 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; + } + return null; + } + + public void putAll(Map m) + { + int msize = m.size(); + Iterator itr = m.entrySet().iterator(); + + for (int i=0; i < msize; i++) + { + Map.Entry e = (Map.Entry) itr.next(); + // Optimize in case the Entry is one of our own. + if (e instanceof Entry) + { + Entry entry = (Entry) e; + put(entry.key, entry.value); + } else - { - list = buckets[hash(((key == null) ? NULL_KEY : key))]; - return (list == null) ? null : list.getEntryByKey(key); - } - } - - /** - * a private method used by inner class HashMapSet to implement its own - * <pre>contains(Map.Entry)</pre> method; returns true if the supplied - * key / value pair is found in this HashMap (again, using <pre>equals()</pre>, - * rather than <pre>==</pre>) - * - * @param entry a Map.Entry to match against key / value pairs in - * this HashMap - */ - private boolean containsEntry(Map.Entry entry) + { + put(e.getKey(), e.getValue()); + } + } + } + + public void clear() + { + modCount++; + for (int i=0; i < buckets.length; i++) + { + buckets[i] = null; + } + size = 0; + } + + /** + * returns a shallow clone of this HashMap (i.e. the Map itself is cloned, but + * its contents are not) + */ + public Object clone() + { + HashMap copy = null; + try + { + copy = (HashMap) super.clone(); + } + catch (CloneNotSupportedException x) + { + } + 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; + } + } + return copy; + } + + /** returns a "set view" of this HashMap's keys */ + public Set keySet() + { + // Create an AbstractSet with custom implementations of those methods that + // can be overriden easily and efficiently. + return new AbstractSet() { - Map.Entry oInternalEntry; - if (entry == null) - { - return false; - } - else - { - oInternalEntry = internalGet(entry.getKey()); - return (oInternalEntry != null && oInternalEntry.equals(entry)); - } - } - - /** - * 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). - */ - private void writeObject(ObjectOutputStream s) - throws IOException + public int size() + { + return size; + } + + public Iterator iterator() + { + return new HashIterator(HashIterator.KEYS); + } + + public void clear() + { + HashMap.this.clear(); + } + + public boolean contains(Object o) + { + 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. + int oldsize = size; + HashMap.this.remove(o); + return (oldsize != size); + } + }; + } + + /** Returns a "collection view" (or "bag view") of this HashMap's values. */ + 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() { - // the fields - s.defaultWriteObject(); - - s.writeInt(capacity); - s.writeInt(size); - Iterator it = entrySet().iterator(); - while (it.hasNext()) - { - Map.Entry oEntry = (Map.Entry) it.next(); - s.writeObject(oEntry.getKey()); - s.writeObject(oEntry.getValue()); - } - } - - /** - * 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). - */ - private void readObject(ObjectInputStream s) - throws IOException, ClassNotFoundException + public int size() + { + return size; + } + + public Iterator iterator() + { + return new HashIterator(HashIterator.VALUES); + } + + public void clear() + { + HashMap.this.clear(); + } + }; + } + + /** Returns a "set view" of this HashMap's entries. */ + public Set entrySet() + { + // Create an AbstractSet with custom implementations of those methods that + // can be overriden easily and efficiently. + return new AbstractSet() { - // the fields - s.defaultReadObject(); - - capacity = s.readInt(); - int iLen = s.readInt(); - size = 0; - modCount = 0; - buckets = new Bucket[capacity]; - - for (int i = 0; i < iLen; i++) - { - Object oKey = s.readObject(); - Object oValue = s.readObject(); - internalPut(oKey, oValue); - } - } - - // INNER CLASSES ------------------------------------------------------------- - // --------------------------------------------------------------------------- + public int size() + { + return size; + } + + public Iterator iterator() + { + return new HashIterator(HashIterator.ENTRIES); + } + + public void clear() + { + HashMap.this.clear(); + } + + 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); + } + + 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; + } + }; + } + + /** Return an index in the buckets array for `key' based on its hashCode() */ + private int hash(Object key) + { + 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) + { + int idx = hash(me.getKey()); + Entry e = buckets[idx]; + while (e != null) + { + if (e.equals(me)) + 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 + * the new hash table. + */ + private void rehash() + { + Entry[] oldBuckets = buckets; - /** - * an inner class providing a Set view of a HashMap; this implementation is - * parameterized to view either a Set of keys or a Set of Map.Entry objects - * - * Note: a lot of these methods are implemented by AbstractSet, and would work - * just fine without any meddling, but far greater efficiency can be gained by - * overriding a number of them. And so I did. - * - * @author Jon Zeppieri - * @version $Revision: 1.6 $ - * @modified $Id: HashMap.java,v 1.6 2000/03/15 21:59:13 rao Exp $ - */ - private class HashMapSet extends AbstractSet - implements Set - { - /** the type of this Set view: KEYS or ENTRIES */ - private int setType; - - /** construct a new HashtableSet with the supplied view type */ - HashMapSet(int type) - { - setType = type; - } - - /** - * adding an element is unsupported; this method simply throws an exception - * - * @throws UnsupportedOperationException - */ - public boolean add(Object o) throws UnsupportedOperationException - { - throw new UnsupportedOperationException(); - } - - /** - * adding an element is unsupported; this method simply throws an exception - * - * @throws UnsupportedOperationException - */ - public boolean addAll(Collection c) throws UnsupportedOperationException - { - throw new UnsupportedOperationException(); - } - - /** - * clears the backing HashMap; this is a prime example of an overridden implementation - * which is far more efficient than its superclass implementation (which uses an iterator - * and is O(n) -- this is an O(1) call) - */ - public void clear() - { - HashMap.this.clear(); - } - - /** - * returns true if the supplied object is contained by this Set - * - * @param o an Object being testing to see if it is in this Set - */ - public boolean contains(Object o) - { - if (setType == KEYS) - return HashMap.this.containsKey(o); - else - return (o instanceof Map.Entry) ? HashMap.this.containsEntry((Map.Entry) o) : false; - } - - /** - * returns true if the backing HashMap is empty (which is the only case either a KEYS - * Set or an ENTRIES Set would be empty) - */ - public boolean isEmpty() - { - return HashMap.this.isEmpty(); - } - - /** - * removes the supplied Object from the Set - * - * @param o the Object to be removed - */ - public boolean remove(Object o) - { - if (setType == KEYS) - return (HashMap.this.remove(o) != null); + int newcapacity = (buckets.length * 2) + 1; + threshold = (int) (newcapacity * loadFactor); + buckets = new Entry[newcapacity]; + + for (int i = 0; i < oldBuckets.length; i++) + { + Entry 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 - return (o instanceof Map.Entry) ? - (HashMap.this.remove(((Map.Entry) o).getKey()) != null) : false; - } - - /** returns the size of this Set (always equal to the size of the backing Hashtable) */ - public int size() - { - return HashMap.this.size(); - } + { + buckets[idx] = e; + } - /** returns an Iterator over the elements of this Set */ - public Iterator iterator() - { - return new HashMapIterator(setType); - } - } - - /** - * Like the above Set view, except this one if for values, which are not - * guaranteed to be unique in a Map; this prvides a Bag of values - * in the HashMap - * - * @author Jon Zeppieri - * @version $Revision: 1.6 $ - * @modified $Id: HashMap.java,v 1.6 2000/03/15 21:59:13 rao Exp $ - */ - private class HashMapCollection extends AbstractCollection - implements Collection + Entry next = e.next; + e.next = null; + e = next; + } + } + } + + /** + * 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). + */ + private void writeObject(ObjectOutputStream s) throws IOException + { + // the threshold and loadFactor fields + s.defaultWriteObject(); + + s.writeInt(buckets.length); + s.writeInt(size); + Iterator it = entrySet().iterator(); + while (it.hasNext()) + { + Map.Entry entry = (Map.Entry) it.next(); + s.writeObject(entry.getKey()); + s.writeObject(entry.getValue()); + } + } + + /** + * 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). + */ + private void readObject(ObjectInputStream s) + throws IOException, ClassNotFoundException + { + // the threshold and loadFactor fields + s.defaultReadObject(); + + int capacity = s.readInt(); + int len = s.readInt(); + size = 0; + modCount = 0; + buckets = new Entry[capacity]; + + for (int i = 0; i < len; i++) + { + Object key = s.readObject(); + Object value = s.readObject(); + put(key, value); + } + } + + /** + * a class which implements the Iterator interface and is used for + * iterating over HashMaps; + * this implementation is parameterized to give a sequential view of + * keys, values, or entries; it also allows the removal of elements, + * as per the Javasoft spec. + * + * @author Jon Zeppieri + * @version $Revision: 1.8 $ + * @modified $Id: HashMap.java,v 1.8 2000/10/26 10:19:00 bryce Exp $ + */ + 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 */ + HashIterator(int type) { - /** a trivial contructor for HashMapCollection */ - HashMapCollection() - { - } - - /** - * adding elements is not supported by this Collection; - * this method merely throws an exception - * - * @throws UnsupportedOperationException - */ - public boolean add(Object o) throws UnsupportedOperationException - { - throw new UnsupportedOperationException(); - } - - /** - * adding elements is not supported by this Collection; - * this method merely throws an exception - * - * @throws UnsupportedOperationException - */ - public boolean addAll(Collection c) throws UnsupportedOperationException - { - throw new UnsupportedOperationException(); - } - - /** removes all elements from this Collection (and from the backing HashMap) */ - public void clear() - { - HashMap.this.clear(); - } - - /** - * returns true if this Collection contains at least one Object which equals() the - * supplied Object - * - * @param o the Object to compare against those in the Set - */ - public boolean contains(Object o) - { - return HashMap.this.containsValue(o); - } - - /** returns true IFF the Collection has no elements */ - public boolean isEmpty() - { - return HashMap.this.isEmpty(); - } - - /** returns the size of this Collection */ - public int size() - { - return HashMap.this.size(); - } - - /** returns an Iterator over the elements in this Collection */ - public Iterator iterator() - { - return new HashMapIterator(VALUES); - } + this.type = type; + knownMod = HashMap.this.modCount; + count = 0; + idx = buckets.length; } - /** - * a class which implements the Iterator interface and is used for - * iterating over HashMaps; - * this implementation is parameterized to give a sequential view of - * keys, values, or entries; it also allows the removal of elements, - * as per the Javasoft spec. - * - * @author Jon Zeppieri - * @version $Revision: 1.6 $ - * @modified $Id: HashMap.java,v 1.6 2000/03/15 21:59:13 rao Exp $ - */ - class HashMapIterator implements Iterator + /** returns true if the Iterator has more elements */ + public boolean hasNext() { - /** the type of this Iterator: KEYS, VALUES, or ENTRIES */ - private int myType; - /** - * the number of modifications to the backing Hashtable for which - * this Iterator can account (idea ripped off from Stuart Ballard) - */ - private int knownMods; - /** the location of our sequential "cursor" */ - private int position; - /** the current index of the BucketList array */ - private int bucketIndex; - /** a reference, originally null, to the specific Bucket our "cursor" is pointing to */ - private Bucket.Node currentNode; - /** a reference to the current key -- used fro removing elements via the Iterator */ - private Object currentKey; - - /** construct a new HashtableIterator with the supllied type: KEYS, VALUES, or ENTRIES */ - HashMapIterator(int type) - { - myType = type; - knownMods = HashMap.this.modCount; - position = 0; - bucketIndex = -1; - currentNode = null; - currentKey = null; - } - - /** - * Stuart Ballard's code: if the backing HashMap has been altered through anything - * but <i>this</i> Iterator's <pre>remove()</pre> method, we will give up right here, - * rather than risking undefined behavior - * - * @throws ConcurrentModificationException - */ - private void checkMod() - { - if (knownMods != HashMap.this.modCount) - throw new ConcurrentModificationException(); - } - - /** returns true if the Iterator has more elements */ - public boolean hasNext() - { - checkMod(); - return position < HashMap.this.size(); - } - - /** returns the next element in the Iterator's sequential view */ - public Object next() - { - Bucket list = null; - Object result; - checkMod(); - try - { - while (currentNode == null) - { - while (list == null) - list = HashMap.this.buckets[++bucketIndex]; - currentNode = list.first; - } - currentKey = currentNode.getKey(); - result = (myType == KEYS) ? currentKey : - ((myType == VALUES) ? currentNode.getValue() : currentNode); - currentNode = currentNode.next; - } - catch(Exception e) - { - throw new NoSuchElementException(); - } - position++; - return result; - } - - /** - * removes from the backing HashMap the last element which was fetched with the - * <pre>next()</pre> method - */ - public void remove() - { - checkMod(); - if (currentKey == null) - { - throw new IllegalStateException(); - } - else - { - HashMap.this.remove(currentKey); - knownMods++; - position--; - currentKey = null; - } - } + if (knownMod != HashMap.this.modCount) + throw new ConcurrentModificationException(); + return count < size; } - /** - * a singleton instance of this class (HashMap.NULL_KEY) - * is used to represent the null key in HashMap objects - * - * @author Jon Zeppieri - * @version $Revision: 1.6 $ - * @modified $Id: HashMap.java,v 1.6 2000/03/15 21:59:13 rao Exp $ - */ - private static class Null + /** returns the next element in the Iterator's sequential view */ + public Object next() { - /** trivial constructor */ - Null() - { + if (knownMod != HashMap.this.modCount) + throw new ConcurrentModificationException(); + if (count == size) + throw new NoSuchElementException(); + count++; + Entry e = null; + if (next != null) + e = next; + + while (e == null) + { + e = buckets[--idx]; } + + next = e.next; + last = e; + if (type == VALUES) + return e.value; + else if (type == KEYS) + return e.key; + return e; } - /** - * a HashMap version of Map.Entry -- one thing in this implementation is - * HashMap-specific: if the key is HashMap.NULL_KEY, getKey() will return - * null - * - * Simply, a key / value pair - * - * @author Jon Zeppieri - * @version $Revision: 1.6 $ - * @modified $Id: HashMap.java,v 1.6 2000/03/15 21:59:13 rao Exp $ + /** + * removes from the backing HashMap the last element which was fetched with the + * <pre>next()</pre> method */ - private static class HashMapEntry extends Bucket.Node implements Map.Entry + public void remove() { - /** construct a new HashMapEntry with the given key and value */ - public HashMapEntry(Object key, Object value) + if (knownMod != HashMap.this.modCount) + throw new ConcurrentModificationException(); + if (last == null) { - super(key, value); + throw new IllegalStateException(); } - - /** - * if the key == HashMap.NULL_KEY, null is returned, otherwise the actual - * key is returned - */ - public Object getKey() + else { - Object oResult = super.getKey(); - return (oResult == HashMap.NULL_KEY) ? null : oResult; + HashMap.this.remove(last.key); + knownMod++; + count--; + last = null; } } - // EOF ----------------------------------------------------------------------- + } } |