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