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

Save This Page
Home » openjdk-7 » java » util » [javadoc | source]