1 /*
2 * Copyright (c) 1994, 2011, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27 import java.io.*;
28
29 /**
30 * This class implements a hash table, which maps keys to values. Any
31 * non-<code>null</code> object can be used as a key or as a value. <p>
32 *
33 * To successfully store and retrieve objects from a hashtable, the
34 * objects used as keys must implement the <code>hashCode</code>
35 * method and the <code>equals</code> method. <p>
36 *
37 * An instance of <code>Hashtable</code> has two parameters that affect its
38 * performance: <i>initial capacity</i> and <i>load factor</i>. The
39 * <i>capacity</i> is the number of <i>buckets</i> in the hash table, and the
40 * <i>initial capacity</i> is simply the capacity at the time the hash table
41 * is created. Note that the hash table is <i>open</i>: in the case of a "hash
42 * collision", a single bucket stores multiple entries, which must be searched
43 * sequentially. The <i>load factor</i> is a measure of how full the hash
44 * table is allowed to get before its capacity is automatically increased.
45 * The initial capacity and load factor parameters are merely hints to
46 * the implementation. The exact details as to when and whether the rehash
47 * method is invoked are implementation-dependent.<p>
48 *
49 * Generally, the default load factor (.75) offers a good tradeoff between
50 * time and space costs. Higher values decrease the space overhead but
51 * increase the time cost to look up an entry (which is reflected in most
52 * <tt>Hashtable</tt> operations, including <tt>get</tt> and <tt>put</tt>).<p>
53 *
54 * The initial capacity controls a tradeoff between wasted space and the
55 * need for <code>rehash</code> operations, which are time-consuming.
56 * No <code>rehash</code> operations will <i>ever</i> occur if the initial
57 * capacity is greater than the maximum number of entries the
58 * <tt>Hashtable</tt> will contain divided by its load factor. However,
59 * setting the initial capacity too high can waste space.<p>
60 *
61 * If many entries are to be made into a <code>Hashtable</code>,
62 * creating it with a sufficiently large capacity may allow the
63 * entries to be inserted more efficiently than letting it perform
64 * automatic rehashing as needed to grow the table. <p>
65 *
66 * This example creates a hashtable of numbers. It uses the names of
67 * the numbers as keys:
68 * <pre> {@code
69 * Hashtable<String, Integer> numbers
70 * = new Hashtable<String, Integer>();
71 * numbers.put("one", 1);
72 * numbers.put("two", 2);
73 * numbers.put("three", 3);}</pre>
74 *
75 * <p>To retrieve a number, use the following code:
76 * <pre> {@code
77 * Integer n = numbers.get("two");
78 * if (n != null) {
79 * System.out.println("two = " + n);
80 * }}</pre>
81 *
82 * <p>The iterators returned by the <tt>iterator</tt> method of the collections
83 * returned by all of this class's "collection view methods" are
84 * <em>fail-fast</em>: if the Hashtable is structurally modified at any time
85 * after the iterator is created, in any way except through the iterator's own
86 * <tt>remove</tt> method, the iterator will throw a {@link
87 * ConcurrentModificationException}. Thus, in the face of concurrent
88 * modification, the iterator fails quickly and cleanly, rather than risking
89 * arbitrary, non-deterministic behavior at an undetermined time in the future.
90 * The Enumerations returned by Hashtable's keys and elements methods are
91 * <em>not</em> fail-fast.
92 *
93 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
94 * as it is, generally speaking, impossible to make any hard guarantees in the
95 * presence of unsynchronized concurrent modification. Fail-fast iterators
96 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
97 * Therefore, it would be wrong to write a program that depended on this
98 * exception for its correctness: <i>the fail-fast behavior of iterators
99 * should be used only to detect bugs.</i>
100 *
101 * <p>As of the Java 2 platform v1.2, this class was retrofitted to
102 * implement the {@link Map} interface, making it a member of the
103 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
104 *
105 * Java Collections Framework</a>. Unlike the new collection
106 * implementations, {@code Hashtable} is synchronized. If a
107 * thread-safe implementation is not needed, it is recommended to use
108 * {@link HashMap} in place of {@code Hashtable}. If a thread-safe
109 * highly-concurrent implementation is desired, then it is recommended
110 * to use {@link java.util.concurrent.ConcurrentHashMap} in place of
111 * {@code Hashtable}.
112 *
113 * @author Arthur van Hoff
114 * @author Josh Bloch
115 * @author Neal Gafter
116 * @see Object#equals(java.lang.Object)
117 * @see Object#hashCode()
118 * @see Hashtable#rehash()
119 * @see Collection
120 * @see Map
121 * @see HashMap
122 * @see TreeMap
123 * @since JDK1.0
124 */
125 public class Hashtable<K,V>
126 extends Dictionary<K,V>
127 implements Map<K,V>, Cloneable, java.io.Serializable {
128
129 /**
130 * The hash table data.
131 */
132 private transient Entry<K,V>[] table;
133
134 /**
135 * The total number of entries in the hash table.
136 */
137 private transient int count;
138
139 /**
140 * The table is rehashed when its size exceeds this threshold. (The
141 * value of this field is (int)(capacity * loadFactor).)
142 *
143 * @serial
144 */
145 private int threshold;
146
147 /**
148 * The load factor for the hashtable.
149 *
150 * @serial
151 */
152 private float loadFactor;
153
154 /**
155 * The number of times this Hashtable has been structurally modified
156 * Structural modifications are those that change the number of entries in
157 * the Hashtable or otherwise modify its internal structure (e.g.,
158 * rehash). This field is used to make iterators on Collection-views of
159 * the Hashtable fail-fast. (See ConcurrentModificationException).
160 */
161 private transient int modCount = 0;
162
163 /** use serialVersionUID from JDK 1.0.2 for interoperability */
164 private static final long serialVersionUID = 1421746759512286392L;
165
166 /**
167 * The default threshold of map capacity above which alternative hashing is
168 * used for String keys. Alternative hashing reduces the incidence of
169 * collisions due to weak hash code calculation for String keys.
170 * <p>
171 * This value may be overridden by defining the system property
172 * {@code jdk.map.althashing.threshold}. A property value of {@code 1}
173 * forces alternative hashing to be used at all times whereas
174 * {@code -1} value ensures that alternative hashing is never used.
175 */
176 static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
177
178 /**
179 * holds values which can't be initialized until after VM is booted.
180 */
181 private static class Holder {
182
183 /**
184 * Table capacity above which to switch to use alternative hashing.
185 */
186 static final int ALTERNATIVE_HASHING_THRESHOLD;
187
188 static {
189 String altThreshold = java.security.AccessController.doPrivileged(
190 new sun.security.action.GetPropertyAction(
191 "jdk.map.althashing.threshold"));
192
193 int threshold;
194 try {
195 threshold = (null != altThreshold)
196 ? Integer.parseInt(altThreshold)
197 : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
198
199 // disable alternative hashing if -1
200 if (threshold == -1) {
201 threshold = Integer.MAX_VALUE;
202 }
203
204 if (threshold < 0) {
205 throw new IllegalArgumentException("value must be positive integer.");
206 }
207 } catch(IllegalArgumentException failed) {
208 throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
209 }
210
211 ALTERNATIVE_HASHING_THRESHOLD = threshold;
212 }
213 }
214
215 /**
216 * A randomizing value associated with this instance that is applied to
217 * hash code of keys to make hash collisions harder to find.
218 */
219 transient int hashSeed;
220
221 /**
222 * Initialize the hashing mask value.
223 */
224 final boolean initHashSeedAsNeeded(int capacity) {
225 boolean currentAltHashing = hashSeed != 0;
226 boolean useAltHashing = sun.misc.VM.isBooted() &&
227 (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
228 boolean switching = currentAltHashing ^ useAltHashing;
229 if (switching) {
230 hashSeed = useAltHashing
231 ? sun.misc.Hashing.randomHashSeed(this)
232 : 0;
233 }
234 return switching;
235 }
236
237 private int hash(Object k) {
238 // hashSeed will be zero if alternative hashing is disabled.
239 return hashSeed ^ k.hashCode();
240 }
241
242 /**
243 * Constructs a new, empty hashtable with the specified initial
244 * capacity and the specified load factor.
245 *
246 * @param initialCapacity the initial capacity of the hashtable.
247 * @param loadFactor the load factor of the hashtable.
248 * @exception IllegalArgumentException if the initial capacity is less
249 * than zero, or if the load factor is nonpositive.
250 */
251 public Hashtable(int initialCapacity, float loadFactor) {
252 if (initialCapacity < 0)
253 throw new IllegalArgumentException("Illegal Capacity: "+
254 initialCapacity);
255 if (loadFactor <= 0 || Float.isNaN(loadFactor))
256 throw new IllegalArgumentException("Illegal Load: "+loadFactor);
257
258 if (initialCapacity==0)
259 initialCapacity = 1;
260 this.loadFactor = loadFactor;
261 table = new Entry[initialCapacity];
262 threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
263 initHashSeedAsNeeded(initialCapacity);
264 }
265
266 /**
267 * Constructs a new, empty hashtable with the specified initial capacity
268 * and default load factor (0.75).
269 *
270 * @param initialCapacity the initial capacity of the hashtable.
271 * @exception IllegalArgumentException if the initial capacity is less
272 * than zero.
273 */
274 public Hashtable(int initialCapacity) {
275 this(initialCapacity, 0.75f);
276 }
277
278 /**
279 * Constructs a new, empty hashtable with a default initial capacity (11)
280 * and load factor (0.75).
281 */
282 public Hashtable() {
283 this(11, 0.75f);
284 }
285
286 /**
287 * Constructs a new hashtable with the same mappings as the given
288 * Map. The hashtable is created with an initial capacity sufficient to
289 * hold the mappings in the given Map and a default load factor (0.75).
290 *
291 * @param t the map whose mappings are to be placed in this map.
292 * @throws NullPointerException if the specified map is null.
293 * @since 1.2
294 */
295 public Hashtable(Map<? extends K, ? extends V> t) {
296 this(Math.max(2*t.size(), 11), 0.75f);
297 putAll(t);
298 }
299
300 /**
301 * Returns the number of keys in this hashtable.
302 *
303 * @return the number of keys in this hashtable.
304 */
305 public synchronized int size() {
306 return count;
307 }
308
309 /**
310 * Tests if this hashtable maps no keys to values.
311 *
312 * @return <code>true</code> if this hashtable maps no keys to values;
313 * <code>false</code> otherwise.
314 */
315 public synchronized boolean isEmpty() {
316 return count == 0;
317 }
318
319 /**
320 * Returns an enumeration of the keys in this hashtable.
321 *
322 * @return an enumeration of the keys in this hashtable.
323 * @see Enumeration
324 * @see #elements()
325 * @see #keySet()
326 * @see Map
327 */
328 public synchronized Enumeration<K> keys() {
329 return this.<K>getEnumeration(KEYS);
330 }
331
332 /**
333 * Returns an enumeration of the values in this hashtable.
334 * Use the Enumeration methods on the returned object to fetch the elements
335 * sequentially.
336 *
337 * @return an enumeration of the values in this hashtable.
338 * @see java.util.Enumeration
339 * @see #keys()
340 * @see #values()
341 * @see Map
342 */
343 public synchronized Enumeration<V> elements() {
344 return this.<V>getEnumeration(VALUES);
345 }
346
347 /**
348 * Tests if some key maps into the specified value in this hashtable.
349 * This operation is more expensive than the {@link #containsKey
350 * containsKey} method.
351 *
352 * <p>Note that this method is identical in functionality to
353 * {@link #containsValue containsValue}, (which is part of the
354 * {@link Map} interface in the collections framework).
355 *
356 * @param value a value to search for
357 * @return <code>true</code> if and only if some key maps to the
358 * <code>value</code> argument in this hashtable as
359 * determined by the <tt>equals</tt> method;
360 * <code>false</code> otherwise.
361 * @exception NullPointerException if the value is <code>null</code>
362 */
363 public synchronized boolean contains(Object value) {
364 if (value == null) {
365 throw new NullPointerException();
366 }
367
368 Entry tab[] = table;
369 for (int i = tab.length ; i-- > 0 ;) {
370 for (Entry<K,V> e = tab[i] ; e != null ; e = e.next) {
371 if (e.value.equals(value)) {
372 return true;
373 }
374 }
375 }
376 return false;
377 }
378
379 /**
380 * Returns true if this hashtable maps one or more keys to this value.
381 *
382 * <p>Note that this method is identical in functionality to {@link
383 * #contains contains} (which predates the {@link Map} interface).
384 *
385 * @param value value whose presence in this hashtable is to be tested
386 * @return <tt>true</tt> if this map maps one or more keys to the
387 * specified value
388 * @throws NullPointerException if the value is <code>null</code>
389 * @since 1.2
390 */
391 public boolean containsValue(Object value) {
392 return contains(value);
393 }
394
395 /**
396 * Tests if the specified object is a key in this hashtable.
397 *
398 * @param key possible key
399 * @return <code>true</code> if and only if the specified object
400 * is a key in this hashtable, as determined by the
401 * <tt>equals</tt> method; <code>false</code> otherwise.
402 * @throws NullPointerException if the key is <code>null</code>
403 * @see #contains(Object)
404 */
405 public synchronized boolean containsKey(Object key) {
406 Entry tab[] = table;
407 int hash = hash(key);
408 int index = (hash & 0x7FFFFFFF) % tab.length;
409 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
410 if ((e.hash == hash) && e.key.equals(key)) {
411 return true;
412 }
413 }
414 return false;
415 }
416
417 /**
418 * Returns the value to which the specified key is mapped,
419 * or {@code null} if this map contains no mapping for the key.
420 *
421 * <p>More formally, if this map contains a mapping from a key
422 * {@code k} to a value {@code v} such that {@code (key.equals(k))},
423 * then this method returns {@code v}; otherwise it returns
424 * {@code null}. (There can be at most one such mapping.)
425 *
426 * @param key the key whose associated value is to be returned
427 * @return the value to which the specified key is mapped, or
428 * {@code null} if this map contains no mapping for the key
429 * @throws NullPointerException if the specified key is null
430 * @see #put(Object, Object)
431 */
432 public synchronized V get(Object key) {
433 Entry tab[] = table;
434 int hash = hash(key);
435 int index = (hash & 0x7FFFFFFF) % tab.length;
436 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
437 if ((e.hash == hash) && e.key.equals(key)) {
438 return e.value;
439 }
440 }
441 return null;
442 }
443
444 /**
445 * The maximum size of array to allocate.
446 * Some VMs reserve some header words in an array.
447 * Attempts to allocate larger arrays may result in
448 * OutOfMemoryError: Requested array size exceeds VM limit
449 */
450 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
451
452 /**
453 * Increases the capacity of and internally reorganizes this
454 * hashtable, in order to accommodate and access its entries more
455 * efficiently. This method is called automatically when the
456 * number of keys in the hashtable exceeds this hashtable's capacity
457 * and load factor.
458 */
459 protected void rehash() {
460 int oldCapacity = table.length;
461 Entry<K,V>[] oldMap = table;
462
463 // overflow-conscious code
464 int newCapacity = (oldCapacity << 1) + 1;
465 if (newCapacity - MAX_ARRAY_SIZE > 0) {
466 if (oldCapacity == MAX_ARRAY_SIZE)
467 // Keep running with MAX_ARRAY_SIZE buckets
468 return;
469 newCapacity = MAX_ARRAY_SIZE;
470 }
471 Entry<K,V>[] newMap = new Entry[newCapacity];
472
473 modCount++;
474 threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
475 boolean rehash = initHashSeedAsNeeded(newCapacity);
476
477 table = newMap;
478
479 for (int i = oldCapacity ; i-- > 0 ;) {
480 for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
481 Entry<K,V> e = old;
482 old = old.next;
483
484 if (rehash) {
485 e.hash = hash(e.key);
486 }
487 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
488 e.next = newMap[index];
489 newMap[index] = e;
490 }
491 }
492 }
493
494 /**
495 * Maps the specified <code>key</code> to the specified
496 * <code>value</code> in this hashtable. Neither the key nor the
497 * value can be <code>null</code>. <p>
498 *
499 * The value can be retrieved by calling the <code>get</code> method
500 * with a key that is equal to the original key.
501 *
502 * @param key the hashtable key
503 * @param value the value
504 * @return the previous value of the specified key in this hashtable,
505 * or <code>null</code> if it did not have one
506 * @exception NullPointerException if the key or value is
507 * <code>null</code>
508 * @see Object#equals(Object)
509 * @see #get(Object)
510 */
511 public synchronized V put(K key, V value) {
512 // Make sure the value is not null
513 if (value == null) {
514 throw new NullPointerException();
515 }
516
517 // Makes sure the key is not already in the hashtable.
518 Entry tab[] = table;
519 int hash = hash(key);
520 int index = (hash & 0x7FFFFFFF) % tab.length;
521 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
522 if ((e.hash == hash) && e.key.equals(key)) {
523 V old = e.value;
524 e.value = value;
525 return old;
526 }
527 }
528
529 modCount++;
530 if (count >= threshold) {
531 // Rehash the table if the threshold is exceeded
532 rehash();
533
534 tab = table;
535 hash = hash(key);
536 index = (hash & 0x7FFFFFFF) % tab.length;
537 }
538
539 // Creates the new entry.
540 Entry<K,V> e = tab[index];
541 tab[index] = new Entry<>(hash, key, value, e);
542 count++;
543 return null;
544 }
545
546 /**
547 * Removes the key (and its corresponding value) from this
548 * hashtable. This method does nothing if the key is not in the hashtable.
549 *
550 * @param key the key that needs to be removed
551 * @return the value to which the key had been mapped in this hashtable,
552 * or <code>null</code> if the key did not have a mapping
553 * @throws NullPointerException if the key is <code>null</code>
554 */
555 public synchronized V remove(Object key) {
556 Entry tab[] = table;
557 int hash = hash(key);
558 int index = (hash & 0x7FFFFFFF) % tab.length;
559 for (Entry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
560 if ((e.hash == hash) && e.key.equals(key)) {
561 modCount++;
562 if (prev != null) {
563 prev.next = e.next;
564 } else {
565 tab[index] = e.next;
566 }
567 count--;
568 V oldValue = e.value;
569 e.value = null;
570 return oldValue;
571 }
572 }
573 return null;
574 }
575
576 /**
577 * Copies all of the mappings from the specified map to this hashtable.
578 * These mappings will replace any mappings that this hashtable had for any
579 * of the keys currently in the specified map.
580 *
581 * @param t mappings to be stored in this map
582 * @throws NullPointerException if the specified map is null
583 * @since 1.2
584 */
585 public synchronized void putAll(Map<? extends K, ? extends V> t) {
586 for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
587 put(e.getKey(), e.getValue());
588 }
589
590 /**
591 * Clears this hashtable so that it contains no keys.
592 */
593 public synchronized void clear() {
594 Entry tab[] = table;
595 modCount++;
596 for (int index = tab.length; --index >= 0; )
597 tab[index] = null;
598 count = 0;
599 }
600
601 /**
602 * Creates a shallow copy of this hashtable. All the structure of the
603 * hashtable itself is copied, but the keys and values are not cloned.
604 * This is a relatively expensive operation.
605 *
606 * @return a clone of the hashtable
607 */
608 public synchronized Object clone() {
609 try {
610 Hashtable<K,V> t = (Hashtable<K,V>) super.clone();
611 t.table = new Entry[table.length];
612 for (int i = table.length ; i-- > 0 ; ) {
613 t.table[i] = (table[i] != null)
614 ? (Entry<K,V>) table[i].clone() : null;
615 }
616 t.keySet = null;
617 t.entrySet = null;
618 t.values = null;
619 t.modCount = 0;
620 return t;
621 } catch (CloneNotSupportedException e) {
622 // this shouldn't happen, since we are Cloneable
623 throw new InternalError();
624 }
625 }
626
627 /**
628 * Returns a string representation of this <tt>Hashtable</tt> object
629 * in the form of a set of entries, enclosed in braces and separated
630 * by the ASCII characters "<tt>, </tt>" (comma and space). Each
631 * entry is rendered as the key, an equals sign <tt>=</tt>, and the
632 * associated element, where the <tt>toString</tt> method is used to
633 * convert the key and element to strings.
634 *
635 * @return a string representation of this hashtable
636 */
637 public synchronized String toString() {
638 int max = size() - 1;
639 if (max == -1)
640 return "{}";
641
642 StringBuilder sb = new StringBuilder();
643 Iterator<Map.Entry<K,V>> it = entrySet().iterator();
644
645 sb.append('{');
646 for (int i = 0; ; i++) {
647 Map.Entry<K,V> e = it.next();
648 K key = e.getKey();
649 V value = e.getValue();
650 sb.append(key == this ? "(this Map)" : key.toString());
651 sb.append('=');
652 sb.append(value == this ? "(this Map)" : value.toString());
653
654 if (i == max)
655 return sb.append('}').toString();
656 sb.append(", ");
657 }
658 }
659
660
661 private <T> Enumeration<T> getEnumeration(int type) {
662 if (count == 0) {
663 return Collections.emptyEnumeration();
664 } else {
665 return new Enumerator<>(type, false);
666 }
667 }
668
669 private <T> Iterator<T> getIterator(int type) {
670 if (count == 0) {
671 return Collections.emptyIterator();
672 } else {
673 return new Enumerator<>(type, true);
674 }
675 }
676
677 // Views
678
679 /**
680 * Each of these fields are initialized to contain an instance of the
681 * appropriate view the first time this view is requested. The views are
682 * stateless, so there's no reason to create more than one of each.
683 */
684 private transient volatile Set<K> keySet = null;
685 private transient volatile Set<Map.Entry<K,V>> entrySet = null;
686 private transient volatile Collection<V> values = null;
687
688 /**
689 * Returns a {@link Set} view of the keys contained in this map.
690 * The set is backed by the map, so changes to the map are
691 * reflected in the set, and vice-versa. If the map is modified
692 * while an iteration over the set is in progress (except through
693 * the iterator's own <tt>remove</tt> operation), the results of
694 * the iteration are undefined. The set supports element removal,
695 * which removes the corresponding mapping from the map, via the
696 * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
697 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
698 * operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
699 * operations.
700 *
701 * @since 1.2
702 */
703 public Set<K> keySet() {
704 if (keySet == null)
705 keySet = Collections.synchronizedSet(new KeySet(), this);
706 return keySet;
707 }
708
709 private class KeySet extends AbstractSet<K> {
710 public Iterator<K> iterator() {
711 return getIterator(KEYS);
712 }
713 public int size() {
714 return count;
715 }
716 public boolean contains(Object o) {
717 return containsKey(o);
718 }
719 public boolean remove(Object o) {
720 return Hashtable.this.remove(o) != null;
721 }
722 public void clear() {
723 Hashtable.this.clear();
724 }
725 }
726
727 /**
728 * Returns a {@link Set} view of the mappings contained in this map.
729 * The set is backed by the map, so changes to the map are
730 * reflected in the set, and vice-versa. If the map is modified
731 * while an iteration over the set is in progress (except through
732 * the iterator's own <tt>remove</tt> operation, or through the
733 * <tt>setValue</tt> operation on a map entry returned by the
734 * iterator) the results of the iteration are undefined. The set
735 * supports element removal, which removes the corresponding
736 * mapping from the map, via the <tt>Iterator.remove</tt>,
737 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
738 * <tt>clear</tt> operations. It does not support the
739 * <tt>add</tt> or <tt>addAll</tt> operations.
740 *
741 * @since 1.2
742 */
743 public Set<Map.Entry<K,V>> entrySet() {
744 if (entrySet==null)
745 entrySet = Collections.synchronizedSet(new EntrySet(), this);
746 return entrySet;
747 }
748
749 private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
750 public Iterator<Map.Entry<K,V>> iterator() {
751 return getIterator(ENTRIES);
752 }
753
754 public boolean add(Map.Entry<K,V> o) {
755 return super.add(o);
756 }
757
758 public boolean contains(Object o) {
759 if (!(o instanceof Map.Entry))
760 return false;
761 Map.Entry entry = (Map.Entry)o;
762 Object key = entry.getKey();
763 Entry[] tab = table;
764 int hash = hash(key);
765 int index = (hash & 0x7FFFFFFF) % tab.length;
766
767 for (Entry e = tab[index]; e != null; e = e.next)
768 if (e.hash==hash && e.equals(entry))
769 return true;
770 return false;
771 }
772
773 public boolean remove(Object o) {
774 if (!(o instanceof Map.Entry))
775 return false;
776 Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
777 K key = entry.getKey();
778 Entry[] tab = table;
779 int hash = hash(key);
780 int index = (hash & 0x7FFFFFFF) % tab.length;
781
782 for (Entry<K,V> e = tab[index], prev = null; e != null;
783 prev = e, e = e.next) {
784 if (e.hash==hash && e.equals(entry)) {
785 modCount++;
786 if (prev != null)
787 prev.next = e.next;
788 else
789 tab[index] = e.next;
790
791 count--;
792 e.value = null;
793 return true;
794 }
795 }
796 return false;
797 }
798
799 public int size() {
800 return count;
801 }
802
803 public void clear() {
804 Hashtable.this.clear();
805 }
806 }
807
808 /**
809 * Returns a {@link Collection} view of the values contained in this map.
810 * The collection is backed by the map, so changes to the map are
811 * reflected in the collection, and vice-versa. If the map is
812 * modified while an iteration over the collection is in progress
813 * (except through the iterator's own <tt>remove</tt> operation),
814 * the results of the iteration are undefined. The collection
815 * supports element removal, which removes the corresponding
816 * mapping from the map, via the <tt>Iterator.remove</tt>,
817 * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
818 * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not
819 * support the <tt>add</tt> or <tt>addAll</tt> operations.
820 *
821 * @since 1.2
822 */
823 public Collection<V> values() {
824 if (values==null)
825 values = Collections.synchronizedCollection(new ValueCollection(),
826 this);
827 return values;
828 }
829
830 private class ValueCollection extends AbstractCollection<V> {
831 public Iterator<V> iterator() {
832 return getIterator(VALUES);
833 }
834 public int size() {
835 return count;
836 }
837 public boolean contains(Object o) {
838 return containsValue(o);
839 }
840 public void clear() {
841 Hashtable.this.clear();
842 }
843 }
844
845 // Comparison and hashing
846
847 /**
848 * Compares the specified Object with this Map for equality,
849 * as per the definition in the Map interface.
850 *
851 * @param o object to be compared for equality with this hashtable
852 * @return true if the specified Object is equal to this Map
853 * @see Map#equals(Object)
854 * @since 1.2
855 */
856 public synchronized boolean equals(Object o) {
857 if (o == this)
858 return true;
859
860 if (!(o instanceof Map))
861 return false;
862 Map<K,V> t = (Map<K,V>) o;
863 if (t.size() != size())
864 return false;
865
866 try {
867 Iterator<Map.Entry<K,V>> i = entrySet().iterator();
868 while (i.hasNext()) {
869 Map.Entry<K,V> e = i.next();
870 K key = e.getKey();
871 V value = e.getValue();
872 if (value == null) {
873 if (!(t.get(key)==null && t.containsKey(key)))
874 return false;
875 } else {
876 if (!value.equals(t.get(key)))
877 return false;
878 }
879 }
880 } catch (ClassCastException unused) {
881 return false;
882 } catch (NullPointerException unused) {
883 return false;
884 }
885
886 return true;
887 }
888
889 /**
890 * Returns the hash code value for this Map as per the definition in the
891 * Map interface.
892 *
893 * @see Map#hashCode()
894 * @since 1.2
895 */
896 public synchronized int hashCode() {
897 /*
898 * This code detects the recursion caused by computing the hash code
899 * of a self-referential hash table and prevents the stack overflow
900 * that would otherwise result. This allows certain 1.1-era
901 * applets with self-referential hash tables to work. This code
902 * abuses the loadFactor field to do double-duty as a hashCode
903 * in progress flag, so as not to worsen the space performance.
904 * A negative load factor indicates that hash code computation is
905 * in progress.
906 */
907 int h = 0;
908 if (count == 0 || loadFactor < 0)
909 return h; // Returns zero
910
911 loadFactor = -loadFactor; // Mark hashCode computation in progress
912 Entry[] tab = table;
913 for (Entry<K,V> entry : tab)
914 while (entry != null) {
915 h += entry.hashCode();
916 entry = entry.next;
917 }
918 loadFactor = -loadFactor; // Mark hashCode computation complete
919
920 return h;
921 }
922
923 /**
924 * Save the state of the Hashtable to a stream (i.e., serialize it).
925 *
926 * @serialData The <i>capacity</i> of the Hashtable (the length of the
927 * bucket array) is emitted (int), followed by the
928 * <i>size</i> of the Hashtable (the number of key-value
929 * mappings), followed by the key (Object) and value (Object)
930 * for each key-value mapping represented by the Hashtable
931 * The key-value mappings are emitted in no particular order.
932 */
933 private void writeObject(java.io.ObjectOutputStream s)
934 throws IOException {
935 Entry<K, V> entryStack = null;
936
937 synchronized (this) {
938 // Write out the length, threshold, loadfactor
939 s.defaultWriteObject();
940
941 // Write out length, count of elements
942 s.writeInt(table.length);
943 s.writeInt(count);
944
945 // Stack copies of the entries in the table
946 for (int index = 0; index < table.length; index++) {
947 Entry<K,V> entry = table[index];
948
949 while (entry != null) {
950 entryStack =
951 new Entry<>(0, entry.key, entry.value, entryStack);
952 entry = entry.next;
953 }
954 }
955 }
956
957 // Write out the key/value objects from the stacked entries
958 while (entryStack != null) {
959 s.writeObject(entryStack.key);
960 s.writeObject(entryStack.value);
961 entryStack = entryStack.next;
962 }
963 }
964
965 /**
966 * Reconstitute the Hashtable from a stream (i.e., deserialize it).
967 */
968 private void readObject(java.io.ObjectInputStream s)
969 throws IOException, ClassNotFoundException
970 {
971 // Read in the length, threshold, and loadfactor
972 s.defaultReadObject();
973
974 // Read the original length of the array and number of elements
975 int origlength = s.readInt();
976 int elements = s.readInt();
977
978 // Compute new size with a bit of room 5% to grow but
979 // no larger than the original size. Make the length
980 // odd if it's large enough, this helps distribute the entries.
981 // Guard against the length ending up zero, that's not valid.
982 int length = (int)(elements * loadFactor) + (elements / 20) + 3;
983 if (length > elements && (length & 1) == 0)
984 length--;
985 if (origlength > 0 && length > origlength)
986 length = origlength;
987
988 Entry<K,V>[] newTable = new Entry[length];
989 threshold = (int) Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1);
990 count = 0;
991 initHashSeedAsNeeded(length);
992
993 // Read the number of elements and then all the key/value objects
994 for (; elements > 0; elements--) {
995 K key = (K)s.readObject();
996 V value = (V)s.readObject();
997 // synch could be eliminated for performance
998 reconstitutionPut(newTable, key, value);
999 }
1000 this.table = newTable;
1001 }
1002
1003 /**
1004 * The put method used by readObject. This is provided because put
1005 * is overridable and should not be called in readObject since the
1006 * subclass will not yet be initialized.
1007 *
1008 * <p>This differs from the regular put method in several ways. No
1009 * checking for rehashing is necessary since the number of elements
1010 * initially in the table is known. The modCount is not incremented
1011 * because we are creating a new instance. Also, no return value
1012 * is needed.
1013 */
1014 private void reconstitutionPut(Entry<K,V>[] tab, K key, V value)
1015 throws StreamCorruptedException
1016 {
1017 if (value == null) {
1018 throw new java.io.StreamCorruptedException();
1019 }
1020 // Makes sure the key is not already in the hashtable.
1021 // This should not happen in deserialized version.
1022 int hash = hash(key);
1023 int index = (hash & 0x7FFFFFFF) % tab.length;
1024 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
1025 if ((e.hash == hash) && e.key.equals(key)) {
1026 throw new java.io.StreamCorruptedException();
1027 }
1028 }
1029 // Creates the new entry.
1030 Entry<K,V> e = tab[index];
1031 tab[index] = new Entry<>(hash, key, value, e);
1032 count++;
1033 }
1034
1035 /**
1036 * Hashtable bucket collision list entry
1037 */
1038 private static class Entry<K,V> implements Map.Entry<K,V> {
1039 int hash;
1040 final K key;
1041 V value;
1042 Entry<K,V> next;
1043
1044 protected Entry(int hash, K key, V value, Entry<K,V> next) {
1045 this.hash = hash;
1046 this.key = key;
1047 this.value = value;
1048 this.next = next;
1049 }
1050
1051 protected Object clone() {
1052 return new Entry<>(hash, key, value,
1053 (next==null ? null : (Entry<K,V>) next.clone()));
1054 }
1055
1056 // Map.Entry Ops
1057
1058 public K getKey() {
1059 return key;
1060 }
1061
1062 public V getValue() {
1063 return value;
1064 }
1065
1066 public V setValue(V value) {
1067 if (value == null)
1068 throw new NullPointerException();
1069
1070 V oldValue = this.value;
1071 this.value = value;
1072 return oldValue;
1073 }
1074
1075 public boolean equals(Object o) {
1076 if (!(o instanceof Map.Entry))
1077 return false;
1078 Map.Entry<?,?> e = (Map.Entry)o;
1079
1080 return key.equals(e.getKey()) && value.equals(e.getValue());
1081 }
1082
1083 public int hashCode() {
1084 return (Objects.hashCode(key) ^ Objects.hashCode(value));
1085 }
1086
1087 public String toString() {
1088 return key.toString()+"="+value.toString();
1089 }
1090 }
1091
1092 // Types of Enumerations/Iterations
1093 private static final int KEYS = 0;
1094 private static final int VALUES = 1;
1095 private static final int ENTRIES = 2;
1096
1097 /**
1098 * A hashtable enumerator class. This class implements both the
1099 * Enumeration and Iterator interfaces, but individual instances
1100 * can be created with the Iterator methods disabled. This is necessary
1101 * to avoid unintentionally increasing the capabilities granted a user
1102 * by passing an Enumeration.
1103 */
1104 private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
1105 Entry[] table = Hashtable.this.table;
1106 int index = table.length;
1107 Entry<K,V> entry = null;
1108 Entry<K,V> lastReturned = null;
1109 int type;
1110
1111 /**
1112 * Indicates whether this Enumerator is serving as an Iterator
1113 * or an Enumeration. (true -> Iterator).
1114 */
1115 boolean iterator;
1116
1117 /**
1118 * The modCount value that the iterator believes that the backing
1119 * Hashtable should have. If this expectation is violated, the iterator
1120 * has detected concurrent modification.
1121 */
1122 protected int expectedModCount = modCount;
1123
1124 Enumerator(int type, boolean iterator) {
1125 this.type = type;
1126 this.iterator = iterator;
1127 }
1128
1129 public boolean hasMoreElements() {
1130 Entry<K,V> e = entry;
1131 int i = index;
1132 Entry[] t = table;
1133 /* Use locals for faster loop iteration */
1134 while (e == null && i > 0) {
1135 e = t[--i];
1136 }
1137 entry = e;
1138 index = i;
1139 return e != null;
1140 }
1141
1142 public T nextElement() {
1143 Entry<K,V> et = entry;
1144 int i = index;
1145 Entry[] t = table;
1146 /* Use locals for faster loop iteration */
1147 while (et == null && i > 0) {
1148 et = t[--i];
1149 }
1150 entry = et;
1151 index = i;
1152 if (et != null) {
1153 Entry<K,V> e = lastReturned = entry;
1154 entry = e.next;
1155 return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
1156 }
1157 throw new NoSuchElementException("Hashtable Enumerator");
1158 }
1159
1160 // Iterator methods
1161 public boolean hasNext() {
1162 return hasMoreElements();
1163 }
1164
1165 public T next() {
1166 if (modCount != expectedModCount)
1167 throw new ConcurrentModificationException();
1168 return nextElement();
1169 }
1170
1171 public void remove() {
1172 if (!iterator)
1173 throw new UnsupportedOperationException();
1174 if (lastReturned == null)
1175 throw new IllegalStateException("Hashtable Enumerator");
1176 if (modCount != expectedModCount)
1177 throw new ConcurrentModificationException();
1178
1179 synchronized(Hashtable.this) {
1180 Entry[] tab = Hashtable.this.table;
1181 int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;
1182
1183 for (Entry<K,V> e = tab[index], prev = null; e != null;
1184 prev = e, e = e.next) {
1185 if (e == lastReturned) {
1186 modCount++;
1187 expectedModCount++;
1188 if (prev == null)
1189 tab[index] = e.next;
1190 else
1191 prev.next = e.next;
1192 count--;
1193 lastReturned = null;
1194 return;
1195 }
1196 }
1197 throw new ConcurrentModificationException();
1198 }
1199 }
1200 }
1201 }