diff options
Diffstat (limited to 'libjava/java/util/Hashtable.java')
| -rw-r--r-- | libjava/java/util/Hashtable.java | 1450 |
1 files changed, 627 insertions, 823 deletions
diff --git a/libjava/java/util/Hashtable.java b/libjava/java/util/Hashtable.java index 2767b5b..92fa48f 100644 --- a/libjava/java/util/Hashtable.java +++ b/libjava/java/util/Hashtable.java @@ -25,14 +25,16 @@ resulting executable to be covered by the GNU General Public License. This exception does not however invalidate any other reasons why the executable file might be covered by the GNU General Public License. */ - package java.util; 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 HashMap. If you fix +// a bug in here, chances are you should make a similar change to the HashMap +// code. /** * a class which implements a Hashtable data structure @@ -57,96 +59,97 @@ import java.io.ObjectStreamField; * Enumeration. The latter can end up in an undefined state if the Hashtable * changes while the Enumeration is open. * + * Unlike HashMap, Hashtable does not accept `null' as a key value. + * * @author Jon Zeppieri - * @version $Revision: 1.7 $ - * @modified $Id: Hashtable.java,v 1.7 2000/03/15 21:59:13 rao Exp $ + * @author Warren Levy + * @author Bryce McKinlay + * @version $Revision: 1.6 $ + * @modified $Id: Hashtable.java,v 1.6 2000/08/19 18:19:42 green Exp $ */ public class Hashtable extends Dictionary implements Map, Cloneable, Serializable { - // STATIC VARIABLES - // ---------------- - - /** - * the default capacity of a Hashtable - * - * This value strikes me as absurdly low, an invitation to all manner of - * hash collisions. Perhaps it should be raised. I set it to 11 since the - * JDK-1.2b4 specification uses that value in the third constructor - * Hashtable(Map t) if the given Map is small. */ - 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; - - // used internally for parameterizing inner classes - private static final int KEYS = 0; - private static final int VALUES = 1; - private static final int ENTRIES = 2; - - // used for serializing instances of this class - private static final ObjectStreamField[] serialPersistentFields = - { new ObjectStreamField("loadFactor", float.class), - new ObjectStreamField("threshold", int.class) }; + /** 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 = 1421746759512286392L; - - // INSTANCE VARIABLES - // ------------------ - - /** the capacity of this Hashtable: denotes the size of the bucket array */ - private int capacity; - - /** the size of this Hashtable: denotes the number of elements currently in - * <pre>this</pre> */ - private int size; - - /** the load factor of this Hashtable: used in computing the threshold */ - private float loadFactor; - - /* the rounded product of the capacity and the load factor; when the - * number of elements exceeds the threshold, the Hashtable calls - * <pre>rehash()</pre> */ - private int threshold; - - /** where the data is actually stored; Bucket implements - * a very simple, lightweight (and hopefully fast) linked-list */ - Bucket[] buckets; - - /** counts the number of modifications this Hashtable has undergone; - * used by Iterators to know when to throw - * ConcurrentModificationExceptions (idea ripped-off from Stuart - * Ballard's AbstractList implementation) */ - int modCount; - - /** - * construct a new Hashtable with the default capacity and the - * default load factor */ + + /** + * The rounded product of the capacity and the load factor; when the number + * of elements exceeds the threshold, the Hashtable calls <pre>rehash()</pre>. + * @serial + */ + int threshold; + + /** Load factor of this Hashtable: used in computing the threshold. + * @serial + */ + float loadFactor = DEFAULT_LOAD_FACTOR; + + /** + * Array containing the actual key-value mappings + */ + transient HashMap.Entry[] buckets; + + /** + * counts the number of modifications this Hashtable has undergone, used + * by Iterators to know when to throw ConcurrentModificationExceptions. + */ + transient int modCount; + + /** the size of this Hashtable: 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. A Hashtable Entry is identical to a HashMap Entry, except that + * `null' is not allowed for keys and values. + */ + static class Entry extends HashMap.Entry + { + Entry(Object key, Object value) + { + super(key, value); + } + + public Object setValue(Object newVal) + { + if (newVal == null) + throw new NullPointerException(); + return super.setValue(newVal); + } + } + + /** + * construct a new Hashtable with the default capacity (11) and the default + * load factor (0.75). + */ public Hashtable() { - init (DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR); + this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR); } - + /** - * construct a new Hashtable with a specific inital capacity and load factor - * - * @param initialCapacity the initial capacity of this Hashtable (>=0) - * @param initialLoadFactor the load factor of this Hashtable - * (a misnomer, really, since the load factor of - * a Hashtable does not change) + * construct a new Hashtable from the given Map * - * @throws IllegalArgumentException if (initialCapacity < 0) || - * (initialLoadFactor > 1.0) || - * (initialLoadFactor <= 0.0) + * every element in Map t will be put into this new Hashtable + * + * @param t a Map whose key / value pairs will be put into + * the new Hashtable. <b>NOTE: key / value pairs + * are not cloned in this constructor</b> */ - public Hashtable(int initialCapacity, float initialLoadFactor) - throws IllegalArgumentException + public Hashtable(Map m) { - if (initialCapacity < 0 || initialLoadFactor <= 0 || initialLoadFactor > 1) - throw new IllegalArgumentException(); - else - init(initialCapacity, initialLoadFactor); + int size = Math.max(m.size() * 2, DEFAULT_CAPACITY); + buckets = new Entry[size]; + threshold = (int) (size * loadFactor); + putAll(m); } - + /** * construct a new Hashtable with a specific inital capacity * @@ -154,66 +157,55 @@ public class Hashtable extends Dictionary * * @throws IllegalArgumentException if (initialCapacity < 0) */ - public Hashtable(int initialCapacity) - throws IllegalArgumentException + public Hashtable(int initialCapacity) throws IllegalArgumentException { - if (initialCapacity < 0) - throw new IllegalArgumentException(); - else - init(initialCapacity, DEFAULT_LOAD_FACTOR); + this(initialCapacity, DEFAULT_LOAD_FACTOR); } - + /** - * construct a new Hashtable from the given Map - * - * every element in Map t will be put into this new Hashtable + * construct a new Hashtable with a specific inital capacity and load factor * - * @param t a Map whose key / value pairs will be put into - * the new Hashtable. <b>NOTE: key / value pairs - * are not cloned in this constructor</b> + * @param initialCapacity the initial capacity (>=0) + * @param loadFactor the load factor + * + * @throws IllegalArgumentException if (initialCapacity < 0) || + * (initialLoadFactor > 1.0) || + * (initialLoadFactor <= 0.0) */ - public Hashtable(Map t) + public Hashtable(int initialCapacity, float loadFactor) + throws IllegalArgumentException { - int mapSize = t.size() * 2; - init (((mapSize > DEFAULT_CAPACITY) ? mapSize : DEFAULT_CAPACITY), - DEFAULT_LOAD_FACTOR); - putAll (t); + 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 key / value pairs stored in this Hashtable */ - public synchronized int size() + + /** Returns the number of key-value mappings currently in this Map */ + public int size() { return size; } - - /** returns true if this Hashtable is empty (size() == 0), false otherwise */ - public synchronized boolean isEmpty() + + /** returns true if there are no key-value mappings currently in this Map */ + public boolean isEmpty() { return size == 0; } - - /** returns an Enumeration of the keys in this Hashtable - * - * <b>WARNING: if a Hashtable is changed while an Enumeration is - * iterating over it, the behavior of the Enumeration is undefined. - * Use keySet().iterator() if you want to be safe.</b> */ + + /** */ public synchronized Enumeration keys() { - return new HashtableEnumeration(KEYS); + return new Enumerator(Enumerator.KEYS); } - /** - * returns an Enumeration of the values in this Hashtable - * - * <b>WARNING: if a Hashtable is changed while an Enumeration is - * iterating over it, the behavior of the Enumeration is undefined. - * Use values().ieterator() if you want to be safe.</b> */ public synchronized Enumeration elements() { - return new HashtableEnumeration(VALUES); + return new Enumerator(Enumerator.VALUES); } - + /** * returns true if this Hashtable contains a value <pre>o</pre>, * such that <pre>o.equals(value)</pre>. @@ -224,325 +216,350 @@ public class Hashtable extends Dictionary * * @param value the value to search for in this Hashtable * - * @throws NullPointerException if <pre>value</pre> is null */ - public boolean contains(Object value) throws NullPointerException - { - if (value == null) - throw new NullPointerException(); - else - return containsValue(value); - } - - /** - * behaves identically to <pre>contains()</pre>, except it does not - * throw a NullPointerException when given a null argument (Note: - * Sun's implementation (JDK1.2beta4) <i>does</i> throw a - * NullPointerException when given a null argument, but this seems - * to go against the Collections Framework specifications, so I have - * not reproduced this behavior. I have submitted a bug report to - * Sun on the mater, but have not received any response yet (26 - * September 1998) - * - * @param value the value to search for in this Hashtable */ - public synchronized boolean containsValue(Object value) + * @throws NullPointerException if <pre>value</pre> is null + */ + public synchronized boolean contains(Object value) { - int i; - Bucket list; - - for (i = 0; i < capacity; i++) + for (int i = 0; i < buckets.length; i++) { - list = buckets[i]; - if (list != null && list.containsValue(value)) - return true; + HashMap.Entry e = buckets[i]; + while (e != null) + { + if (value.equals(e.value)) + return true; + e = e.next; + } } return false; } - + /** - * returns true if the supplied key is found in this Hashtable - * (strictly, if there exists a key <pre>k</pre> in the Hashtable, - * such that <pre>k.equals(key)</pre>) + * returns true if this Hashtable contains a value <pre>o</pre>, such that + * <pre>o.equals(value)</pre>. * - * @param key the key to search for in this Hashtable */ - public synchronized boolean containsKey(Object key) + * @param value the value to search for in this Hashtable + * + * @throws NullPointerException if <pre>value</pre> is null + */ + public boolean containsValue(Object value) { - return (internalGet(key) != null); + return contains(value); } - - /** - * a private method used by inner class HashtableSet to implement - * its own <pre>contains(Map.Entry)</pre> method; returns true if - * the supplied key / value pair is found in this Hashtable (again, - * using <pre>equals()</pre>, rather than <pre>==</pre>) + + /** + * returns true if the supplied object equals (<pre>equals()</pre>) a key + * in this Hashtable * - * @param entry a Map.Entry to match against key / value pairs in - * this Hashtable */ - private synchronized boolean containsEntry(Map.Entry entry) + * @param key the key to search for in this Hashtable + */ + public synchronized boolean containsKey(Object key) { - Object o; - if (entry == null) + int idx = hash(key); + HashMap.Entry e = buckets[idx]; + while (e != null) { - return false; - } - else - { - o = internalGet(entry.getKey()); - return (o != null && o.equals(entry.getValue())); + if (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 + + /** + * 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 */ + * @param key the key for which to fetch an associated value + */ public synchronized Object get(Object key) { - return internalGet(key); - } - - /** - * 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 Object internalGet(Object key) - { - Bucket list; - if (key == null || size == 0) + int idx = hash(key); + HashMap.Entry e = buckets[idx]; + while (e != null) { - return null; - } - else - { - list = buckets[hash(key)]; - return (list == null) ? null : list.getValueByKey(key); + if (key.equals(e.key)) + return e.value; + e = e.next; } + return null; } - - /** - * increases the size of the Hashtable and rehashes all keys to new - * array indices; this is called when the addition of a new value - * would cause size() > threshold */ - protected void rehash() + + /** + * puts the supplied value into the Map, mapped by the supplied key + * + * @param key the key used to locate the value + * @param value the value to be stored in the table + */ + public synchronized Object put(Object key, Object value) { - 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++) + int idx = hash(key); + HashMap.Entry e = buckets[idx]; + HashMap.Entry last = e; // Final entry in bucket's linked list, if any. + + // Hashtable does not accept null values. This method doesn't dereference + // `value' anywhere, so check for it explicitly. + if (value == null) + throw new NullPointerException(); + + while (e != null) { - if (data[i] != null) + if (key.equals(e.key)) { - node = data[i].first; - while (node != null) - { - internalPut(node.getKey(), node.getValue()); - node = node.next; - } + Object r = e.value; + e.value = value; + return r; + } + else + { + last = e; + e = e.next; } } - } - - /** - * puts the supplied value into the Hashtable, mapped by the - * supplied key; neither the key nore the value is allowed to be - * <pre>null</pre>, otherwise a <pre>NullPointerException</pre> will - * be thrown - * - * @param key the Hashtable key used to locate the value - * @param value the value to be stored in the Hashtable */ - public synchronized Object put(Object key, Object value) - throws NullPointerException - { - if (key == null || value == null) - throw new NullPointerException(); - else - return internalPut(key, value); - } - - /** - * A private method with a semi-interesting history (it's at least - * two hours old now); orginally, this functionality was in the - * public <pre>put()</pre> method, but while searching (fruitlessly) - * on the JDC for some clarification of Javasoft's bizarre - * Serialization documentation, I instead came across a JDK bug - * which had been fixed in JDK-1.2b3. Extending Hashtable was a - * pain, because <pre>put()</pre> was apparently being used - * internally by the class when the Hashtable was rehashed, and this - * was causing odd behavior for people who had overridden - * <pre>put()</pre> in a Hashtable subclass. Well, I was also - * calling <pre>put()</pre> internally, and realized that my code - * would have the same problem. [No, I have never looked at the - * Javasoft code; it was just the easiest thing to do]. So I put - * the real work in a private method, and I call <i>this</i> for - * internal use. Except...not all the time. What about - * <pre>putAll()</pre>? Well, it seems reasonably clear from the - * Collections spec that <pre>putAll()</pre> is <i>supposed</i> to - * call <pre>put()</pre>. So, it still does. Confused yet? - * - * @param key the Hashtable key used to locate the value - * @param value the value to be stored in the Hashtable */ - private Object internalPut(Object key, Object value) - { - HashtableEntry entry; - Bucket list; - int hashIndex; - Object oResult; - modCount++; - if (size == threshold) - rehash(); - entry = new HashtableEntry(key, value); - hashIndex = hash(key); - list = buckets[hashIndex]; - if (list == null) + // At this point, we know we need to add a new entry. + if (++size > threshold) { - list = new Bucket(); - buckets[hashIndex] = list; - } - oResult = list.add(entry); - if (oResult == null) - { - size++; - return null; + 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 - { - return oResult; - } + buckets[idx] = e; + + return null; } - + /** - * removes from the Hashtable and returns the value which is mapped - * by the supplied key; if the key maps to nothing, then the - * Hashtable remains unchanged, and <pre>null</pre> is returned + * removes from the table and returns the value which is mapped by the + * supplied key; if the key maps to nothing, then the table remains + * unchanged, and <pre>null</pre> is returned * - * @param key the key used to locate the value to remove from the Hashtable */ + * @param key the key used to locate the value to remove + */ public synchronized Object remove(Object key) { - Bucket list; - int index; - Object result = null; - if (key != null && size > 0) + modCount++; + int idx = hash(key); + HashMap.Entry e = buckets[idx]; + HashMap.Entry last = null; + + while (e != null) { - index = hash(key); - list = buckets[index]; - if (list != null) + if (key.equals(e.key)) { - result = list.removeByKey(key); - if (result != null) - { - size--; - modCount++; - if (list.first == null) - buckets[index] = null; - } + if (last == null) + buckets[idx] = e.next; + else + last.next = e.next; + size--; + return e.value; } + last = e; + e = e.next; } - return result; + return null; } - - /** - * part of the Map interface; for each Map.Entry in t, the key/value - * pair is added to this Hashtable, <b>using the <pre>put()</pre> - * method -- this may not be you want, so be warned (see notes to - * <pre>internalPut()</pre>, above</b> - * - * @param t a Map whose key/value pairs will be added to this Hashtable */ - public synchronized void putAll(Map t) throws NullPointerException + + public synchronized void putAll(Map m) { - Map.Entry entry; - Iterator it = t.entrySet().iterator(); - while (it.hasNext()) + int msize = m.size(); + Iterator itr = m.entrySet().iterator(); + + for (int i=0; i < msize; i++) { - entry = (Map.Entry) it.next(); - put(entry.getKey(), entry.getValue()); + 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 + { + put(e.getKey(), e.getValue()); + } } } - - /** empties this Hashtable of all elements */ public synchronized void clear() { - size = 0; modCount++; - buckets = new Bucket[capacity]; + for (int i=0; i < buckets.length; i++) + { + buckets[i] = null; + } + size = 0; } - + /** - * returns a shallow clone of this Hashtable (i.e. the Hashtable - * itself is cloned, but its contents are not) */ + * returns a shallow clone of this Hashtable (i.e. the Map itself is cloned, + * but its contents are not) + */ public synchronized Object clone() { - Map.Entry entry; - Iterator it = entrySet().iterator(); - Hashtable clone = new Hashtable(capacity, loadFactor); - while (it.hasNext()) + Hashtable copy = null; + try + { + copy = (Hashtable) super.clone(); + } + catch (CloneNotSupportedException x) + { + } + copy.buckets = new Entry[buckets.length]; + + for (int i=0; i < buckets.length; i++) { - entry = (Map.Entry) it.next(); - clone.internalPut(entry.getKey(), entry.getValue()); + HashMap.Entry e = buckets[i]; + HashMap.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 clone; + return copy; } - /** - * returns a String representation of this Hashtable - * - * the String representation of a Hashtable is defined by Sun and - * looks like this: - * <pre> - * {name_1=value_1, name_2=value_2, name_3=value_3, ..., name_N=value_N} - * </pre> - * for N elements in this Hashtable */ public synchronized String toString() { - Map.Entry entry; - Iterator it = entrySet().iterator(); - StringBuffer sb = new StringBuffer("{"); - boolean isFirst = true; - while (it.hasNext()) + Iterator entries = entrySet().iterator(); + StringBuffer r = new StringBuffer("{"); + for (int pos = 0; pos < size; pos++) { - entry = (Map.Entry) it.next(); - if (isFirst) - isFirst = false; - else - sb.append(", "); - sb.append(entry.getKey().toString()).append("=").append(entry.getValue().toString()); + r.append(entries.next()); + if (pos < size - 1) + r.append(", "); } - sb.append("}"); - return sb.toString(); + r.append("}"); + return r.toString(); } - - /** returns a Set of Keys in this Hashtable */ - public synchronized Set keySet() + + /** returns a "set view" of this Hashtable's keys */ + public Set keySet() { - return new HashtableSet(KEYS); + // Create a synchronized AbstractSet with custom implementations of those + // methods that can be overriden easily and efficiently. + Set r = new AbstractSet() + { + public int size() + { + return size; + } + + public Iterator iterator() + { + return new HashIterator(HashIterator.KEYS); + } + + public void clear() + { + Hashtable.this.clear(); + } + + public boolean contains(Object o) + { + return Hashtable.this.containsKey(o); + } + + public boolean remove(Object o) + { + return (Hashtable.this.remove(o) != null); + } + }; + + return Collections.synchronizedSet(r); } - /** - * returns a Set of Map.Entry objects in this Hashtable; - * note, this was called <pre>entries()</pre> prior to JDK-1.2b4 */ - public synchronized Set entrySet() + /** Returns a "collection view" (or "bag view") of this Hashtable's values. + */ + public Collection values() { - return new HashtableSet(ENTRIES); + // We don't bother overriding many of the optional methods, as doing so + // wouldn't provide any significant performance advantage. + Collection r = new AbstractCollection() + { + public int size() + { + return size; + } + + public Iterator iterator() + { + return new HashIterator(HashIterator.VALUES); + } + + public void clear() + { + Hashtable.this.clear(); + } + }; + + return Collections.synchronizedCollection(r); } - - // This is the pre JDK1.2b4 named method for the above - // public Set entries() - // { - // return entrySet(); - // } - - /** returns a Collection of values in this Hashtable */ - public synchronized Collection values() + + /** Returns a "set view" of this Hashtable's entries. */ + public Set entrySet() { - return new HashtableCollection(); + // Create an AbstractSet with custom implementations of those methods that + // can be overriden easily and efficiently. + Set r = new AbstractSet() + { + public int size() + { + return size; + } + + public Iterator iterator() + { + return new HashIterator(HashIterator.ENTRIES); + } + + public void clear() + { + Hashtable.this.clear(); + } + + public boolean contains(Object o) + { + if (!(o instanceof Map.Entry)) + return false; + Map.Entry me = (Map.Entry) o; + HashMap.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; + HashMap.Entry e = getEntry(me); + if (e != null) + { + Hashtable.this.remove(e.key); + return true; + } + return false; + } + }; + + return Collections.synchronizedSet(r); } /** returns true if this Hashtable equals the supplied Object <pre>o</pre>; @@ -555,522 +572,309 @@ public class Hashtable extends Dictionary * for each key in o.keySet(), o.get(key).equals(get(key)) *</pre> */ - public synchronized boolean equals(Object o) + public boolean equals(Object o) { - Map other; - Set keys = keySet(); - Object currentKey; - Iterator it; - if (o instanceof Map) + if (o == this) + return true; + if (!(o instanceof Map)) + return false; + + Map m = (Map) o; + Set s = m.entrySet(); + Iterator itr = entrySet().iterator(); + + if (m.size() != size) + return false; + + for (int pos = 0; pos < size; pos++) { - other = (Map) o; - if (other.keySet().equals(keys)) - { - it = keys.iterator(); - while (it.hasNext()) - { - currentKey = it.next(); - if (!get(currentKey).equals(other.get(currentKey))) - return false; - } - return true; - } + if (!s.contains(itr.next())) + return false; } - return false; + return true; } /** a Map's hashCode is the sum of the hashCodes of all of its Map.Entry objects */ - public synchronized int hashCode() + public int hashCode() { - Iterator it = entrySet().iterator(); - int result = 0; - while (it.hasNext()) - result += it.next().hashCode(); - return result; - } - - /** - * a private method, called by all of the constructors to initialize a new Hashtable - * - * @param initialCapacity the initial capacity of this Hashtable (>=0) - * @param initialLoadFactor the load factor of this Hashtable - * (a misnomer, really, since the load factor of - * a Hashtable 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]; + int hashcode = 0; + Iterator itr = entrySet().iterator(); + for (int pos = 0; pos < size; pos++) + { + hashcode += itr.next().hashCode(); + } + return hashcode; } - /** private -- simply hashes a non-null Object to its array index */ + /** Return an index in the buckets array for `key' based on its hashCode() */ private int hash(Object key) { - return Math.abs(key.hashCode() % capacity); + return Math.abs(key.hashCode() % buckets.length); } - - /** Serialize this Object in a manner which is binary-compatible - with the JDK */ - private void writeObject(ObjectOutputStream s) throws IOException + + private HashMap.Entry getEntry(Map.Entry me) { - ObjectOutputStream.PutField oFields; - Iterator it = entrySet().iterator(); - Map.Entry oEntry; - oFields = s.putFields(); - oFields.put("loadFactor", loadFactor); - oFields.put("threshold", threshold); - s.writeFields(); - - s.writeInt(capacity); - s.writeInt(size); - while (it.hasNext()) + int idx = hash(me.getKey()); + HashMap.Entry e = buckets[idx]; + while (e != null) { - oEntry = (Map.Entry) it.next(); - s.writeObject(oEntry.getKey()); - s.writeObject(oEntry.getValue()); + if (e.equals(me)) + return e; + e = e.next; } + return null; } - /** Deserialize this Object in a manner which is binary-compatible - with the JDK */ - private void readObject(ObjectInputStream s) - throws IOException, ClassNotFoundException + /** + * increases the size of the Hashtable 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. + */ + protected void rehash() { - int i; - int iLen; - Object oKey, oValue; - ObjectInputStream.GetField oFields; - oFields = s.readFields(); - loadFactor = oFields.get("loadFactor", DEFAULT_LOAD_FACTOR); - threshold = oFields.get("threshold", - (int) (DEFAULT_LOAD_FACTOR - * (float) DEFAULT_CAPACITY)); + HashMap.Entry[] oldBuckets = buckets; - capacity = s.readInt(); - iLen = s.readInt(); - size = 0; - modCount = 0; - buckets = new Bucket[capacity]; + int newcapacity = (buckets.length * 2) + 1; + threshold = (int) (newcapacity * loadFactor); + buckets = new Entry[newcapacity]; - for (i = 0; i < iLen; i++) + for (int i = 0; i < oldBuckets.length; i++) { - oKey = s.readObject(); - oValue = s.readObject(); - internalPut(oKey, oValue); + HashMap.Entry e = oldBuckets[i]; + while (e != null) + { + int idx = hash(e.key); + HashMap.Entry dest = buckets[idx]; + + if (dest != null) + { + while (dest.next != null) + dest = dest.next; + dest.next = e; + } + else + { + buckets[idx] = e; + } + + HashMap.Entry next = e.next; + e.next = null; + e = next; + } } } - + /** - * a Hashtable version of Map.Entry -- one thing in this implementation is - * Hashtable-specific: a NullPointerException is thrown if someone calls - * <pre>setValue(null)</pre> - * - * Simply, a key / value pair - * - * @author Jon Zeppieri - * @version $Revision: 1.7 $ - * @modified $Id: Hashtable.java,v 1.7 2000/03/15 21:59:13 rao Exp $ + * 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 static class HashtableEntry extends Bucket.Node implements Map.Entry - { - /** construct a new HastableEntry with the given key and value */ - public HashtableEntry(Object key, Object value) - { - super(key, value); - } - - /** sets the value of this Map.Entry; throws NullPointerException if - * <pre>newValue</pre> is null - * - * @throws NullPointerException if <pre>newValue</pre> is null - */ - public Object setValue(Object newValue) - throws UnsupportedOperationException, ClassCastException, - IllegalArgumentException, NullPointerException - { - if (newValue == null) - throw new NullPointerException(); - else - return super.setValue(newValue); - } - } - - - /** - * an inner class representing an Enumeration view of this - * Hashtable, providing sequential access to its elements; this - * implementation is parameterized to provide access either to the - * keys or to the values in the Hashtable - * - * @author Jon Zeppieri - * @version $Revision: 1.7 $ - * @modified $Id: Hashtable.java,v 1.7 2000/03/15 21:59:13 rao Exp $ */ - private class HashtableEnumeration implements Enumeration - { - /** the type of Enumeration: KEYS or VALUES */ - private int myType; - /** where are we in our iteration over the elements of this Hashtable */ - private int position; - /** our current index into the BucketList array */ - private int bucketIndex; - /** a reference to the specific Bucket at which our "cursor" is positioned */ - private Bucket.Node currentNode; - - /** - * construct a new HashtableEnumeration with the given type of view - * - * @param type KEYS or VALUES: the type of view this Enumeration is - * providing - */ - HashtableEnumeration(int type) - { - myType = type; - position = 0; - bucketIndex = -1; - currentNode = null; - } - - /** - * returns true if not all elements have been retrived from the Enuemration - * - * <b>NOTE: modifications to the backing Hashtable while iterating - * through an Enumeration can result in undefined behavior, as the - * cursor may no longer be appropriately positioned</b> */ - public boolean hasMoreElements() - { - return position < Hashtable.this.size(); - } - - /** - * returns the next element from the Enuemration - * - * <b>NOTE: modifications to the backing Hashtable while iterating - * through an Enumeration can result in undefined behavior, as the - * cursor may no longer be appropriately positioned</b> - * - * @throws NoSuchElementException if there are no more elements left in - * the sequential view */ - public Object nextElement() - { - Bucket list = null; - Object result; - try - { - while (currentNode == null) - { - while (list == null) - list = Hashtable.this.buckets[++bucketIndex]; - currentNode = list.first; - } - result = (myType == KEYS) ? currentNode.getKey() : - currentNode.getValue(); - currentNode = currentNode.next; - } - catch(Exception e) - { - throw new NoSuchElementException(); - } - position++; - return result; - } - } - - /** - * an inner class providing a Set view of a Hashtable; 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.7 $ - * @modified $Id: Hashtable.java,v 1.7 2000/03/15 21:59:13 rao Exp $ */ - private class HashtableSet extends AbstractSet + private void writeObject(ObjectOutputStream s) throws IOException { - /** the type of this Set view: KEYS or ENTRIES */ - private int setType; - - /** construct a new HashtableSet with the supplied view type */ - HashtableSet(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 Hashtable; 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() - { - Hashtable.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 Hashtable.this.containsKey(o); - else - return (o instanceof Map.Entry) ? Hashtable.this.containsEntry((Map.Entry) o) : false; - } - - /** - * returns true if the backing Hashtable is empty (which is the - * only case either a KEYS Set or an ENTRIES Set would be empty) */ - public boolean isEmpty() - { - return Hashtable.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 (Hashtable.this.remove(o) != null); - else - return (o instanceof Map.Entry) ? - (Hashtable.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 Hashtable.this.size(); - } - - /** returns an Iterator over the elements of this Set */ - public Iterator iterator() - { - return new HashtableIterator(setType); - } + // 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()); + } } - + /** - * Like the above Set view, except this one if for values, which are not - * guaranteed to be unique in a Hashtable; this prvides a Bag of values - * in the Hashtable - * - * @author Jon Zeppieri - * @version $Revision: 1.7 $ - * @modified $Id: Hashtable.java,v 1.7 2000/03/15 21:59:13 rao Exp $ + * 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 class HashtableCollection extends AbstractCollection + private void readObject(ObjectInputStream s) + throws IOException, ClassNotFoundException { - /** a trivial contructor for HashtableCollection */ - HashtableCollection() - { - } - - /** - * 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 Set (and from the backing Hashtable) */ - public void clear() - { - Hashtable.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 Hashtable.this.containsValue(o); - } - - /** returns true IFF the Collection has no elements */ - public boolean isEmpty() - { - return Hashtable.this.isEmpty(); - } - - /** returns the size of this Collection */ - public int size() - { - return Hashtable.this.size(); - } - - /** returns an Iterator over the elements in this Collection */ - public Iterator iterator() - { - return new HashtableIterator(VALUES); - } + // 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); + } } - + /** - * Hashtable's version of the JDK-1.2 counterpart to the Enumeration; + * a class which implements the Iterator interface and is used for + * iterating over Hashtables; * 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.7 $ - * @modified $Id: Hashtable.java,v 1.7 2000/03/15 21:59:13 rao Exp $ + * @version $Revision: 1.8 $ + * @modified $Id: HashMap.java,v 1.8 2000/10/26 10:19:00 bryce Exp $ */ - class HashtableIterator implements Iterator - { - /** 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 */ - HashtableIterator(int type) - { - myType = type; - knownMods = Hashtable.this.modCount; - position = 0; - bucketIndex = -1; - currentNode = null; - currentKey = null; - } - - /** - * Stuart Ballard's code: if the backing Hashtable 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() + 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. + HashMap.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. + HashMap.Entry next; + + /* Construct a new HashIterator with the supplied type: + KEYS, VALUES, or ENTRIES */ + HashIterator(int type) { - if (knownMods != Hashtable.this.modCount) - throw new ConcurrentModificationException(); + this.type = type; + knownMod = Hashtable.this.modCount; + count = 0; + idx = buckets.length; } - + /** returns true if the Iterator has more elements */ public boolean hasNext() { - checkMod(); - return position < Hashtable.this.size(); + if (knownMod != Hashtable.this.modCount) + throw new ConcurrentModificationException(); + return count < size; } - - /** returns the next element in the Iterator's sequential view */ + + /** 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 = Hashtable.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(); + if (knownMod != Hashtable.this.modCount) + throw new ConcurrentModificationException(); + if (count == size) + throw new NoSuchElementException(); + count++; + HashMap.Entry e = null; + if (next != null) + e = next; + + while (e == null) + { + e = buckets[--idx]; } - position++; - return result; + + next = e.next; + last = e; + if (type == VALUES) + return e.value; + else if (type == KEYS) + return e.key; + return e; } - + /** - * removes from the backing Hashtable the last element which was - * fetched with the <pre>next()</pre> method */ + * Removes from the backing Hashtable the last element which was fetched + * with the <pre>next()</pre> method. + */ public void remove() { - checkMod(); - if (currentKey == null) + if (knownMod != Hashtable.this.modCount) + throw new ConcurrentModificationException(); + if (last == null) { throw new IllegalStateException(); } else { - Hashtable.this.remove(currentKey); - knownMods++; - position--; - currentKey = null; + Hashtable.this.remove(last.key); + knownMod++; + count--; + last = null; } } } -} - - + /** + * Enumeration view of this Hashtable, providing sequential access to its + * elements; this implementation is parameterized to provide access either + * to the keys or to the values in the Hashtable. + * + * <b>NOTE: Enumeration is not safe if new elements are put in the table as + * this could cause a rehash and we'd completely lose our place. Even + * without a rehash, it is undetermined if a new element added would + * appear in the enumeration. The spec says nothing about this, but + * the "Java Class Libraries" book infers that modifications to the + * hashtable during enumeration causes indeterminate results. Don't do it! + * + * @author Jon Zeppieri + * @version $Revision: 1.6 $ + * @modified $Id: Hashtable.java,v 1.6 2000/08/19 18:19:42 green Exp $ */ + class Enumerator implements Enumeration + { + static final int KEYS = 0; + static final int VALUES = 1; + + int type; + // The total number of elements returned by nextElement(). Used to + // determine if there are more elements remaining. + int count; + // current index in the physical hash table. + int idx; + // the last Entry returned. + HashMap.Entry last; + + Enumerator(int type) + { + this.type = type; + this.count = 0; + this.idx = buckets.length; + } + public boolean hasMoreElements() + { + return count < Hashtable.this.size; + } + public Object nextElement() + { + if (count >= size) + throw new NoSuchElementException(); + count++; + HashMap.Entry e; + if (last != null) + e = last.next; + while (e == null) + { + e = buckets[--idx]; + } + last = e; + if (type == VALUES) + return e.value; + return e.key; + } + } +} |