1 /* Hashtable.java -- a class providing a basic hashtable data structure,
2 mapping Object --> Object
3 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005, 2006
4 Free Software Foundation, Inc.
6 This file is part of GNU Classpath.
8 GNU Classpath is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
13 GNU Classpath is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GNU Classpath; see the file COPYING. If not, write to the
20 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
23 Linking this library statically or dynamically with other modules is
24 making a combined work based on this library. Thus, the terms and
25 conditions of the GNU General Public License cover the whole
28 As a special exception, the copyright holders of this library give you
29 permission to link this library with independent modules to produce an
30 executable, regardless of the license terms of these independent
31 modules, and to copy and distribute the resulting executable under
32 terms of your choice, provided that you also meet, for each linked
33 independent module, the terms and conditions of the license of that
34 module. An independent module is a module which is not derived from
35 or based on this library. If you modify this library, you may extend
36 this exception to your version of the library, but you are not
37 obligated to do so. If you do not wish to do so, delete this
38 exception statement from your version. */
42 import java.io.IOException;
43 import java.io.ObjectInputStream;
44 import java.io.ObjectOutputStream;
45 import java.io.Serializable;
47 // NOTE: This implementation is very similar to that of HashMap. If you fix
48 // a bug in here, chances are you should make a similar change to the HashMap
52 * A class which implements a hashtable data structure.
55 * This implementation of Hashtable uses a hash-bucket approach. That is:
56 * linear probing and rehashing is avoided; instead, each hashed value maps
57 * to a simple linked-list which, in the best case, only has one node.
58 * Assuming a large enough table, low enough load factor, and / or well
59 * implemented hashCode() methods, Hashtable should provide O(1)
60 * insertion, deletion, and searching of keys. Hashtable is O(n) in
61 * the worst case for all of these (if all keys hash to the same bucket).
64 * This is a JDK-1.2 compliant implementation of Hashtable. As such, it
65 * belongs, partially, to the Collections framework (in that it implements
66 * Map). For backwards compatibility, it inherits from the obsolete and
67 * utterly useless Dictionary class.
70 * Being a hybrid of old and new, Hashtable has methods which provide redundant
71 * capability, but with subtle and even crucial differences.
72 * For example, one can iterate over various aspects of a Hashtable with
73 * either an Iterator (which is the JDK-1.2 way of doing things) or with an
74 * Enumeration. The latter can end up in an undefined state if the Hashtable
75 * changes while the Enumeration is open.
78 * Unlike HashMap, Hashtable does not accept `null' as a key value. Also,
79 * all accesses are synchronized: in a single thread environment, this is
80 * expensive, but in a multi-thread environment, this saves you the effort
81 * of extra synchronization. However, the old-style enumerators are not
82 * synchronized, because they can lead to unspecified behavior even if
83 * they were synchronized. You have been warned.
86 * The iterators are <i>fail-fast</i>, meaning that any structural
87 * modification, except for <code>remove()</code> called on the iterator
88 * itself, cause the iterator to throw a
89 * <code>ConcurrentModificationException</code> rather than exhibit
90 * non-deterministic behavior.
92 * @author Jon Zeppieri
94 * @author Bryce McKinlay
95 * @author Eric Blake (ebb9@email.byu.edu)
98 * @see IdentityHashMap
101 * @status updated to 1.4
103 public class Hashtable extends Dictionary
104 implements Map, Cloneable, Serializable
106 // WARNING: Hashtable is a CORE class in the bootstrap cycle. See the
107 // comments in vm/reference/java/lang/Runtime for implications of this fact.
109 /** Default number of buckets. This is the value the JDK 1.3 uses. Some
110 * early documentation specified this value as 101. That is incorrect.
112 private static final int DEFAULT_CAPACITY = 11;
115 * The default load factor; this is explicitly specified by the spec.
117 private static final float DEFAULT_LOAD_FACTOR = 0.75f;
120 * Compatible with JDK 1.0+.
122 private static final long serialVersionUID = 1421746759512286392L;
125 * The rounded product of the capacity and the load factor; when the number
126 * of elements exceeds the threshold, the Hashtable calls
127 * <code>rehash()</code>.
130 private int threshold;
133 * Load factor of this Hashtable: used in computing the threshold.
136 private final float loadFactor;
139 * Array containing the actual key-value mappings.
141 // Package visible for use by nested classes.
142 transient HashEntry[] buckets;
145 * Counts the number of modifications this Hashtable has undergone, used
146 * by Iterators to know when to throw ConcurrentModificationExceptions.
148 // Package visible for use by nested classes.
149 transient int modCount;
152 * The size of this Hashtable: denotes the number of key-value pairs.
154 // Package visible for use by nested classes.
158 * The cache for {@link #keySet()}.
160 private transient Set keys;
163 * The cache for {@link #values()}.
165 private transient Collection values;
168 * The cache for {@link #entrySet()}.
170 private transient Set entries;
173 * Class to represent an entry in the hash table. Holds a single key-value
174 * pair. A Hashtable Entry is identical to a HashMap Entry, except that
175 * `null' is not allowed for keys and values.
177 private static final class HashEntry extends AbstractMap.BasicMapEntry
179 /** The next entry in the linked list. */
183 * Simple constructor.
184 * @param key the key, already guaranteed non-null
185 * @param value the value, already guaranteed non-null
187 HashEntry(Object key, Object value)
194 * @param newVal the new value
195 * @return the prior value
196 * @throws NullPointerException if <code>newVal</code> is null
198 public Object setValue(Object newVal)
201 throw new NullPointerException();
202 return super.setValue(newVal);
207 * Construct a new Hashtable with the default capacity (11) and the default
208 * load factor (0.75).
212 this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
216 * Construct a new Hashtable from the given Map, with initial capacity
217 * the greater of the size of <code>m</code> or the default of 11.
220 * Every element in Map m will be put into this new Hashtable.
222 * @param m a Map whose key / value pairs will be put into
223 * the new Hashtable. <b>NOTE: key / value pairs
224 * are not cloned in this constructor.</b>
225 * @throws NullPointerException if m is null, or if m contains a mapping
229 public Hashtable(Map m)
231 this(Math.max(m.size() * 2, DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR);
236 * Construct a new Hashtable with a specific inital capacity and
237 * default load factor of 0.75.
239 * @param initialCapacity the initial capacity of this Hashtable (>= 0)
240 * @throws IllegalArgumentException if (initialCapacity < 0)
242 public Hashtable(int initialCapacity)
244 this(initialCapacity, DEFAULT_LOAD_FACTOR);
248 * Construct a new Hashtable with a specific initial capacity and
251 * @param initialCapacity the initial capacity (>= 0)
252 * @param loadFactor the load factor (> 0, not NaN)
253 * @throws IllegalArgumentException if (initialCapacity < 0) ||
254 * ! (loadFactor > 0.0)
256 public Hashtable(int initialCapacity, float loadFactor)
258 if (initialCapacity < 0)
259 throw new IllegalArgumentException("Illegal Capacity: "
261 if (! (loadFactor > 0)) // check for NaN too
262 throw new IllegalArgumentException("Illegal Load: " + loadFactor);
264 if (initialCapacity == 0)
266 buckets = new HashEntry[initialCapacity];
267 this.loadFactor = loadFactor;
268 threshold = (int) (initialCapacity * loadFactor);
272 * Returns the number of key-value mappings currently in this hashtable.
275 public synchronized int size()
281 * Returns true if there are no key-value mappings currently in this table.
282 * @return <code>size() == 0</code>
284 public synchronized boolean isEmpty()
290 * Return an enumeration of the keys of this table. There's no point
291 * in synchronizing this, as you have already been warned that the
292 * enumeration is not specified to be thread-safe.
298 public Enumeration keys()
300 return new KeyEnumerator();
304 * Return an enumeration of the values of this table. There's no point
305 * in synchronizing this, as you have already been warned that the
306 * enumeration is not specified to be thread-safe.
312 public Enumeration elements()
314 return new ValueEnumerator();
318 * Returns true if this Hashtable contains a value <code>o</code>,
319 * such that <code>o.equals(value)</code>. This is the same as
320 * <code>containsValue()</code>, and is O(n).
323 * @param value the value to search for in this Hashtable
324 * @return true if at least one key maps to the value
325 * @throws NullPointerException if <code>value</code> is null
326 * @see #containsValue(Object)
327 * @see #containsKey(Object)
329 public synchronized boolean contains(Object value)
332 throw new NullPointerException();
334 for (int i = buckets.length - 1; i >= 0; i--)
336 HashEntry e = buckets[i];
339 if (e.value.equals(value))
349 * Returns true if this Hashtable contains a value <code>o</code>, such that
350 * <code>o.equals(value)</code>. This is the new API for the old
351 * <code>contains()</code>.
353 * @param value the value to search for in this Hashtable
354 * @return true if at least one key maps to the value
355 * @see #contains(Object)
356 * @see #containsKey(Object)
357 * @throws NullPointerException if <code>value</code> is null
360 public boolean containsValue(Object value)
362 // Delegate to older method to make sure code overriding it continues
364 return contains(value);
368 * Returns true if the supplied object <code>equals()</code> a key
371 * @param key the key to search for in this Hashtable
372 * @return true if the key is in the table
373 * @throws NullPointerException if key is null
374 * @see #containsValue(Object)
376 public synchronized boolean containsKey(Object key)
379 HashEntry e = buckets[idx];
382 if (e.key.equals(key))
390 * Return the value in this Hashtable associated with the supplied key,
391 * or <code>null</code> if the key maps to nothing.
393 * @param key the key for which to fetch an associated value
394 * @return what the key maps to, if present
395 * @throws NullPointerException if key is null
396 * @see #put(Object, Object)
397 * @see #containsKey(Object)
399 public synchronized Object get(Object key)
402 HashEntry e = buckets[idx];
405 if (e.key.equals(key))
413 * Puts the supplied value into the Map, mapped by the supplied key.
414 * Neither parameter may be null. The value may be retrieved by any
415 * object which <code>equals()</code> this key.
417 * @param key the key used to locate the value
418 * @param value the value to be stored in the table
419 * @return the prior mapping of the key, or null if there was none
420 * @throws NullPointerException if key or value is null
422 * @see Object#equals(Object)
424 public synchronized Object put(Object key, Object value)
427 HashEntry e = buckets[idx];
429 // Check if value is null since it is not permitted.
431 throw new NullPointerException();
435 if (e.key.equals(key))
437 // Bypass e.setValue, since we already know value is non-null.
448 // At this point, we know we need to add a new entry.
450 if (++size > threshold)
453 // Need a new hash value to suit the bigger table.
457 e = new HashEntry(key, value);
459 e.next = buckets[idx];
466 * Removes from the table and returns the value which is mapped by the
467 * supplied key. If the key maps to nothing, then the table remains
468 * unchanged, and <code>null</code> is returned.
470 * @param key the key used to locate the value to remove
471 * @return whatever the key mapped to, if present
473 public synchronized Object remove(Object key)
476 HashEntry e = buckets[idx];
477 HashEntry last = null;
481 if (e.key.equals(key))
485 buckets[idx] = e.next;
498 * Copies all elements of the given map into this hashtable. However, no
499 * mapping can contain null as key or value. If this table already has
500 * a mapping for a key, the new mapping replaces the current one.
502 * @param m the map to be hashed into this
503 * @throws NullPointerException if m is null, or contains null keys or values
505 public synchronized void putAll(Map m)
507 Iterator itr = m.entrySet().iterator();
509 while (itr.hasNext())
511 Map.Entry e = (Map.Entry) itr.next();
512 // Optimize in case the Entry is one of our own.
513 if (e instanceof AbstractMap.BasicMapEntry)
515 AbstractMap.BasicMapEntry entry = (AbstractMap.BasicMapEntry) e;
516 put(entry.key, entry.value);
520 put(e.getKey(), e.getValue());
526 * Clears the hashtable so it has no keys. This is O(1).
528 public synchronized void clear()
533 Arrays.fill(buckets, null);
539 * Returns a shallow clone of this Hashtable. The Map itself is cloned,
540 * but its contents are not. This is O(n).
544 public synchronized Object clone()
546 Hashtable copy = null;
549 copy = (Hashtable) super.clone();
551 catch (CloneNotSupportedException x)
553 // This is impossible.
555 copy.buckets = new HashEntry[buckets.length];
556 copy.putAllInternal(this);
565 * Converts this Hashtable to a String, surrounded by braces, and with
566 * key/value pairs listed with an equals sign between, separated by a
567 * comma and space. For example, <code>"{a=1, b=2}"</code>.<p>
569 * NOTE: if the <code>toString()</code> method of any key or value
570 * throws an exception, this will fail for the same reason.
572 * @return the string representation
574 public synchronized String toString()
576 // Since we are already synchronized, and entrySet().iterator()
577 // would repeatedly re-lock/release the monitor, we directly use the
578 // unsynchronized EntryIterator instead.
579 Iterator entries = new EntryIterator();
580 StringBuffer r = new StringBuffer("{");
581 for (int pos = size; pos > 0; pos--)
583 r.append(entries.next());
592 * Returns a "set view" of this Hashtable's keys. The set is backed by
593 * the hashtable, so changes in one show up in the other. The set supports
594 * element removal, but not element addition. The set is properly
595 * synchronized on the original hashtable. Sun has not documented the
596 * proper interaction of null with this set, but has inconsistent behavior
597 * in the JDK. Therefore, in this implementation, contains, remove,
598 * containsAll, retainAll, removeAll, and equals just ignore a null key
599 * rather than throwing a {@link NullPointerException}.
601 * @return a set view of the keys
610 // Create a synchronized AbstractSet with custom implementations of
611 // those methods that can be overridden easily and efficiently.
612 Set r = new AbstractSet()
619 public Iterator iterator()
621 return new KeyIterator();
626 Hashtable.this.clear();
629 public boolean contains(Object o)
633 return containsKey(o);
636 public boolean remove(Object o)
638 return Hashtable.this.remove(o) != null;
641 // We must specify the correct object to synchronize upon, hence the
642 // use of a non-public API
643 keys = new Collections.SynchronizedSet(this, r);
649 * Returns a "collection view" (or "bag view") of this Hashtable's values.
650 * The collection is backed by the hashtable, so changes in one show up
651 * in the other. The collection supports element removal, but not element
652 * addition. The collection is properly synchronized on the original
653 * hashtable. Sun has not documented the proper interaction of null with
654 * this set, but has inconsistent behavior in the JDK. Therefore, in this
655 * implementation, contains, remove, containsAll, retainAll, removeAll, and
656 * equals just ignore a null value rather than throwing a
657 * {@link NullPointerException}.
659 * @return a bag view of the values
664 public Collection values()
668 // We don't bother overriding many of the optional methods, as doing so
669 // wouldn't provide any significant performance advantage.
670 Collection r = new AbstractCollection()
677 public Iterator iterator()
679 return new ValueIterator();
684 Hashtable.this.clear();
687 // We must specify the correct object to synchronize upon, hence the
688 // use of a non-public API
689 values = new Collections.SynchronizedCollection(this, r);
695 * Returns a "set view" of this Hashtable's entries. The set is backed by
696 * the hashtable, so changes in one show up in the other. The set supports
697 * element removal, but not element addition. The set is properly
698 * synchronized on the original hashtable. Sun has not documented the
699 * proper interaction of null with this set, but has inconsistent behavior
700 * in the JDK. Therefore, in this implementation, contains, remove,
701 * containsAll, retainAll, removeAll, and equals just ignore a null entry,
702 * or an entry with a null key or value, rather than throwing a
703 * {@link NullPointerException}. However, calling entry.setValue(null)
707 * Note that the iterators for all three views, from keySet(), entrySet(),
708 * and values(), traverse the hashtable in the same sequence.
710 * @return a set view of the entries
716 public Set entrySet()
720 // Create an AbstractSet with custom implementations of those methods
721 // that can be overridden easily and efficiently.
722 Set r = new AbstractSet()
729 public Iterator iterator()
731 return new EntryIterator();
736 Hashtable.this.clear();
739 public boolean contains(Object o)
741 return getEntry(o) != null;
744 public boolean remove(Object o)
746 HashEntry e = getEntry(o);
749 Hashtable.this.remove(e.key);
755 // We must specify the correct object to synchronize upon, hence the
756 // use of a non-public API
757 entries = new Collections.SynchronizedSet(this, r);
763 * Returns true if this Hashtable equals the supplied Object <code>o</code>.
764 * As specified by Map, this is:
766 * (o instanceof Map) && entrySet().equals(((Map) o).entrySet());
769 * @param o the object to compare to
770 * @return true if o is an equal map
773 public boolean equals(Object o)
775 // no need to synchronize, entrySet().equals() does that
778 if (!(o instanceof Map))
781 return entrySet().equals(((Map) o).entrySet());
785 * Returns the hashCode for this Hashtable. As specified by Map, this is
786 * the sum of the hashCodes of all of its Map.Entry objects
788 * @return the sum of the hashcodes of the entries
791 public synchronized int hashCode()
793 // Since we are already synchronized, and entrySet().iterator()
794 // would repeatedly re-lock/release the monitor, we directly use the
795 // unsynchronized EntryIterator instead.
796 Iterator itr = new EntryIterator();
798 for (int pos = size; pos > 0; pos--)
799 hashcode += itr.next().hashCode();
805 * Helper method that returns an index in the buckets array for `key'
806 * based on its hashCode().
809 * @return the bucket number
810 * @throws NullPointerException if key is null
812 private int hash(Object key)
814 // Note: Inline Math.abs here, for less method overhead, and to avoid
815 // a bootstrap dependency, since Math relies on native methods.
816 int hash = key.hashCode() % buckets.length;
817 return hash < 0 ? -hash : hash;
821 * Helper method for entrySet(), which matches both key and value
822 * simultaneously. Ignores null, as mentioned in entrySet().
824 * @param o the entry to match
825 * @return the matching entry, if found, or null
828 // Package visible, for use in nested classes.
829 HashEntry getEntry(Object o)
831 if (! (o instanceof Map.Entry))
833 Object key = ((Map.Entry) o).getKey();
838 HashEntry e = buckets[idx];
849 * A simplified, more efficient internal implementation of putAll(). clone()
850 * should not call putAll or put, in order to be compatible with the JDK
851 * implementation with respect to subclasses.
853 * @param m the map to initialize this from
855 void putAllInternal(Map m)
857 Iterator itr = m.entrySet().iterator();
860 while (itr.hasNext())
863 Map.Entry e = (Map.Entry) itr.next();
864 Object key = e.getKey();
866 HashEntry he = new HashEntry(key, e.getValue());
867 he.next = buckets[idx];
873 * Increases the size of the Hashtable and rehashes all keys to new array
874 * indices; this is called when the addition of a new value would cause
875 * size() > threshold. Note that the existing Entry objects are reused in
876 * the new hash table.
879 * This is not specified, but the new size is twice the current size plus
880 * one; this number is not always prime, unfortunately. This implementation
881 * is not synchronized, as it is only invoked from synchronized methods.
883 protected void rehash()
885 HashEntry[] oldBuckets = buckets;
887 int newcapacity = (buckets.length * 2) + 1;
888 threshold = (int) (newcapacity * loadFactor);
889 buckets = new HashEntry[newcapacity];
891 for (int i = oldBuckets.length - 1; i >= 0; i--)
893 HashEntry e = oldBuckets[i];
896 int idx = hash(e.key);
897 HashEntry dest = buckets[idx];
901 HashEntry next = dest.next;
914 HashEntry next = e.next;
922 * Serializes this object to the given stream.
924 * @param s the stream to write to
925 * @throws IOException if the underlying stream fails
926 * @serialData the <i>capacity</i> (int) that is the length of the
927 * bucket array, the <i>size</i> (int) of the hash map
928 * are emitted first. They are followed by size entries,
929 * each consisting of a key (Object) and a value (Object).
931 private synchronized void writeObject(ObjectOutputStream s)
934 // Write the threshold and loadFactor fields.
935 s.defaultWriteObject();
937 s.writeInt(buckets.length);
939 // Since we are already synchronized, and entrySet().iterator()
940 // would repeatedly re-lock/release the monitor, we directly use the
941 // unsynchronized EntryIterator instead.
942 Iterator it = new EntryIterator();
945 HashEntry entry = (HashEntry) it.next();
946 s.writeObject(entry.key);
947 s.writeObject(entry.value);
952 * Deserializes this object from the given stream.
954 * @param s the stream to read from
955 * @throws ClassNotFoundException if the underlying stream fails
956 * @throws IOException if the underlying stream fails
957 * @serialData the <i>capacity</i> (int) that is the length of the
958 * bucket array, the <i>size</i> (int) of the hash map
959 * are emitted first. They are followed by size entries,
960 * each consisting of a key (Object) and a value (Object).
962 private void readObject(ObjectInputStream s)
963 throws IOException, ClassNotFoundException
965 // Read the threshold and loadFactor fields.
966 s.defaultReadObject();
968 // Read and use capacity.
969 buckets = new HashEntry[s.readInt()];
970 int len = s.readInt();
972 // Read and use key/value pairs.
973 // TODO: should we be defensive programmers, and check for illegal nulls?
975 put(s.readObject(), s.readObject());
979 * A class which implements the Iterator interface and is used for
980 * iterating over Hashtables.
981 * This implementation iterates entries. Subclasses are used to
982 * iterate key and values. It also allows the removal of elements,
983 * as per the Javasoft spec. Note that it is not synchronized; this
984 * is a performance enhancer since it is never exposed externally
985 * and is only used within synchronized blocks above.
987 * @author Jon Zeppieri
988 * @author Fridjof Siebert
990 private class EntryIterator implements Iterator
993 * The number of modifications to the backing Hashtable that we know about.
995 int knownMod = modCount;
996 /** The number of elements remaining to be returned by next(). */
998 /** Current index in the physical hash table. */
999 int idx = buckets.length;
1000 /** The last Entry returned by a next() call. */
1003 * The next entry that should be returned by next(). It is set to something
1004 * if we're iterating through a bucket that contains multiple linked
1005 * entries. It is null if next() needs to find a new bucket.
1010 * Construct a new EtryIterator
1018 * Returns true if the Iterator has more elements.
1019 * @return true if there are more elements
1021 public boolean hasNext()
1027 * Returns the next element in the Iterator's sequential view.
1028 * @return the next element
1029 * @throws ConcurrentModificationException if the hashtable was modified
1030 * @throws NoSuchElementException if there is none
1032 public Object next()
1034 if (knownMod != modCount)
1035 throw new ConcurrentModificationException();
1037 throw new NoSuchElementException();
1053 * Removes from the backing Hashtable the last element which was fetched
1054 * with the <code>next()</code> method.
1055 * @throws ConcurrentModificationException if the hashtable was modified
1056 * @throws IllegalStateException if called when there is no last element
1058 public void remove()
1060 if (knownMod != modCount)
1061 throw new ConcurrentModificationException();
1063 throw new IllegalStateException();
1065 Hashtable.this.remove(last.key);
1069 } // class EntryIterator
1072 * A class which implements the Iterator interface and is used for
1073 * iterating over keys in Hashtables.
1075 * @author Fridtjof Siebert
1077 private class KeyIterator extends EntryIterator
1080 * Returns the next element in the Iterator's sequential view.
1082 * @return the next element
1084 * @throws ConcurrentModificationException if the hashtable was modified
1085 * @throws NoSuchElementException if there is none
1087 public Object next()
1089 return ((HashEntry)super.next()).key;
1091 } // class KeyIterator
1096 * A class which implements the Iterator interface and is used for
1097 * iterating over values in Hashtables.
1099 * @author Fridtjof Siebert
1101 private class ValueIterator extends EntryIterator
1104 * Returns the next element in the Iterator's sequential view.
1106 * @return the next element
1108 * @throws ConcurrentModificationException if the hashtable was modified
1109 * @throws NoSuchElementException if there is none
1111 public Object next()
1113 return ((HashEntry)super.next()).value;
1115 } // class ValueIterator
1118 * Enumeration view of the entries in this Hashtable, providing
1119 * sequential access to its elements.
1121 * <b>NOTE</b>: Enumeration is not safe if new elements are put in the table
1122 * as this could cause a rehash and we'd completely lose our place. Even
1123 * without a rehash, it is undetermined if a new element added would
1124 * appear in the enumeration. The spec says nothing about this, but
1125 * the "Java Class Libraries" book implies that modifications to the
1126 * hashtable during enumeration causes indeterminate results. Don't do it!
1128 * @author Jon Zeppieri
1129 * @author Fridjof Siebert
1131 private class EntryEnumerator implements Enumeration
1133 /** The number of elements remaining to be returned by next(). */
1135 /** Current index in the physical hash table. */
1136 int idx = buckets.length;
1138 * Entry which will be returned by the next nextElement() call. It is
1139 * set if we are iterating through a bucket with multiple entries, or null
1140 * if we must look in the next bucket.
1145 * Construct the enumeration.
1149 // Nothing to do here.
1153 * Checks whether more elements remain in the enumeration.
1154 * @return true if nextElement() will not fail.
1156 public boolean hasMoreElements()
1162 * Returns the next element.
1163 * @return the next element
1164 * @throws NoSuchElementException if there is none.
1166 public Object nextElement()
1169 throw new NoSuchElementException("Hashtable Enumerator");
1182 } // class EntryEnumerator
1186 * Enumeration view of this Hashtable, providing sequential access to its
1189 * <b>NOTE</b>: Enumeration is not safe if new elements are put in the table
1190 * as this could cause a rehash and we'd completely lose our place. Even
1191 * without a rehash, it is undetermined if a new element added would
1192 * appear in the enumeration. The spec says nothing about this, but
1193 * the "Java Class Libraries" book implies that modifications to the
1194 * hashtable during enumeration causes indeterminate results. Don't do it!
1196 * @author Jon Zeppieri
1197 * @author Fridjof Siebert
1199 private final class KeyEnumerator extends EntryEnumerator
1202 * Returns the next element.
1203 * @return the next element
1204 * @throws NoSuchElementException if there is none.
1206 public Object nextElement()
1208 HashEntry entry = (HashEntry) super.nextElement();
1209 Object retVal = null;
1214 } // class KeyEnumerator
1218 * Enumeration view of this Hashtable, providing sequential access to its
1221 * <b>NOTE</b>: Enumeration is not safe if new elements are put in the table
1222 * as this could cause a rehash and we'd completely lose our place. Even
1223 * without a rehash, it is undetermined if a new element added would
1224 * appear in the enumeration. The spec says nothing about this, but
1225 * the "Java Class Libraries" book implies that modifications to the
1226 * hashtable during enumeration causes indeterminate results. Don't do it!
1228 * @author Jon Zeppieri
1229 * @author Fridjof Siebert
1231 private final class ValueEnumerator extends EntryEnumerator
1234 * Returns the next element.
1235 * @return the next element
1236 * @throws NoSuchElementException if there is none.
1238 public Object nextElement()
1240 HashEntry entry = (HashEntry) super.nextElement();
1241 Object retVal = null;
1243 retVal = entry.value;
1246 } // class ValueEnumerator
1248 } // class Hashtable