View Javadoc
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>,&nbsp;</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 = null;
621     private transient volatile Set<Map.Entry<K,V>> entrySet = null;
622     private transient volatile Collection<V> values = null;
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 length, threshold, loadfactor
1136             s.defaultWriteObject();
1137 
1138             // Write out length, 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 length, threshold, and loadfactor
1169         s.defaultReadObject();
1170 
1171         // Read the original length of the array and number of elements
1172         int origlength = s.readInt();
1173         int elements = s.readInt();
1174 
1175         // Compute new size with a bit of room 5% to grow but
1176         // no larger than the original size.  Make the length
1177         // odd if it's large enough, this helps distribute the entries.
1178         // Guard against the length ending up zero, that's not valid.
1179         int length = (int)(elements * loadFactor) + (elements / 20) + 3;
1180         if (length > elements && (length & 1) == 0)
1181             length--;
1182         if (origlength > 0 && length > origlength)
1183             length = origlength;
1184         table = new Entry<?,?>[length];
1185         threshold = (int)Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1);
1186         count = 0;
1187 
1188         // Read the number of elements and then all the key/value objects
1189         for (; elements > 0; elements--) {
1190             @SuppressWarnings("unchecked")
1191                 K key = (K)s.readObject();
1192             @SuppressWarnings("unchecked")
1193                 V value = (V)s.readObject();
1194             // synch could be eliminated for performance
1195             reconstitutionPut(table, key, value);
1196         }
1197     }
1198 
1199     /**
1200      * The put method used by readObject. This is provided because put
1201      * is overridable and should not be called in readObject since the
1202      * subclass will not yet be initialized.
1203      *
1204      * <p>This differs from the regular put method in several ways. No
1205      * checking for rehashing is necessary since the number of elements
1206      * initially in the table is known. The modCount is not incremented
1207      * because we are creating a new instance. Also, no return value
1208      * is needed.
1209      */
1210     private void reconstitutionPut(Entry<?,?>[] tab, K key, V value)
1211         throws StreamCorruptedException
1212     {
1213         if (value == null) {
1214             throw new java.io.StreamCorruptedException();
1215         }
1216         // Makes sure the key is not already in the hashtable.
1217         // This should not happen in deserialized version.
1218         int hash = key.hashCode();
1219         int index = (hash & 0x7FFFFFFF) % tab.length;
1220         for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
1221             if ((e.hash == hash) && e.key.equals(key)) {
1222                 throw new java.io.StreamCorruptedException();
1223             }
1224         }
1225         // Creates the new entry.
1226         @SuppressWarnings("unchecked")
1227             Entry<K,V> e = (Entry<K,V>)tab[index];
1228         tab[index] = new Entry<>(hash, key, value, e);
1229         count++;
1230     }
1231 
1232     /**
1233      * Hashtable bucket collision list entry
1234      */
1235     private static class Entry<K,V> implements Map.Entry<K,V> {
1236         final int hash;
1237         final K key;
1238         V value;
1239         Entry<K,V> next;
1240 
1241         protected Entry(int hash, K key, V value, Entry<K,V> next) {
1242             this.hash = hash;
1243             this.key =  key;
1244             this.value = value;
1245             this.next = next;
1246         }
1247 
1248         @SuppressWarnings("unchecked")
1249         protected Object clone() {
1250             return new Entry<>(hash, key, value,
1251                                   (next==null ? null : (Entry<K,V>) next.clone()));
1252         }
1253 
1254         // Map.Entry Ops
1255 
1256         public K getKey() {
1257             return key;
1258         }
1259 
1260         public V getValue() {
1261             return value;
1262         }
1263 
1264         public V setValue(V value) {
1265             if (value == null)
1266                 throw new NullPointerException();
1267 
1268             V oldValue = this.value;
1269             this.value = value;
1270             return oldValue;
1271         }
1272 
1273         public boolean equals(Object o) {
1274             if (!(o instanceof Map.Entry))
1275                 return false;
1276             Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1277 
1278             return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
1279                (value==null ? e.getValue()==null : value.equals(e.getValue()));
1280         }
1281 
1282         public int hashCode() {
1283             return hash ^ Objects.hashCode(value);
1284         }
1285 
1286         public String toString() {
1287             return key.toString()+"="+value.toString();
1288         }
1289     }
1290 
1291     // Types of Enumerations/Iterations
1292     private static final int KEYS = 0;
1293     private static final int VALUES = 1;
1294     private static final int ENTRIES = 2;
1295 
1296     /**
1297      * A hashtable enumerator class.  This class implements both the
1298      * Enumeration and Iterator interfaces, but individual instances
1299      * can be created with the Iterator methods disabled.  This is necessary
1300      * to avoid unintentionally increasing the capabilities granted a user
1301      * by passing an Enumeration.
1302      */
1303     private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
1304         Entry<?,?>[] table = Hashtable.this.table;
1305         int index = table.length;
1306         Entry<?,?> entry = null;
1307         Entry<?,?> lastReturned = null;
1308         int type;
1309 
1310         /**
1311          * Indicates whether this Enumerator is serving as an Iterator
1312          * or an Enumeration.  (true -> Iterator).
1313          */
1314         boolean iterator;
1315 
1316         /**
1317          * The modCount value that the iterator believes that the backing
1318          * Hashtable should have.  If this expectation is violated, the iterator
1319          * has detected concurrent modification.
1320          */
1321         protected int expectedModCount = modCount;
1322 
1323         Enumerator(int type, boolean iterator) {
1324             this.type = type;
1325             this.iterator = iterator;
1326         }
1327 
1328         public boolean hasMoreElements() {
1329             Entry<?,?> e = entry;
1330             int i = index;
1331             Entry<?,?>[] t = table;
1332             /* Use locals for faster loop iteration */
1333             while (e == null && i > 0) {
1334                 e = t[--i];
1335             }
1336             entry = e;
1337             index = i;
1338             return e != null;
1339         }
1340 
1341         @SuppressWarnings("unchecked")
1342         public T nextElement() {
1343             Entry<?,?> et = entry;
1344             int i = index;
1345             Entry<?,?>[] t = table;
1346             /* Use locals for faster loop iteration */
1347             while (et == null && i > 0) {
1348                 et = t[--i];
1349             }
1350             entry = et;
1351             index = i;
1352             if (et != null) {
1353                 Entry<?,?> e = lastReturned = entry;
1354                 entry = e.next;
1355                 return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
1356             }
1357             throw new NoSuchElementException("Hashtable Enumerator");
1358         }
1359 
1360         // Iterator methods
1361         public boolean hasNext() {
1362             return hasMoreElements();
1363         }
1364 
1365         public T next() {
1366             if (modCount != expectedModCount)
1367                 throw new ConcurrentModificationException();
1368             return nextElement();
1369         }
1370 
1371         public void remove() {
1372             if (!iterator)
1373                 throw new UnsupportedOperationException();
1374             if (lastReturned == null)
1375                 throw new IllegalStateException("Hashtable Enumerator");
1376             if (modCount != expectedModCount)
1377                 throw new ConcurrentModificationException();
1378 
1379             synchronized(Hashtable.this) {
1380                 Entry<?,?>[] tab = Hashtable.this.table;
1381                 int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;
1382 
1383                 @SuppressWarnings("unchecked")
1384                 Entry<K,V> e = (Entry<K,V>)tab[index];
1385                 for(Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
1386                     if (e == lastReturned) {
1387                         modCount++;
1388                         expectedModCount++;
1389                         if (prev == null)
1390                             tab[index] = e.next;
1391                         else
1392                             prev.next = e.next;
1393                         count--;
1394                         lastReturned = null;
1395                         return;
1396                     }
1397                 }
1398                 throw new ConcurrentModificationException();
1399             }
1400         }
1401     }
1402 }