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