content: /*
   * Copyright (C) 2014 The Android Open Source Project
   * Copyright (c) 1994, 2013, Oracle and/or its affiliates. All rights reserved.
   * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   *
   * This code is free software; you can redistribute it and/or modify it
   * under the terms of the GNU General Public License version 2 only, as
   * published by the Free Software Foundation.  Oracle designates this
   * particular file as subject to the "Classpath" exception as provided
   * by Oracle in the LICENSE file that accompanied this code.
   *
   * This code is distributed in the hope that it will be useful, but WITHOUT
   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
   * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
   * version 2 for more details (a copy is included in the LICENSE file that
   * accompanied this code).
   *
   * You should have received a copy of the GNU General Public License version
   * 2 along with this work; if not, write to the Free Software Foundation,
   * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
   *
   * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
   * or visit www.oracle.com if you need additional information or have any
   * questions.
   */
  
  package java.util;
  
  import java.io.*;
  import java.util.function.BiConsumer;
  import java.util.function.BiFunction;
  import java.util.function.Function;
  
  /**
   * This class implements a hash table, which maps keys to values. Any
   * non-<code>null</code> object can be used as a key or as a value. <p>
   *
   * To successfully store and retrieve objects from a hashtable, the
   * objects used as keys must implement the <code>hashCode</code>
   * method and the <code>equals</code> method. <p>
   *
   * An instance of <code>Hashtable</code> has two parameters that affect its
   * performance: <i>initial capacity</i> and <i>load factor</i>.  The
   * <i>capacity</i> is the number of <i>buckets</i> in the hash table, and the
   * <i>initial capacity</i> is simply the capacity at the time the hash table
   * is created.  Note that the hash table is <i>open</i>: in the case of a "hash
   * collision", a single bucket stores multiple entries, which must be searched
   * sequentially.  The <i>load factor</i> is a measure of how full the hash
   * table is allowed to get before its capacity is automatically increased.
   * The initial capacity and load factor parameters are merely hints to
   * the implementation.  The exact details as to when and whether the rehash
   * method is invoked are implementation-dependent.<p>
   *
   * Generally, the default load factor (.75) offers a good tradeoff between
   * time and space costs.  Higher values decrease the space overhead but
   * increase the time cost to look up an entry (which is reflected in most
   * <tt>Hashtable</tt> operations, including <tt>get</tt> and <tt>put</tt>).<p>
   *
   * The initial capacity controls a tradeoff between wasted space and the
   * need for <code>rehash</code> operations, which are time-consuming.
   * No <code>rehash</code> operations will <i>ever</i> occur if the initial
   * capacity is greater than the maximum number of entries the
   * <tt>Hashtable</tt> will contain divided by its load factor.  However,
   * setting the initial capacity too high can waste space.<p>
   *
   * If many entries are to be made into a <code>Hashtable</code>,
   * creating it with a sufficiently large capacity may allow the
   * entries to be inserted more efficiently than letting it perform
   * automatic rehashing as needed to grow the table. <p>
   *
   * This example creates a hashtable of numbers. It uses the names of
   * the numbers as keys:
   * <pre>   {@code
   *   Hashtable<String, Integer> numbers
   *     = new Hashtable<String, Integer>();
   *   numbers.put("one", 1);
   *   numbers.put("two", 2);
   *   numbers.put("three", 3);}</pre>
   *
   * <p>To retrieve a number, use the following code:
   * <pre>   {@code
   *   Integer n = numbers.get("two");
   *   if (n != null) {
   *     System.out.println("two = " + n);
   *   }}</pre>
   *
   * <p>The iterators returned by the <tt>iterator</tt> method of the collections
   * returned by all of this class's "collection view methods" are
   * <em>fail-fast</em>: if the Hashtable is structurally modified at any time
   * after the iterator is created, in any way except through the iterator's own
   * <tt>remove</tt> method, the iterator will throw a {@link
   * ConcurrentModificationException}.  Thus, in the face of concurrent
   * modification, the iterator fails quickly and cleanly, rather than risking
   * arbitrary, non-deterministic behavior at an undetermined time in the future.
   * The Enumerations returned by Hashtable's keys and elements methods are
   * <em>not</em> fail-fast.
   *
   * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
   * as it is, generally speaking, impossible to make any hard guarantees in the
   * presence of unsynchronized concurrent modification.  Fail-fast iterators
   * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
   * Therefore, it would be wrong to write a program that depended on this
   * exception for its correctness: <i>the fail-fast behavior of iterators
   * should be used only to detect bugs.</i>
   *
   * <p>As of the Java 2 platform v1.2, this class was retrofitted to
   * implement the {@link Map} interface, making it a member of the
   * <a href="{@docRoot}/../technotes/guides/collections/index.html">
   *
   * Java Collections Framework</a>.  Unlike the new collection
   * implementations, {@code Hashtable} is synchronized.  If a
   * thread-safe implementation is not needed, it is recommended to use
   * {@link HashMap} in place of {@code Hashtable}.  If a thread-safe
   * highly-concurrent implementation is desired, then it is recommended
   * to use {@link java.util.concurrent.ConcurrentHashMap} in place of
   * {@code Hashtable}.
   *
   * @author  Arthur van Hoff
   * @author  Josh Bloch
   * @author  Neal Gafter
   * @see     Object#equals(Object)
   * @see     Object#hashCode()
   * @see     Hashtable#rehash()
   * @see     Collection
   * @see     Map
   * @see     HashMap
   * @see     TreeMap
   * @since JDK1.0
   */
  public class Hashtable<K,V>
      extends Dictionary<K,V>
      implements Map<K,V>, Cloneable, Serializable {
  
      /**
       * The hash table data.
       */
      private transient HashtableEntry<?,?>[] table;
  
      /**
       * The total number of entries in the hash table.
       */
      private transient int count;
  
      /**
       * The table is rehashed when its size exceeds this threshold.  (The
       * value of this field is (int)(capacity * loadFactor).)
       *
       * @serial
       */
      private int threshold;
  
      /**
       * The load factor for the hashtable.
       *
       * @serial
       */
      private float loadFactor;
  
      /**
       * The number of times this Hashtable has been structurally modified
       * Structural modifications are those that change the number of entries in
       * the Hashtable or otherwise modify its internal structure (e.g.,
       * rehash).  This field is used to make iterators on Collection-views of
       * the Hashtable fail-fast.  (See ConcurrentModificationException).
       */
      private transient int modCount = 0;
  
      /** use serialVersionUID from JDK 1.0.2 for interoperability */
      private static final long serialVersionUID = 1421746759512286392L;
  
      /**
       * Constructs a new, empty hashtable with the specified initial
       * capacity and the specified load factor.
       *
       * @param      initialCapacity   the initial capacity of the hashtable.
       * @param      loadFactor        the load factor of the hashtable.
       * @exception  IllegalArgumentException  if the initial capacity is less
       *             than zero, or if the load factor is nonpositive.
       */
      public Hashtable(int initialCapacity, float loadFactor) {
          if (initialCapacity < 0)
              throw new IllegalArgumentException("Illegal Capacity: "+
                                                 initialCapacity);
          if (loadFactor <= 0 || Float.isNaN(loadFactor))
              throw new IllegalArgumentException("Illegal Load: "+loadFactor);
  
          if (initialCapacity==0)
              initialCapacity = 1;
          this.loadFactor = loadFactor;
          table = new HashtableEntry<?,?>[initialCapacity];
          // Android-changed: Ignore loadFactor when calculating threshold from initialCapacity
          // threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
          threshold = (int)Math.min(initialCapacity, MAX_ARRAY_SIZE + 1);
      }
  
      /**
       * Constructs a new, empty hashtable with the specified initial capacity
       * and default load factor (0.75).
       *
       * @param     initialCapacity   the initial capacity of the hashtable.
       * @exception IllegalArgumentException if the initial capacity is less
       *              than zero.
       */
      public Hashtable(int initialCapacity) {
          this(initialCapacity, 0.75f);
      }
  
      /**
       * Constructs a new, empty hashtable with a default initial capacity (11)
       * and load factor (0.75).
       */
      public Hashtable() {
          this(11, 0.75f);
      }
  
      /**
       * Constructs a new hashtable with the same mappings as the given
       * Map.  The hashtable is created with an initial capacity sufficient to
       * hold the mappings in the given Map and a default load factor (0.75).
       *
       * @param t the map whose mappings are to be placed in this map.
       * @throws NullPointerException if the specified map is null.
       * @since   1.2
       */
      public Hashtable(Map<? extends K, ? extends V> t) {
          this(Math.max(2*t.size(), 11), 0.75f);
          putAll(t);
      }
  
      /**
       * Returns the number of keys in this hashtable.
       *
       * @return  the number of keys in this hashtable.
       */
      public synchronized int size() {
          return count;
      }
  
      /**
       * Tests if this hashtable maps no keys to values.
       *
       * @return  <code>true</code> if this hashtable maps no keys to values;
       *          <code>false</code> otherwise.
       */
      public synchronized boolean isEmpty() {
          return count == 0;
      }
  
      /**
       * Returns an enumeration of the keys in this hashtable.
       *
       * @return  an enumeration of the keys in this hashtable.
       * @see     Enumeration
       * @see     #elements()
       * @see     #keySet()
       * @see     Map
       */
      public synchronized Enumeration<K> keys() {
          return this.<K>getEnumeration(KEYS);
      }
  
      /**
       * Returns an enumeration of the values in this hashtable.
       * Use the Enumeration methods on the returned object to fetch the elements
       * sequentially.
       *
       * @return  an enumeration of the values in this hashtable.
       * @see     Enumeration
       * @see     #keys()
       * @see     #values()
       * @see     Map
       */
      public synchronized Enumeration<V> elements() {
          return this.<V>getEnumeration(VALUES);
      }
  
      /**
       * Tests if some key maps into the specified value in this hashtable.
       * This operation is more expensive than the {@link #containsKey
       * containsKey} method.
       *
       * <p>Note that this method is identical in functionality to
       * {@link #containsValue containsValue}, (which is part of the
       * {@link Map} interface in the collections framework).
       *
       * @param      value   a value to search for
       * @return     <code>true</code> if and only if some key maps to the
       *             <code>value</code> argument in this hashtable as
       *             determined by the <tt>equals</tt> method;
       *             <code>false</code> otherwise.
       * @exception  NullPointerException  if the value is <code>null</code>
       */
      public synchronized boolean contains(Object value) {
          if (value == null) {
              throw new NullPointerException();
          }
  
          HashtableEntry<?,?> tab[] = table;
          for (int i = tab.length ; i-- > 0 ;) {
              for (HashtableEntry<?,?> e = tab[i] ; e != null ; e = e.next) {
                  if (e.value.equals(value)) {
                      return true;
                  }
              }
          }
          return false;
      }
  
      /**
       * Returns true if this hashtable maps one or more keys to this value.
       *
       * <p>Note that this method is identical in functionality to {@link
       * #contains contains} (which predates the {@link Map} interface).
       *
       * @param value value whose presence in this hashtable is to be tested
       * @return <tt>true</tt> if this map maps one or more keys to the
       *         specified value
       * @throws NullPointerException  if the value is <code>null</code>
       * @since 1.2
       */
      public boolean containsValue(Object value) {
          return contains(value);
      }
  
      /**
       * Tests if the specified object is a key in this hashtable.
       *
       * @param   key   possible key
       * @return  <code>true</code> if and only if the specified object
       *          is a key in this hashtable, as determined by the
       *          <tt>equals</tt> method; <code>false</code> otherwise.
       * @throws  NullPointerException  if the key is <code>null</code>
       * @see     #contains(Object)
       */
      public synchronized boolean containsKey(Object key) {
          HashtableEntry<?,?> tab[] = table;
          int hash = key.hashCode();
          int index = (hash & 0x7FFFFFFF) % tab.length;
          for (HashtableEntry<?,?> e = tab[index] ; e != null ; e = e.next) {
              if ((e.hash == hash) && e.key.equals(key)) {
                  return true;
              }
          }
          return false;
      }
  
      /**
       * Returns the value to which the specified key is mapped,
       * or {@code null} if this map contains no mapping for the key.
       *
       * <p>More formally, if this map contains a mapping from a key
       * {@code k} to a value {@code v} such that {@code (key.equals(k))},
       * then this method returns {@code v}; otherwise it returns
       * {@code null}.  (There can be at most one such mapping.)
       *
       * @param key the key whose associated value is to be returned
       * @return the value to which the specified key is mapped, or
       *         {@code null} if this map contains no mapping for the key
       * @throws NullPointerException if the specified key is null
       * @see     #put(Object, Object)
       */
      @SuppressWarnings("unchecked")
      public synchronized V get(Object key) {
          HashtableEntry<?,?> tab[] = table;
          int hash = key.hashCode();
          int index = (hash & 0x7FFFFFFF) % tab.length;
          for (HashtableEntry<?,?> e = tab[index] ; e != null ; e = e.next) {
              if ((e.hash == hash) && e.key.equals(key)) {
                  return (V)e.value;
              }
          }
          return null;
      }
  
      /**
       * The maximum size of array to allocate.
       * Some VMs reserve some header words in an array.
       * Attempts to allocate larger arrays may result in
       * OutOfMemoryError: Requested array size exceeds VM limit
       */
      private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  
      /**
       * Increases the capacity of and internally reorganizes this
       * hashtable, in order to accommodate and access its entries more
       * efficiently.  This method is called automatically when the
       * number of keys in the hashtable exceeds this hashtable's capacity
       * and load factor.
       */
      @SuppressWarnings("unchecked")
      protected void rehash() {
          int oldCapacity = table.length;
          HashtableEntry<?,?>[] oldMap = table;
  
          // overflow-conscious code
          int newCapacity = (oldCapacity << 1) + 1;
          if (newCapacity - MAX_ARRAY_SIZE > 0) {
              if (oldCapacity == MAX_ARRAY_SIZE)
                  // Keep running with MAX_ARRAY_SIZE buckets
                  return;
              newCapacity = MAX_ARRAY_SIZE;
          }
          HashtableEntry<?,?>[] newMap = new HashtableEntry<?,?>[newCapacity];
  
          modCount++;
          threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
          table = newMap;
  
          for (int i = oldCapacity ; i-- > 0 ;) {
              for (HashtableEntry<K,V> old = (HashtableEntry<K,V>)oldMap[i] ; old != null ; ) {
                  HashtableEntry<K,V> e = old;
                  old = old.next;
  
                  int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                  e.next = (HashtableEntry<K,V>)newMap[index];
                  newMap[index] = e;
              }
          }
      }
  
      private void addEntry(int hash, K key, V value, int index) {
          modCount++;
  
          HashtableEntry<?,?> tab[] = table;
          if (count >= threshold) {
              // Rehash the table if the threshold is exceeded
              rehash();
  
              tab = table;
              hash = key.hashCode();
              index = (hash & 0x7FFFFFFF) % tab.length;
          }
  
          // Creates the new entry.
          @SuppressWarnings("unchecked")
          HashtableEntry<K,V> e = (HashtableEntry<K,V>) tab[index];
          tab[index] = new HashtableEntry<>(hash, key, value, e);
          count++;
      }
  
      /**
       * Maps the specified <code>key</code> to the specified
       * <code>value</code> in this hashtable. Neither the key nor the
       * value can be <code>null</code>. <p>
       *
       * The value can be retrieved by calling the <code>get</code> method
       * with a key that is equal to the original key.
       *
       * @param      key     the hashtable key
       * @param      value   the value
       * @return     the previous value of the specified key in this hashtable,
       *             or <code>null</code> if it did not have one
       * @exception  NullPointerException  if the key or value is
       *               <code>null</code>
       * @see     Object#equals(Object)
       * @see     #get(Object)
       */
      public synchronized V put(K key, V value) {
          // Make sure the value is not null
          if (value == null) {
              throw new NullPointerException();
          }
  
          // Makes sure the key is not already in the hashtable.
          HashtableEntry<?,?> tab[] = table;
          int hash = key.hashCode();
          int index = (hash & 0x7FFFFFFF) % tab.length;
          @SuppressWarnings("unchecked")
          HashtableEntry<K,V> entry = (HashtableEntry<K,V>)tab[index];
          for(; entry != null ; entry = entry.next) {
              if ((entry.hash == hash) && entry.key.equals(key)) {
                  V old = entry.value;
                  entry.value = value;
                  return old;
              }
          }
  
          addEntry(hash, key, value, index);
          return null;
      }
  
      /**
       * Removes the key (and its corresponding value) from this
       * hashtable. This method does nothing if the key is not in the hashtable.
       *
       * @param   key   the key that needs to be removed
       * @return  the value to which the key had been mapped in this hashtable,
       *          or <code>null</code> if the key did not have a mapping
       * @throws  NullPointerException  if the key is <code>null</code>
       */
      public synchronized V remove(Object key) {
          HashtableEntry<?,?> tab[] = table;
          int hash = key.hashCode();
          int index = (hash & 0x7FFFFFFF) % tab.length;
          @SuppressWarnings("unchecked")
          HashtableEntry<K,V> e = (HashtableEntry<K,V>)tab[index];
          for(HashtableEntry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
              if ((e.hash == hash) && e.key.equals(key)) {
                  modCount++;
                  if (prev != null) {
                      prev.next = e.next;
                  } else {
                      tab[index] = e.next;
                  }
                  count--;
                  V oldValue = e.value;
                  e.value = null;
                  return oldValue;
              }
          }
          return null;
      }
  
      /**
       * Copies all of the mappings from the specified map to this hashtable.
       * These mappings will replace any mappings that this hashtable had for any
       * of the keys currently in the specified map.
       *
       * @param t mappings to be stored in this map
       * @throws NullPointerException if the specified map is null
       * @since 1.2
       */
      public synchronized void putAll(Map<? extends K, ? extends V> t) {
          for (Entry<? extends K, ? extends V> e : t.entrySet())
              put(e.getKey(), e.getValue());
      }
  
      /**
       * Clears this hashtable so that it contains no keys.
       */
      public synchronized void clear() {
          HashtableEntry<?,?> tab[] = table;
          modCount++;
          for (int index = tab.length; --index >= 0; )
              tab[index] = null;
          count = 0;
      }
  
      /**
       * Creates a shallow copy of this hashtable. All the structure of the
       * hashtable itself is copied, but the keys and values are not cloned.
       * This is a relatively expensive operation.
       *
       * @return  a clone of the hashtable
       */
      public synchronized Object clone() {
          try {
              Hashtable<?,?> t = (Hashtable<?,?>)super.clone();
              t.table = new HashtableEntry<?,?>[table.length];
              for (int i = table.length ; i-- > 0 ; ) {
                  t.table[i] = (table[i] != null)
                      ? (HashtableEntry<?,?>) table[i].clone() : null;
              }
              t.keySet = null;
              t.entrySet = null;
              t.values = null;
              t.modCount = 0;
              return t;
          } catch (CloneNotSupportedException e) {
              // this shouldn't happen, since we are Cloneable
              throw new InternalError(e);
          }
      }
  
      /**
       * Returns a string representation of this <tt>Hashtable</tt> object
       * in the form of a set of entries, enclosed in braces and separated
       * by the ASCII characters "<tt>,&nbsp;</tt>" (comma and space). Each
       * entry is rendered as the key, an equals sign <tt>=</tt>, and the
       * associated element, where the <tt>toString</tt> method is used to
       * convert the key and element to strings.
       *
       * @return  a string representation of this hashtable
       */
      public synchronized String toString() {
          int max = size() - 1;
          if (max == -1)
              return "{}";
  
          StringBuilder sb = new StringBuilder();
          Iterator<Entry<K,V>> it = entrySet().iterator();
  
          sb.append('{');
          for (int i = 0; ; i++) {
              Entry<K,V> e = it.next();
              K key = e.getKey();
              V value = e.getValue();
              sb.append(key   == this ? "(this Map)" : key.toString());
              sb.append('=');
              sb.append(value == this ? "(this Map)" : value.toString());
  
              if (i == max)
                  return sb.append('}').toString();
              sb.append(", ");
          }
      }
  
  
      private <T> Enumeration<T> getEnumeration(int type) {
          if (count == 0) {
              return Collections.emptyEnumeration();
          } else {
              return new Enumerator<>(type, false);
          }
      }
  
      private <T> Iterator<T> getIterator(int type) {
          if (count == 0) {
              return Collections.emptyIterator();
          } else {
              return new Enumerator<>(type, true);
          }
      }
  
      // Views
  
      /**
       * Each of these fields are initialized to contain an instance of the
       * appropriate view the first time this view is requested.  The views are
       * stateless, so there's no reason to create more than one of each.
       */
      private transient volatile Set<K> keySet;
      private transient volatile Set<Entry<K,V>> entrySet;
      private transient volatile Collection<V> values;
  
      /**
       * Returns a {@link Set} view of the keys contained in this map.
       * The set is backed by the map, so changes to the map are
       * reflected in the set, and vice-versa.  If the map is modified
       * while an iteration over the set is in progress (except through
       * the iterator's own <tt>remove</tt> operation), the results of
       * the iteration are undefined.  The set supports element removal,
       * which removes the corresponding mapping from the map, via the
       * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
       * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
       * operations.  It does not support the <tt>add</tt> or <tt>addAll</tt>
       * operations.
       *
       * @since 1.2
       */
      public Set<K> keySet() {
          if (keySet == null)
              keySet = Collections.synchronizedSet(new KeySet(), this);
          return keySet;
      }
  
      private class KeySet extends AbstractSet<K> {
          public Iterator<K> iterator() {
              return getIterator(KEYS);
          }
          public int size() {
              return count;
          }
          public boolean contains(Object o) {
              return containsKey(o);
          }
          public boolean remove(Object o) {
              return Hashtable.this.remove(o) != null;
          }
          public void clear() {
              Hashtable.this.clear();
          }
      }
  
      /**
       * Returns a {@link Set} view of the mappings contained in this map.
       * The set is backed by the map, so changes to the map are
       * reflected in the set, and vice-versa.  If the map is modified
       * while an iteration over the set is in progress (except through
       * the iterator's own <tt>remove</tt> operation, or through the
       * <tt>setValue</tt> operation on a map entry returned by the
       * iterator) the results of the iteration are undefined.  The set
       * supports element removal, which removes the corresponding
       * mapping from the map, via the <tt>Iterator.remove</tt>,
       * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
       * <tt>clear</tt> operations.  It does not support the
       * <tt>add</tt> or <tt>addAll</tt> operations.
       *
       * @since 1.2
       */
      public Set<Entry<K,V>> entrySet() {
          if (entrySet==null)
              entrySet = Collections.synchronizedSet(new EntrySet(), this);
          return entrySet;
      }
  
      private class EntrySet extends AbstractSet<Entry<K,V>> {
          public Iterator<Entry<K,V>> iterator() {
              return getIterator(ENTRIES);
          }
  
          public boolean add(Entry<K,V> o) {
              return super.add(o);
          }
  
          public boolean contains(Object o) {
              if (!(o instanceof Map.Entry))
                  return false;
              Entry<?,?> entry = (Entry<?,?>)o;
              Object key = entry.getKey();
              HashtableEntry<?,?>[] tab = table;
              int hash = key.hashCode();
              int index = (hash & 0x7FFFFFFF) % tab.length;
  
              for (HashtableEntry<?,?> e = tab[index]; e != null; e = e.next)
                  if (e.hash==hash && e.equals(entry))
                      return true;
              return false;
          }
  
          public boolean remove(Object o) {
              if (!(o instanceof Map.Entry))
                  return false;
              Entry<?,?> entry = (Entry<?,?>) o;
              Object key = entry.getKey();
              HashtableEntry<?,?>[] tab = table;
              int hash = key.hashCode();
              int index = (hash & 0x7FFFFFFF) % tab.length;
  
              @SuppressWarnings("unchecked")
              HashtableEntry<K,V> e = (HashtableEntry<K,V>)tab[index];
              for(HashtableEntry<K,V> prev = null; e != null; prev = e, e = e.next) {
                  if (e.hash==hash && e.equals(entry)) {
                      modCount++;
                      if (prev != null)
                          prev.next = e.next;
                      else
                          tab[index] = e.next;
  
                      count--;
                      e.value = null;
                      return true;
                  }
              }
              return false;
          }
  
          public int size() {
              return count;
          }
  
          public void clear() {
              Hashtable.this.clear();
          }
      }
  
      /**
       * Returns a {@link Collection} view of the values contained in this map.
       * The collection is backed by the map, so changes to the map are
       * reflected in the collection, and vice-versa.  If the map is
       * modified while an iteration over the collection is in progress
       * (except through the iterator's own <tt>remove</tt> operation),
       * the results of the iteration are undefined.  The collection
       * supports element removal, which removes the corresponding
       * mapping from the map, via the <tt>Iterator.remove</tt>,
       * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
       * <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
       * support the <tt>add</tt> or <tt>addAll</tt> operations.
       *
       * @since 1.2
       */
      public Collection<V> values() {
          if (values==null)
              values = Collections.synchronizedCollection(new ValueCollection(),
                                                          this);
          return values;
      }
  
      private class ValueCollection extends AbstractCollection<V> {
          public Iterator<V> iterator() {
              return getIterator(VALUES);
          }
          public int size() {
              return count;
          }
          public boolean contains(Object o) {
              return containsValue(o);
          }
          public void clear() {
              Hashtable.this.clear();
          }
      }
  
      // Comparison and hashing
  
      /**
       * Compares the specified Object with this Map for equality,
       * as per the definition in the Map interface.
       *
       * @param  o object to be compared for equality with this hashtable
       * @return true if the specified Object is equal to this Map
       * @see Map#equals(Object)
       * @since 1.2
       */
      public synchronized boolean equals(Object o) {
          if (o == this)
              return true;
  
          if (!(o instanceof Map))
              return false;
          Map<?,?> t = (Map<?,?>) o;
          if (t.size() != size())
              return false;
  
          try {
              Iterator<Entry<K,V>> i = entrySet().iterator();
              while (i.hasNext()) {
                  Entry<K,V> e = i.next();
                  K key = e.getKey();
                  V value = e.getValue();
                  if (value == null) {
                      if (!(t.get(key)==null && t.containsKey(key)))
                          return false;
                  } else {
                      if (!value.equals(t.get(key)))
                          return false;
                  }
              }
          } catch (ClassCastException unused)   {
              return false;
          } catch (NullPointerException unused) {
              return false;
          }
  
          return true;
      }
  
      /**
       * Returns the hash code value for this Map as per the definition in the
       * Map interface.
       *
       * @see Map#hashCode()
       * @since 1.2
       */
      public synchronized int hashCode() {
          /*
           * This code detects the recursion caused by computing the hash code
           * of a self-referential hash table and prevents the stack overflow
           * that would otherwise result.  This allows certain 1.1-era
           * applets with self-referential hash tables to work.  This code
           * abuses the loadFactor field to do double-duty as a hashCode
           * in progress flag, so as not to worsen the space performance.
           * A negative load factor indicates that hash code computation is
           * in progress.
           */
          int h = 0;
          if (count == 0 || loadFactor < 0)
              return h;  // Returns zero
  
          loadFactor = -loadFactor;  // Mark hashCode computation in progress
          HashtableEntry<?,?>[] tab = table;
          for (HashtableEntry<?,?> entry : tab) {
              while (entry != null) {
                  h += entry.hashCode();
                  entry = entry.next;
              }
          }
  
          loadFactor = -loadFactor;  // Mark hashCode computation complete
  
          return h;
      }
  
      @Override
      public synchronized V getOrDefault(Object key, V defaultValue) {
          V result = get(key);
          return (null == result) ? defaultValue : result;
      }
  
      @SuppressWarnings("unchecked")
      @Override
      public synchronized void forEach(BiConsumer<? super K, ? super V> action) {
          Objects.requireNonNull(action);     // explicit check required in case
                                              // table is empty.
          final int expectedModCount = modCount;
  
          HashtableEntry<?, ?>[] tab = table;
          for (HashtableEntry<?, ?> entry : tab) {
              while (entry != null) {
                  action.accept((K)entry.key, (V)entry.value);
                  entry = entry.next;
  
                  if (expectedModCount != modCount) {
                      throw new ConcurrentModificationException();
                  }
              }
          }
      }
  
      @SuppressWarnings("unchecked")
      @Override
      public synchronized void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
          Objects.requireNonNull(function);     // explicit check required in case
                                                // table is empty.
          final int expectedModCount = modCount;
  
          HashtableEntry<K, V>[] tab = (HashtableEntry<K, V>[])table;
          for (HashtableEntry<K, V> entry : tab) {
              while (entry != null) {
                  entry.value = Objects.requireNonNull(
                      function.apply(entry.key, entry.value));
                  entry = entry.next;
  
                  if (expectedModCount != modCount) {
                      throw new ConcurrentModificationException();
                  }
              }
          }
      }
  
      @Override
      public synchronized V putIfAbsent(K key, V value) {
          Objects.requireNonNull(value);
  
          // Makes sure the key is not already in the hashtable.
          HashtableEntry<?,?> tab[] = table;
          int hash = key.hashCode();
          int index = (hash & 0x7FFFFFFF) % tab.length;
          @SuppressWarnings("unchecked")
          HashtableEntry<K,V> entry = (HashtableEntry<K,V>)tab[index];
          for (; entry != null; entry = entry.next) {
              if ((entry.hash == hash) && entry.key.equals(key)) {
                  V old = entry.value;
                  if (old == null) {
                      entry.value = value;
                  }
                  return old;
              }
          }
  
          addEntry(hash, key, value, index);
          return null;
      }
  
      @Override
      public synchronized boolean remove(Object key, Object value) {
          Objects.requireNonNull(value);
  
          HashtableEntry<?,?> tab[] = table;
          int hash = key.hashCode();
          int index = (hash & 0x7FFFFFFF) % tab.length;
          @SuppressWarnings("unchecked")
          HashtableEntry<K,V> e = (HashtableEntry<K,V>)tab[index];
          for (HashtableEntry<K,V> prev = null; e != null; prev = e, e = e.next) {
              if ((e.hash == hash) && e.key.equals(key) && e.value.equals(value)) {
                  modCount++;
                  if (prev != null) {
                      prev.next = e.next;
                  } else {
                      tab[index] = e.next;
                  }
                  count--;
                  e.value = null;
                  return true;
              }
          }
          return false;
      }
  
      @Override
      public synchronized boolean replace(K key, V oldValue, V newValue) {
          Objects.requireNonNull(oldValue);
          Objects.requireNonNull(newValue);
          HashtableEntry<?,?> tab[] = table;
          int hash = key.hashCode();
          int index = (hash & 0x7FFFFFFF) % tab.length;
          @SuppressWarnings("unchecked")
          HashtableEntry<K,V> e = (HashtableEntry<K,V>)tab[index];
          for (; e != null; e = e.next) {
              if ((e.hash == hash) && e.key.equals(key)) {
                  if (e.value.equals(oldValue)) {
                      e.value = newValue;
                      return true;
                  } else {
                      return false;
                  }
              }
          }
          return false;
      }
  
      @Override
      public synchronized V replace(K key, V value) {
          Objects.requireNonNull(value);
          HashtableEntry<?,?> tab[] = table;
          int hash = key.hashCode();
          int index = (hash & 0x7FFFFFFF) % tab.length;
          @SuppressWarnings("unchecked")
          HashtableEntry<K,V> e = (HashtableEntry<K,V>)tab[index];
          for (; e != null; e = e.next) {
              if ((e.hash == hash) && e.key.equals(key)) {
                  V oldValue = e.value;
                  e.value = value;
                  return oldValue;
              }
          }
          return null;
      }
  
      @Override
      public synchronized V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
          Objects.requireNonNull(mappingFunction);
  
          HashtableEntry<?,?> tab[] = table;
          int hash = key.hashCode();
          int index = (hash & 0x7FFFFFFF) % tab.length;
          @SuppressWarnings("unchecked")
          HashtableEntry<K,V> e = (HashtableEntry<K,V>)tab[index];
          for (; e != null; e = e.next) {
              if (e.hash == hash && e.key.equals(key)) {
                  // Hashtable not accept null value
                  return e.value;
              }
          }
  
          V newValue = mappingFunction.apply(key);
          if (newValue != null) {
              addEntry(hash, key, newValue, index);
          }
  
          return newValue;
      }
  
      @Override
      public synchronized V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
          Objects.requireNonNull(remappingFunction);
  
          HashtableEntry<?,?> tab[] = table;
          int hash = key.hashCode();
          int index = (hash & 0x7FFFFFFF) % tab.length;
          @SuppressWarnings("unchecked")
          HashtableEntry<K,V> e = (HashtableEntry<K,V>)tab[index];
          for (HashtableEntry<K,V> prev = null; e != null; prev = e, e = e.next) {
              if (e.hash == hash && e.key.equals(key)) {
                  V newValue = remappingFunction.apply(key, e.value);
                  if (newValue == null) {
                      modCount++;
                      if (prev != null) {
                          prev.next = e.next;
                      } else {
                          tab[index] = e.next;
                      }
                      count--;
                  } else {
                      e.value = newValue;
                  }
                  return newValue;
              }
          }
          return null;
      }
  
      @Override
      public synchronized V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
          Objects.requireNonNull(remappingFunction);
  
          HashtableEntry<?,?> tab[] = table;
          int hash = key.hashCode();
          int index = (hash & 0x7FFFFFFF) % tab.length;
          @SuppressWarnings("unchecked")
          HashtableEntry<K,V> e = (HashtableEntry<K,V>)tab[index];
          for (HashtableEntry<K,V> prev = null; e != null; prev = e, e = e.next) {
              if (e.hash == hash && Objects.equals(e.key, key)) {
                  V newValue = remappingFunction.apply(key, e.value);
                  if (newValue == null) {
                      modCount++;
                      if (prev != null) {
                          prev.next = e.next;
                      } else {
                          tab[index] = e.next;
                      }
                      count--;
                  } else {
                      e.value = newValue;
                  }
                  return newValue;
              }
          }
  
          V newValue = remappingFunction.apply(key, null);
          if (newValue != null) {
              addEntry(hash, key, newValue, index);
          }
  
          return newValue;
      }
  
      @Override
      public synchronized V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
          Objects.requireNonNull(remappingFunction);
  
          HashtableEntry<?,?> tab[] = table;
          int hash = key.hashCode();
          int index = (hash & 0x7FFFFFFF) % tab.length;
          @SuppressWarnings("unchecked")
          HashtableEntry<K,V> e = (HashtableEntry<K,V>)tab[index];
          for (HashtableEntry<K,V> prev = null; e != null; prev = e, e = e.next) {
              if (e.hash == hash && e.key.equals(key)) {
                  V newValue = remappingFunction.apply(e.value, value);
                  if (newValue == null) {
                      modCount++;
                      if (prev != null) {
                          prev.next = e.next;
                      } else {
                          tab[index] = e.next;
                      }
                      count--;
                  } else {
                      e.value = newValue;
                  }
                  return newValue;
              }
          }
  
          if (value != null) {
              addEntry(hash, key, value, index);
          }
  
          return value;
      }
  
      /**
       * Save the state of the Hashtable to a stream (i.e., serialize it).
       *
       * @serialData The <i>capacity</i> of the Hashtable (the length of the
       *             bucket array) is emitted (int), followed by the
       *             <i>size</i> of the Hashtable (the number of key-value
       *             mappings), followed by the key (Object) and value (Object)
       *             for each key-value mapping represented by the Hashtable
       *             The key-value mappings are emitted in no particular order.
       */
      private void writeObject(ObjectOutputStream s)
              throws IOException {
          HashtableEntry<Object, Object> entryStack = null;
  
          synchronized (this) {
              // Write out the threshold and loadFactor
              s.defaultWriteObject();
  
              // Write out the length and count of elements
              s.writeInt(table.length);
              s.writeInt(count);
  
              // Stack copies of the entries in the table
              for (int index = 0; index < table.length; index++) {
                  HashtableEntry<?,?> entry = table[index];
  
                  while (entry != null) {
                      entryStack =
                          new HashtableEntry<>(0, entry.key, entry.value, entryStack);
                      entry = entry.next;
                  }
              }
          }
  
          // Write out the key/value objects from the stacked entries
          while (entryStack != null) {
              s.writeObject(entryStack.key);
              s.writeObject(entryStack.value);
              entryStack = entryStack.next;
          }
      }
  
      /**
       * Reconstitute the Hashtable from a stream (i.e., deserialize it).
       */
      private void readObject(ObjectInputStream s)
           throws IOException, ClassNotFoundException
      {
          // Read in the threshold and loadFactor
          s.defaultReadObject();
  
          // Validate loadFactor (ignore threshold - it will be re-computed)
          if (loadFactor <= 0 || Float.isNaN(loadFactor))
              throw new StreamCorruptedException("Illegal Load: " + loadFactor);
  
          // Read the original length of the array and number of elements
          int origlength = s.readInt();
          int elements = s.readInt();
  
          // Validate # of elements
          if (elements < 0)
              throw new StreamCorruptedException("Illegal # of Elements: " + elements);
  
          // Clamp original length to be more than elements / loadFactor
          // (this is the invariant enforced with auto-growth)
          origlength = Math.max(origlength, (int)(elements / loadFactor) + 1);
  
          // Compute new length with a bit of room 5% + 3 to grow but
          // no larger than the clamped original length.  Make the length
          // odd if it's large enough, this helps distribute the entries.
          // Guard against the length ending up zero, that's not valid.
          int length = (int)((elements + elements / 20) / loadFactor) + 3;
          if (length > elements && (length & 1) == 0)
              length--;
          length = Math.min(length, origlength);
          table = new HashtableEntry<?,?>[length];
          threshold = (int)Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1);
          count = 0;
  
          // Read the number of elements and then all the key/value objects
          for (; elements > 0; elements--) {
              @SuppressWarnings("unchecked")
                  K key = (K)s.readObject();
              @SuppressWarnings("unchecked")
                  V value = (V)s.readObject();
              // sync is eliminated for performance
              reconstitutionPut(table, key, value);
          }
      }
  
      /**
       * The put method used by readObject. This is provided because put
       * is overridable and should not be called in readObject since the
       * subclass will not yet be initialized.
       *
       * <p>This differs from the regular put method in several ways. No
       * checking for rehashing is necessary since the number of elements
       * initially in the table is known. The modCount is not incremented and
       * there's no synchronization because we are creating a new instance.
       * Also, no return value is needed.
       */
      private void reconstitutionPut(HashtableEntry<?,?>[] tab, K key, V value)
          throws StreamCorruptedException
      {
          if (value == null) {
              throw new StreamCorruptedException();
          }
          // Makes sure the key is not already in the hashtable.
          // This should not happen in deserialized version.
          int hash = key.hashCode();
          int index = (hash & 0x7FFFFFFF) % tab.length;
          for (HashtableEntry<?,?> e = tab[index] ; e != null ; e = e.next) {
              if ((e.hash == hash) && e.key.equals(key)) {
                  throw new StreamCorruptedException();
              }
          }
          // Creates the new entry.
          @SuppressWarnings("unchecked")
              HashtableEntry<K,V> e = (HashtableEntry<K,V>)tab[index];
          tab[index] = new HashtableEntry<>(hash, key, value, e);
          count++;
      }
  
      /**
       * Hashtable bucket collision list entry
       */
      // BEGIN Android-changed: Renamed Entry -> HashtableEntry.
      // Code references to "HashTable.Entry" must mean Map.Entry
      //
      // This mirrors the corresponding rename of LinkedHashMap's
      // Entry->LinkedHashMapEntry.
      //
      // This is for source compatibility with earlier versions of Android.
      // Otherwise, it would hide Map.Entry which would break compilation
      // of code like:
      //
      // Hashtable.Entry<K, V> entry = hashtable.entrySet().iterator.next();
      //
      // To compile, that code snippet's "HashtableMap.Entry" must
      // mean java.util.Map.Entry which is the compile time type of
      // entrySet()'s elements.
      //
      private static class HashtableEntry<K,V> implements Entry<K,V> {
      // END Android-changed: Renamed Entry -> HashtableEntry.
          final int hash;
          final K key;
          V value;
          HashtableEntry<K,V> next;
  
          protected HashtableEntry(int hash, K key, V value, HashtableEntry<K,V> next) {
              this.hash = hash;
              this.key =  key;
              this.value = value;
              this.next = next;
          }
  
          @SuppressWarnings("unchecked")
          protected Object clone() {
              return new HashtableEntry<>(hash, key, value,
                                    (next==null ? null : (HashtableEntry<K,V>) next.clone()));
          }
  
          // Map.Entry Ops
  
          public K getKey() {
              return key;
          }
  
          public V getValue() {
              return value;
          }
  
          public V setValue(V value) {
              if (value == null)
                  throw new NullPointerException();
  
              V oldValue = this.value;
              this.value = value;
              return oldValue;
          }
  
          public boolean equals(Object o) {
              if (!(o instanceof Map.Entry))
                  return false;
              Entry<?,?> e = (Entry<?,?>)o;
  
              return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
                 (value==null ? e.getValue()==null : value.equals(e.getValue()));
          }
  
          public int hashCode() {
              return hash ^ Objects.hashCode(value);
          }
  
          public String toString() {
              return key.toString()+"="+value.toString();
          }
      }
  
      // Types of Enumerations/Iterations
      private static final int KEYS = 0;
      private static final int VALUES = 1;
      private static final int ENTRIES = 2;
  
      /**
       * A hashtable enumerator class.  This class implements both the
       * Enumeration and Iterator interfaces, but individual instances
       * can be created with the Iterator methods disabled.  This is necessary
       * to avoid unintentionally increasing the capabilities granted a user
       * by passing an Enumeration.
       */
      private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
          HashtableEntry<?,?>[] table = Hashtable.this.table;
          int index = table.length;
          HashtableEntry<?,?> entry;
          HashtableEntry<?,?> lastReturned;
          int type;
  
          /**
           * Indicates whether this Enumerator is serving as an Iterator
           * or an Enumeration.  (true -> Iterator).
           */
          boolean iterator;
  
          /**
           * The modCount value that the iterator believes that the backing
           * Hashtable should have.  If this expectation is violated, the iterator
           * has detected concurrent modification.
           */
          protected int expectedModCount = modCount;
  
          Enumerator(int type, boolean iterator) {
              this.type = type;
              this.iterator = iterator;
          }
  
          public boolean hasMoreElements() {
              HashtableEntry<?,?> e = entry;
              int i = index;
              HashtableEntry<?,?>[] t = table;
              /* Use locals for faster loop iteration */
              while (e == null && i > 0) {
                  e = t[--i];
              }
              entry = e;
              index = i;
              return e != null;
          }
  
          @SuppressWarnings("unchecked")
          public T nextElement() {
              HashtableEntry<?,?> et = entry;
              int i = index;
              HashtableEntry<?,?>[] t = table;
              /* Use locals for faster loop iteration */
              while (et == null && i > 0) {
                  et = t[--i];
              }
              entry = et;
              index = i;
              if (et != null) {
                  HashtableEntry<?,?> e = lastReturned = entry;
                  entry = e.next;
                  return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
              }
              throw new NoSuchElementException("Hashtable Enumerator");
          }
  
          // Iterator methods
          public boolean hasNext() {
              return hasMoreElements();
          }
  
          public T next() {
              if (modCount != expectedModCount)
                  throw new ConcurrentModificationException();
              return nextElement();
          }
  
          public void remove() {
              if (!iterator)
                  throw new UnsupportedOperationException();
              if (lastReturned == null)
                  throw new IllegalStateException("Hashtable Enumerator");
              if (modCount != expectedModCount)
                  throw new ConcurrentModificationException();
  
              synchronized(Hashtable.this) {
                  HashtableEntry<?,?>[] tab = Hashtable.this.table;
                  int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;
  
                  @SuppressWarnings("unchecked")
                  HashtableEntry<K,V> e = (HashtableEntry<K,V>)tab[index];
                  for(HashtableEntry<K,V> prev = null; e != null; prev = e, e = e.next) {
                      if (e == lastReturned) {
                          modCount++;
                          expectedModCount++;
                          if (prev == null)
                              tab[index] = e.next;
                          else
                              prev.next = e.next;
                          count--;
                          lastReturned = null;
                          return;
                      }
                  }
                  throw new ConcurrentModificationException();
              }
          }
      }
  }
  