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 gnu
.java
.lang
.CPStringBuilder
;
44 import java
.io
.IOException
;
45 import java
.io
.ObjectInputStream
;
46 import java
.io
.ObjectOutputStream
;
47 import java
.io
.Serializable
;
49 // NOTE: This implementation is very similar to that of HashMap. If you fix
50 // a bug in here, chances are you should make a similar change to the HashMap
54 * A class which implements a hashtable data structure.
57 * This implementation of Hashtable uses a hash-bucket approach. That is:
58 * linear probing and rehashing is avoided; instead, each hashed value maps
59 * to a simple linked-list which, in the best case, only has one node.
60 * Assuming a large enough table, low enough load factor, and / or well
61 * implemented hashCode() methods, Hashtable should provide O(1)
62 * insertion, deletion, and searching of keys. Hashtable is O(n) in
63 * the worst case for all of these (if all keys hash to the same bucket).
66 * This is a JDK-1.2 compliant implementation of Hashtable. As such, it
67 * belongs, partially, to the Collections framework (in that it implements
68 * Map). For backwards compatibility, it inherits from the obsolete and
69 * utterly useless Dictionary class.
72 * Being a hybrid of old and new, Hashtable has methods which provide redundant
73 * capability, but with subtle and even crucial differences.
74 * For example, one can iterate over various aspects of a Hashtable with
75 * either an Iterator (which is the JDK-1.2 way of doing things) or with an
76 * Enumeration. The latter can end up in an undefined state if the Hashtable
77 * changes while the Enumeration is open.
80 * Unlike HashMap, Hashtable does not accept `null' as a key value. Also,
81 * all accesses are synchronized: in a single thread environment, this is
82 * expensive, but in a multi-thread environment, this saves you the effort
83 * of extra synchronization. However, the old-style enumerators are not
84 * synchronized, because they can lead to unspecified behavior even if
85 * they were synchronized. You have been warned.
88 * The iterators are <i>fail-fast</i>, meaning that any structural
89 * modification, except for <code>remove()</code> called on the iterator
90 * itself, cause the iterator to throw a
91 * <code>ConcurrentModificationException</code> rather than exhibit
92 * non-deterministic behavior.
94 * @author Jon Zeppieri
96 * @author Bryce McKinlay
97 * @author Eric Blake (ebb9@email.byu.edu)
100 * @see IdentityHashMap
103 * @status updated to 1.4
105 public class Hashtable
<K
, V
> extends Dictionary
<K
, V
>
106 implements Map
<K
, V
>, Cloneable
, Serializable
108 // WARNING: Hashtable is a CORE class in the bootstrap cycle. See the
109 // comments in vm/reference/java/lang/Runtime for implications of this fact.
111 /** Default number of buckets. This is the value the JDK 1.3 uses. Some
112 * early documentation specified this value as 101. That is incorrect.
114 private static final int DEFAULT_CAPACITY
= 11;
117 * The default load factor; this is explicitly specified by the spec.
119 private static final float DEFAULT_LOAD_FACTOR
= 0.75f
;
122 * Compatible with JDK 1.0+.
124 private static final long serialVersionUID
= 1421746759512286392L;
127 * The rounded product of the capacity and the load factor; when the number
128 * of elements exceeds the threshold, the Hashtable calls
129 * <code>rehash()</code>.
132 private int threshold
;
135 * Load factor of this Hashtable: used in computing the threshold.
138 private final float loadFactor
;
141 * Array containing the actual key-value mappings.
143 // Package visible for use by nested classes.
144 transient HashEntry
<K
, V
>[] buckets
;
147 * Counts the number of modifications this Hashtable has undergone, used
148 * by Iterators to know when to throw ConcurrentModificationExceptions.
150 // Package visible for use by nested classes.
151 transient int modCount
;
154 * The size of this Hashtable: denotes the number of key-value pairs.
156 // Package visible for use by nested classes.
160 * The cache for {@link #keySet()}.
162 private transient Set
<K
> keys
;
165 * The cache for {@link #values()}.
167 private transient Collection
<V
> values
;
170 * The cache for {@link #entrySet()}.
172 private transient Set
<Map
.Entry
<K
, V
>> entries
;
175 * Class to represent an entry in the hash table. Holds a single key-value
176 * pair. A Hashtable Entry is identical to a HashMap Entry, except that
177 * `null' is not allowed for keys and values.
179 private static final class HashEntry
<K
, V
>
180 extends AbstractMap
.SimpleEntry
<K
, V
>
182 /** The next entry in the linked list. */
183 HashEntry
<K
, V
> next
;
186 * Simple constructor.
187 * @param key the key, already guaranteed non-null
188 * @param value the value, already guaranteed non-null
190 HashEntry(K key
, V value
)
197 * @param newVal the new value
198 * @return the prior value
199 * @throws NullPointerException if <code>newVal</code> is null
201 public V
setValue(V newVal
)
204 throw new NullPointerException();
205 return super.setValue(newVal
);
210 * Construct a new Hashtable with the default capacity (11) and the default
211 * load factor (0.75).
215 this(DEFAULT_CAPACITY
, DEFAULT_LOAD_FACTOR
);
219 * Construct a new Hashtable from the given Map, with initial capacity
220 * the greater of the size of <code>m</code> or the default of 11.
223 * Every element in Map m will be put into this new Hashtable.
225 * @param m a Map whose key / value pairs will be put into
226 * the new Hashtable. <b>NOTE: key / value pairs
227 * are not cloned in this constructor.</b>
228 * @throws NullPointerException if m is null, or if m contains a mapping
232 public Hashtable(Map
<?
extends K
, ?
extends V
> m
)
234 this(Math
.max(m
.size() * 2, DEFAULT_CAPACITY
), DEFAULT_LOAD_FACTOR
);
239 * Construct a new Hashtable with a specific inital capacity and
240 * default load factor of 0.75.
242 * @param initialCapacity the initial capacity of this Hashtable (>= 0)
243 * @throws IllegalArgumentException if (initialCapacity < 0)
245 public Hashtable(int initialCapacity
)
247 this(initialCapacity
, DEFAULT_LOAD_FACTOR
);
251 * Construct a new Hashtable with a specific initial capacity and
254 * @param initialCapacity the initial capacity (>= 0)
255 * @param loadFactor the load factor (> 0, not NaN)
256 * @throws IllegalArgumentException if (initialCapacity < 0) ||
257 * ! (loadFactor > 0.0)
259 public Hashtable(int initialCapacity
, float loadFactor
)
261 if (initialCapacity
< 0)
262 throw new IllegalArgumentException("Illegal Capacity: "
264 if (! (loadFactor
> 0)) // check for NaN too
265 throw new IllegalArgumentException("Illegal Load: " + loadFactor
);
267 if (initialCapacity
== 0)
269 buckets
= (HashEntry
<K
, V
>[]) new HashEntry
[initialCapacity
];
270 this.loadFactor
= loadFactor
;
271 threshold
= (int) (initialCapacity
* loadFactor
);
275 * Returns the number of key-value mappings currently in this hashtable.
278 public synchronized int size()
284 * Returns true if there are no key-value mappings currently in this table.
285 * @return <code>size() == 0</code>
287 public synchronized boolean isEmpty()
293 * Return an enumeration of the keys of this table. There's no point
294 * in synchronizing this, as you have already been warned that the
295 * enumeration is not specified to be thread-safe.
301 public Enumeration
<K
> keys()
303 return new KeyEnumerator();
307 * Return an enumeration of the values of this table. There's no point
308 * in synchronizing this, as you have already been warned that the
309 * enumeration is not specified to be thread-safe.
315 public Enumeration
<V
> elements()
317 return new ValueEnumerator();
321 * Returns true if this Hashtable contains a value <code>o</code>,
322 * such that <code>o.equals(value)</code>. This is the same as
323 * <code>containsValue()</code>, and is O(n).
326 * @param value the value to search for in this Hashtable
327 * @return true if at least one key maps to the value
328 * @throws NullPointerException if <code>value</code> is null
329 * @see #containsValue(Object)
330 * @see #containsKey(Object)
332 public synchronized boolean contains(Object value
)
335 throw new NullPointerException();
337 for (int i
= buckets
.length
- 1; i
>= 0; i
--)
339 HashEntry
<K
, V
> e
= buckets
[i
];
342 if (e
.value
.equals(value
))
352 * Returns true if this Hashtable contains a value <code>o</code>, such that
353 * <code>o.equals(value)</code>. This is the new API for the old
354 * <code>contains()</code>.
356 * @param value the value to search for in this Hashtable
357 * @return true if at least one key maps to the value
358 * @see #contains(Object)
359 * @see #containsKey(Object)
360 * @throws NullPointerException if <code>value</code> is null
363 public boolean containsValue(Object value
)
365 // Delegate to older method to make sure code overriding it continues
367 return contains(value
);
371 * Returns true if the supplied object <code>equals()</code> a key
374 * @param key the key to search for in this Hashtable
375 * @return true if the key is in the table
376 * @throws NullPointerException if key is null
377 * @see #containsValue(Object)
379 public synchronized boolean containsKey(Object key
)
382 HashEntry
<K
, V
> e
= buckets
[idx
];
385 if (e
.key
.equals(key
))
393 * Return the value in this Hashtable associated with the supplied key,
394 * or <code>null</code> if the key maps to nothing.
396 * @param key the key for which to fetch an associated value
397 * @return what the key maps to, if present
398 * @throws NullPointerException if key is null
399 * @see #put(Object, Object)
400 * @see #containsKey(Object)
402 public synchronized V
get(Object key
)
405 HashEntry
<K
, V
> e
= buckets
[idx
];
408 if (e
.key
.equals(key
))
416 * Puts the supplied value into the Map, mapped by the supplied key.
417 * Neither parameter may be null. The value may be retrieved by any
418 * object which <code>equals()</code> this key.
420 * @param key the key used to locate the value
421 * @param value the value to be stored in the table
422 * @return the prior mapping of the key, or null if there was none
423 * @throws NullPointerException if key or value is null
425 * @see Object#equals(Object)
427 public synchronized V
put(K key
, V value
)
430 HashEntry
<K
, V
> e
= buckets
[idx
];
432 // Check if value is null since it is not permitted.
434 throw new NullPointerException();
438 if (e
.key
.equals(key
))
440 // Bypass e.setValue, since we already know value is non-null.
451 // At this point, we know we need to add a new entry.
453 if (++size
> threshold
)
456 // Need a new hash value to suit the bigger table.
460 e
= new HashEntry
<K
, V
>(key
, value
);
462 e
.next
= buckets
[idx
];
469 * Removes from the table and returns the value which is mapped by the
470 * supplied key. If the key maps to nothing, then the table remains
471 * unchanged, and <code>null</code> is returned.
473 * @param key the key used to locate the value to remove
474 * @return whatever the key mapped to, if present
476 public synchronized V
remove(Object key
)
479 HashEntry
<K
, V
> e
= buckets
[idx
];
480 HashEntry
<K
, V
> last
= null;
484 if (e
.key
.equals(key
))
488 buckets
[idx
] = e
.next
;
501 * Copies all elements of the given map into this hashtable. However, no
502 * mapping can contain null as key or value. If this table already has
503 * a mapping for a key, the new mapping replaces the current one.
505 * @param m the map to be hashed into this
506 * @throws NullPointerException if m is null, or contains null keys or values
508 public synchronized void putAll(Map
<?
extends K
, ?
extends V
> m
)
510 final Map
<K
,V
> addMap
= (Map
<K
,V
>) m
;
511 final Iterator
<Map
.Entry
<K
,V
>> it
= addMap
.entrySet().iterator();
514 final Map
.Entry
<K
,V
> e
= it
.next();
515 // Optimize in case the Entry is one of our own.
516 if (e
instanceof AbstractMap
.SimpleEntry
)
518 AbstractMap
.SimpleEntry
<?
extends K
, ?
extends V
> entry
519 = (AbstractMap
.SimpleEntry
<?
extends K
, ?
extends V
>) e
;
520 put(entry
.key
, entry
.value
);
524 put(e
.getKey(), e
.getValue());
530 * Clears the hashtable so it has no keys. This is O(1).
532 public synchronized void clear()
537 Arrays
.fill(buckets
, null);
543 * Returns a shallow clone of this Hashtable. The Map itself is cloned,
544 * but its contents are not. This is O(n).
548 public synchronized Object
clone()
550 Hashtable
<K
, V
> copy
= null;
553 copy
= (Hashtable
<K
, V
>) super.clone();
555 catch (CloneNotSupportedException x
)
557 // This is impossible.
559 copy
.buckets
= (HashEntry
<K
, V
>[]) new HashEntry
[buckets
.length
];
560 copy
.putAllInternal(this);
569 * Converts this Hashtable to a String, surrounded by braces, and with
570 * key/value pairs listed with an equals sign between, separated by a
571 * comma and space. For example, <code>"{a=1, b=2}"</code>.<p>
573 * NOTE: if the <code>toString()</code> method of any key or value
574 * throws an exception, this will fail for the same reason.
576 * @return the string representation
578 public synchronized String
toString()
580 // Since we are already synchronized, and entrySet().iterator()
581 // would repeatedly re-lock/release the monitor, we directly use the
582 // unsynchronized EntryIterator instead.
583 Iterator
<Map
.Entry
<K
, V
>> entries
= new EntryIterator();
584 CPStringBuilder r
= new CPStringBuilder("{");
585 for (int pos
= size
; pos
> 0; pos
--)
587 r
.append(entries
.next());
596 * Returns a "set view" of this Hashtable's keys. The set is backed by
597 * the hashtable, so changes in one show up in the other. The set supports
598 * element removal, but not element addition. The set is properly
599 * synchronized on the original hashtable. Sun has not documented the
600 * proper interaction of null with this set, but has inconsistent behavior
601 * in the JDK. Therefore, in this implementation, contains, remove,
602 * containsAll, retainAll, removeAll, and equals just ignore a null key
603 * rather than throwing a {@link NullPointerException}.
605 * @return a set view of the keys
610 public Set
<K
> keySet()
614 // Create a synchronized AbstractSet with custom implementations of
615 // those methods that can be overridden easily and efficiently.
616 Set
<K
> r
= new AbstractSet
<K
>()
623 public Iterator
<K
> iterator()
625 return new KeyIterator();
630 Hashtable
.this.clear();
633 public boolean contains(Object o
)
637 return containsKey(o
);
640 public boolean remove(Object o
)
642 return Hashtable
.this.remove(o
) != null;
645 // We must specify the correct object to synchronize upon, hence the
646 // use of a non-public API
647 keys
= new Collections
.SynchronizedSet
<K
>(this, r
);
653 * Returns a "collection view" (or "bag view") of this Hashtable's values.
654 * The collection is backed by the hashtable, so changes in one show up
655 * in the other. The collection supports element removal, but not element
656 * addition. The collection is properly synchronized on the original
657 * hashtable. Sun has not documented the proper interaction of null with
658 * this set, but has inconsistent behavior in the JDK. Therefore, in this
659 * implementation, contains, remove, containsAll, retainAll, removeAll, and
660 * equals just ignore a null value rather than throwing a
661 * {@link NullPointerException}.
663 * @return a bag view of the values
668 public Collection
<V
> values()
672 // We don't bother overriding many of the optional methods, as doing so
673 // wouldn't provide any significant performance advantage.
674 Collection
<V
> r
= new AbstractCollection
<V
>()
681 public Iterator
<V
> iterator()
683 return new ValueIterator();
688 Hashtable
.this.clear();
691 // We must specify the correct object to synchronize upon, hence the
692 // use of a non-public API
693 values
= new Collections
.SynchronizedCollection
<V
>(this, r
);
699 * Returns a "set view" of this Hashtable's entries. The set is backed by
700 * the hashtable, so changes in one show up in the other. The set supports
701 * element removal, but not element addition. The set is properly
702 * synchronized on the original hashtable. Sun has not documented the
703 * proper interaction of null with this set, but has inconsistent behavior
704 * in the JDK. Therefore, in this implementation, contains, remove,
705 * containsAll, retainAll, removeAll, and equals just ignore a null entry,
706 * or an entry with a null key or value, rather than throwing a
707 * {@link NullPointerException}. However, calling entry.setValue(null)
711 * Note that the iterators for all three views, from keySet(), entrySet(),
712 * and values(), traverse the hashtable in the same sequence.
714 * @return a set view of the entries
720 public Set
<Map
.Entry
<K
, V
>> entrySet()
724 // Create an AbstractSet with custom implementations of those methods
725 // that can be overridden easily and efficiently.
726 Set
<Map
.Entry
<K
, V
>> r
= new AbstractSet
<Map
.Entry
<K
, V
>>()
733 public Iterator
<Map
.Entry
<K
, V
>> iterator()
735 return new EntryIterator();
740 Hashtable
.this.clear();
743 public boolean contains(Object o
)
745 return getEntry(o
) != null;
748 public boolean remove(Object o
)
750 HashEntry
<K
, V
> e
= getEntry(o
);
753 Hashtable
.this.remove(e
.key
);
759 // We must specify the correct object to synchronize upon, hence the
760 // use of a non-public API
761 entries
= new Collections
.SynchronizedSet
<Map
.Entry
<K
, V
>>(this, r
);
767 * Returns true if this Hashtable equals the supplied Object <code>o</code>.
768 * As specified by Map, this is:
770 * (o instanceof Map) && entrySet().equals(((Map) o).entrySet());
773 * @param o the object to compare to
774 * @return true if o is an equal map
777 public boolean equals(Object o
)
779 // no need to synchronize, entrySet().equals() does that.
782 if (!(o
instanceof Map
))
785 return entrySet().equals(((Map
) o
).entrySet());
789 * Returns the hashCode for this Hashtable. As specified by Map, this is
790 * the sum of the hashCodes of all of its Map.Entry objects
792 * @return the sum of the hashcodes of the entries
795 public synchronized int hashCode()
797 // Since we are already synchronized, and entrySet().iterator()
798 // would repeatedly re-lock/release the monitor, we directly use the
799 // unsynchronized EntryIterator instead.
800 Iterator
<Map
.Entry
<K
, V
>> itr
= new EntryIterator();
802 for (int pos
= size
; pos
> 0; pos
--)
803 hashcode
+= itr
.next().hashCode();
809 * Helper method that returns an index in the buckets array for `key'
810 * based on its hashCode().
813 * @return the bucket number
814 * @throws NullPointerException if key is null
816 private int hash(Object key
)
818 // Note: Inline Math.abs here, for less method overhead, and to avoid
819 // a bootstrap dependency, since Math relies on native methods.
820 int hash
= key
.hashCode() % buckets
.length
;
821 return hash
< 0 ?
-hash
: hash
;
825 * Helper method for entrySet(), which matches both key and value
826 * simultaneously. Ignores null, as mentioned in entrySet().
828 * @param o the entry to match
829 * @return the matching entry, if found, or null
832 // Package visible, for use in nested classes.
833 HashEntry
<K
, V
> getEntry(Object o
)
835 if (! (o
instanceof Map
.Entry
))
837 K key
= ((Map
.Entry
<K
, V
>) o
).getKey();
842 HashEntry
<K
, V
> e
= buckets
[idx
];
853 * A simplified, more efficient internal implementation of putAll(). clone()
854 * should not call putAll or put, in order to be compatible with the JDK
855 * implementation with respect to subclasses.
857 * @param m the map to initialize this from
859 void putAllInternal(Map
<?
extends K
, ?
extends V
> m
)
861 final Map
<K
,V
> addMap
= (Map
<K
,V
>) m
;
862 final Iterator
<Map
.Entry
<K
,V
>> it
= addMap
.entrySet().iterator();
866 final Map
.Entry
<K
,V
> e
= it
.next();
870 HashEntry
<K
, V
> he
= new HashEntry
<K
, V
>(key
, e
.getValue());
871 he
.next
= buckets
[idx
];
877 * Increases the size of the Hashtable and rehashes all keys to new array
878 * indices; this is called when the addition of a new value would cause
879 * size() > threshold. Note that the existing Entry objects are reused in
880 * the new hash table.
883 * This is not specified, but the new size is twice the current size plus
884 * one; this number is not always prime, unfortunately. This implementation
885 * is not synchronized, as it is only invoked from synchronized methods.
887 protected void rehash()
889 HashEntry
<K
, V
>[] oldBuckets
= buckets
;
891 int newcapacity
= (buckets
.length
* 2) + 1;
892 threshold
= (int) (newcapacity
* loadFactor
);
893 buckets
= (HashEntry
<K
, V
>[]) new HashEntry
[newcapacity
];
895 for (int i
= oldBuckets
.length
- 1; i
>= 0; i
--)
897 HashEntry
<K
, V
> e
= oldBuckets
[i
];
900 int idx
= hash(e
.key
);
901 HashEntry
<K
, V
> dest
= buckets
[idx
];
905 HashEntry next
= dest
.next
;
918 HashEntry
<K
, V
> next
= e
.next
;
926 * Serializes this object to the given stream.
928 * @param s the stream to write to
929 * @throws IOException if the underlying stream fails
930 * @serialData the <i>capacity</i> (int) that is the length of the
931 * bucket array, the <i>size</i> (int) of the hash map
932 * are emitted first. They are followed by size entries,
933 * each consisting of a key (Object) and a value (Object).
935 private synchronized void writeObject(ObjectOutputStream s
)
938 // Write the threshold and loadFactor fields.
939 s
.defaultWriteObject();
941 s
.writeInt(buckets
.length
);
943 // Since we are already synchronized, and entrySet().iterator()
944 // would repeatedly re-lock/release the monitor, we directly use the
945 // unsynchronized EntryIterator instead.
946 Iterator
<Map
.Entry
<K
, V
>> it
= new EntryIterator();
949 HashEntry
<K
, V
> entry
= (HashEntry
<K
, V
>) it
.next();
950 s
.writeObject(entry
.key
);
951 s
.writeObject(entry
.value
);
956 * Deserializes this object from the given stream.
958 * @param s the stream to read from
959 * @throws ClassNotFoundException if the underlying stream fails
960 * @throws IOException if the underlying stream fails
961 * @serialData the <i>capacity</i> (int) that is the length of the
962 * bucket array, the <i>size</i> (int) of the hash map
963 * are emitted first. They are followed by size entries,
964 * each consisting of a key (Object) and a value (Object).
966 private void readObject(ObjectInputStream s
)
967 throws IOException
, ClassNotFoundException
969 // Read the threshold and loadFactor fields.
970 s
.defaultReadObject();
972 // Read and use capacity.
973 buckets
= (HashEntry
<K
, V
>[]) new HashEntry
[s
.readInt()];
974 int len
= s
.readInt();
976 // Read and use key/value pairs.
977 // TODO: should we be defensive programmers, and check for illegal nulls?
979 put((K
) s
.readObject(), (V
) s
.readObject());
983 * A class which implements the Iterator interface and is used for
984 * iterating over Hashtables.
985 * This implementation iterates entries. Subclasses are used to
986 * iterate key and values. It also allows the removal of elements,
987 * as per the Javasoft spec. Note that it is not synchronized; this
988 * is a performance enhancer since it is never exposed externally
989 * and is only used within synchronized blocks above.
991 * @author Jon Zeppieri
992 * @author Fridjof Siebert
994 private class EntryIterator
995 implements Iterator
<Entry
<K
,V
>>
998 * The number of modifications to the backing Hashtable that we know about.
1000 int knownMod
= modCount
;
1001 /** The number of elements remaining to be returned by next(). */
1003 /** Current index in the physical hash table. */
1004 int idx
= buckets
.length
;
1005 /** The last Entry returned by a next() call. */
1006 HashEntry
<K
, V
> last
;
1008 * The next entry that should be returned by next(). It is set to something
1009 * if we're iterating through a bucket that contains multiple linked
1010 * entries. It is null if next() needs to find a new bucket.
1012 HashEntry
<K
, V
> next
;
1015 * Construct a new EntryIterator
1023 * Returns true if the Iterator has more elements.
1024 * @return true if there are more elements
1026 public boolean hasNext()
1032 * Returns the next element in the Iterator's sequential view.
1033 * @return the next element
1034 * @throws ConcurrentModificationException if the hashtable was modified
1035 * @throws NoSuchElementException if there is none
1037 public Map
.Entry
<K
,V
> next()
1039 if (knownMod
!= modCount
)
1040 throw new ConcurrentModificationException();
1042 throw new NoSuchElementException();
1044 HashEntry
<K
, V
> e
= next
;
1058 * Removes from the backing Hashtable the last element which was fetched
1059 * with the <code>next()</code> method.
1060 * @throws ConcurrentModificationException if the hashtable was modified
1061 * @throws IllegalStateException if called when there is no last element
1063 public void remove()
1065 if (knownMod
!= modCount
)
1066 throw new ConcurrentModificationException();
1068 throw new IllegalStateException();
1070 Hashtable
.this.remove(last
.key
);
1074 } // class EntryIterator
1077 * A class which implements the Iterator interface and is used for
1078 * iterating over keys in Hashtables. This class uses an
1079 * <code>EntryIterator</code> to obtain the keys of each entry.
1081 * @author Fridtjof Siebert
1082 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
1084 private class KeyIterator
1085 implements Iterator
<K
>
1089 * This entry iterator is used for most operations. Only
1090 * <code>next()</code> gives a different result, by returning just
1091 * the key rather than the whole element.
1093 private final EntryIterator iterator
;
1096 * Construct a new KeyIterator
1100 iterator
= new EntryIterator();
1105 * Returns true if the entry iterator has more elements.
1107 * @return true if there are more elements
1108 * @throws ConcurrentModificationException if the hashtable was modified
1110 public boolean hasNext()
1112 return iterator
.hasNext();
1116 * Returns the next element in the Iterator's sequential view.
1118 * @return the next element
1120 * @throws ConcurrentModificationException if the hashtable was modified
1121 * @throws NoSuchElementException if there is none
1125 return ((HashEntry
<K
,V
>) iterator
.next()).key
;
1129 * Removes the last element used by the <code>next()</code> method
1130 * using the entry iterator.
1132 * @throws ConcurrentModificationException if the hashtable was modified
1133 * @throws IllegalStateException if called when there is no last element
1135 public void remove()
1139 } // class KeyIterator
1142 * A class which implements the Iterator interface and is used for
1143 * iterating over values in Hashtables. This class uses an
1144 * <code>EntryIterator</code> to obtain the values of each entry.
1146 * @author Fridtjof Siebert
1147 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
1149 private class ValueIterator
1150 implements Iterator
<V
>
1154 * This entry iterator is used for most operations. Only
1155 * <code>next()</code> gives a different result, by returning just
1156 * the value rather than the whole element.
1158 private final EntryIterator iterator
;
1161 * Construct a new KeyIterator
1165 iterator
= new EntryIterator();
1170 * Returns true if the entry iterator has more elements.
1172 * @return true if there are more elements
1173 * @throws ConcurrentModificationException if the hashtable was modified
1175 public boolean hasNext()
1177 return iterator
.hasNext();
1181 * Returns the value of the next element in the iterator's sequential view.
1183 * @return the next value
1185 * @throws ConcurrentModificationException if the hashtable was modified
1186 * @throws NoSuchElementException if there is none
1190 return ((HashEntry
<K
,V
>) iterator
.next()).value
;
1194 * Removes the last element used by the <code>next()</code> method
1195 * using the entry iterator.
1197 * @throws ConcurrentModificationException if the hashtable was modified
1198 * @throws IllegalStateException if called when there is no last element
1200 public void remove()
1205 } // class ValueIterator
1208 * Enumeration view of the entries in this Hashtable, providing
1209 * sequential access to its elements.
1211 * <b>NOTE</b>: Enumeration is not safe if new elements are put in the table
1212 * as this could cause a rehash and we'd completely lose our place. Even
1213 * without a rehash, it is undetermined if a new element added would
1214 * appear in the enumeration. The spec says nothing about this, but
1215 * the "Java Class Libraries" book implies that modifications to the
1216 * hashtable during enumeration causes indeterminate results. Don't do it!
1218 * @author Jon Zeppieri
1219 * @author Fridjof Siebert
1221 private class EntryEnumerator
1222 implements Enumeration
<Entry
<K
,V
>>
1224 /** The number of elements remaining to be returned by next(). */
1226 /** Current index in the physical hash table. */
1227 int idx
= buckets
.length
;
1229 * Entry which will be returned by the next nextElement() call. It is
1230 * set if we are iterating through a bucket with multiple entries, or null
1231 * if we must look in the next bucket.
1233 HashEntry
<K
, V
> next
;
1236 * Construct the enumeration.
1240 // Nothing to do here.
1244 * Checks whether more elements remain in the enumeration.
1245 * @return true if nextElement() will not fail.
1247 public boolean hasMoreElements()
1253 * Returns the next element.
1254 * @return the next element
1255 * @throws NoSuchElementException if there is none.
1257 public Map
.Entry
<K
,V
> nextElement()
1260 throw new NoSuchElementException("Hashtable Enumerator");
1262 HashEntry
<K
, V
> e
= next
;
1273 } // class EntryEnumerator
1277 * Enumeration view of this Hashtable, providing sequential access to its
1280 * <b>NOTE</b>: Enumeration is not safe if new elements are put in the table
1281 * as this could cause a rehash and we'd completely lose our place. Even
1282 * without a rehash, it is undetermined if a new element added would
1283 * appear in the enumeration. The spec says nothing about this, but
1284 * the "Java Class Libraries" book implies that modifications to the
1285 * hashtable during enumeration causes indeterminate results. Don't do it!
1287 * @author Jon Zeppieri
1288 * @author Fridjof Siebert
1289 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
1291 private final class KeyEnumerator
1292 implements Enumeration
<K
>
1295 * This entry enumerator is used for most operations. Only
1296 * <code>nextElement()</code> gives a different result, by returning just
1297 * the key rather than the whole element.
1299 private final EntryEnumerator enumerator
;
1302 * Construct a new KeyEnumerator
1306 enumerator
= new EntryEnumerator();
1311 * Returns true if the entry enumerator has more elements.
1313 * @return true if there are more elements
1314 * @throws ConcurrentModificationException if the hashtable was modified
1316 public boolean hasMoreElements()
1318 return enumerator
.hasMoreElements();
1322 * Returns the next element.
1323 * @return the next element
1324 * @throws NoSuchElementException if there is none.
1326 public K
nextElement()
1328 HashEntry
<K
,V
> entry
= (HashEntry
<K
,V
>) enumerator
.nextElement();
1334 } // class KeyEnumerator
1338 * Enumeration view of this Hashtable, providing sequential access to its
1341 * <b>NOTE</b>: Enumeration is not safe if new elements are put in the table
1342 * as this could cause a rehash and we'd completely lose our place. Even
1343 * without a rehash, it is undetermined if a new element added would
1344 * appear in the enumeration. The spec says nothing about this, but
1345 * the "Java Class Libraries" book implies that modifications to the
1346 * hashtable during enumeration causes indeterminate results. Don't do it!
1348 * @author Jon Zeppieri
1349 * @author Fridjof Siebert
1350 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
1352 private final class ValueEnumerator
1353 implements Enumeration
<V
>
1356 * This entry enumerator is used for most operations. Only
1357 * <code>nextElement()</code> gives a different result, by returning just
1358 * the value rather than the whole element.
1360 private final EntryEnumerator enumerator
;
1363 * Construct a new ValueEnumerator
1367 enumerator
= new EntryEnumerator();
1372 * Returns true if the entry enumerator has more elements.
1374 * @return true if there are more elements
1375 * @throws ConcurrentModificationException if the hashtable was modified
1377 public boolean hasMoreElements()
1379 return enumerator
.hasMoreElements();
1383 * Returns the next element.
1384 * @return the next element
1385 * @throws NoSuchElementException if there is none.
1387 public V
nextElement()
1389 HashEntry
<K
,V
> entry
= (HashEntry
<K
,V
>) enumerator
.nextElement();
1392 retVal
= entry
.value
;
1395 } // class ValueEnumerator
1397 } // class Hashtable