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