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