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