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

    1   /*
    2    * Copyright (c) 2000, 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 the <tt>Map</tt> interface with a hash table, using
   31    * reference-equality in place of object-equality when comparing keys (and
   32    * values).  In other words, in an <tt>IdentityHashMap</tt>, two keys
   33    * <tt>k1</tt> and <tt>k2</tt> are considered equal if and only if
   34    * <tt>(k1==k2)</tt>.  (In normal <tt>Map</tt> implementations (like
   35    * <tt>HashMap</tt>) two keys <tt>k1</tt> and <tt>k2</tt> are considered equal
   36    * if and only if <tt>(k1==null ? k2==null : k1.equals(k2))</tt>.)
   37    *
   38    * <p><b>This class is <i>not</i> a general-purpose <tt>Map</tt>
   39    * implementation!  While this class implements the <tt>Map</tt> interface, it
   40    * intentionally violates <tt>Map's</tt> general contract, which mandates the
   41    * use of the <tt>equals</tt> method when comparing objects.  This class is
   42    * designed for use only in the rare cases wherein reference-equality
   43    * semantics are required.</b>
   44    *
   45    * <p>A typical use of this class is <i>topology-preserving object graph
   46    * transformations</i>, such as serialization or deep-copying.  To perform such
   47    * a transformation, a program must maintain a "node table" that keeps track
   48    * of all the object references that have already been processed.  The node
   49    * table must not equate distinct objects even if they happen to be equal.
   50    * Another typical use of this class is to maintain <i>proxy objects</i>.  For
   51    * example, a debugging facility might wish to maintain a proxy object for
   52    * each object in the program being debugged.
   53    *
   54    * <p>This class provides all of the optional map operations, and permits
   55    * <tt>null</tt> values and the <tt>null</tt> key.  This class makes no
   56    * guarantees as to the order of the map; in particular, it does not guarantee
   57    * that the order will remain constant over time.
   58    *
   59    * <p>This class provides constant-time performance for the basic
   60    * operations (<tt>get</tt> and <tt>put</tt>), assuming the system
   61    * identity hash function ({@link System#identityHashCode(Object)})
   62    * disperses elements properly among the buckets.
   63    *
   64    * <p>This class has one tuning parameter (which affects performance but not
   65    * semantics): <i>expected maximum size</i>.  This parameter is the maximum
   66    * number of key-value mappings that the map is expected to hold.  Internally,
   67    * this parameter is used to determine the number of buckets initially
   68    * comprising the hash table.  The precise relationship between the expected
   69    * maximum size and the number of buckets is unspecified.
   70    *
   71    * <p>If the size of the map (the number of key-value mappings) sufficiently
   72    * exceeds the expected maximum size, the number of buckets is increased
   73    * Increasing the number of buckets ("rehashing") may be fairly expensive, so
   74    * it pays to create identity hash maps with a sufficiently large expected
   75    * maximum size.  On the other hand, iteration over collection views requires
   76    * time proportional to the number of buckets in the hash table, so it
   77    * pays not to set the expected maximum size too high if you are especially
   78    * concerned with iteration performance or memory usage.
   79    *
   80    * <p><strong>Note that this implementation is not synchronized.</strong>
   81    * If multiple threads access an identity hash map concurrently, and at
   82    * least one of the threads modifies the map structurally, it <i>must</i>
   83    * be synchronized externally.  (A structural modification is any operation
   84    * that adds or deletes one or more mappings; merely changing the value
   85    * associated with a key that an instance already contains is not a
   86    * structural modification.)  This is typically accomplished by
   87    * synchronizing on some object that naturally encapsulates the map.
   88    *
   89    * If no such object exists, the map should be "wrapped" using the
   90    * {@link Collections#synchronizedMap Collections.synchronizedMap}
   91    * method.  This is best done at creation time, to prevent accidental
   92    * unsynchronized access to the map:<pre>
   93    *   Map m = Collections.synchronizedMap(new IdentityHashMap(...));</pre>
   94    *
   95    * <p>The iterators returned by the <tt>iterator</tt> method of the
   96    * collections returned by all of this class's "collection view
   97    * methods" are <i>fail-fast</i>: if the map is structurally modified
   98    * at any time after the iterator is created, in any way except
   99    * through the iterator's own <tt>remove</tt> method, the iterator
  100    * will throw a {@link ConcurrentModificationException}.  Thus, in the
  101    * face of concurrent modification, the iterator fails quickly and
  102    * cleanly, rather than risking arbitrary, non-deterministic behavior
  103    * at an undetermined time in the future.
  104    *
  105    * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
  106    * as it is, generally speaking, impossible to make any hard guarantees in the
  107    * presence of unsynchronized concurrent modification.  Fail-fast iterators
  108    * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
  109    * Therefore, it would be wrong to write a program that depended on this
  110    * exception for its correctness: <i>fail-fast iterators should be used only
  111    * to detect bugs.</i>
  112    *
  113    * <p>Implementation note: This is a simple <i>linear-probe</i> hash table,
  114    * as described for example in texts by Sedgewick and Knuth.  The array
  115    * alternates holding keys and values.  (This has better locality for large
  116    * tables than does using separate arrays.)  For many JRE implementations
  117    * and operation mixes, this class will yield better performance than
  118    * {@link HashMap} (which uses <i>chaining</i> rather than linear-probing).
  119    *
  120    * <p>This class is a member of the
  121    * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  122    * Java Collections Framework</a>.
  123    *
  124    * @see     System#identityHashCode(Object)
  125    * @see     Object#hashCode()
  126    * @see     Collection
  127    * @see     Map
  128    * @see     HashMap
  129    * @see     TreeMap
  130    * @author  Doug Lea and Josh Bloch
  131    * @since   1.4
  132    */
  133   
  134   public class IdentityHashMap<K,V>
  135       extends AbstractMap<K,V>
  136       implements Map<K,V>, java.io.Serializable, Cloneable
  137   {
  138       /**
  139        * The initial capacity used by the no-args constructor.
  140        * MUST be a power of two.  The value 32 corresponds to the
  141        * (specified) expected maximum size of 21, given a load factor
  142        * of 2/3.
  143        */
  144       private static final int DEFAULT_CAPACITY = 32;
  145   
  146       /**
  147        * The minimum capacity, used if a lower value is implicitly specified
  148        * by either of the constructors with arguments.  The value 4 corresponds
  149        * to an expected maximum size of 2, given a load factor of 2/3.
  150        * MUST be a power of two.
  151        */
  152       private static final int MINIMUM_CAPACITY = 4;
  153   
  154       /**
  155        * The maximum capacity, used if a higher value is implicitly specified
  156        * by either of the constructors with arguments.
  157        * MUST be a power of two <= 1<<29.
  158        */
  159       private static final int MAXIMUM_CAPACITY = 1 << 29;
  160   
  161       /**
  162        * The table, resized as necessary. Length MUST always be a power of two.
  163        */
  164       private transient Object[] table;
  165   
  166       /**
  167        * The number of key-value mappings contained in this identity hash map.
  168        *
  169        * @serial
  170        */
  171       private int size;
  172   
  173       /**
  174        * The number of modifications, to support fast-fail iterators
  175        */
  176       private transient int modCount;
  177   
  178       /**
  179        * The next size value at which to resize (capacity * load factor).
  180        */
  181       private transient int threshold;
  182   
  183       /**
  184        * Value representing null keys inside tables.
  185        */
  186       private static final Object NULL_KEY = new Object();
  187   
  188       /**
  189        * Use NULL_KEY for key if it is null.
  190        */
  191       private static Object maskNull(Object key) {
  192           return (key == null ? NULL_KEY : key);
  193       }
  194   
  195       /**
  196        * Returns internal representation of null key back to caller as null.
  197        */
  198       private static Object unmaskNull(Object key) {
  199           return (key == NULL_KEY ? null : key);
  200       }
  201   
  202       /**
  203        * Constructs a new, empty identity hash map with a default expected
  204        * maximum size (21).
  205        */
  206       public IdentityHashMap() {
  207           init(DEFAULT_CAPACITY);
  208       }
  209   
  210       /**
  211        * Constructs a new, empty map with the specified expected maximum size.
  212        * Putting more than the expected number of key-value mappings into
  213        * the map may cause the internal data structure to grow, which may be
  214        * somewhat time-consuming.
  215        *
  216        * @param expectedMaxSize the expected maximum size of the map
  217        * @throws IllegalArgumentException if <tt>expectedMaxSize</tt> is negative
  218        */
  219       public IdentityHashMap(int expectedMaxSize) {
  220           if (expectedMaxSize < 0)
  221               throw new IllegalArgumentException("expectedMaxSize is negative: "
  222                                                  + expectedMaxSize);
  223           init(capacity(expectedMaxSize));
  224       }
  225   
  226       /**
  227        * Returns the appropriate capacity for the specified expected maximum
  228        * size.  Returns the smallest power of two between MINIMUM_CAPACITY
  229        * and MAXIMUM_CAPACITY, inclusive, that is greater than
  230        * (3 * expectedMaxSize)/2, if such a number exists.  Otherwise
  231        * returns MAXIMUM_CAPACITY.  If (3 * expectedMaxSize)/2 is negative, it
  232        * is assumed that overflow has occurred, and MAXIMUM_CAPACITY is returned.
  233        */
  234       private int capacity(int expectedMaxSize) {
  235           // Compute min capacity for expectedMaxSize given a load factor of 2/3
  236           int minCapacity = (3 * expectedMaxSize)/2;
  237   
  238           // Compute the appropriate capacity
  239           int result;
  240           if (minCapacity > MAXIMUM_CAPACITY || minCapacity < 0) {
  241               result = MAXIMUM_CAPACITY;
  242           } else {
  243               result = MINIMUM_CAPACITY;
  244               while (result < minCapacity)
  245                   result <<= 1;
  246           }
  247           return result;
  248       }
  249   
  250       /**
  251        * Initializes object to be an empty map with the specified initial
  252        * capacity, which is assumed to be a power of two between
  253        * MINIMUM_CAPACITY and MAXIMUM_CAPACITY inclusive.
  254        */
  255       private void init(int initCapacity) {
  256           // assert (initCapacity & -initCapacity) == initCapacity; // power of 2
  257           // assert initCapacity >= MINIMUM_CAPACITY;
  258           // assert initCapacity <= MAXIMUM_CAPACITY;
  259   
  260           threshold = (initCapacity * 2)/3;
  261           table = new Object[2 * initCapacity];
  262       }
  263   
  264       /**
  265        * Constructs a new identity hash map containing the keys-value mappings
  266        * in the specified map.
  267        *
  268        * @param m the map whose mappings are to be placed into this map
  269        * @throws NullPointerException if the specified map is null
  270        */
  271       public IdentityHashMap(Map<? extends K, ? extends V> m) {
  272           // Allow for a bit of growth
  273           this((int) ((1 + m.size()) * 1.1));
  274           putAll(m);
  275       }
  276   
  277       /**
  278        * Returns the number of key-value mappings in this identity hash map.
  279        *
  280        * @return the number of key-value mappings in this map
  281        */
  282       public int size() {
  283           return size;
  284       }
  285   
  286       /**
  287        * Returns <tt>true</tt> if this identity hash map contains no key-value
  288        * mappings.
  289        *
  290        * @return <tt>true</tt> if this identity hash map contains no key-value
  291        *         mappings
  292        */
  293       public boolean isEmpty() {
  294           return size == 0;
  295       }
  296   
  297       /**
  298        * Returns index for Object x.
  299        */
  300       private static int hash(Object x, int length) {
  301           int h = System.identityHashCode(x);
  302           // Multiply by -127, and left-shift to use least bit as part of hash
  303           return ((h << 1) - (h << 8)) & (length - 1);
  304       }
  305   
  306       /**
  307        * Circularly traverses table of size len.
  308        */
  309       private static int nextKeyIndex(int i, int len) {
  310           return (i + 2 < len ? i + 2 : 0);
  311       }
  312   
  313       /**
  314        * Returns the value to which the specified key is mapped,
  315        * or {@code null} if this map contains no mapping for the key.
  316        *
  317        * <p>More formally, if this map contains a mapping from a key
  318        * {@code k} to a value {@code v} such that {@code (key == k)},
  319        * then this method returns {@code v}; otherwise it returns
  320        * {@code null}.  (There can be at most one such mapping.)
  321        *
  322        * <p>A return value of {@code null} does not <i>necessarily</i>
  323        * indicate that the map contains no mapping for the key; it's also
  324        * possible that the map explicitly maps the key to {@code null}.
  325        * The {@link #containsKey containsKey} operation may be used to
  326        * distinguish these two cases.
  327        *
  328        * @see #put(Object, Object)
  329        */
  330       public V get(Object key) {
  331           Object k = maskNull(key);
  332           Object[] tab = table;
  333           int len = tab.length;
  334           int i = hash(k, len);
  335           while (true) {
  336               Object item = tab[i];
  337               if (item == k)
  338                   return (V) tab[i + 1];
  339               if (item == null)
  340                   return null;
  341               i = nextKeyIndex(i, len);
  342           }
  343       }
  344   
  345       /**
  346        * Tests whether the specified object reference is a key in this identity
  347        * hash map.
  348        *
  349        * @param   key   possible key
  350        * @return  <code>true</code> if the specified object reference is a key
  351        *          in this map
  352        * @see     #containsValue(Object)
  353        */
  354       public boolean containsKey(Object key) {
  355           Object k = maskNull(key);
  356           Object[] tab = table;
  357           int len = tab.length;
  358           int i = hash(k, len);
  359           while (true) {
  360               Object item = tab[i];
  361               if (item == k)
  362                   return true;
  363               if (item == null)
  364                   return false;
  365               i = nextKeyIndex(i, len);
  366           }
  367       }
  368   
  369       /**
  370        * Tests whether the specified object reference is a value in this identity
  371        * hash map.
  372        *
  373        * @param value value whose presence in this map is to be tested
  374        * @return <tt>true</tt> if this map maps one or more keys to the
  375        *         specified object reference
  376        * @see     #containsKey(Object)
  377        */
  378       public boolean containsValue(Object value) {
  379           Object[] tab = table;
  380           for (int i = 1; i < tab.length; i += 2)
  381               if (tab[i] == value && tab[i - 1] != null)
  382                   return true;
  383   
  384           return false;
  385       }
  386   
  387       /**
  388        * Tests if the specified key-value mapping is in the map.
  389        *
  390        * @param   key   possible key
  391        * @param   value possible value
  392        * @return  <code>true</code> if and only if the specified key-value
  393        *          mapping is in the map
  394        */
  395       private boolean containsMapping(Object key, Object value) {
  396           Object k = maskNull(key);
  397           Object[] tab = table;
  398           int len = tab.length;
  399           int i = hash(k, len);
  400           while (true) {
  401               Object item = tab[i];
  402               if (item == k)
  403                   return tab[i + 1] == value;
  404               if (item == null)
  405                   return false;
  406               i = nextKeyIndex(i, len);
  407           }
  408       }
  409   
  410       /**
  411        * Associates the specified value with the specified key in this identity
  412        * hash map.  If the map previously contained a mapping for the key, the
  413        * old value is replaced.
  414        *
  415        * @param key the key with which the specified value is to be associated
  416        * @param value the value to be associated with the specified key
  417        * @return the previous value associated with <tt>key</tt>, or
  418        *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
  419        *         (A <tt>null</tt> return can also indicate that the map
  420        *         previously associated <tt>null</tt> with <tt>key</tt>.)
  421        * @see     Object#equals(Object)
  422        * @see     #get(Object)
  423        * @see     #containsKey(Object)
  424        */
  425       public V put(K key, V value) {
  426           Object k = maskNull(key);
  427           Object[] tab = table;
  428           int len = tab.length;
  429           int i = hash(k, len);
  430   
  431           Object item;
  432           while ( (item = tab[i]) != null) {
  433               if (item == k) {
  434                   V oldValue = (V) tab[i + 1];
  435                   tab[i + 1] = value;
  436                   return oldValue;
  437               }
  438               i = nextKeyIndex(i, len);
  439           }
  440   
  441           modCount++;
  442           tab[i] = k;
  443           tab[i + 1] = value;
  444           if (++size >= threshold)
  445               resize(len); // len == 2 * current capacity.
  446           return null;
  447       }
  448   
  449       /**
  450        * Resize the table to hold given capacity.
  451        *
  452        * @param newCapacity the new capacity, must be a power of two.
  453        */
  454       private void resize(int newCapacity) {
  455           // assert (newCapacity & -newCapacity) == newCapacity; // power of 2
  456           int newLength = newCapacity * 2;
  457   
  458           Object[] oldTable = table;
  459           int oldLength = oldTable.length;
  460           if (oldLength == 2*MAXIMUM_CAPACITY) { // can't expand any further
  461               if (threshold == MAXIMUM_CAPACITY-1)
  462                   throw new IllegalStateException("Capacity exhausted.");
  463               threshold = MAXIMUM_CAPACITY-1;  // Gigantic map!
  464               return;
  465           }
  466           if (oldLength >= newLength)
  467               return;
  468   
  469           Object[] newTable = new Object[newLength];
  470           threshold = newLength / 3;
  471   
  472           for (int j = 0; j < oldLength; j += 2) {
  473               Object key = oldTable[j];
  474               if (key != null) {
  475                   Object value = oldTable[j+1];
  476                   oldTable[j] = null;
  477                   oldTable[j+1] = null;
  478                   int i = hash(key, newLength);
  479                   while (newTable[i] != null)
  480                       i = nextKeyIndex(i, newLength);
  481                   newTable[i] = key;
  482                   newTable[i + 1] = value;
  483               }
  484           }
  485           table = newTable;
  486       }
  487   
  488       /**
  489        * Copies all of the mappings from the specified map to this map.
  490        * These mappings will replace any mappings that this map had for
  491        * any of the keys currently in the specified map.
  492        *
  493        * @param m mappings to be stored in this map
  494        * @throws NullPointerException if the specified map is null
  495        */
  496       public void putAll(Map<? extends K, ? extends V> m) {
  497           int n = m.size();
  498           if (n == 0)
  499               return;
  500           if (n > threshold) // conservatively pre-expand
  501               resize(capacity(n));
  502   
  503           for (Entry<? extends K, ? extends V> e : m.entrySet())
  504               put(e.getKey(), e.getValue());
  505       }
  506   
  507       /**
  508        * Removes the mapping for this key from this map if present.
  509        *
  510        * @param key key whose mapping is to be removed from the map
  511        * @return the previous value associated with <tt>key</tt>, or
  512        *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
  513        *         (A <tt>null</tt> return can also indicate that the map
  514        *         previously associated <tt>null</tt> with <tt>key</tt>.)
  515        */
  516       public V remove(Object key) {
  517           Object k = maskNull(key);
  518           Object[] tab = table;
  519           int len = tab.length;
  520           int i = hash(k, len);
  521   
  522           while (true) {
  523               Object item = tab[i];
  524               if (item == k) {
  525                   modCount++;
  526                   size--;
  527                   V oldValue = (V) tab[i + 1];
  528                   tab[i + 1] = null;
  529                   tab[i] = null;
  530                   closeDeletion(i);
  531                   return oldValue;
  532               }
  533               if (item == null)
  534                   return null;
  535               i = nextKeyIndex(i, len);
  536           }
  537   
  538       }
  539   
  540       /**
  541        * Removes the specified key-value mapping from the map if it is present.
  542        *
  543        * @param   key   possible key
  544        * @param   value possible value
  545        * @return  <code>true</code> if and only if the specified key-value
  546        *          mapping was in the map
  547        */
  548       private boolean removeMapping(Object key, Object value) {
  549           Object k = maskNull(key);
  550           Object[] tab = table;
  551           int len = tab.length;
  552           int i = hash(k, len);
  553   
  554           while (true) {
  555               Object item = tab[i];
  556               if (item == k) {
  557                   if (tab[i + 1] != value)
  558                       return false;
  559                   modCount++;
  560                   size--;
  561                   tab[i] = null;
  562                   tab[i + 1] = null;
  563                   closeDeletion(i);
  564                   return true;
  565               }
  566               if (item == null)
  567                   return false;
  568               i = nextKeyIndex(i, len);
  569           }
  570       }
  571   
  572       /**
  573        * Rehash all possibly-colliding entries following a
  574        * deletion. This preserves the linear-probe
  575        * collision properties required by get, put, etc.
  576        *
  577        * @param d the index of a newly empty deleted slot
  578        */
  579       private void closeDeletion(int d) {
  580           // Adapted from Knuth Section 6.4 Algorithm R
  581           Object[] tab = table;
  582           int len = tab.length;
  583   
  584           // Look for items to swap into newly vacated slot
  585           // starting at index immediately following deletion,
  586           // and continuing until a null slot is seen, indicating
  587           // the end of a run of possibly-colliding keys.
  588           Object item;
  589           for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;
  590                i = nextKeyIndex(i, len) ) {
  591               // The following test triggers if the item at slot i (which
  592               // hashes to be at slot r) should take the spot vacated by d.
  593               // If so, we swap it in, and then continue with d now at the
  594               // newly vacated i.  This process will terminate when we hit
  595               // the null slot at the end of this run.
  596               // The test is messy because we are using a circular table.
  597               int r = hash(item, len);
  598               if ((i < r && (r <= d || d <= i)) || (r <= d && d <= i)) {
  599                   tab[d] = item;
  600                   tab[d + 1] = tab[i + 1];
  601                   tab[i] = null;
  602                   tab[i + 1] = null;
  603                   d = i;
  604               }
  605           }
  606       }
  607   
  608       /**
  609        * Removes all of the mappings from this map.
  610        * The map will be empty after this call returns.
  611        */
  612       public void clear() {
  613           modCount++;
  614           Object[] tab = table;
  615           for (int i = 0; i < tab.length; i++)
  616               tab[i] = null;
  617           size = 0;
  618       }
  619   
  620       /**
  621        * Compares the specified object with this map for equality.  Returns
  622        * <tt>true</tt> if the given object is also a map and the two maps
  623        * represent identical object-reference mappings.  More formally, this
  624        * map is equal to another map <tt>m</tt> if and only if
  625        * <tt>this.entrySet().equals(m.entrySet())</tt>.
  626        *
  627        * <p><b>Owing to the reference-equality-based semantics of this map it is
  628        * possible that the symmetry and transitivity requirements of the
  629        * <tt>Object.equals</tt> contract may be violated if this map is compared
  630        * to a normal map.  However, the <tt>Object.equals</tt> contract is
  631        * guaranteed to hold among <tt>IdentityHashMap</tt> instances.</b>
  632        *
  633        * @param  o object to be compared for equality with this map
  634        * @return <tt>true</tt> if the specified object is equal to this map
  635        * @see Object#equals(Object)
  636        */
  637       public boolean equals(Object o) {
  638           if (o == this) {
  639               return true;
  640           } else if (o instanceof IdentityHashMap) {
  641               IdentityHashMap m = (IdentityHashMap) o;
  642               if (m.size() != size)
  643                   return false;
  644   
  645               Object[] tab = m.table;
  646               for (int i = 0; i < tab.length; i+=2) {
  647                   Object k = tab[i];
  648                   if (k != null && !containsMapping(k, tab[i + 1]))
  649                       return false;
  650               }
  651               return true;
  652           } else if (o instanceof Map) {
  653               Map m = (Map)o;
  654               return entrySet().equals(m.entrySet());
  655           } else {
  656               return false;  // o is not a Map
  657           }
  658       }
  659   
  660       /**
  661        * Returns the hash code value for this map.  The hash code of a map is
  662        * defined to be the sum of the hash codes of each entry in the map's
  663        * <tt>entrySet()</tt> view.  This ensures that <tt>m1.equals(m2)</tt>
  664        * implies that <tt>m1.hashCode()==m2.hashCode()</tt> for any two
  665        * <tt>IdentityHashMap</tt> instances <tt>m1</tt> and <tt>m2</tt>, as
  666        * required by the general contract of {@link Object#hashCode}.
  667        *
  668        * <p><b>Owing to the reference-equality-based semantics of the
  669        * <tt>Map.Entry</tt> instances in the set returned by this map's
  670        * <tt>entrySet</tt> method, it is possible that the contractual
  671        * requirement of <tt>Object.hashCode</tt> mentioned in the previous
  672        * paragraph will be violated if one of the two objects being compared is
  673        * an <tt>IdentityHashMap</tt> instance and the other is a normal map.</b>
  674        *
  675        * @return the hash code value for this map
  676        * @see Object#equals(Object)
  677        * @see #equals(Object)
  678        */
  679       public int hashCode() {
  680           int result = 0;
  681           Object[] tab = table;
  682           for (int i = 0; i < tab.length; i +=2) {
  683               Object key = tab[i];
  684               if (key != null) {
  685                   Object k = unmaskNull(key);
  686                   result += System.identityHashCode(k) ^
  687                             System.identityHashCode(tab[i + 1]);
  688               }
  689           }
  690           return result;
  691       }
  692   
  693       /**
  694        * Returns a shallow copy of this identity hash map: the keys and values
  695        * themselves are not cloned.
  696        *
  697        * @return a shallow copy of this map
  698        */
  699       public Object clone() {
  700           try {
  701               IdentityHashMap<K,V> m = (IdentityHashMap<K,V>) super.clone();
  702               m.entrySet = null;
  703               m.table = table.clone();
  704               return m;
  705           } catch (CloneNotSupportedException e) {
  706               throw new InternalError();
  707           }
  708       }
  709   
  710       private abstract class IdentityHashMapIterator<T> implements Iterator<T> {
  711           int index = (size != 0 ? 0 : table.length); // current slot.
  712           int expectedModCount = modCount; // to support fast-fail
  713           int lastReturnedIndex = -1;      // to allow remove()
  714           boolean indexValid; // To avoid unnecessary next computation
  715           Object[] traversalTable = table; // reference to main table or copy
  716   
  717           public boolean hasNext() {
  718               Object[] tab = traversalTable;
  719               for (int i = index; i < tab.length; i+=2) {
  720                   Object key = tab[i];
  721                   if (key != null) {
  722                       index = i;
  723                       return indexValid = true;
  724                   }
  725               }
  726               index = tab.length;
  727               return false;
  728           }
  729   
  730           protected int nextIndex() {
  731               if (modCount != expectedModCount)
  732                   throw new ConcurrentModificationException();
  733               if (!indexValid && !hasNext())
  734                   throw new NoSuchElementException();
  735   
  736               indexValid = false;
  737               lastReturnedIndex = index;
  738               index += 2;
  739               return lastReturnedIndex;
  740           }
  741   
  742           public void remove() {
  743               if (lastReturnedIndex == -1)
  744                   throw new IllegalStateException();
  745               if (modCount != expectedModCount)
  746                   throw new ConcurrentModificationException();
  747   
  748               expectedModCount = ++modCount;
  749               int deletedSlot = lastReturnedIndex;
  750               lastReturnedIndex = -1;
  751               // back up index to revisit new contents after deletion
  752               index = deletedSlot;
  753               indexValid = false;
  754   
  755               // Removal code proceeds as in closeDeletion except that
  756               // it must catch the rare case where an element already
  757               // seen is swapped into a vacant slot that will be later
  758               // traversed by this iterator. We cannot allow future
  759               // next() calls to return it again.  The likelihood of
  760               // this occurring under 2/3 load factor is very slim, but
  761               // when it does happen, we must make a copy of the rest of
  762               // the table to use for the rest of the traversal. Since
  763               // this can only happen when we are near the end of the table,
  764               // even in these rare cases, this is not very expensive in
  765               // time or space.
  766   
  767               Object[] tab = traversalTable;
  768               int len = tab.length;
  769   
  770               int d = deletedSlot;
  771               K key = (K) tab[d];
  772               tab[d] = null;        // vacate the slot
  773               tab[d + 1] = null;
  774   
  775               // If traversing a copy, remove in real table.
  776               // We can skip gap-closure on copy.
  777               if (tab != IdentityHashMap.this.table) {
  778                   IdentityHashMap.this.remove(key);
  779                   expectedModCount = modCount;
  780                   return;
  781               }
  782   
  783               size--;
  784   
  785               Object item;
  786               for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;
  787                    i = nextKeyIndex(i, len)) {
  788                   int r = hash(item, len);
  789                   // See closeDeletion for explanation of this conditional
  790                   if ((i < r && (r <= d || d <= i)) ||
  791                       (r <= d && d <= i)) {
  792   
  793                       // If we are about to swap an already-seen element
  794                       // into a slot that may later be returned by next(),
  795                       // then clone the rest of table for use in future
  796                       // next() calls. It is OK that our copy will have
  797                       // a gap in the "wrong" place, since it will never
  798                       // be used for searching anyway.
  799   
  800                       if (i < deletedSlot && d >= deletedSlot &&
  801                           traversalTable == IdentityHashMap.this.table) {
  802                           int remaining = len - deletedSlot;
  803                           Object[] newTable = new Object[remaining];
  804                           System.arraycopy(tab, deletedSlot,
  805                                            newTable, 0, remaining);
  806                           traversalTable = newTable;
  807                           index = 0;
  808                       }
  809   
  810                       tab[d] = item;
  811                       tab[d + 1] = tab[i + 1];
  812                       tab[i] = null;
  813                       tab[i + 1] = null;
  814                       d = i;
  815                   }
  816               }
  817           }
  818       }
  819   
  820       private class KeyIterator extends IdentityHashMapIterator<K> {
  821           public K next() {
  822               return (K) unmaskNull(traversalTable[nextIndex()]);
  823           }
  824       }
  825   
  826       private class ValueIterator extends IdentityHashMapIterator<V> {
  827           public V next() {
  828               return (V) traversalTable[nextIndex() + 1];
  829           }
  830       }
  831   
  832       private class EntryIterator
  833           extends IdentityHashMapIterator<Map.Entry<K,V>>
  834       {
  835           private Entry lastReturnedEntry = null;
  836   
  837           public Map.Entry<K,V> next() {
  838               lastReturnedEntry = new Entry(nextIndex());
  839               return lastReturnedEntry;
  840           }
  841   
  842           public void remove() {
  843               lastReturnedIndex =
  844                   ((null == lastReturnedEntry) ? -1 : lastReturnedEntry.index);
  845               super.remove();
  846               lastReturnedEntry.index = lastReturnedIndex;
  847               lastReturnedEntry = null;
  848           }
  849   
  850           private class Entry implements Map.Entry<K,V> {
  851               private int index;
  852   
  853               private Entry(int index) {
  854                   this.index = index;
  855               }
  856   
  857               public K getKey() {
  858                   checkIndexForEntryUse();
  859                   return (K) unmaskNull(traversalTable[index]);
  860               }
  861   
  862               public V getValue() {
  863                   checkIndexForEntryUse();
  864                   return (V) traversalTable[index+1];
  865               }
  866   
  867               public V setValue(V value) {
  868                   checkIndexForEntryUse();
  869                   V oldValue = (V) traversalTable[index+1];
  870                   traversalTable[index+1] = value;
  871                   // if shadowing, force into main table
  872                   if (traversalTable != IdentityHashMap.this.table)
  873                       put((K) traversalTable[index], value);
  874                   return oldValue;
  875               }
  876   
  877               public boolean equals(Object o) {
  878                   if (index < 0)
  879                       return super.equals(o);
  880   
  881                   if (!(o instanceof Map.Entry))
  882                       return false;
  883                   Map.Entry e = (Map.Entry)o;
  884                   return (e.getKey() == unmaskNull(traversalTable[index]) &&
  885                          e.getValue() == traversalTable[index+1]);
  886               }
  887   
  888               public int hashCode() {
  889                   if (lastReturnedIndex < 0)
  890                       return super.hashCode();
  891   
  892                   return (System.identityHashCode(unmaskNull(traversalTable[index])) ^
  893                          System.identityHashCode(traversalTable[index+1]));
  894               }
  895   
  896               public String toString() {
  897                   if (index < 0)
  898                       return super.toString();
  899   
  900                   return (unmaskNull(traversalTable[index]) + "="
  901                           + traversalTable[index+1]);
  902               }
  903   
  904               private void checkIndexForEntryUse() {
  905                   if (index < 0)
  906                       throw new IllegalStateException("Entry was removed");
  907               }
  908           }
  909       }
  910   
  911       // Views
  912   
  913       /**
  914        * This field is initialized to contain an instance of the entry set
  915        * view the first time this view is requested.  The view is stateless,
  916        * so there's no reason to create more than one.
  917        */
  918       private transient Set<Map.Entry<K,V>> entrySet = null;
  919   
  920       /**
  921        * Returns an identity-based set view of the keys contained in this map.
  922        * The set is backed by the map, so changes to the map are reflected in
  923        * the set, and vice-versa.  If the map is modified while an iteration
  924        * over the set is in progress, the results of the iteration are
  925        * undefined.  The set supports element removal, which removes the
  926        * corresponding mapping from the map, via the <tt>Iterator.remove</tt>,
  927        * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
  928        * <tt>clear</tt> methods.  It does not support the <tt>add</tt> or
  929        * <tt>addAll</tt> methods.
  930        *
  931        * <p><b>While the object returned by this method implements the
  932        * <tt>Set</tt> interface, it does <i>not</i> obey <tt>Set's</tt> general
  933        * contract.  Like its backing map, the set returned by this method
  934        * defines element equality as reference-equality rather than
  935        * object-equality.  This affects the behavior of its <tt>contains</tt>,
  936        * <tt>remove</tt>, <tt>containsAll</tt>, <tt>equals</tt>, and
  937        * <tt>hashCode</tt> methods.</b>
  938        *
  939        * <p><b>The <tt>equals</tt> method of the returned set returns <tt>true</tt>
  940        * only if the specified object is a set containing exactly the same
  941        * object references as the returned set.  The symmetry and transitivity
  942        * requirements of the <tt>Object.equals</tt> contract may be violated if
  943        * the set returned by this method is compared to a normal set.  However,
  944        * the <tt>Object.equals</tt> contract is guaranteed to hold among sets
  945        * returned by this method.</b>
  946        *
  947        * <p>The <tt>hashCode</tt> method of the returned set returns the sum of
  948        * the <i>identity hashcodes</i> of the elements in the set, rather than
  949        * the sum of their hashcodes.  This is mandated by the change in the
  950        * semantics of the <tt>equals</tt> method, in order to enforce the
  951        * general contract of the <tt>Object.hashCode</tt> method among sets
  952        * returned by this method.
  953        *
  954        * @return an identity-based set view of the keys contained in this map
  955        * @see Object#equals(Object)
  956        * @see System#identityHashCode(Object)
  957        */
  958       public Set<K> keySet() {
  959           Set<K> ks = keySet;
  960           if (ks != null)
  961               return ks;
  962           else
  963               return keySet = new KeySet();
  964       }
  965   
  966       private class KeySet extends AbstractSet<K> {
  967           public Iterator<K> iterator() {
  968               return new KeyIterator();
  969           }
  970           public int size() {
  971               return size;
  972           }
  973           public boolean contains(Object o) {
  974               return containsKey(o);
  975           }
  976           public boolean remove(Object o) {
  977               int oldSize = size;
  978               IdentityHashMap.this.remove(o);
  979               return size != oldSize;
  980           }
  981           /*
  982            * Must revert from AbstractSet's impl to AbstractCollection's, as
  983            * the former contains an optimization that results in incorrect
  984            * behavior when c is a smaller "normal" (non-identity-based) Set.
  985            */
  986           public boolean removeAll(Collection<?> c) {
  987               boolean modified = false;
  988               for (Iterator<K> i = iterator(); i.hasNext(); ) {
  989                   if (c.contains(i.next())) {
  990                       i.remove();
  991                       modified = true;
  992                   }
  993               }
  994               return modified;
  995           }
  996           public void clear() {
  997               IdentityHashMap.this.clear();
  998           }
  999           public int hashCode() {
 1000               int result = 0;
 1001               for (K key : this)
 1002                   result += System.identityHashCode(key);
 1003               return result;
 1004           }
 1005       }
 1006   
 1007       /**
 1008        * Returns a {@link Collection} view of the values contained in this map.
 1009        * The collection is backed by the map, so changes to the map are
 1010        * reflected in the collection, and vice-versa.  If the map is
 1011        * modified while an iteration over the collection is in progress,
 1012        * the results of the iteration are undefined.  The collection
 1013        * supports element removal, which removes the corresponding
 1014        * mapping from the map, via the <tt>Iterator.remove</tt>,
 1015        * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
 1016        * <tt>retainAll</tt> and <tt>clear</tt> methods.  It does not
 1017        * support the <tt>add</tt> or <tt>addAll</tt> methods.
 1018        *
 1019        * <p><b>While the object returned by this method implements the
 1020        * <tt>Collection</tt> interface, it does <i>not</i> obey
 1021        * <tt>Collection's</tt> general contract.  Like its backing map,
 1022        * the collection returned by this method defines element equality as
 1023        * reference-equality rather than object-equality.  This affects the
 1024        * behavior of its <tt>contains</tt>, <tt>remove</tt> and
 1025        * <tt>containsAll</tt> methods.</b>
 1026        */
 1027       public Collection<V> values() {
 1028           Collection<V> vs = values;
 1029           if (vs != null)
 1030               return vs;
 1031           else
 1032               return values = new Values();
 1033       }
 1034   
 1035       private class Values extends AbstractCollection<V> {
 1036           public Iterator<V> iterator() {
 1037               return new ValueIterator();
 1038           }
 1039           public int size() {
 1040               return size;
 1041           }
 1042           public boolean contains(Object o) {
 1043               return containsValue(o);
 1044           }
 1045           public boolean remove(Object o) {
 1046               for (Iterator<V> i = iterator(); i.hasNext(); ) {
 1047                   if (i.next() == o) {
 1048                       i.remove();
 1049                       return true;
 1050                   }
 1051               }
 1052               return false;
 1053           }
 1054           public void clear() {
 1055               IdentityHashMap.this.clear();
 1056           }
 1057       }
 1058   
 1059       /**
 1060        * Returns a {@link Set} view of the mappings contained in this map.
 1061        * Each element in the returned set is a reference-equality-based
 1062        * <tt>Map.Entry</tt>.  The set is backed by the map, so changes
 1063        * to the map are reflected in the set, and vice-versa.  If the
 1064        * map is modified while an iteration over the set is in progress,
 1065        * the results of the iteration are undefined.  The set supports
 1066        * element removal, which removes the corresponding mapping from
 1067        * the map, via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
 1068        * <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt>
 1069        * methods.  It does not support the <tt>add</tt> or
 1070        * <tt>addAll</tt> methods.
 1071        *
 1072        * <p>Like the backing map, the <tt>Map.Entry</tt> objects in the set
 1073        * returned by this method define key and value equality as
 1074        * reference-equality rather than object-equality.  This affects the
 1075        * behavior of the <tt>equals</tt> and <tt>hashCode</tt> methods of these
 1076        * <tt>Map.Entry</tt> objects.  A reference-equality based <tt>Map.Entry
 1077        * e</tt> is equal to an object <tt>o</tt> if and only if <tt>o</tt> is a
 1078        * <tt>Map.Entry</tt> and <tt>e.getKey()==o.getKey() &amp;&amp;
 1079        * e.getValue()==o.getValue()</tt>.  To accommodate these equals
 1080        * semantics, the <tt>hashCode</tt> method returns
 1081        * <tt>System.identityHashCode(e.getKey()) ^
 1082        * System.identityHashCode(e.getValue())</tt>.
 1083        *
 1084        * <p><b>Owing to the reference-equality-based semantics of the
 1085        * <tt>Map.Entry</tt> instances in the set returned by this method,
 1086        * it is possible that the symmetry and transitivity requirements of
 1087        * the {@link Object#equals(Object)} contract may be violated if any of
 1088        * the entries in the set is compared to a normal map entry, or if
 1089        * the set returned by this method is compared to a set of normal map
 1090        * entries (such as would be returned by a call to this method on a normal
 1091        * map).  However, the <tt>Object.equals</tt> contract is guaranteed to
 1092        * hold among identity-based map entries, and among sets of such entries.
 1093        * </b>
 1094        *
 1095        * @return a set view of the identity-mappings contained in this map
 1096        */
 1097       public Set<Map.Entry<K,V>> entrySet() {
 1098           Set<Map.Entry<K,V>> es = entrySet;
 1099           if (es != null)
 1100               return es;
 1101           else
 1102               return entrySet = new EntrySet();
 1103       }
 1104   
 1105       private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
 1106           public Iterator<Map.Entry<K,V>> iterator() {
 1107               return new EntryIterator();
 1108           }
 1109           public boolean contains(Object o) {
 1110               if (!(o instanceof Map.Entry))
 1111                   return false;
 1112               Map.Entry entry = (Map.Entry)o;
 1113               return containsMapping(entry.getKey(), entry.getValue());
 1114           }
 1115           public boolean remove(Object o) {
 1116               if (!(o instanceof Map.Entry))
 1117                   return false;
 1118               Map.Entry entry = (Map.Entry)o;
 1119               return removeMapping(entry.getKey(), entry.getValue());
 1120           }
 1121           public int size() {
 1122               return size;
 1123           }
 1124           public void clear() {
 1125               IdentityHashMap.this.clear();
 1126           }
 1127           /*
 1128            * Must revert from AbstractSet's impl to AbstractCollection's, as
 1129            * the former contains an optimization that results in incorrect
 1130            * behavior when c is a smaller "normal" (non-identity-based) Set.
 1131            */
 1132           public boolean removeAll(Collection<?> c) {
 1133               boolean modified = false;
 1134               for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); ) {
 1135                   if (c.contains(i.next())) {
 1136                       i.remove();
 1137                       modified = true;
 1138                   }
 1139               }
 1140               return modified;
 1141           }
 1142   
 1143           public Object[] toArray() {
 1144               int size = size();
 1145               Object[] result = new Object[size];
 1146               Iterator<Map.Entry<K,V>> it = iterator();
 1147               for (int i = 0; i < size; i++)
 1148                   result[i] = new AbstractMap.SimpleEntry<>(it.next());
 1149               return result;
 1150           }
 1151   
 1152           @SuppressWarnings("unchecked")
 1153           public <T> T[] toArray(T[] a) {
 1154               int size = size();
 1155               if (a.length < size)
 1156                   a = (T[])java.lang.reflect.Array
 1157                       .newInstance(a.getClass().getComponentType(), size);
 1158               Iterator<Map.Entry<K,V>> it = iterator();
 1159               for (int i = 0; i < size; i++)
 1160                   a[i] = (T) new AbstractMap.SimpleEntry<>(it.next());
 1161               if (a.length > size)
 1162                   a[size] = null;
 1163               return a;
 1164           }
 1165       }
 1166   
 1167   
 1168       private static final long serialVersionUID = 8188218128353913216L;
 1169   
 1170       /**
 1171        * Save the state of the <tt>IdentityHashMap</tt> instance to a stream
 1172        * (i.e., serialize it).
 1173        *
 1174        * @serialData The <i>size</i> of the HashMap (the number of key-value
 1175        *          mappings) (<tt>int</tt>), followed by the key (Object) and
 1176        *          value (Object) for each key-value mapping represented by the
 1177        *          IdentityHashMap.  The key-value mappings are emitted in no
 1178        *          particular order.
 1179        */
 1180       private void writeObject(java.io.ObjectOutputStream s)
 1181           throws java.io.IOException  {
 1182           // Write out and any hidden stuff
 1183           s.defaultWriteObject();
 1184   
 1185           // Write out size (number of Mappings)
 1186           s.writeInt(size);
 1187   
 1188           // Write out keys and values (alternating)
 1189           Object[] tab = table;
 1190           for (int i = 0; i < tab.length; i += 2) {
 1191               Object key = tab[i];
 1192               if (key != null) {
 1193                   s.writeObject(unmaskNull(key));
 1194                   s.writeObject(tab[i + 1]);
 1195               }
 1196           }
 1197       }
 1198   
 1199       /**
 1200        * Reconstitute the <tt>IdentityHashMap</tt> instance from a stream (i.e.,
 1201        * deserialize it).
 1202        */
 1203       private void readObject(java.io.ObjectInputStream s)
 1204           throws java.io.IOException, ClassNotFoundException  {
 1205           // Read in any hidden stuff
 1206           s.defaultReadObject();
 1207   
 1208           // Read in size (number of Mappings)
 1209           int size = s.readInt();
 1210   
 1211           // Allow for 33% growth (i.e., capacity is >= 2* size()).
 1212           init(capacity((size*4)/3));
 1213   
 1214           // Read the keys and values, and put the mappings in the table
 1215           for (int i=0; i<size; i++) {
 1216               K key = (K) s.readObject();
 1217               V value = (V) s.readObject();
 1218               putForCreate(key, value);
 1219           }
 1220       }
 1221   
 1222       /**
 1223        * The put method for readObject.  It does not resize the table,
 1224        * update modCount, etc.
 1225        */
 1226       private void putForCreate(K key, V value)
 1227           throws IOException
 1228       {
 1229           K k = (K)maskNull(key);
 1230           Object[] tab = table;
 1231           int len = tab.length;
 1232           int i = hash(k, len);
 1233   
 1234           Object item;
 1235           while ( (item = tab[i]) != null) {
 1236               if (item == k)
 1237                   throw new java.io.StreamCorruptedException();
 1238               i = nextKeyIndex(i, len);
 1239           }
 1240           tab[i] = k;
 1241           tab[i + 1] = value;
 1242       }
 1243   }

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