/[classpath]/classpath/java/util/Hashtable.java
ViewVC logotype

Contents of /classpath/java/util/Hashtable.java

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1.28 - (show annotations) (download)
Tue May 7 05:13:05 2002 UTC (21 years, 11 months ago) by ericb
Branch: MAIN
CVS Tags: classpath-0_05-release, classpath-0_06-release
Changes since 1.27: +2 -1 lines
2002-05-06  Eric Blake  <ebb9@email.byu.edu>

	* Makefile.am (SUBDIRS): Alphabetize.
	* java/util/AbstractList.java (SubList): Increase member
	visibility for fewer accessor methods.
	* java/util/Hashmap.java (getEntry): Ditto.
	* java/util/Hashtable.java (getEntry): Ditto.
	* java/util/LinkedList.java (getEntry, removeEntry): Ditto.
	* java/util/WeakHashMap.java (buckets, internalRemove): Ditto.

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.
4
5 This file is part of GNU Classpath.
6
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)
10 any later version.
11
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.
16
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
20 02111-1307 USA.
21
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
25 combination.
26
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. */
38
39 package java.util;
40
41 import java.io.IOException;
42 import java.io.Serializable;
43 import java.io.ObjectInputStream;
44 import java.io.ObjectOutputStream;
45
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
48 // code.
49
50 /**
51 * A class which implements a hashtable data structure.
52 * <p>
53 *
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).
61 * <p>
62 *
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.
67 * <p>
68 *
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.
75 * <p>
76 *
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.
83 * <p>
84 *
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.
90 *
91 * @author Jon Zeppieri
92 * @author Warren Levy
93 * @author Bryce McKinlay
94 * @author Eric Blake <ebb9@email.byu.edu>
95 * @see HashMap
96 * @see TreeMap
97 * @see IdentityHashMap
98 * @see LinkedHashMap
99 * @since 1.0
100 * @status updated to 1.4
101 */
102 public class Hashtable extends Dictionary
103 implements Map, Cloneable, Serializable
104 {
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.
107
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.
110 */
111 private static final int DEFAULT_CAPACITY = 11;
112
113 /** An "enum" of iterator types. */
114 // Package visible for use by nested classes.
115 static final int KEYS = 0,
116 VALUES = 1,
117 ENTRIES = 2;
118
119 /**
120 * The default load factor; this is explicitly specified by the spec.
121 */
122 private static final float DEFAULT_LOAD_FACTOR = 0.75f;
123
124 /**
125 * Compatible with JDK 1.0+.
126 */
127 private static final long serialVersionUID = 1421746759512286392L;
128
129 /**
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>.
133 * @serial
134 */
135 private int threshold;
136
137 /**
138 * Load factor of this Hashtable: used in computing the threshold.
139 * @serial
140 */
141 private final float loadFactor;
142
143 /**
144 * Array containing the actual key-value mappings.
145 */
146 // Package visible for use by nested classes.
147 transient HashEntry[] buckets;
148
149 /**
150 * Counts the number of modifications this Hashtable has undergone, used
151 * by Iterators to know when to throw ConcurrentModificationExceptions.
152 */
153 // Package visible for use by nested classes.
154 transient int modCount;
155
156 /**
157 * The size of this Hashtable: denotes the number of key-value pairs.
158 */
159 // Package visible for use by nested classes.
160 transient int size;
161
162 /**
163 * The cache for {@link #keySet()}.
164 */
165 private transient Set keys;
166
167 /**
168 * The cache for {@link #values()}.
169 */
170 private transient Collection values;
171
172 /**
173 * The cache for {@link #entrySet()}.
174 */
175 private transient Set entries;
176
177 /**
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.
181 */
182 private static final class HashEntry extends AbstractMap.BasicMapEntry
183 {
184 /** The next entry in the linked list. */
185 HashEntry next;
186
187 /**
188 * Simple constructor.
189 * @param key the key, already guaranteed non-null
190 * @param value the value, already guaranteed non-null
191 */
192 HashEntry(Object key, Object value)
193 {
194 super(key, value);
195 }
196
197 /**
198 * Resets the value.
199 * @param newValue the new value
200 * @return the prior value
201 * @throws NullPointerException if <code>newVal</code> is null
202 */
203 public Object setValue(Object newVal)
204 {
205 if (newVal == null)
206 throw new NullPointerException();
207 return super.setValue(newVal);
208 }
209 }
210
211 /**
212 * Construct a new Hashtable with the default capacity (11) and the default
213 * load factor (0.75).
214 */
215 public Hashtable()
216 {
217 this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
218 }
219
220 /**
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.
223 * <p>
224 *
225 * Every element in Map m will be put into this new Hashtable.
226 *
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
231 * to or from `null'.
232 * @since 1.2
233 */
234 public Hashtable(Map m)
235 {
236 this(Math.max(m.size() * 2, DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR);
237 putAllInternal(m);
238 }
239
240 /**
241 * Construct a new Hashtable with a specific inital capacity and
242 * default load factor of 0.75.
243 *
244 * @param initialCapacity the initial capacity of this Hashtable (&gt;= 0)
245 * @throws IllegalArgumentException if (initialCapacity &lt; 0)
246 */
247 public Hashtable(int initialCapacity)
248 {
249 this(initialCapacity, DEFAULT_LOAD_FACTOR);
250 }
251
252 /**
253 * Construct a new Hashtable with a specific initial capacity and
254 * load factor.
255 *
256 * @param initialCapacity the initial capacity (&gt;= 0)
257 * @param loadFactor the load factor (&gt; 0, not NaN)
258 * @throws IllegalArgumentException if (initialCapacity &lt; 0) ||
259 * ! (loadFactor &gt; 0.0)
260 */
261 public Hashtable(int initialCapacity, float loadFactor)
262 {
263 if (initialCapacity < 0)
264 throw new IllegalArgumentException("Illegal Capacity: "
265 + initialCapacity);
266 if (! (loadFactor > 0)) // check for NaN too
267 throw new IllegalArgumentException("Illegal Load: " + loadFactor);
268
269 if (initialCapacity == 0)
270 initialCapacity = 1;
271 buckets = new HashEntry[initialCapacity];
272 this.loadFactor = loadFactor;
273 threshold = (int) (initialCapacity * loadFactor);
274 }
275
276 /**
277 * Returns the number of key-value mappings currently in this hashtable.
278 * @return the size
279 */
280 public synchronized int size()
281 {
282 return size;
283 }
284
285 /**
286 * Returns true if there are no key-value mappings currently in this table.
287 * @return <code>size() == 0</code>
288 */
289 public synchronized boolean isEmpty()
290 {
291 return size == 0;
292 }
293
294 /**
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.
298 *
299 * @return the keys
300 * @see #elements()
301 * @see #keySet()
302 */
303 public Enumeration keys()
304 {
305 return new Enumerator(KEYS);
306 }
307
308 /**
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.
312 *
313 * @return the values
314 * @see #keys()
315 * @see #values()
316 */
317 public Enumeration elements()
318 {
319 return new Enumerator(VALUES);
320 }
321
322 /**
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).
326 * <p>
327 *
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)
333 */
334 public synchronized boolean contains(Object value)
335 {
336 return containsValue(value);
337 }
338
339 /**
340 * Returns true if this Hashtable contains a value <code>o</code>, such that
341 * <code>o.equals(value)</code>. This is the new API for the old
342 * <code>contains()</code>.
343 *
344 * @param value the value to search for in this Hashtable
345 * @return true if at least one key maps to the value
346 * @see #contains(Object)
347 * @see #containsKey(Object)
348 * @throws NullPointerException if <code>value</code> is null
349 * @since 1.2
350 */
351 public boolean containsValue(Object value)
352 {
353 for (int i = buckets.length - 1; i >= 0; i--)
354 {
355 HashEntry e = buckets[i];
356 while (e != null)
357 {
358 if (value.equals(e.value))
359 return true;
360 e = e.next;
361 }
362 }
363
364 // Must throw on null argument even if the table is empty
365 if (value == null)
366 throw new NullPointerException();
367
368 return false;
369 }
370
371 /**
372 * Returns true if the supplied object <code>equals()</code> a key
373 * in this Hashtable.
374 *
375 * @param key the key to search for in this Hashtable
376 * @return true if the key is in the table
377 * @throws NullPointerException if key is null
378 * @see #containsValue(Object)
379 */
380 public synchronized boolean containsKey(Object key)
381 {
382 int idx = hash(key);
383 HashEntry e = buckets[idx];
384 while (e != null)
385 {
386 if (key.equals(e.key))
387 return true;
388 e = e.next;
389 }
390 return false;
391 }
392
393 /**
394 * Return the value in this Hashtable associated with the supplied key,
395 * or <code>null</code> if the key maps to nothing.
396 *
397 * @param key the key for which to fetch an associated value
398 * @return what the key maps to, if present
399 * @throws NullPointerException if key is null
400 * @see #put(Object, Object)
401 * @see #containsKey(Object)
402 */
403 public synchronized Object get(Object key)
404 {
405 int idx = hash(key);
406 HashEntry e = buckets[idx];
407 while (e != null)
408 {
409 if (key.equals(e.key))
410 return e.value;
411 e = e.next;
412 }
413 return null;
414 }
415
416 /**
417 * Puts the supplied value into the Map, mapped by the supplied key.
418 * Neither parameter may be null. The value may be retrieved by any
419 * object which <code>equals()</code> this key.
420 *
421 * @param key the key used to locate the value
422 * @param value the value to be stored in the table
423 * @return the prior mapping of the key, or null if there was none
424 * @throws NullPointerException if key or value is null
425 * @see #get(Object)
426 * @see Object#equals(Object)
427 */
428 public synchronized Object put(Object key, Object value)
429 {
430 int idx = hash(key);
431 HashEntry e = buckets[idx];
432
433 // Check if value is null since it is not permitted.
434 if (value == null)
435 throw new NullPointerException();
436
437 while (e != null)
438 {
439 if (key.equals(e.key))
440 {
441 // Bypass e.setValue, since we already know value is non-null.
442 Object r = e.value;
443 e.value = value;
444 return r;
445 }
446 else
447 {
448 e = e.next;
449 }
450 }
451
452 // At this point, we know we need to add a new entry.
453 modCount++;
454 if (++size > threshold)
455 {
456 rehash();
457 // Need a new hash value to suit the bigger table.
458 idx = hash(key);
459 }
460
461 e = new HashEntry(key, value);
462
463 e.next = buckets[idx];
464 buckets[idx] = e;
465
466 return null;
467 }
468
469 /**
470 * Removes from the table and returns the value which is mapped by the
471 * supplied key. If the key maps to nothing, then the table remains
472 * unchanged, and <code>null</code> is returned.
473 *
474 * @param key the key used to locate the value to remove
475 * @return whatever the key mapped to, if present
476 */
477 public synchronized Object remove(Object key)
478 {
479 int idx = hash(key);
480 HashEntry e = buckets[idx];
481 HashEntry last = null;
482
483 while (e != null)
484 {
485 if (key.equals(e.key))
486 {
487 modCount++;
488 if (last == null)
489 buckets[idx] = e.next;
490 else
491 last.next = e.next;
492 size--;
493 return e.value;
494 }
495 last = e;
496 e = e.next;
497 }
498 return null;
499 }
500
501 /**
502 * Copies all elements of the given map into this hashtable. However, no
503 * mapping can contain null as key or value. If this table already has
504 * a mapping for a key, the new mapping replaces the current one.
505 *
506 * @param m the map to be hashed into this
507 * @throws NullPointerException if m is null, or contains null keys or values
508 */
509 public synchronized void putAll(Map m)
510 {
511 Iterator itr = m.entrySet().iterator();
512
513 for (int msize = m.size(); msize > 0; msize--)
514 {
515 Map.Entry e = (Map.Entry) itr.next();
516 // Optimize in case the Entry is one of our own.
517 if (e instanceof AbstractMap.BasicMapEntry)
518 {
519 AbstractMap.BasicMapEntry entry = (AbstractMap.BasicMapEntry) e;
520 put(entry.key, entry.value);
521 }
522 else
523 {
524 put(e.getKey(), e.getValue());
525 }
526 }
527 }
528
529 /**
530 * Clears the hashtable so it has no keys. This is O(1).
531 */
532 public synchronized void clear()
533 {
534 if (size > 0)
535 {
536 modCount++;
537 Arrays.fill(buckets, null);
538 size = 0;
539 }
540 }
541
542 /**
543 * Returns a shallow clone of this Hashtable. The Map itself is cloned,
544 * but its contents are not. This is O(n).
545 *
546 * @return the clone
547 */
548 public synchronized Object clone()
549 {
550 Hashtable copy = null;
551 try
552 {
553 copy = (Hashtable) super.clone();
554 }
555 catch (CloneNotSupportedException x)
556 {
557 // This is impossible.
558 }
559 copy.buckets = new HashEntry[buckets.length];
560 copy.putAllInternal(this);
561 // Clear the caches.
562 copy.keys = null;
563 copy.values = null;
564 copy.entries = null;
565 return copy;
566 }
567
568 /**
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>
572 *
573 * NOTE: if the <code>toString()</code> method of any key or value
574 * throws an exception, this will fail for the same reason.
575 *
576 * @return the string representation
577 */
578 public synchronized String toString()
579 {
580 // Since we are already synchronized, and entrySet().iterator()
581 // would repeatedly re-lock/release the monitor, we directly use the
582 // unsynchronized HashIterator instead.
583 Iterator entries = new HashIterator(ENTRIES);
584 StringBuffer r = new StringBuffer("{");
585 for (int pos = size; pos > 0; pos--)
586 {
587 r.append(entries.next());
588 if (pos > 1)
589 r.append(", ");
590 }
591 r.append("}");
592 return r.toString();
593 }
594
595 /**
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}.
604 *
605 * @return a set view of the keys
606 * @see #values()
607 * @see #entrySet()
608 * @since 1.2
609 */
610 public Set keySet()
611 {
612 if (keys == null)
613 {
614 // Create a synchronized AbstractSet with custom implementations of
615 // those methods that can be overridden easily and efficiently.
616 Set r = new AbstractSet()
617 {
618 public int size()
619 {
620 return size;
621 }
622
623 public Iterator iterator()
624 {
625 return new HashIterator(KEYS);
626 }
627
628 public void clear()
629 {
630 Hashtable.this.clear();
631 }
632
633 public boolean contains(Object o)
634 {
635 if (o == null)
636 return false;
637 return containsKey(o);
638 }
639
640 public boolean remove(Object o)
641 {
642 return Hashtable.this.remove(o) != null;
643 }
644 };
645 // We must specify the correct object to synchronize upon, hence the
646 // use of a non-public API
647 keys = new Collections.SynchronizedSet(this, r);
648 }
649 return keys;
650 }
651
652 /**
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}.
662 *
663 * @return a bag view of the values
664 * @see #keySet()
665 * @see #entrySet()
666 * @since 1.2
667 */
668 public Collection values()
669 {
670 if (values == null)
671 {
672 // We don't bother overriding many of the optional methods, as doing so
673 // wouldn't provide any significant performance advantage.
674 Collection r = new AbstractCollection()
675 {
676 public int size()
677 {
678 return size;
679 }
680
681 public Iterator iterator()
682 {
683 return new HashIterator(VALUES);
684 }
685
686 public void clear()
687 {
688 Hashtable.this.clear();
689 }
690 };
691 // We must specify the correct object to synchronize upon, hence the
692 // use of a non-public API
693 values = new Collections.SynchronizedCollection(this, r);
694 }
695 return values;
696 }
697
698 /**
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)
708 * will fail.
709 * <p>
710 *
711 * Note that the iterators for all three views, from keySet(), entrySet(),
712 * and values(), traverse the hashtable in the same sequence.
713 *
714 * @return a set view of the entries
715 * @see #keySet()
716 * @see #values()
717 * @see Map.Entry
718 * @since 1.2
719 */
720 public Set entrySet()
721 {
722 if (entries == null)
723 {
724 // Create an AbstractSet with custom implementations of those methods
725 // that can be overridden easily and efficiently.
726 Set r = new AbstractSet()
727 {
728 public int size()
729 {
730 return size;
731 }
732
733 public Iterator iterator()
734 {
735 return new HashIterator(ENTRIES);
736 }
737
738 public void clear()
739 {
740 Hashtable.this.clear();
741 }
742
743 public boolean contains(Object o)
744 {
745 return getEntry(o) != null;
746 }
747
748 public boolean remove(Object o)
749 {
750 HashEntry e = getEntry(o);
751 if (e != null)
752 {
753 Hashtable.this.remove(e.key);
754 return true;
755 }
756 return false;
757 }
758 };
759 // We must specify the correct object to synchronize upon, hence the
760 // use of a non-public API
761 entries = new Collections.SynchronizedSet(this, r);
762 }
763 return entries;
764 }
765
766 /**
767 * Returns true if this Hashtable equals the supplied Object <code>o</code>.
768 * As specified by Map, this is:
769 * <code>
770 * (o instanceof Map) && entrySet().equals(((Map) o).entrySet());
771 * </code>
772 *
773 * @param o the object to compare to
774 * @return true if o is an equal map
775 * @since 1.2
776 */
777 public boolean equals(Object o)
778 {
779 // no need to synchronize, entrySet().equals() does that
780 if (o == this)
781 return true;
782 if (!(o instanceof Map))
783 return false;
784
785 return entrySet().equals(((Map) o).entrySet());
786 }
787
788 /**
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
791 *
792 * @return the sum of the hashcodes of the entries
793 * @since 1.2
794 */
795 public synchronized int hashCode()
796 {
797 // Since we are already synchronized, and entrySet().iterator()
798 // would repeatedly re-lock/release the monitor, we directly use the
799 // unsynchronized HashIterator instead.
800 Iterator itr = new HashIterator(ENTRIES);
801 int hashcode = 0;
802 for (int pos = size; pos > 0; pos--)
803 hashcode += itr.next().hashCode();
804
805 return hashcode;
806 }
807
808 /**
809 * Helper method that returns an index in the buckets array for `key'
810 * based on its hashCode().
811 *
812 * @param key the key
813 * @return the bucket number
814 * @throws NullPointerException if key is null
815 */
816 private int hash(Object key)
817 {
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;
822 }
823
824 /**
825 * Helper method for entrySet(), which matches both key and value
826 * simultaneously. Ignores null, as mentioned in entrySet().
827 *
828 * @param o the entry to match
829 * @return the matching entry, if found, or null
830 * @see #entrySet()
831 */
832 // Package visible, for use in nested classes.
833 HashEntry getEntry(Object o)
834 {
835 if (! (o instanceof Map.Entry))
836 return null;
837 Object key = ((Map.Entry) o).getKey();
838 if (key == null)
839 return null;
840
841 int idx = hash(key);
842 HashEntry e = buckets[idx];
843 while (e != null)
844 {
845 if (o.equals(e))
846 return e;
847 e = e.next;
848 }
849 return null;
850 }
851
852 /**
853 * A simplified, more efficient internal implementation of putAll(). The
854 * Map constructor and clone() should not call putAll or put, in order to
855 * be compatible with the JDK implementation with respect to subclasses.
856 *
857 * @param m the map to initialize this from
858 */
859 void putAllInternal(Map m)
860 {
861 Iterator itr = m.entrySet().iterator();
862 int msize = m.size();
863 this.size = msize;
864
865 for (; msize > 0; msize--)
866 {
867 Map.Entry e = (Map.Entry) itr.next();
868 Object key = e.getKey();
869 int idx = hash(key);
870 HashEntry he = new HashEntry(key, e.getValue());
871 he.next = buckets[idx];
872 buckets[idx] = he;
873 }
874 }
875
876 /**
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() &gt; threshold. Note that the existing Entry objects are reused in
880 * the new hash table.
881 * <p>
882 *
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.
886 */
887 protected void rehash()
888 {
889 HashEntry[] oldBuckets = buckets;
890
891 int newcapacity = (buckets.length * 2) + 1;
892 threshold = (int) (newcapacity * loadFactor);
893 buckets = new HashEntry[newcapacity];
894
895 for (int i = oldBuckets.length - 1; i >= 0; i--)
896 {
897 HashEntry e = oldBuckets[i];
898 while (e != null)
899 {
900 int idx = hash(e.key);
901 HashEntry dest = buckets[idx];
902
903 if (dest != null)
904 {
905 while (dest.next != null)
906 dest = dest.next;
907 dest.next = e;
908 }
909 else
910 {
911 buckets[idx] = e;
912 }
913
914 HashEntry next = e.next;
915 e.next = null;
916 e = next;
917 }
918 }
919 }
920
921 /**
922 * Serializes this object to the given stream.
923 *
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).
930 */
931 private synchronized void writeObject(ObjectOutputStream s)
932 throws IOException
933 {
934 // Write the threshold and loadFactor fields.
935 s.defaultWriteObject();
936
937 s.writeInt(buckets.length);
938 s.writeInt(size);
939 // Since we are already synchronized, and entrySet().iterator()
940 // would repeatedly re-lock/release the monitor, we directly use the
941 // unsynchronized HashIterator instead.
942 Iterator it = new HashIterator(ENTRIES);
943 while (it.hasNext())
944 {
945 HashEntry entry = (HashEntry) it.next();
946 s.writeObject(entry.key);
947 s.writeObject(entry.value);
948 }
949 }
950
951 /**
952 * Deserializes this object from the given stream.
953 *
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).
961 */
962 private void readObject(ObjectInputStream s)
963 throws IOException, ClassNotFoundException
964 {
965 // Read the threshold and loadFactor fields.
966 s.defaultReadObject();
967
968 // Read and use capacity.
969 buckets = new HashEntry[s.readInt()];
970 int len = s.readInt();
971
972 // Read and use key/value pairs.
973 // TODO: should we be defensive programmers, and check for illegal nulls?
974 while (--len >= 0)
975 put(s.readObject(), s.readObject());
976 }
977
978 /**
979 * A class which implements the Iterator interface and is used for
980 * iterating over Hashtables.
981 * This implementation is parameterized to give a sequential view of
982 * keys, values, or entries; it also allows the removal of elements,
983 * as per the Javasoft spec. Note that it is not synchronized; this is
984 * a performance enhancer since it is never exposed externally and is
985 * only used within synchronized blocks above.
986 *
987 * @author Jon Zeppieri
988 */
989 private final class HashIterator implements Iterator
990 {
991 /**
992 * The type of this Iterator: {@link #KEYS}, {@link #VALUES},
993 * or {@link #ENTRIES}.
994 */
995 final int type;
996 /**
997 * The number of modifications to the backing Hashtable that we know about.
998 */
999 int knownMod = modCount;
1000 /** The number of elements remaining to be returned by next(). */
1001 int count = size;
1002 /** Current index in the physical hash table. */
1003 int idx = buckets.length;
1004 /** The last Entry returned by a next() call. */
1005 HashEntry last;
1006 /**
1007 * The next entry that should be returned by next(). It is set to something
1008 * if we're iterating through a bucket that contains multiple linked
1009 * entries. It is null if next() needs to find a new bucket.
1010 */
1011 HashEntry next;
1012
1013 /**
1014 * Construct a new HashIterator with the supplied type.
1015 * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
1016 */
1017 HashIterator(int type)
1018 {
1019 this.type = type;
1020 }
1021
1022 /**
1023 * Returns true if the Iterator has more elements.
1024 * @return true if there are more elements
1025 * @throws ConcurrentModificationException if the hashtable was modified
1026 */
1027 public boolean hasNext()
1028 {
1029 if (knownMod != modCount)
1030 throw new ConcurrentModificationException();
1031 return count > 0;
1032 }
1033
1034 /**
1035 * Returns the next element in the Iterator's sequential view.
1036 * @return the next element
1037 * @throws ConcurrentModificationException if the hashtable was modified
1038 * @throws NoSuchElementException if there is none
1039 */
1040 public Object next()
1041 {
1042 if (knownMod != modCount)
1043 throw new ConcurrentModificationException();
1044 if (count == 0)
1045 throw new NoSuchElementException();
1046 count--;
1047 HashEntry e = next;
1048
1049 while (e == null)
1050 e = buckets[--idx];
1051
1052 next = e.next;
1053 last = e;
1054 if (type == VALUES)
1055 return e.value;
1056 if (type == KEYS)
1057 return e.key;
1058 return e;
1059 }
1060
1061 /**
1062 * Removes from the backing Hashtable the last element which was fetched
1063 * with the <code>next()</code> method.
1064 * @throws ConcurrentModificationException if the hashtable was modified
1065 * @throws IllegalStateException if called when there is no last element
1066 */
1067 public void remove()
1068 {
1069 if (knownMod != modCount)
1070 throw new ConcurrentModificationException();
1071 if (last == null)
1072 throw new IllegalStateException();
1073
1074 Hashtable.this.remove(last.key);
1075 last = null;
1076 knownMod++;
1077 }
1078 } // class HashIterator
1079
1080
1081 /**
1082 * Enumeration view of this Hashtable, providing sequential access to its
1083 * elements; this implementation is parameterized to provide access either
1084 * to the keys or to the values in the Hashtable.
1085 *
1086 * <b>NOTE</b>: Enumeration is not safe if new elements are put in the table
1087 * as this could cause a rehash and we'd completely lose our place. Even
1088 * without a rehash, it is undetermined if a new element added would
1089 * appear in the enumeration. The spec says nothing about this, but
1090 * the "Java Class Libraries" book infers that modifications to the
1091 * hashtable during enumeration causes indeterminate results. Don't do it!
1092 *
1093 * @author Jon Zeppieri
1094 */
1095 private final class Enumerator implements Enumeration
1096 {
1097 /**
1098 * The type of this Iterator: {@link #KEYS} or {@link #VALUES}.
1099 */
1100 final int type;
1101 /** The number of elements remaining to be returned by next(). */
1102 int count = size;
1103 /** Current index in the physical hash table. */
1104 int idx = buckets.length;
1105 /**
1106 * Entry which will be returned by the next nextElement() call. It is
1107 * set if we are iterating through a bucket with multiple entries, or null
1108 * if we must look in the next bucket.
1109 */
1110 HashEntry next;
1111
1112 /**
1113 * Construct the enumeration.
1114 * @param type either {@link #KEYS} or {@link #VALUES}.
1115 */
1116 Enumerator(int type)
1117 {
1118 this.type = type;
1119 }
1120
1121 /**
1122 * Checks whether more elements remain in the enumeration.
1123 * @return true if nextElement() will not fail.
1124 */
1125 public boolean hasMoreElements()
1126 {
1127 return count > 0;
1128 }
1129
1130 /**
1131 * Returns the next element.
1132 * @return the next element
1133 * @throws NoSuchElementException if there is none.
1134 */
1135 public Object nextElement()
1136 {
1137 if (count == 0)
1138 throw new NoSuchElementException("Hashtable Enumerator");
1139 count--;
1140 HashEntry e = next;
1141
1142 while (e == null)
1143 e = buckets[--idx];
1144
1145 next = e.next;
1146 return type == VALUES ? e.value : e.key;
1147 }
1148 } // class Enumerator
1149 } // class Hashtable

savannah-hackers-public@gnu.org
ViewVC Help
Powered by ViewVC 1.1.26