1 /* Hashtable.java -- a class providing a basic hashtable data structure,
2 mapping Object --> Object
3 Copyright (C) 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
5 This file is part of GNU Classpath.
7 GNU Classpath is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GNU Classpath is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU Classpath; see the file COPYING. If not, write to the
19 Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
22 Linking this library statically or dynamically with other modules is
23 making a combined work based on this library. Thus, the terms and
24 conditions of the GNU General Public License cover the whole
27 As a special exception, the copyright holders of this library give you
28 permission to link this library with independent modules to produce an
29 executable, regardless of the license terms of these independent
30 modules, and to copy and distribute the resulting executable under
31 terms of your choice, provided that you also meet, for each linked
32 independent module, the terms and conditions of the license of that
33 module. An independent module is a module which is not derived from
34 or based on this library. If you modify this library, you may extend
35 this exception to your version of the library, but you are not
36 obligated to do so. If you do not wish to do so, delete this
37 exception statement from your version. */
41 import java
.io
.IOException
;
42 import java
.io
.Serializable
;
43 import java
.io
.ObjectInputStream
;
44 import java
.io
.ObjectOutputStream
;
46 // NOTE: This implementation is very similar to that of HashMap. If you fix
47 // a bug in here, chances are you should make a similar change to the HashMap
51 * A class which implements a hashtable data structure.
54 * This implementation of Hashtable uses a hash-bucket approach. That is:
55 * linear probing and rehashing is avoided; instead, each hashed value maps
56 * to a simple linked-list which, in the best case, only has one node.
57 * Assuming a large enough table, low enough load factor, and / or well
58 * implemented hashCode() methods, Hashtable should provide O(1)
59 * insertion, deletion, and searching of keys. Hashtable is O(n) in
60 * the worst case for all of these (if all keys hash to the same bucket).
63 * This is a JDK-1.2 compliant implementation of Hashtable. As such, it
64 * belongs, partially, to the Collections framework (in that it implements
65 * Map). For backwards compatibility, it inherits from the obsolete and
66 * utterly useless Dictionary class.
69 * Being a hybrid of old and new, Hashtable has methods which provide redundant
70 * capability, but with subtle and even crucial differences.
71 * For example, one can iterate over various aspects of a Hashtable with
72 * either an Iterator (which is the JDK-1.2 way of doing things) or with an
73 * Enumeration. The latter can end up in an undefined state if the Hashtable
74 * changes while the Enumeration is open.
77 * Unlike HashMap, Hashtable does not accept `null' as a key value. Also,
78 * all accesses are synchronized: in a single thread environment, this is
79 * expensive, but in a multi-thread environment, this saves you the effort
80 * of extra synchronization. However, the old-style enumerators are not
81 * synchronized, because they can lead to unspecified behavior even if
82 * they were synchronized. You have been warned.
85 * The iterators are <i>fail-fast</i>, meaning that any structural
86 * modification, except for <code>remove()</code> called on the iterator
87 * itself, cause the iterator to throw a
88 * <code>ConcurrentModificationException</code> rather than exhibit
89 * non-deterministic behavior.
91 * @author Jon Zeppieri
93 * @author Bryce McKinlay
94 * @author Eric Blake <ebb9@email.byu.edu>
97 * @see IdentityHashMap
100 * @status updated to 1.4
102 public class Hashtable
extends Dictionary
103 implements Map
, Cloneable
, Serializable
105 // WARNING: Hashtable is a CORE class in the bootstrap cycle. See the
106 // comments in vm/reference/java/lang/Runtime for implications of this fact.
108 /** Default number of buckets. This is the value the JDK 1.3 uses. Some
109 * early documentation specified this value as 101. That is incorrect.
111 private static final int DEFAULT_CAPACITY
= 11;
113 /** An "enum" of iterator types. */
114 // Package visible for use by nested classes.
115 static final int KEYS
= 0,
120 * The default load factor; this is explicitly specified by the spec.
122 private static final float DEFAULT_LOAD_FACTOR
= 0.75f
;
125 * Compatible with JDK 1.0+.
127 private static final long serialVersionUID
= 1421746759512286392L;
130 * The rounded product of the capacity and the load factor; when the number
131 * of elements exceeds the threshold, the Hashtable calls
132 * <code>rehash()</code>.
135 private int threshold
;
138 * Load factor of this Hashtable: used in computing the threshold.
141 private final float loadFactor
;
144 * Array containing the actual key-value mappings.
146 // Package visible for use by nested classes.
147 transient HashEntry
[] buckets
;
150 * Counts the number of modifications this Hashtable has undergone, used
151 * by Iterators to know when to throw ConcurrentModificationExceptions.
153 // Package visible for use by nested classes.
154 transient int modCount
;
157 * The size of this Hashtable: denotes the number of key-value pairs.
159 // Package visible for use by nested classes.
163 * The cache for {@link #keySet()}.
165 private transient Set keys
;
168 * The cache for {@link #values()}.
170 private transient Collection values
;
173 * The cache for {@link #entrySet()}.
175 private transient Set entries
;
178 * Class to represent an entry in the hash table. Holds a single key-value
179 * pair. A Hashtable Entry is identical to a HashMap Entry, except that
180 * `null' is not allowed for keys and values.
182 private static final class HashEntry
extends AbstractMap
.BasicMapEntry
184 /** The next entry in the linked list. */
188 * Simple constructor.
189 * @param key the key, already guaranteed non-null
190 * @param value the value, already guaranteed non-null
192 HashEntry(Object key
, Object value
)
199 * @param newValue the new value
200 * @return the prior value
201 * @throws NullPointerException if <code>newVal</code> is null
203 public Object
setValue(Object newVal
)
206 throw new NullPointerException();
207 return super.setValue(newVal
);
212 * Construct a new Hashtable with the default capacity (11) and the default
213 * load factor (0.75).
217 this(DEFAULT_CAPACITY
, DEFAULT_LOAD_FACTOR
);
221 * Construct a new Hashtable from the given Map, with initial capacity
222 * the greater of the size of <code>m</code> or the default of 11.
225 * Every element in Map m will be put into this new Hashtable.
227 * @param m a Map whose key / value pairs will be put into
228 * the new Hashtable. <b>NOTE: key / value pairs
229 * are not cloned in this constructor.</b>
230 * @throws NullPointerException if m is null, or if m contains a mapping
234 public Hashtable(Map m
)
236 this(Math
.max(m
.size() * 2, DEFAULT_CAPACITY
), DEFAULT_LOAD_FACTOR
);
241 * Construct a new Hashtable with a specific inital capacity and
242 * default load factor of 0.75.
244 * @param initialCapacity the initial capacity of this Hashtable (>= 0)
245 * @throws IllegalArgumentException if (initialCapacity < 0)
247 public Hashtable(int initialCapacity
)
249 this(initialCapacity
, DEFAULT_LOAD_FACTOR
);
253 * Construct a new Hashtable with a specific initial capacity and
256 * @param initialCapacity the initial capacity (>= 0)
257 * @param loadFactor the load factor (> 0, not NaN)
258 * @throws IllegalArgumentException if (initialCapacity < 0) ||
259 * ! (loadFactor > 0.0)
261 public Hashtable(int initialCapacity
, float loadFactor
)
263 if (initialCapacity
< 0)
264 throw new IllegalArgumentException("Illegal Capacity: "
266 if (! (loadFactor
> 0)) // check for NaN too
267 throw new IllegalArgumentException("Illegal Load: " + loadFactor
);
269 if (initialCapacity
== 0)
271 buckets
= new HashEntry
[initialCapacity
];
272 this.loadFactor
= loadFactor
;
273 threshold
= (int) (initialCapacity
* loadFactor
);
277 * Returns the number of key-value mappings currently in this hashtable.
280 public synchronized int size()
286 * Returns true if there are no key-value mappings currently in this table.
287 * @return <code>size() == 0</code>
289 public synchronized boolean isEmpty()
295 * Return an enumeration of the keys of this table. There's no point
296 * in synchronizing this, as you have already been warned that the
297 * enumeration is not specified to be thread-safe.
303 public Enumeration
keys()
305 return new Enumerator(KEYS
);
309 * Return an enumeration of the values of this table. There's no point
310 * in synchronizing this, as you have already been warned that the
311 * enumeration is not specified to be thread-safe.
317 public Enumeration
elements()
319 return new Enumerator(VALUES
);
323 * Returns true if this Hashtable contains a value <code>o</code>,
324 * such that <code>o.equals(value)</code>. This is the same as
325 * <code>containsValue()</code>, and is O(n).
328 * @param value the value to search for in this Hashtable
329 * @return true if at least one key maps to the value
330 * @throws NullPointerException if <code>value</code> is null
331 * @see #containsValue(Object)
332 * @see #containsKey(Object)
334 public synchronized boolean contains(Object value
)
336 for (int i
= buckets
.length
- 1; i
>= 0; i
--)
338 HashEntry e
= buckets
[i
];
341 if (value
.equals(e
.value
))
347 // Must throw on null argument even if the table is empty
349 throw new NullPointerException();
355 * Returns true if this Hashtable contains a value <code>o</code>, such that
356 * <code>o.equals(value)</code>. This is the new API for the old
357 * <code>contains()</code>.
359 * @param value the value to search for in this Hashtable
360 * @return true if at least one key maps to the value
361 * @see #contains(Object)
362 * @see #containsKey(Object)
363 * @throws NullPointerException if <code>value</code> is null
366 public boolean containsValue(Object value
)
368 // Delegate to older method to make sure code overriding it continues
370 return contains(value
);
374 * Returns true if the supplied object <code>equals()</code> a key
377 * @param key the key to search for in this Hashtable
378 * @return true if the key is in the table
379 * @throws NullPointerException if key is null
380 * @see #containsValue(Object)
382 public synchronized boolean containsKey(Object key
)
385 HashEntry e
= buckets
[idx
];
388 if (key
.equals(e
.key
))
396 * Return the value in this Hashtable associated with the supplied key,
397 * or <code>null</code> if the key maps to nothing.
399 * @param key the key for which to fetch an associated value
400 * @return what the key maps to, if present
401 * @throws NullPointerException if key is null
402 * @see #put(Object, Object)
403 * @see #containsKey(Object)
405 public synchronized Object
get(Object key
)
408 HashEntry e
= buckets
[idx
];
411 if (key
.equals(e
.key
))
419 * Puts the supplied value into the Map, mapped by the supplied key.
420 * Neither parameter may be null. The value may be retrieved by any
421 * object which <code>equals()</code> this key.
423 * @param key the key used to locate the value
424 * @param value the value to be stored in the table
425 * @return the prior mapping of the key, or null if there was none
426 * @throws NullPointerException if key or value is null
428 * @see Object#equals(Object)
430 public synchronized Object
put(Object key
, Object value
)
433 HashEntry e
= buckets
[idx
];
435 // Check if value is null since it is not permitted.
437 throw new NullPointerException();
441 if (key
.equals(e
.key
))
443 // Bypass e.setValue, since we already know value is non-null.
454 // At this point, we know we need to add a new entry.
456 if (++size
> threshold
)
459 // Need a new hash value to suit the bigger table.
463 e
= new HashEntry(key
, value
);
465 e
.next
= buckets
[idx
];
472 * Removes from the table and returns the value which is mapped by the
473 * supplied key. If the key maps to nothing, then the table remains
474 * unchanged, and <code>null</code> is returned.
476 * @param key the key used to locate the value to remove
477 * @return whatever the key mapped to, if present
479 public synchronized Object
remove(Object key
)
482 HashEntry e
= buckets
[idx
];
483 HashEntry last
= null;
487 if (key
.equals(e
.key
))
491 buckets
[idx
] = e
.next
;
504 * Copies all elements of the given map into this hashtable. However, no
505 * mapping can contain null as key or value. If this table already has
506 * a mapping for a key, the new mapping replaces the current one.
508 * @param m the map to be hashed into this
509 * @throws NullPointerException if m is null, or contains null keys or values
511 public synchronized void putAll(Map m
)
513 Iterator itr
= m
.entrySet().iterator();
515 while (itr
.hasNext())
517 Map
.Entry e
= (Map
.Entry
) itr
.next();
518 // Optimize in case the Entry is one of our own.
519 if (e
instanceof AbstractMap
.BasicMapEntry
)
521 AbstractMap
.BasicMapEntry entry
= (AbstractMap
.BasicMapEntry
) e
;
522 put(entry
.key
, entry
.value
);
526 put(e
.getKey(), e
.getValue());
532 * Clears the hashtable so it has no keys. This is O(1).
534 public synchronized void clear()
539 Arrays
.fill(buckets
, null);
545 * Returns a shallow clone of this Hashtable. The Map itself is cloned,
546 * but its contents are not. This is O(n).
550 public synchronized Object
clone()
552 Hashtable copy
= null;
555 copy
= (Hashtable
) super.clone();
557 catch (CloneNotSupportedException x
)
559 // This is impossible.
561 copy
.buckets
= new HashEntry
[buckets
.length
];
562 copy
.putAllInternal(this);
571 * Converts this Hashtable to a String, surrounded by braces, and with
572 * key/value pairs listed with an equals sign between, separated by a
573 * comma and space. For example, <code>"{a=1, b=2}"</code>.<p>
575 * NOTE: if the <code>toString()</code> method of any key or value
576 * throws an exception, this will fail for the same reason.
578 * @return the string representation
580 public synchronized String
toString()
582 // Since we are already synchronized, and entrySet().iterator()
583 // would repeatedly re-lock/release the monitor, we directly use the
584 // unsynchronized HashIterator instead.
585 Iterator entries
= new HashIterator(ENTRIES
);
586 StringBuffer r
= new StringBuffer("{");
587 for (int pos
= size
; pos
> 0; pos
--)
589 r
.append(entries
.next());
598 * Returns a "set view" of this Hashtable's keys. The set is backed by
599 * the hashtable, so changes in one show up in the other. The set supports
600 * element removal, but not element addition. The set is properly
601 * synchronized on the original hashtable. Sun has not documented the
602 * proper interaction of null with this set, but has inconsistent behavior
603 * in the JDK. Therefore, in this implementation, contains, remove,
604 * containsAll, retainAll, removeAll, and equals just ignore a null key
605 * rather than throwing a {@link NullPointerException}.
607 * @return a set view of the keys
616 // Create a synchronized AbstractSet with custom implementations of
617 // those methods that can be overridden easily and efficiently.
618 Set r
= new AbstractSet()
625 public Iterator
iterator()
627 return new HashIterator(KEYS
);
632 Hashtable
.this.clear();
635 public boolean contains(Object o
)
639 return containsKey(o
);
642 public boolean remove(Object o
)
644 return Hashtable
.this.remove(o
) != null;
647 // We must specify the correct object to synchronize upon, hence the
648 // use of a non-public API
649 keys
= new Collections
.SynchronizedSet(this, r
);
655 * Returns a "collection view" (or "bag view") of this Hashtable's values.
656 * The collection is backed by the hashtable, so changes in one show up
657 * in the other. The collection supports element removal, but not element
658 * addition. The collection is properly synchronized on the original
659 * hashtable. Sun has not documented the proper interaction of null with
660 * this set, but has inconsistent behavior in the JDK. Therefore, in this
661 * implementation, contains, remove, containsAll, retainAll, removeAll, and
662 * equals just ignore a null value rather than throwing a
663 * {@link NullPointerException}.
665 * @return a bag view of the values
670 public Collection
values()
674 // We don't bother overriding many of the optional methods, as doing so
675 // wouldn't provide any significant performance advantage.
676 Collection r
= new AbstractCollection()
683 public Iterator
iterator()
685 return new HashIterator(VALUES
);
690 Hashtable
.this.clear();
693 // We must specify the correct object to synchronize upon, hence the
694 // use of a non-public API
695 values
= new Collections
.SynchronizedCollection(this, r
);
701 * Returns a "set view" of this Hashtable's entries. The set is backed by
702 * the hashtable, so changes in one show up in the other. The set supports
703 * element removal, but not element addition. The set is properly
704 * synchronized on the original hashtable. Sun has not documented the
705 * proper interaction of null with this set, but has inconsistent behavior
706 * in the JDK. Therefore, in this implementation, contains, remove,
707 * containsAll, retainAll, removeAll, and equals just ignore a null entry,
708 * or an entry with a null key or value, rather than throwing a
709 * {@link NullPointerException}. However, calling entry.setValue(null)
713 * Note that the iterators for all three views, from keySet(), entrySet(),
714 * and values(), traverse the hashtable in the same sequence.
716 * @return a set view of the entries
722 public Set
entrySet()
726 // Create an AbstractSet with custom implementations of those methods
727 // that can be overridden easily and efficiently.
728 Set r
= new AbstractSet()
735 public Iterator
iterator()
737 return new HashIterator(ENTRIES
);
742 Hashtable
.this.clear();
745 public boolean contains(Object o
)
747 return getEntry(o
) != null;
750 public boolean remove(Object o
)
752 HashEntry e
= getEntry(o
);
755 Hashtable
.this.remove(e
.key
);
761 // We must specify the correct object to synchronize upon, hence the
762 // use of a non-public API
763 entries
= new Collections
.SynchronizedSet(this, r
);
769 * Returns true if this Hashtable equals the supplied Object <code>o</code>.
770 * As specified by Map, this is:
772 * (o instanceof Map) && entrySet().equals(((Map) o).entrySet());
775 * @param o the object to compare to
776 * @return true if o is an equal map
779 public boolean equals(Object o
)
781 // no need to synchronize, entrySet().equals() does that
784 if (!(o
instanceof Map
))
787 return entrySet().equals(((Map
) o
).entrySet());
791 * Returns the hashCode for this Hashtable. As specified by Map, this is
792 * the sum of the hashCodes of all of its Map.Entry objects
794 * @return the sum of the hashcodes of the entries
797 public synchronized int hashCode()
799 // Since we are already synchronized, and entrySet().iterator()
800 // would repeatedly re-lock/release the monitor, we directly use the
801 // unsynchronized HashIterator instead.
802 Iterator itr
= new HashIterator(ENTRIES
);
804 for (int pos
= size
; pos
> 0; pos
--)
805 hashcode
+= itr
.next().hashCode();
811 * Helper method that returns an index in the buckets array for `key'
812 * based on its hashCode().
815 * @return the bucket number
816 * @throws NullPointerException if key is null
818 private int hash(Object key
)
820 // Note: Inline Math.abs here, for less method overhead, and to avoid
821 // a bootstrap dependency, since Math relies on native methods.
822 int hash
= key
.hashCode() % buckets
.length
;
823 return hash
< 0 ?
-hash
: hash
;
827 * Helper method for entrySet(), which matches both key and value
828 * simultaneously. Ignores null, as mentioned in entrySet().
830 * @param o the entry to match
831 * @return the matching entry, if found, or null
834 // Package visible, for use in nested classes.
835 HashEntry
getEntry(Object o
)
837 if (! (o
instanceof Map
.Entry
))
839 Object key
= ((Map
.Entry
) o
).getKey();
844 HashEntry e
= buckets
[idx
];
855 * A simplified, more efficient internal implementation of putAll(). clone()
856 * should not call putAll or put, in order to be compatible with the JDK
857 * implementation with respect to subclasses.
859 * @param m the map to initialize this from
861 void putAllInternal(Map m
)
863 Iterator itr
= m
.entrySet().iterator();
866 while (itr
.hasNext())
869 Map
.Entry e
= (Map
.Entry
) itr
.next();
870 Object key
= e
.getKey();
872 HashEntry he
= new HashEntry(key
, e
.getValue());
873 he
.next
= buckets
[idx
];
879 * Increases the size of the Hashtable and rehashes all keys to new array
880 * indices; this is called when the addition of a new value would cause
881 * size() > threshold. Note that the existing Entry objects are reused in
882 * the new hash table.
885 * This is not specified, but the new size is twice the current size plus
886 * one; this number is not always prime, unfortunately. This implementation
887 * is not synchronized, as it is only invoked from synchronized methods.
889 protected void rehash()
891 HashEntry
[] oldBuckets
= buckets
;
893 int newcapacity
= (buckets
.length
* 2) + 1;
894 threshold
= (int) (newcapacity
* loadFactor
);
895 buckets
= new HashEntry
[newcapacity
];
897 for (int i
= oldBuckets
.length
- 1; i
>= 0; i
--)
899 HashEntry e
= oldBuckets
[i
];
902 int idx
= hash(e
.key
);
903 HashEntry dest
= buckets
[idx
];
907 while (dest
.next
!= null)
916 HashEntry next
= e
.next
;
924 * Serializes this object to the given stream.
926 * @param s the stream to write to
927 * @throws IOException if the underlying stream fails
928 * @serialData the <i>capacity</i> (int) that is the length of the
929 * bucket array, the <i>size</i> (int) of the hash map
930 * are emitted first. They are followed by size entries,
931 * each consisting of a key (Object) and a value (Object).
933 private synchronized void writeObject(ObjectOutputStream s
)
936 // Write the threshold and loadFactor fields.
937 s
.defaultWriteObject();
939 s
.writeInt(buckets
.length
);
941 // Since we are already synchronized, and entrySet().iterator()
942 // would repeatedly re-lock/release the monitor, we directly use the
943 // unsynchronized HashIterator instead.
944 Iterator it
= new HashIterator(ENTRIES
);
947 HashEntry entry
= (HashEntry
) it
.next();
948 s
.writeObject(entry
.key
);
949 s
.writeObject(entry
.value
);
954 * Deserializes this object from the given stream.
956 * @param s the stream to read from
957 * @throws ClassNotFoundException if the underlying stream fails
958 * @throws IOException if the underlying stream fails
959 * @serialData the <i>capacity</i> (int) that is the length of the
960 * bucket array, the <i>size</i> (int) of the hash map
961 * are emitted first. They are followed by size entries,
962 * each consisting of a key (Object) and a value (Object).
964 private void readObject(ObjectInputStream s
)
965 throws IOException
, ClassNotFoundException
967 // Read the threshold and loadFactor fields.
968 s
.defaultReadObject();
970 // Read and use capacity.
971 buckets
= new HashEntry
[s
.readInt()];
972 int len
= s
.readInt();
974 // Read and use key/value pairs.
975 // TODO: should we be defensive programmers, and check for illegal nulls?
977 put(s
.readObject(), s
.readObject());
981 * A class which implements the Iterator interface and is used for
982 * iterating over Hashtables.
983 * This implementation is parameterized to give a sequential view of
984 * keys, values, or entries; it also allows the removal of elements,
985 * as per the Javasoft spec. Note that it is not synchronized; this is
986 * a performance enhancer since it is never exposed externally and is
987 * only used within synchronized blocks above.
989 * @author Jon Zeppieri
991 private final class HashIterator
implements Iterator
994 * The type of this Iterator: {@link #KEYS}, {@link #VALUES},
995 * or {@link #ENTRIES}.
999 * The number of modifications to the backing Hashtable that we know about.
1001 int knownMod
= modCount
;
1002 /** The number of elements remaining to be returned by next(). */
1004 /** Current index in the physical hash table. */
1005 int idx
= buckets
.length
;
1006 /** The last Entry returned by a next() call. */
1009 * The next entry that should be returned by next(). It is set to something
1010 * if we're iterating through a bucket that contains multiple linked
1011 * entries. It is null if next() needs to find a new bucket.
1016 * Construct a new HashIterator with the supplied type.
1017 * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
1019 HashIterator(int type
)
1025 * Returns true if the Iterator has more elements.
1026 * @return true if there are more elements
1027 * @throws ConcurrentModificationException if the hashtable was modified
1029 public boolean hasNext()
1031 if (knownMod
!= modCount
)
1032 throw new ConcurrentModificationException();
1037 * Returns the next element in the Iterator's sequential view.
1038 * @return the next element
1039 * @throws ConcurrentModificationException if the hashtable was modified
1040 * @throws NoSuchElementException if there is none
1042 public Object
next()
1044 if (knownMod
!= modCount
)
1045 throw new ConcurrentModificationException();
1047 throw new NoSuchElementException();
1064 * Removes from the backing Hashtable the last element which was fetched
1065 * with the <code>next()</code> method.
1066 * @throws ConcurrentModificationException if the hashtable was modified
1067 * @throws IllegalStateException if called when there is no last element
1069 public void remove()
1071 if (knownMod
!= modCount
)
1072 throw new ConcurrentModificationException();
1074 throw new IllegalStateException();
1076 Hashtable
.this.remove(last
.key
);
1080 } // class HashIterator
1084 * Enumeration view of this Hashtable, providing sequential access to its
1085 * elements; this implementation is parameterized to provide access either
1086 * to the keys or to the values in the Hashtable.
1088 * <b>NOTE</b>: Enumeration is not safe if new elements are put in the table
1089 * as this could cause a rehash and we'd completely lose our place. Even
1090 * without a rehash, it is undetermined if a new element added would
1091 * appear in the enumeration. The spec says nothing about this, but
1092 * the "Java Class Libraries" book infers that modifications to the
1093 * hashtable during enumeration causes indeterminate results. Don't do it!
1095 * @author Jon Zeppieri
1097 private final class Enumerator
implements Enumeration
1100 * The type of this Iterator: {@link #KEYS} or {@link #VALUES}.
1103 /** The number of elements remaining to be returned by next(). */
1105 /** Current index in the physical hash table. */
1106 int idx
= buckets
.length
;
1108 * Entry which will be returned by the next nextElement() call. It is
1109 * set if we are iterating through a bucket with multiple entries, or null
1110 * if we must look in the next bucket.
1115 * Construct the enumeration.
1116 * @param type either {@link #KEYS} or {@link #VALUES}.
1118 Enumerator(int type
)
1124 * Checks whether more elements remain in the enumeration.
1125 * @return true if nextElement() will not fail.
1127 public boolean hasMoreElements()
1133 * Returns the next element.
1134 * @return the next element
1135 * @throws NoSuchElementException if there is none.
1137 public Object
nextElement()
1140 throw new NoSuchElementException("Hashtable Enumerator");
1148 return type
== VALUES ? e
.value
: e
.key
;
1150 } // class Enumerator
1151 } // class Hashtable