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 * If {@code true} then perform alternative hashing of String keys to reduce
217 * the incidence of collisions due to weak hash code calculation.
218 */
219 transient boolean useAltHashing;
220
221 // Unsafe mechanics
222 /**
223 * Unsafe utilities
224 */
225 private static final sun.misc.Unsafe UNSAFE;
226
227 /**
228 * Offset of "final" hashSeed field we must set in readObject() method.
229 */
230 private static final long HASHSEED_OFFSET;
231
232 static {
233 try {
234 UNSAFE = sun.misc.Unsafe.getUnsafe();
235 HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
236 Hashtable.class.getDeclaredField("hashSeed"));
237 } catch (NoSuchFieldException | SecurityException e) {
238 throw new Error("Failed to record hashSeed offset", e);
239 }
240 }
241
242 /**
243 * A randomizing value associated with this instance that is applied to
244 * hash code of keys to make hash collisions harder to find.
245 */
246 transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);
247
248 private int hash(Object k) {
249 if (useAltHashing) {
250 if (k.getClass() == String.class) {
251 return sun.misc.Hashing.stringHash32((String) k);
252 } else {
253 int h = hashSeed ^ k.hashCode();
254
255 // This function ensures that hashCodes that differ only by
256 // constant multiples at each bit position have a bounded
257 // number of collisions (approximately 8 at default load factor).
258 h ^= (h >>> 20) ^ (h >>> 12);
259 return h ^ (h >>> 7) ^ (h >>> 4);
260 }
261 } else {
262 return k.hashCode();
263 }
264 }
265
266 /**
267 * Constructs a new, empty hashtable with the specified initial
268 * capacity and the specified load factor.
269 *
270 * @param initialCapacity the initial capacity of the hashtable.
271 * @param loadFactor the load factor of the hashtable.
272 * @exception IllegalArgumentException if the initial capacity is less
273 * than zero, or if the load factor is nonpositive.
274 */
275 public Hashtable(int initialCapacity, float loadFactor) {
276 if (initialCapacity < 0)
277 throw new IllegalArgumentException("Illegal Capacity: "+
278 initialCapacity);
279 if (loadFactor <= 0 || Float.isNaN(loadFactor))
280 throw new IllegalArgumentException("Illegal Load: "+loadFactor);
281
282 if (initialCapacity==0)
283 initialCapacity = 1;
284 this.loadFactor = loadFactor;
285 table = new Entry[initialCapacity];
286 threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
287 useAltHashing = sun.misc.VM.isBooted() &&
288 (initialCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
289 }
290
291 /**
292 * Constructs a new, empty hashtable with the specified initial capacity
293 * and default load factor (0.75).
294 *
295 * @param initialCapacity the initial capacity of the hashtable.
296 * @exception IllegalArgumentException if the initial capacity is less
297 * than zero.
298 */
299 public Hashtable(int initialCapacity) {
300 this(initialCapacity, 0.75f);
301 }
302
303 /**
304 * Constructs a new, empty hashtable with a default initial capacity (11)
305 * and load factor (0.75).
306 */
307 public Hashtable() {
308 this(11, 0.75f);
309 }
310
311 /**
312 * Constructs a new hashtable with the same mappings as the given
313 * Map. The hashtable is created with an initial capacity sufficient to
314 * hold the mappings in the given Map and a default load factor (0.75).
315 *
316 * @param t the map whose mappings are to be placed in this map.
317 * @throws NullPointerException if the specified map is null.
318 * @since 1.2
319 */
320 public Hashtable(Map<? extends K, ? extends V> t) {
321 this(Math.max(2*t.size(), 11), 0.75f);
322 putAll(t);
323 }
324
325 /**
326 * Returns the number of keys in this hashtable.
327 *
328 * @return the number of keys in this hashtable.
329 */
330 public synchronized int size() {
331 return count;
332 }
333
334 /**
335 * Tests if this hashtable maps no keys to values.
336 *
337 * @return <code>true</code> if this hashtable maps no keys to values;
338 * <code>false</code> otherwise.
339 */
340 public synchronized boolean isEmpty() {
341 return count == 0;
342 }
343
344 /**
345 * Returns an enumeration of the keys in this hashtable.
346 *
347 * @return an enumeration of the keys in this hashtable.
348 * @see Enumeration
349 * @see #elements()
350 * @see #keySet()
351 * @see Map
352 */
353 public synchronized Enumeration<K> keys() {
354 return this.<K>getEnumeration(KEYS);
355 }
356
357 /**
358 * Returns an enumeration of the values in this hashtable.
359 * Use the Enumeration methods on the returned object to fetch the elements
360 * sequentially.
361 *
362 * @return an enumeration of the values in this hashtable.
363 * @see java.util.Enumeration
364 * @see #keys()
365 * @see #values()
366 * @see Map
367 */
368 public synchronized Enumeration<V> elements() {
369 return this.<V>getEnumeration(VALUES);
370 }
371
372 /**
373 * Tests if some key maps into the specified value in this hashtable.
374 * This operation is more expensive than the {@link #containsKey
375 * containsKey} method.
376 *
377 * <p>Note that this method is identical in functionality to
378 * {@link #containsValue containsValue}, (which is part of the
379 * {@link Map} interface in the collections framework).
380 *
381 * @param value a value to search for
382 * @return <code>true</code> if and only if some key maps to the
383 * <code>value</code> argument in this hashtable as
384 * determined by the <tt>equals</tt> method;
385 * <code>false</code> otherwise.
386 * @exception NullPointerException if the value is <code>null</code>
387 */
388 public synchronized boolean contains(Object value) {
389 if (value == null) {
390 throw new NullPointerException();
391 }
392
393 Entry tab[] = table;
394 for (int i = tab.length ; i-- > 0 ;) {
395 for (Entry<K,V> e = tab[i] ; e != null ; e = e.next) {
396 if (e.value.equals(value)) {
397 return true;
398 }
399 }
400 }
401 return false;
402 }
403
404 /**
405 * Returns true if this hashtable maps one or more keys to this value.
406 *
407 * <p>Note that this method is identical in functionality to {@link
408 * #contains contains} (which predates the {@link Map} interface).
409 *
410 * @param value value whose presence in this hashtable is to be tested
411 * @return <tt>true</tt> if this map maps one or more keys to the
412 * specified value
413 * @throws NullPointerException if the value is <code>null</code>
414 * @since 1.2
415 */
416 public boolean containsValue(Object value) {
417 return contains(value);
418 }
419
420 /**
421 * Tests if the specified object is a key in this hashtable.
422 *
423 * @param key possible key
424 * @return <code>true</code> if and only if the specified object
425 * is a key in this hashtable, as determined by the
426 * <tt>equals</tt> method; <code>false</code> otherwise.
427 * @throws NullPointerException if the key is <code>null</code>
428 * @see #contains(Object)
429 */
430 public synchronized boolean containsKey(Object key) {
431 Entry tab[] = table;
432 int hash = hash(key);
433 int index = (hash & 0x7FFFFFFF) % tab.length;
434 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
435 if ((e.hash == hash) && e.key.equals(key)) {
436 return true;
437 }
438 }
439 return false;
440 }
441
442 /**
443 * Returns the value to which the specified key is mapped,
444 * or {@code null} if this map contains no mapping for the key.
445 *
446 * <p>More formally, if this map contains a mapping from a key
447 * {@code k} to a value {@code v} such that {@code (key.equals(k))},
448 * then this method returns {@code v}; otherwise it returns
449 * {@code null}. (There can be at most one such mapping.)
450 *
451 * @param key the key whose associated value is to be returned
452 * @return the value to which the specified key is mapped, or
453 * {@code null} if this map contains no mapping for the key
454 * @throws NullPointerException if the specified key is null
455 * @see #put(Object, Object)
456 */
457 public synchronized V get(Object key) {
458 Entry tab[] = table;
459 int hash = hash(key);
460 int index = (hash & 0x7FFFFFFF) % tab.length;
461 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
462 if ((e.hash == hash) && e.key.equals(key)) {
463 return e.value;
464 }
465 }
466 return null;
467 }
468
469 /**
470 * The maximum size of array to allocate.
471 * Some VMs reserve some header words in an array.
472 * Attempts to allocate larger arrays may result in
473 * OutOfMemoryError: Requested array size exceeds VM limit
474 */
475 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
476
477 /**
478 * Increases the capacity of and internally reorganizes this
479 * hashtable, in order to accommodate and access its entries more
480 * efficiently. This method is called automatically when the
481 * number of keys in the hashtable exceeds this hashtable's capacity
482 * and load factor.
483 */
484 protected void rehash() {
485 int oldCapacity = table.length;
486 Entry<K,V>[] oldMap = table;
487
488 // overflow-conscious code
489 int newCapacity = (oldCapacity << 1) + 1;
490 if (newCapacity - MAX_ARRAY_SIZE > 0) {
491 if (oldCapacity == MAX_ARRAY_SIZE)
492 // Keep running with MAX_ARRAY_SIZE buckets
493 return;
494 newCapacity = MAX_ARRAY_SIZE;
495 }
496 Entry<K,V>[] newMap = new Entry[newCapacity];
497
498 modCount++;
499 threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
500 boolean currentAltHashing = useAltHashing;
501 useAltHashing = sun.misc.VM.isBooted() &&
502 (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
503 boolean rehash = currentAltHashing ^ useAltHashing;
504
505 table = newMap;
506
507 for (int i = oldCapacity ; i-- > 0 ;) {
508 for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
509 Entry<K,V> e = old;
510 old = old.next;
511
512 if (rehash) {
513 e.hash = hash(e.key);
514 }
515 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
516 e.next = newMap[index];
517 newMap[index] = e;
518 }
519 }
520 }
521
522 /**
523 * Maps the specified <code>key</code> to the specified
524 * <code>value</code> in this hashtable. Neither the key nor the
525 * value can be <code>null</code>. <p>
526 *
527 * The value can be retrieved by calling the <code>get</code> method
528 * with a key that is equal to the original key.
529 *
530 * @param key the hashtable key
531 * @param value the value
532 * @return the previous value of the specified key in this hashtable,
533 * or <code>null</code> if it did not have one
534 * @exception NullPointerException if the key or value is
535 * <code>null</code>
536 * @see Object#equals(Object)
537 * @see #get(Object)
538 */
539 public synchronized V put(K key, V value) {
540 // Make sure the value is not null
541 if (value == null) {
542 throw new NullPointerException();
543 }
544
545 // Makes sure the key is not already in the hashtable.
546 Entry tab[] = table;
547 int hash = hash(key);
548 int index = (hash & 0x7FFFFFFF) % tab.length;
549 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
550 if ((e.hash == hash) && e.key.equals(key)) {
551 V old = e.value;
552 e.value = value;
553 return old;
554 }
555 }
556
557 modCount++;
558 if (count >= threshold) {
559 // Rehash the table if the threshold is exceeded
560 rehash();
561
562 tab = table;
563 hash = hash(key);
564 index = (hash & 0x7FFFFFFF) % tab.length;
565 }
566
567 // Creates the new entry.
568 Entry<K,V> e = tab[index];
569 tab[index] = new Entry<>(hash, key, value, e);
570 count++;
571 return null;
572 }
573
574 /**
575 * Removes the key (and its corresponding value) from this
576 * hashtable. This method does nothing if the key is not in the hashtable.
577 *
578 * @param key the key that needs to be removed
579 * @return the value to which the key had been mapped in this hashtable,
580 * or <code>null</code> if the key did not have a mapping
581 * @throws NullPointerException if the key is <code>null</code>
582 */
583 public synchronized V remove(Object key) {
584 Entry tab[] = table;
585 int hash = hash(key);
586 int index = (hash & 0x7FFFFFFF) % tab.length;
587 for (Entry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
588 if ((e.hash == hash) && e.key.equals(key)) {
589 modCount++;
590 if (prev != null) {
591 prev.next = e.next;
592 } else {
593 tab[index] = e.next;
594 }
595 count--;
596 V oldValue = e.value;
597 e.value = null;
598 return oldValue;
599 }
600 }
601 return null;
602 }
603
604 /**
605 * Copies all of the mappings from the specified map to this hashtable.
606 * These mappings will replace any mappings that this hashtable had for any
607 * of the keys currently in the specified map.
608 *
609 * @param t mappings to be stored in this map
610 * @throws NullPointerException if the specified map is null
611 * @since 1.2
612 */
613 public synchronized void putAll(Map<? extends K, ? extends V> t) {
614 for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
615 put(e.getKey(), e.getValue());
616 }
617
618 /**
619 * Clears this hashtable so that it contains no keys.
620 */
621 public synchronized void clear() {
622 Entry tab[] = table;
623 modCount++;
624 for (int index = tab.length; --index >= 0; )
625 tab[index] = null;
626 count = 0;
627 }
628
629 /**
630 * Creates a shallow copy of this hashtable. All the structure of the
631 * hashtable itself is copied, but the keys and values are not cloned.
632 * This is a relatively expensive operation.
633 *
634 * @return a clone of the hashtable
635 */
636 public synchronized Object clone() {
637 try {
638 Hashtable<K,V> t = (Hashtable<K,V>) super.clone();
639 t.table = new Entry[table.length];
640 for (int i = table.length ; i-- > 0 ; ) {
641 t.table[i] = (table[i] != null)
642 ? (Entry<K,V>) table[i].clone() : null;
643 }
644 t.keySet = null;
645 t.entrySet = null;
646 t.values = null;
647 t.modCount = 0;
648 return t;
649 } catch (CloneNotSupportedException e) {
650 // this shouldn't happen, since we are Cloneable
651 throw new InternalError();
652 }
653 }
654
655 /**
656 * Returns a string representation of this <tt>Hashtable</tt> object
657 * in the form of a set of entries, enclosed in braces and separated
658 * by the ASCII characters "<tt>, </tt>" (comma and space). Each
659 * entry is rendered as the key, an equals sign <tt>=</tt>, and the
660 * associated element, where the <tt>toString</tt> method is used to
661 * convert the key and element to strings.
662 *
663 * @return a string representation of this hashtable
664 */
665 public synchronized String toString() {
666 int max = size() - 1;
667 if (max == -1)
668 return "{}";
669
670 StringBuilder sb = new StringBuilder();
671 Iterator<Map.Entry<K,V>> it = entrySet().iterator();
672
673 sb.append('{');
674 for (int i = 0; ; i++) {
675 Map.Entry<K,V> e = it.next();
676 K key = e.getKey();
677 V value = e.getValue();
678 sb.append(key == this ? "(this Map)" : key.toString());
679 sb.append('=');
680 sb.append(value == this ? "(this Map)" : value.toString());
681
682 if (i == max)
683 return sb.append('}').toString();
684 sb.append(", ");
685 }
686 }
687
688
689 private <T> Enumeration<T> getEnumeration(int type) {
690 if (count == 0) {
691 return Collections.emptyEnumeration();
692 } else {
693 return new Enumerator<>(type, false);
694 }
695 }
696
697 private <T> Iterator<T> getIterator(int type) {
698 if (count == 0) {
699 return Collections.emptyIterator();
700 } else {
701 return new Enumerator<>(type, true);
702 }
703 }
704
705 // Views
706
707 /**
708 * Each of these fields are initialized to contain an instance of the
709 * appropriate view the first time this view is requested. The views are
710 * stateless, so there's no reason to create more than one of each.
711 */
712 private transient volatile Set<K> keySet = null;
713 private transient volatile Set<Map.Entry<K,V>> entrySet = null;
714 private transient volatile Collection<V> values = null;
715
716 /**
717 * Returns a {@link Set} view of the keys contained in this map.
718 * The set is backed by the map, so changes to the map are
719 * reflected in the set, and vice-versa. If the map is modified
720 * while an iteration over the set is in progress (except through
721 * the iterator's own <tt>remove</tt> operation), the results of
722 * the iteration are undefined. The set supports element removal,
723 * which removes the corresponding mapping from the map, via the
724 * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
725 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
726 * operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
727 * operations.
728 *
729 * @since 1.2
730 */
731 public Set<K> keySet() {
732 if (keySet == null)
733 keySet = Collections.synchronizedSet(new KeySet(), this);
734 return keySet;
735 }
736
737 private class KeySet extends AbstractSet<K> {
738 public Iterator<K> iterator() {
739 return getIterator(KEYS);
740 }
741 public int size() {
742 return count;
743 }
744 public boolean contains(Object o) {
745 return containsKey(o);
746 }
747 public boolean remove(Object o) {
748 return Hashtable.this.remove(o) != null;
749 }
750 public void clear() {
751 Hashtable.this.clear();
752 }
753 }
754
755 /**
756 * Returns a {@link Set} view of the mappings contained in this map.
757 * The set is backed by the map, so changes to the map are
758 * reflected in the set, and vice-versa. If the map is modified
759 * while an iteration over the set is in progress (except through
760 * the iterator's own <tt>remove</tt> operation, or through the
761 * <tt>setValue</tt> operation on a map entry returned by the
762 * iterator) the results of the iteration are undefined. The set
763 * supports element removal, which removes the corresponding
764 * mapping from the map, via the <tt>Iterator.remove</tt>,
765 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
766 * <tt>clear</tt> operations. It does not support the
767 * <tt>add</tt> or <tt>addAll</tt> operations.
768 *
769 * @since 1.2
770 */
771 public Set<Map.Entry<K,V>> entrySet() {
772 if (entrySet==null)
773 entrySet = Collections.synchronizedSet(new EntrySet(), this);
774 return entrySet;
775 }
776
777 private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
778 public Iterator<Map.Entry<K,V>> iterator() {
779 return getIterator(ENTRIES);
780 }
781
782 public boolean add(Map.Entry<K,V> o) {
783 return super.add(o);
784 }
785
786 public boolean contains(Object o) {
787 if (!(o instanceof Map.Entry))
788 return false;
789 Map.Entry entry = (Map.Entry)o;
790 Object key = entry.getKey();
791 Entry[] tab = table;
792 int hash = hash(key);
793 int index = (hash & 0x7FFFFFFF) % tab.length;
794
795 for (Entry e = tab[index]; e != null; e = e.next)
796 if (e.hash==hash && e.equals(entry))
797 return true;
798 return false;
799 }
800
801 public boolean remove(Object o) {
802 if (!(o instanceof Map.Entry))
803 return false;
804 Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
805 K key = entry.getKey();
806 Entry[] tab = table;
807 int hash = hash(key);
808 int index = (hash & 0x7FFFFFFF) % tab.length;
809
810 for (Entry<K,V> e = tab[index], prev = null; e != null;
811 prev = e, e = e.next) {
812 if (e.hash==hash && e.equals(entry)) {
813 modCount++;
814 if (prev != null)
815 prev.next = e.next;
816 else
817 tab[index] = e.next;
818
819 count--;
820 e.value = null;
821 return true;
822 }
823 }
824 return false;
825 }
826
827 public int size() {
828 return count;
829 }
830
831 public void clear() {
832 Hashtable.this.clear();
833 }
834 }
835
836 /**
837 * Returns a {@link Collection} view of the values contained in this map.
838 * The collection is backed by the map, so changes to the map are
839 * reflected in the collection, and vice-versa. If the map is
840 * modified while an iteration over the collection is in progress
841 * (except through the iterator's own <tt>remove</tt> operation),
842 * the results of the iteration are undefined. The collection
843 * supports element removal, which removes the corresponding
844 * mapping from the map, via the <tt>Iterator.remove</tt>,
845 * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
846 * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not
847 * support the <tt>add</tt> or <tt>addAll</tt> operations.
848 *
849 * @since 1.2
850 */
851 public Collection<V> values() {
852 if (values==null)
853 values = Collections.synchronizedCollection(new ValueCollection(),
854 this);
855 return values;
856 }
857
858 private class ValueCollection extends AbstractCollection<V> {
859 public Iterator<V> iterator() {
860 return getIterator(VALUES);
861 }
862 public int size() {
863 return count;
864 }
865 public boolean contains(Object o) {
866 return containsValue(o);
867 }
868 public void clear() {
869 Hashtable.this.clear();
870 }
871 }
872
873 // Comparison and hashing
874
875 /**
876 * Compares the specified Object with this Map for equality,
877 * as per the definition in the Map interface.
878 *
879 * @param o object to be compared for equality with this hashtable
880 * @return true if the specified Object is equal to this Map
881 * @see Map#equals(Object)
882 * @since 1.2
883 */
884 public synchronized boolean equals(Object o) {
885 if (o == this)
886 return true;
887
888 if (!(o instanceof Map))
889 return false;
890 Map<K,V> t = (Map<K,V>) o;
891 if (t.size() != size())
892 return false;
893
894 try {
895 Iterator<Map.Entry<K,V>> i = entrySet().iterator();
896 while (i.hasNext()) {
897 Map.Entry<K,V> e = i.next();
898 K key = e.getKey();
899 V value = e.getValue();
900 if (value == null) {
901 if (!(t.get(key)==null && t.containsKey(key)))
902 return false;
903 } else {
904 if (!value.equals(t.get(key)))
905 return false;
906 }
907 }
908 } catch (ClassCastException unused) {
909 return false;
910 } catch (NullPointerException unused) {
911 return false;
912 }
913
914 return true;
915 }
916
917 /**
918 * Returns the hash code value for this Map as per the definition in the
919 * Map interface.
920 *
921 * @see Map#hashCode()
922 * @since 1.2
923 */
924 public synchronized int hashCode() {
925 /*
926 * This code detects the recursion caused by computing the hash code
927 * of a self-referential hash table and prevents the stack overflow
928 * that would otherwise result. This allows certain 1.1-era
929 * applets with self-referential hash tables to work. This code
930 * abuses the loadFactor field to do double-duty as a hashCode
931 * in progress flag, so as not to worsen the space performance.
932 * A negative load factor indicates that hash code computation is
933 * in progress.
934 */
935 int h = 0;
936 if (count == 0 || loadFactor < 0)
937 return h; // Returns zero
938
939 loadFactor = -loadFactor; // Mark hashCode computation in progress
940 Entry[] tab = table;
941 for (Entry<K,V> entry : tab)
942 while (entry != null) {
943 h += entry.hashCode();
944 entry = entry.next;
945 }
946 loadFactor = -loadFactor; // Mark hashCode computation complete
947
948 return h;
949 }
950
951 /**
952 * Save the state of the Hashtable to a stream (i.e., serialize it).
953 *
954 * @serialData The <i>capacity</i> of the Hashtable (the length of the
955 * bucket array) is emitted (int), followed by the
956 * <i>size</i> of the Hashtable (the number of key-value
957 * mappings), followed by the key (Object) and value (Object)
958 * for each key-value mapping represented by the Hashtable
959 * The key-value mappings are emitted in no particular order.
960 */
961 private void writeObject(java.io.ObjectOutputStream s)
962 throws IOException {
963 Entry<K, V> entryStack = null;
964
965 synchronized (this) {
966 // Write out the length, threshold, loadfactor
967 s.defaultWriteObject();
968
969 // Write out length, count of elements
970 s.writeInt(table.length);
971 s.writeInt(count);
972
973 // Stack copies of the entries in the table
974 for (int index = 0; index < table.length; index++) {
975 Entry<K,V> entry = table[index];
976
977 while (entry != null) {
978 entryStack =
979 new Entry<>(0, entry.key, entry.value, entryStack);
980 entry = entry.next;
981 }
982 }
983 }
984
985 // Write out the key/value objects from the stacked entries
986 while (entryStack != null) {
987 s.writeObject(entryStack.key);
988 s.writeObject(entryStack.value);
989 entryStack = entryStack.next;
990 }
991 }
992
993 /**
994 * Reconstitute the Hashtable from a stream (i.e., deserialize it).
995 */
996 private void readObject(java.io.ObjectInputStream s)
997 throws IOException, ClassNotFoundException
998 {
999 // Read in the length, threshold, and loadfactor
1000 s.defaultReadObject();
1001
1002 // set hashSeed
1003 UNSAFE.putIntVolatile(this, HASHSEED_OFFSET,
1004 sun.misc.Hashing.randomHashSeed(this));
1005
1006 // Read the original length of the array and number of elements
1007 int origlength = s.readInt();
1008 int elements = s.readInt();
1009
1010 // Compute new size with a bit of room 5% to grow but
1011 // no larger than the original size. Make the length
1012 // odd if it's large enough, this helps distribute the entries.
1013 // Guard against the length ending up zero, that's not valid.
1014 int length = (int)(elements * loadFactor) + (elements / 20) + 3;
1015 if (length > elements && (length & 1) == 0)
1016 length--;
1017 if (origlength > 0 && length > origlength)
1018 length = origlength;
1019
1020 Entry<K,V>[] table = new Entry[length];
1021 threshold = (int) Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1);
1022 count = 0;
1023 useAltHashing = sun.misc.VM.isBooted() &&
1024 (length >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
1025
1026 // Read the number of elements and then all the key/value objects
1027 for (; elements > 0; elements--) {
1028 K key = (K)s.readObject();
1029 V value = (V)s.readObject();
1030 // synch could be eliminated for performance
1031 reconstitutionPut(table, key, value);
1032 }
1033 this.table = table;
1034 }
1035
1036 /**
1037 * The put method used by readObject. This is provided because put
1038 * is overridable and should not be called in readObject since the
1039 * subclass will not yet be initialized.
1040 *
1041 * <p>This differs from the regular put method in several ways. No
1042 * checking for rehashing is necessary since the number of elements
1043 * initially in the table is known. The modCount is not incremented
1044 * because we are creating a new instance. Also, no return value
1045 * is needed.
1046 */
1047 private void reconstitutionPut(Entry<K,V>[] tab, K key, V value)
1048 throws StreamCorruptedException
1049 {
1050 if (value == null) {
1051 throw new java.io.StreamCorruptedException();
1052 }
1053 // Makes sure the key is not already in the hashtable.
1054 // This should not happen in deserialized version.
1055 int hash = hash(key);
1056 int index = (hash & 0x7FFFFFFF) % tab.length;
1057 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
1058 if ((e.hash == hash) && e.key.equals(key)) {
1059 throw new java.io.StreamCorruptedException();
1060 }
1061 }
1062 // Creates the new entry.
1063 Entry<K,V> e = tab[index];
1064 tab[index] = new Entry<>(hash, key, value, e);
1065 count++;
1066 }
1067
1068 /**
1069 * Hashtable bucket collision list entry
1070 */
1071 private static class Entry<K,V> implements Map.Entry<K,V> {
1072 int hash;
1073 final K key;
1074 V value;
1075 Entry<K,V> next;
1076
1077 protected Entry(int hash, K key, V value, Entry<K,V> next) {
1078 this.hash = hash;
1079 this.key = key;
1080 this.value = value;
1081 this.next = next;
1082 }
1083
1084 protected Object clone() {
1085 return new Entry<>(hash, key, value,
1086 (next==null ? null : (Entry<K,V>) next.clone()));
1087 }
1088
1089 // Map.Entry Ops
1090
1091 public K getKey() {
1092 return key;
1093 }
1094
1095 public V getValue() {
1096 return value;
1097 }
1098
1099 public V setValue(V value) {
1100 if (value == null)
1101 throw new NullPointerException();
1102
1103 V oldValue = this.value;
1104 this.value = value;
1105 return oldValue;
1106 }
1107
1108 public boolean equals(Object o) {
1109 if (!(o instanceof Map.Entry))
1110 return false;
1111 Map.Entry<?,?> e = (Map.Entry)o;
1112
1113 return key.equals(e.getKey()) && value.equals(e.getValue());
1114 }
1115
1116 public int hashCode() {
1117 return (Objects.hashCode(key) ^ Objects.hashCode(value));
1118 }
1119
1120 public String toString() {
1121 return key.toString()+"="+value.toString();
1122 }
1123 }
1124
1125 // Types of Enumerations/Iterations
1126 private static final int KEYS = 0;
1127 private static final int VALUES = 1;
1128 private static final int ENTRIES = 2;
1129
1130 /**
1131 * A hashtable enumerator class. This class implements both the
1132 * Enumeration and Iterator interfaces, but individual instances
1133 * can be created with the Iterator methods disabled. This is necessary
1134 * to avoid unintentionally increasing the capabilities granted a user
1135 * by passing an Enumeration.
1136 */
1137 private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
1138 Entry[] table = Hashtable.this.table;
1139 int index = table.length;
1140 Entry<K,V> entry = null;
1141 Entry<K,V> lastReturned = null;
1142 int type;
1143
1144 /**
1145 * Indicates whether this Enumerator is serving as an Iterator
1146 * or an Enumeration. (true -> Iterator).
1147 */
1148 boolean iterator;
1149
1150 /**
1151 * The modCount value that the iterator believes that the backing
1152 * Hashtable should have. If this expectation is violated, the iterator
1153 * has detected concurrent modification.
1154 */
1155 protected int expectedModCount = modCount;
1156
1157 Enumerator(int type, boolean iterator) {
1158 this.type = type;
1159 this.iterator = iterator;
1160 }
1161
1162 public boolean hasMoreElements() {
1163 Entry<K,V> e = entry;
1164 int i = index;
1165 Entry[] t = table;
1166 /* Use locals for faster loop iteration */
1167 while (e == null && i > 0) {
1168 e = t[--i];
1169 }
1170 entry = e;
1171 index = i;
1172 return e != null;
1173 }
1174
1175 public T nextElement() {
1176 Entry<K,V> et = entry;
1177 int i = index;
1178 Entry[] t = table;
1179 /* Use locals for faster loop iteration */
1180 while (et == null && i > 0) {
1181 et = t[--i];
1182 }
1183 entry = et;
1184 index = i;
1185 if (et != null) {
1186 Entry<K,V> e = lastReturned = entry;
1187 entry = e.next;
1188 return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
1189 }
1190 throw new NoSuchElementException("Hashtable Enumerator");
1191 }
1192
1193 // Iterator methods
1194 public boolean hasNext() {
1195 return hasMoreElements();
1196 }
1197
1198 public T next() {
1199 if (modCount != expectedModCount)
1200 throw new ConcurrentModificationException();
1201 return nextElement();
1202 }
1203
1204 public void remove() {
1205 if (!iterator)
1206 throw new UnsupportedOperationException();
1207 if (lastReturned == null)
1208 throw new IllegalStateException("Hashtable Enumerator");
1209 if (modCount != expectedModCount)
1210 throw new ConcurrentModificationException();
1211
1212 synchronized(Hashtable.this) {
1213 Entry[] tab = Hashtable.this.table;
1214 int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;
1215
1216 for (Entry<K,V> e = tab[index], prev = null; e != null;
1217 prev = e, e = e.next) {
1218 if (e == lastReturned) {
1219 modCount++;
1220 expectedModCount++;
1221 if (prev == null)
1222 tab[index] = e.next;
1223 else
1224 prev.next = e.next;
1225 count--;
1226 lastReturned = null;
1227 return;
1228 }
1229 }
1230 throw new ConcurrentModificationException();
1231 }
1232 }
1233 }
1234 }