0001 /*
0002 * Copyright 2000-2006 Sun Microsystems, Inc. All Rights Reserved.
0003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0004 *
0005 * This code is free software; you can redistribute it and/or modify it
0006 * under the terms of the GNU General Public License version 2 only, as
0007 * published by the Free Software Foundation. Sun designates this
0008 * particular file as subject to the "Classpath" exception as provided
0009 * by Sun in the LICENSE file that accompanied this code.
0010 *
0011 * This code is distributed in the hope that it will be useful, but WITHOUT
0012 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0013 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0014 * version 2 for more details (a copy is included in the LICENSE file that
0015 * accompanied this code).
0016 *
0017 * You should have received a copy of the GNU General Public License version
0018 * 2 along with this work; if not, write to the Free Software Foundation,
0019 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0020 *
0021 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
0022 * CA 95054 USA or visit www.sun.com if you need additional information or
0023 * have any questions.
0024 */
0025
0026 package java.util;
0027
0028 import java.io.*;
0029
0030 /**
0031 * This class implements the <tt>Map</tt> interface with a hash table, using
0032 * reference-equality in place of object-equality when comparing keys (and
0033 * values). In other words, in an <tt>IdentityHashMap</tt>, two keys
0034 * <tt>k1</tt> and <tt>k2</tt> are considered equal if and only if
0035 * <tt>(k1==k2)</tt>. (In normal <tt>Map</tt> implementations (like
0036 * <tt>HashMap</tt>) two keys <tt>k1</tt> and <tt>k2</tt> are considered equal
0037 * if and only if <tt>(k1==null ? k2==null : k1.equals(k2))</tt>.)
0038 *
0039 * <p><b>This class is <i>not</i> a general-purpose <tt>Map</tt>
0040 * implementation! While this class implements the <tt>Map</tt> interface, it
0041 * intentionally violates <tt>Map's</tt> general contract, which mandates the
0042 * use of the <tt>equals</tt> method when comparing objects. This class is
0043 * designed for use only in the rare cases wherein reference-equality
0044 * semantics are required.</b>
0045 *
0046 * <p>A typical use of this class is <i>topology-preserving object graph
0047 * transformations</i>, such as serialization or deep-copying. To perform such
0048 * a transformation, a program must maintain a "node table" that keeps track
0049 * of all the object references that have already been processed. The node
0050 * table must not equate distinct objects even if they happen to be equal.
0051 * Another typical use of this class is to maintain <i>proxy objects</i>. For
0052 * example, a debugging facility might wish to maintain a proxy object for
0053 * each object in the program being debugged.
0054 *
0055 * <p>This class provides all of the optional map operations, and permits
0056 * <tt>null</tt> values and the <tt>null</tt> key. This class makes no
0057 * guarantees as to the order of the map; in particular, it does not guarantee
0058 * that the order will remain constant over time.
0059 *
0060 * <p>This class provides constant-time performance for the basic
0061 * operations (<tt>get</tt> and <tt>put</tt>), assuming the system
0062 * identity hash function ({@link System#identityHashCode(Object)})
0063 * disperses elements properly among the buckets.
0064 *
0065 * <p>This class has one tuning parameter (which affects performance but not
0066 * semantics): <i>expected maximum size</i>. This parameter is the maximum
0067 * number of key-value mappings that the map is expected to hold. Internally,
0068 * this parameter is used to determine the number of buckets initially
0069 * comprising the hash table. The precise relationship between the expected
0070 * maximum size and the number of buckets is unspecified.
0071 *
0072 * <p>If the size of the map (the number of key-value mappings) sufficiently
0073 * exceeds the expected maximum size, the number of buckets is increased
0074 * Increasing the number of buckets ("rehashing") may be fairly expensive, so
0075 * it pays to create identity hash maps with a sufficiently large expected
0076 * maximum size. On the other hand, iteration over collection views requires
0077 * time proportional to the number of buckets in the hash table, so it
0078 * pays not to set the expected maximum size too high if you are especially
0079 * concerned with iteration performance or memory usage.
0080 *
0081 * <p><strong>Note that this implementation is not synchronized.</strong>
0082 * If multiple threads access an identity hash map concurrently, and at
0083 * least one of the threads modifies the map structurally, it <i>must</i>
0084 * be synchronized externally. (A structural modification is any operation
0085 * that adds or deletes one or more mappings; merely changing the value
0086 * associated with a key that an instance already contains is not a
0087 * structural modification.) This is typically accomplished by
0088 * synchronizing on some object that naturally encapsulates the map.
0089 *
0090 * If no such object exists, the map should be "wrapped" using the
0091 * {@link Collections#synchronizedMap Collections.synchronizedMap}
0092 * method. This is best done at creation time, to prevent accidental
0093 * unsynchronized access to the map:<pre>
0094 * Map m = Collections.synchronizedMap(new IdentityHashMap(...));</pre>
0095 *
0096 * <p>The iterators returned by the <tt>iterator</tt> method of the
0097 * collections returned by all of this class's "collection view
0098 * methods" are <i>fail-fast</i>: if the map is structurally modified
0099 * at any time after the iterator is created, in any way except
0100 * through the iterator's own <tt>remove</tt> method, the iterator
0101 * will throw a {@link ConcurrentModificationException}. Thus, in the
0102 * face of concurrent modification, the iterator fails quickly and
0103 * cleanly, rather than risking arbitrary, non-deterministic behavior
0104 * at an undetermined time in the future.
0105 *
0106 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
0107 * as it is, generally speaking, impossible to make any hard guarantees in the
0108 * presence of unsynchronized concurrent modification. Fail-fast iterators
0109 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
0110 * Therefore, it would be wrong to write a program that depended on this
0111 * exception for its correctness: <i>fail-fast iterators should be used only
0112 * to detect bugs.</i>
0113 *
0114 * <p>Implementation note: This is a simple <i>linear-probe</i> hash table,
0115 * as described for example in texts by Sedgewick and Knuth. The array
0116 * alternates holding keys and values. (This has better locality for large
0117 * tables than does using separate arrays.) For many JRE implementations
0118 * and operation mixes, this class will yield better performance than
0119 * {@link HashMap} (which uses <i>chaining</i> rather than linear-probing).
0120 *
0121 * <p>This class is a member of the
0122 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
0123 * Java Collections Framework</a>.
0124 *
0125 * @see System#identityHashCode(Object)
0126 * @see Object#hashCode()
0127 * @see Collection
0128 * @see Map
0129 * @see HashMap
0130 * @see TreeMap
0131 * @author Doug Lea and Josh Bloch
0132 * @since 1.4
0133 */
0134
0135 public class IdentityHashMap<K, V> extends AbstractMap<K, V> implements
0136 Map<K, V>, java.io.Serializable, Cloneable {
0137 /**
0138 * The initial capacity used by the no-args constructor.
0139 * MUST be a power of two. The value 32 corresponds to the
0140 * (specified) expected maximum size of 21, given a load factor
0141 * of 2/3.
0142 */
0143 private static final int DEFAULT_CAPACITY = 32;
0144
0145 /**
0146 * The minimum capacity, used if a lower value is implicitly specified
0147 * by either of the constructors with arguments. The value 4 corresponds
0148 * to an expected maximum size of 2, given a load factor of 2/3.
0149 * MUST be a power of two.
0150 */
0151 private static final int MINIMUM_CAPACITY = 4;
0152
0153 /**
0154 * The maximum capacity, used if a higher value is implicitly specified
0155 * by either of the constructors with arguments.
0156 * MUST be a power of two <= 1<<29.
0157 */
0158 private static final int MAXIMUM_CAPACITY = 1 << 29;
0159
0160 /**
0161 * The table, resized as necessary. Length MUST always be a power of two.
0162 */
0163 private transient Object[] table;
0164
0165 /**
0166 * The number of key-value mappings contained in this identity hash map.
0167 *
0168 * @serial
0169 */
0170 private int size;
0171
0172 /**
0173 * The number of modifications, to support fast-fail iterators
0174 */
0175 private transient volatile int modCount;
0176
0177 /**
0178 * The next size value at which to resize (capacity * load factor).
0179 */
0180 private transient int threshold;
0181
0182 /**
0183 * Value representing null keys inside tables.
0184 */
0185 private static final Object NULL_KEY = new Object();
0186
0187 /**
0188 * Use NULL_KEY for key if it is null.
0189 */
0190
0191 private static Object maskNull(Object key) {
0192 return (key == null ? NULL_KEY : key);
0193 }
0194
0195 /**
0196 * Returns internal representation of null key back to caller as null.
0197 */
0198 private static Object unmaskNull(Object key) {
0199 return (key == NULL_KEY ? null : key);
0200 }
0201
0202 /**
0203 * Constructs a new, empty identity hash map with a default expected
0204 * maximum size (21).
0205 */
0206 public IdentityHashMap() {
0207 init(DEFAULT_CAPACITY);
0208 }
0209
0210 /**
0211 * Constructs a new, empty map with the specified expected maximum size.
0212 * Putting more than the expected number of key-value mappings into
0213 * the map may cause the internal data structure to grow, which may be
0214 * somewhat time-consuming.
0215 *
0216 * @param expectedMaxSize the expected maximum size of the map
0217 * @throws IllegalArgumentException if <tt>expectedMaxSize</tt> is negative
0218 */
0219 public IdentityHashMap(int expectedMaxSize) {
0220 if (expectedMaxSize < 0)
0221 throw new IllegalArgumentException(
0222 "expectedMaxSize is negative: " + expectedMaxSize);
0223 init(capacity(expectedMaxSize));
0224 }
0225
0226 /**
0227 * Returns the appropriate capacity for the specified expected maximum
0228 * size. Returns the smallest power of two between MINIMUM_CAPACITY
0229 * and MAXIMUM_CAPACITY, inclusive, that is greater than
0230 * (3 * expectedMaxSize)/2, if such a number exists. Otherwise
0231 * returns MAXIMUM_CAPACITY. If (3 * expectedMaxSize)/2 is negative, it
0232 * is assumed that overflow has occurred, and MAXIMUM_CAPACITY is returned.
0233 */
0234 private int capacity(int expectedMaxSize) {
0235 // Compute min capacity for expectedMaxSize given a load factor of 2/3
0236 int minCapacity = (3 * expectedMaxSize) / 2;
0237
0238 // Compute the appropriate capacity
0239 int result;
0240 if (minCapacity > MAXIMUM_CAPACITY || minCapacity < 0) {
0241 result = MAXIMUM_CAPACITY;
0242 } else {
0243 result = MINIMUM_CAPACITY;
0244 while (result < minCapacity)
0245 result <<= 1;
0246 }
0247 return result;
0248 }
0249
0250 /**
0251 * Initializes object to be an empty map with the specified initial
0252 * capacity, which is assumed to be a power of two between
0253 * MINIMUM_CAPACITY and MAXIMUM_CAPACITY inclusive.
0254 */
0255 private void init(int initCapacity) {
0256 // assert (initCapacity & -initCapacity) == initCapacity; // power of 2
0257 // assert initCapacity >= MINIMUM_CAPACITY;
0258 // assert initCapacity <= MAXIMUM_CAPACITY;
0259
0260 threshold = (initCapacity * 2) / 3;
0261 table = new Object[2 * initCapacity];
0262 }
0263
0264 /**
0265 * Constructs a new identity hash map containing the keys-value mappings
0266 * in the specified map.
0267 *
0268 * @param m the map whose mappings are to be placed into this map
0269 * @throws NullPointerException if the specified map is null
0270 */
0271 public IdentityHashMap(Map<? extends K, ? extends V> m) {
0272 // Allow for a bit of growth
0273 this ((int) ((1 + m.size()) * 1.1));
0274 putAll(m);
0275 }
0276
0277 /**
0278 * Returns the number of key-value mappings in this identity hash map.
0279 *
0280 * @return the number of key-value mappings in this map
0281 */
0282 public int size() {
0283 return size;
0284 }
0285
0286 /**
0287 * Returns <tt>true</tt> if this identity hash map contains no key-value
0288 * mappings.
0289 *
0290 * @return <tt>true</tt> if this identity hash map contains no key-value
0291 * mappings
0292 */
0293 public boolean isEmpty() {
0294 return size == 0;
0295 }
0296
0297 /**
0298 * Returns index for Object x.
0299 */
0300 private static int hash(Object x, int length) {
0301 int h = System.identityHashCode(x);
0302 // Multiply by -127, and left-shift to use least bit as part of hash
0303 return ((h << 1) - (h << 8)) & (length - 1);
0304 }
0305
0306 /**
0307 * Circularly traverses table of size len.
0308 */
0309 private static int nextKeyIndex(int i, int len) {
0310 return (i + 2 < len ? i + 2 : 0);
0311 }
0312
0313 /**
0314 * Returns the value to which the specified key is mapped,
0315 * or {@code null} if this map contains no mapping for the key.
0316 *
0317 * <p>More formally, if this map contains a mapping from a key
0318 * {@code k} to a value {@code v} such that {@code (key == k)},
0319 * then this method returns {@code v}; otherwise it returns
0320 * {@code null}. (There can be at most one such mapping.)
0321 *
0322 * <p>A return value of {@code null} does not <i>necessarily</i>
0323 * indicate that the map contains no mapping for the key; it's also
0324 * possible that the map explicitly maps the key to {@code null}.
0325 * The {@link #containsKey containsKey} operation may be used to
0326 * distinguish these two cases.
0327 *
0328 * @see #put(Object, Object)
0329 */
0330 public V get(Object key) {
0331 Object k = maskNull(key);
0332 Object[] tab = table;
0333 int len = tab.length;
0334 int i = hash(k, len);
0335 while (true) {
0336 Object item = tab[i];
0337 if (item == k)
0338 return (V) tab[i + 1];
0339 if (item == null)
0340 return null;
0341 i = nextKeyIndex(i, len);
0342 }
0343 }
0344
0345 /**
0346 * Tests whether the specified object reference is a key in this identity
0347 * hash map.
0348 *
0349 * @param key possible key
0350 * @return <code>true</code> if the specified object reference is a key
0351 * in this map
0352 * @see #containsValue(Object)
0353 */
0354 public boolean containsKey(Object key) {
0355 Object k = maskNull(key);
0356 Object[] tab = table;
0357 int len = tab.length;
0358 int i = hash(k, len);
0359 while (true) {
0360 Object item = tab[i];
0361 if (item == k)
0362 return true;
0363 if (item == null)
0364 return false;
0365 i = nextKeyIndex(i, len);
0366 }
0367 }
0368
0369 /**
0370 * Tests whether the specified object reference is a value in this identity
0371 * hash map.
0372 *
0373 * @param value value whose presence in this map is to be tested
0374 * @return <tt>true</tt> if this map maps one or more keys to the
0375 * specified object reference
0376 * @see #containsKey(Object)
0377 */
0378 public boolean containsValue(Object value) {
0379 Object[] tab = table;
0380 for (int i = 1; i < tab.length; i += 2)
0381 if (tab[i] == value)
0382 return true;
0383
0384 return false;
0385 }
0386
0387 /**
0388 * Tests if the specified key-value mapping is in the map.
0389 *
0390 * @param key possible key
0391 * @param value possible value
0392 * @return <code>true</code> if and only if the specified key-value
0393 * mapping is in the map
0394 */
0395 private boolean containsMapping(Object key, Object value) {
0396 Object k = maskNull(key);
0397 Object[] tab = table;
0398 int len = tab.length;
0399 int i = hash(k, len);
0400 while (true) {
0401 Object item = tab[i];
0402 if (item == k)
0403 return tab[i + 1] == value;
0404 if (item == null)
0405 return false;
0406 i = nextKeyIndex(i, len);
0407 }
0408 }
0409
0410 /**
0411 * Associates the specified value with the specified key in this identity
0412 * hash map. If the map previously contained a mapping for the key, the
0413 * old value is replaced.
0414 *
0415 * @param key the key with which the specified value is to be associated
0416 * @param value the value to be associated with the specified key
0417 * @return the previous value associated with <tt>key</tt>, or
0418 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
0419 * (A <tt>null</tt> return can also indicate that the map
0420 * previously associated <tt>null</tt> with <tt>key</tt>.)
0421 * @see Object#equals(Object)
0422 * @see #get(Object)
0423 * @see #containsKey(Object)
0424 */
0425 public V put(K key, V value) {
0426 Object k = maskNull(key);
0427 Object[] tab = table;
0428 int len = tab.length;
0429 int i = hash(k, len);
0430
0431 Object item;
0432 while ((item = tab[i]) != null) {
0433 if (item == k) {
0434 V oldValue = (V) tab[i + 1];
0435 tab[i + 1] = value;
0436 return oldValue;
0437 }
0438 i = nextKeyIndex(i, len);
0439 }
0440
0441 modCount++;
0442 tab[i] = k;
0443 tab[i + 1] = value;
0444 if (++size >= threshold)
0445 resize(len); // len == 2 * current capacity.
0446 return null;
0447 }
0448
0449 /**
0450 * Resize the table to hold given capacity.
0451 *
0452 * @param newCapacity the new capacity, must be a power of two.
0453 */
0454 private void resize(int newCapacity) {
0455 // assert (newCapacity & -newCapacity) == newCapacity; // power of 2
0456 int newLength = newCapacity * 2;
0457
0458 Object[] oldTable = table;
0459 int oldLength = oldTable.length;
0460 if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any further
0461 if (threshold == MAXIMUM_CAPACITY - 1)
0462 throw new IllegalStateException("Capacity exhausted.");
0463 threshold = MAXIMUM_CAPACITY - 1; // Gigantic map!
0464 return;
0465 }
0466 if (oldLength >= newLength)
0467 return;
0468
0469 Object[] newTable = new Object[newLength];
0470 threshold = newLength / 3;
0471
0472 for (int j = 0; j < oldLength; j += 2) {
0473 Object key = oldTable[j];
0474 if (key != null) {
0475 Object value = oldTable[j + 1];
0476 oldTable[j] = null;
0477 oldTable[j + 1] = null;
0478 int i = hash(key, newLength);
0479 while (newTable[i] != null)
0480 i = nextKeyIndex(i, newLength);
0481 newTable[i] = key;
0482 newTable[i + 1] = value;
0483 }
0484 }
0485 table = newTable;
0486 }
0487
0488 /**
0489 * Copies all of the mappings from the specified map to this map.
0490 * These mappings will replace any mappings that this map had for
0491 * any of the keys currently in the specified map.
0492 *
0493 * @param m mappings to be stored in this map
0494 * @throws NullPointerException if the specified map is null
0495 */
0496 public void putAll(Map<? extends K, ? extends V> m) {
0497 int n = m.size();
0498 if (n == 0)
0499 return;
0500 if (n > threshold) // conservatively pre-expand
0501 resize(capacity(n));
0502
0503 for (Entry<? extends K, ? extends V> e : m.entrySet())
0504 put(e.getKey(), e.getValue());
0505 }
0506
0507 /**
0508 * Removes the mapping for this key from this map if present.
0509 *
0510 * @param key key whose mapping is to be removed from the map
0511 * @return the previous value associated with <tt>key</tt>, or
0512 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
0513 * (A <tt>null</tt> return can also indicate that the map
0514 * previously associated <tt>null</tt> with <tt>key</tt>.)
0515 */
0516 public V remove(Object key) {
0517 Object k = maskNull(key);
0518 Object[] tab = table;
0519 int len = tab.length;
0520 int i = hash(k, len);
0521
0522 while (true) {
0523 Object item = tab[i];
0524 if (item == k) {
0525 modCount++;
0526 size--;
0527 V oldValue = (V) tab[i + 1];
0528 tab[i + 1] = null;
0529 tab[i] = null;
0530 closeDeletion(i);
0531 return oldValue;
0532 }
0533 if (item == null)
0534 return null;
0535 i = nextKeyIndex(i, len);
0536 }
0537
0538 }
0539
0540 /**
0541 * Removes the specified key-value mapping from the map if it is present.
0542 *
0543 * @param key possible key
0544 * @param value possible value
0545 * @return <code>true</code> if and only if the specified key-value
0546 * mapping was in the map
0547 */
0548 private boolean removeMapping(Object key, Object value) {
0549 Object k = maskNull(key);
0550 Object[] tab = table;
0551 int len = tab.length;
0552 int i = hash(k, len);
0553
0554 while (true) {
0555 Object item = tab[i];
0556 if (item == k) {
0557 if (tab[i + 1] != value)
0558 return false;
0559 modCount++;
0560 size--;
0561 tab[i] = null;
0562 tab[i + 1] = null;
0563 closeDeletion(i);
0564 return true;
0565 }
0566 if (item == null)
0567 return false;
0568 i = nextKeyIndex(i, len);
0569 }
0570 }
0571
0572 /**
0573 * Rehash all possibly-colliding entries following a
0574 * deletion. This preserves the linear-probe
0575 * collision properties required by get, put, etc.
0576 *
0577 * @param d the index of a newly empty deleted slot
0578 */
0579 private void closeDeletion(int d) {
0580 // Adapted from Knuth Section 6.4 Algorithm R
0581 Object[] tab = table;
0582 int len = tab.length;
0583
0584 // Look for items to swap into newly vacated slot
0585 // starting at index immediately following deletion,
0586 // and continuing until a null slot is seen, indicating
0587 // the end of a run of possibly-colliding keys.
0588 Object item;
0589 for (int i = nextKeyIndex(d, len); (item = tab[i]) != null; i = nextKeyIndex(
0590 i, len)) {
0591 // The following test triggers if the item at slot i (which
0592 // hashes to be at slot r) should take the spot vacated by d.
0593 // If so, we swap it in, and then continue with d now at the
0594 // newly vacated i. This process will terminate when we hit
0595 // the null slot at the end of this run.
0596 // The test is messy because we are using a circular table.
0597 int r = hash(item, len);
0598 if ((i < r && (r <= d || d <= i)) || (r <= d && d <= i)) {
0599 tab[d] = item;
0600 tab[d + 1] = tab[i + 1];
0601 tab[i] = null;
0602 tab[i + 1] = null;
0603 d = i;
0604 }
0605 }
0606 }
0607
0608 /**
0609 * Removes all of the mappings from this map.
0610 * The map will be empty after this call returns.
0611 */
0612 public void clear() {
0613 modCount++;
0614 Object[] tab = table;
0615 for (int i = 0; i < tab.length; i++)
0616 tab[i] = null;
0617 size = 0;
0618 }
0619
0620 /**
0621 * Compares the specified object with this map for equality. Returns
0622 * <tt>true</tt> if the given object is also a map and the two maps
0623 * represent identical object-reference mappings. More formally, this
0624 * map is equal to another map <tt>m</tt> if and only if
0625 * <tt>this.entrySet().equals(m.entrySet())</tt>.
0626 *
0627 * <p><b>Owing to the reference-equality-based semantics of this map it is
0628 * possible that the symmetry and transitivity requirements of the
0629 * <tt>Object.equals</tt> contract may be violated if this map is compared
0630 * to a normal map. However, the <tt>Object.equals</tt> contract is
0631 * guaranteed to hold among <tt>IdentityHashMap</tt> instances.</b>
0632 *
0633 * @param o object to be compared for equality with this map
0634 * @return <tt>true</tt> if the specified object is equal to this map
0635 * @see Object#equals(Object)
0636 */
0637 public boolean equals(Object o) {
0638 if (o == this ) {
0639 return true;
0640 } else if (o instanceof IdentityHashMap) {
0641 IdentityHashMap m = (IdentityHashMap) o;
0642 if (m.size() != size)
0643 return false;
0644
0645 Object[] tab = m.table;
0646 for (int i = 0; i < tab.length; i += 2) {
0647 Object k = tab[i];
0648 if (k != null && !containsMapping(k, tab[i + 1]))
0649 return false;
0650 }
0651 return true;
0652 } else if (o instanceof Map) {
0653 Map m = (Map) o;
0654 return entrySet().equals(m.entrySet());
0655 } else {
0656 return false; // o is not a Map
0657 }
0658 }
0659
0660 /**
0661 * Returns the hash code value for this map. The hash code of a map is
0662 * defined to be the sum of the hash codes of each entry in the map's
0663 * <tt>entrySet()</tt> view. This ensures that <tt>m1.equals(m2)</tt>
0664 * implies that <tt>m1.hashCode()==m2.hashCode()</tt> for any two
0665 * <tt>IdentityHashMap</tt> instances <tt>m1</tt> and <tt>m2</tt>, as
0666 * required by the general contract of {@link Object#hashCode}.
0667 *
0668 * <p><b>Owing to the reference-equality-based semantics of the
0669 * <tt>Map.Entry</tt> instances in the set returned by this map's
0670 * <tt>entrySet</tt> method, it is possible that the contractual
0671 * requirement of <tt>Object.hashCode</tt> mentioned in the previous
0672 * paragraph will be violated if one of the two objects being compared is
0673 * an <tt>IdentityHashMap</tt> instance and the other is a normal map.</b>
0674 *
0675 * @return the hash code value for this map
0676 * @see Object#equals(Object)
0677 * @see #equals(Object)
0678 */
0679 public int hashCode() {
0680 int result = 0;
0681 Object[] tab = table;
0682 for (int i = 0; i < tab.length; i += 2) {
0683 Object key = tab[i];
0684 if (key != null) {
0685 Object k = unmaskNull(key);
0686 result += System.identityHashCode(k)
0687 ^ System.identityHashCode(tab[i + 1]);
0688 }
0689 }
0690 return result;
0691 }
0692
0693 /**
0694 * Returns a shallow copy of this identity hash map: the keys and values
0695 * themselves are not cloned.
0696 *
0697 * @return a shallow copy of this map
0698 */
0699 public Object clone() {
0700 try {
0701 IdentityHashMap<K, V> m = (IdentityHashMap<K, V>) super
0702 .clone();
0703 m.entrySet = null;
0704 m.table = (Object[]) table.clone();
0705 return m;
0706 } catch (CloneNotSupportedException e) {
0707 throw new InternalError();
0708 }
0709 }
0710
0711 private abstract class IdentityHashMapIterator<T> implements
0712 Iterator<T> {
0713 int index = (size != 0 ? 0 : table.length); // current slot.
0714 int expectedModCount = modCount; // to support fast-fail
0715 int lastReturnedIndex = -1; // to allow remove()
0716 boolean indexValid; // To avoid unnecessary next computation
0717 Object[] traversalTable = table; // reference to main table or copy
0718
0719 public boolean hasNext() {
0720 Object[] tab = traversalTable;
0721 for (int i = index; i < tab.length; i += 2) {
0722 Object key = tab[i];
0723 if (key != null) {
0724 index = i;
0725 return indexValid = true;
0726 }
0727 }
0728 index = tab.length;
0729 return false;
0730 }
0731
0732 protected int nextIndex() {
0733 if (modCount != expectedModCount)
0734 throw new ConcurrentModificationException();
0735 if (!indexValid && !hasNext())
0736 throw new NoSuchElementException();
0737
0738 indexValid = false;
0739 lastReturnedIndex = index;
0740 index += 2;
0741 return lastReturnedIndex;
0742 }
0743
0744 public void remove() {
0745 if (lastReturnedIndex == -1)
0746 throw new IllegalStateException();
0747 if (modCount != expectedModCount)
0748 throw new ConcurrentModificationException();
0749
0750 expectedModCount = ++modCount;
0751 int deletedSlot = lastReturnedIndex;
0752 lastReturnedIndex = -1;
0753 size--;
0754 // back up index to revisit new contents after deletion
0755 index = deletedSlot;
0756 indexValid = false;
0757
0758 // Removal code proceeds as in closeDeletion except that
0759 // it must catch the rare case where an element already
0760 // seen is swapped into a vacant slot that will be later
0761 // traversed by this iterator. We cannot allow future
0762 // next() calls to return it again. The likelihood of
0763 // this occurring under 2/3 load factor is very slim, but
0764 // when it does happen, we must make a copy of the rest of
0765 // the table to use for the rest of the traversal. Since
0766 // this can only happen when we are near the end of the table,
0767 // even in these rare cases, this is not very expensive in
0768 // time or space.
0769
0770 Object[] tab = traversalTable;
0771 int len = tab.length;
0772
0773 int d = deletedSlot;
0774 K key = (K) tab[d];
0775 tab[d] = null; // vacate the slot
0776 tab[d + 1] = null;
0777
0778 // If traversing a copy, remove in real table.
0779 // We can skip gap-closure on copy.
0780 if (tab != IdentityHashMap.this .table) {
0781 IdentityHashMap.this .remove(key);
0782 expectedModCount = modCount;
0783 return;
0784 }
0785
0786 Object item;
0787 for (int i = nextKeyIndex(d, len); (item = tab[i]) != null; i = nextKeyIndex(
0788 i, len)) {
0789 int r = hash(item, len);
0790 // See closeDeletion for explanation of this conditional
0791 if ((i < r && (r <= d || d <= i)) || (r <= d && d <= i)) {
0792
0793 // If we are about to swap an already-seen element
0794 // into a slot that may later be returned by next(),
0795 // then clone the rest of table for use in future
0796 // next() calls. It is OK that our copy will have
0797 // a gap in the "wrong" place, since it will never
0798 // be used for searching anyway.
0799
0800 if (i < deletedSlot
0801 && d >= deletedSlot
0802 && traversalTable == IdentityHashMap.this .table) {
0803 int remaining = len - deletedSlot;
0804 Object[] newTable = new Object[remaining];
0805 System.arraycopy(tab, deletedSlot, newTable, 0,
0806 remaining);
0807 traversalTable = newTable;
0808 index = 0;
0809 }
0810
0811 tab[d] = item;
0812 tab[d + 1] = tab[i + 1];
0813 tab[i] = null;
0814 tab[i + 1] = null;
0815 d = i;
0816 }
0817 }
0818 }
0819 }
0820
0821 private class KeyIterator extends IdentityHashMapIterator<K> {
0822 public K next() {
0823 return (K) unmaskNull(traversalTable[nextIndex()]);
0824 }
0825 }
0826
0827 private class ValueIterator extends IdentityHashMapIterator<V> {
0828 public V next() {
0829 return (V) traversalTable[nextIndex() + 1];
0830 }
0831 }
0832
0833 /**
0834 * Since we don't use Entry objects, we use the Iterator
0835 * itself as an entry.
0836 */
0837 private class EntryIterator extends
0838 IdentityHashMapIterator<Map.Entry<K, V>> implements
0839 Map.Entry<K, V> {
0840 public Map.Entry<K, V> next() {
0841 nextIndex();
0842 return this ;
0843 }
0844
0845 public K getKey() {
0846 // Provide a better exception than out of bounds index
0847 if (lastReturnedIndex < 0)
0848 throw new IllegalStateException("Entry was removed");
0849
0850 return (K) unmaskNull(traversalTable[lastReturnedIndex]);
0851 }
0852
0853 public V getValue() {
0854 // Provide a better exception than out of bounds index
0855 if (lastReturnedIndex < 0)
0856 throw new IllegalStateException("Entry was removed");
0857
0858 return (V) traversalTable[lastReturnedIndex + 1];
0859 }
0860
0861 public V setValue(V value) {
0862 // It would be mean-spirited to proceed here if remove() called
0863 if (lastReturnedIndex < 0)
0864 throw new IllegalStateException("Entry was removed");
0865 V oldValue = (V) traversalTable[lastReturnedIndex + 1];
0866 traversalTable[lastReturnedIndex + 1] = value;
0867 // if shadowing, force into main table
0868 if (traversalTable != IdentityHashMap.this .table)
0869 put((K) traversalTable[lastReturnedIndex], value);
0870 return oldValue;
0871 }
0872
0873 public boolean equals(Object o) {
0874 if (lastReturnedIndex < 0)
0875 return super .equals(o);
0876
0877 if (!(o instanceof Map.Entry))
0878 return false;
0879 Map.Entry e = (Map.Entry) o;
0880 return e.getKey() == getKey() && e.getValue() == getValue();
0881 }
0882
0883 public int hashCode() {
0884 if (lastReturnedIndex < 0)
0885 return super .hashCode();
0886
0887 return System.identityHashCode(getKey())
0888 ^ System.identityHashCode(getValue());
0889 }
0890
0891 public String toString() {
0892 if (lastReturnedIndex < 0)
0893 return super .toString();
0894
0895 return getKey() + "=" + getValue();
0896 }
0897 }
0898
0899 // Views
0900
0901 /**
0902 * This field is initialized to contain an instance of the entry set
0903 * view the first time this view is requested. The view is stateless,
0904 * so there's no reason to create more than one.
0905 */
0906
0907 private transient Set<Map.Entry<K, V>> entrySet = null;
0908
0909 /**
0910 * Returns an identity-based set view of the keys contained in this map.
0911 * The set is backed by the map, so changes to the map are reflected in
0912 * the set, and vice-versa. If the map is modified while an iteration
0913 * over the set is in progress, the results of the iteration are
0914 * undefined. The set supports element removal, which removes the
0915 * corresponding mapping from the map, via the <tt>Iterator.remove</tt>,
0916 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
0917 * <tt>clear</tt> methods. It does not support the <tt>add</tt> or
0918 * <tt>addAll</tt> methods.
0919 *
0920 * <p><b>While the object returned by this method implements the
0921 * <tt>Set</tt> interface, it does <i>not</i> obey <tt>Set's</tt> general
0922 * contract. Like its backing map, the set returned by this method
0923 * defines element equality as reference-equality rather than
0924 * object-equality. This affects the behavior of its <tt>contains</tt>,
0925 * <tt>remove</tt>, <tt>containsAll</tt>, <tt>equals</tt>, and
0926 * <tt>hashCode</tt> methods.</b>
0927 *
0928 * <p><b>The <tt>equals</tt> method of the returned set returns <tt>true</tt>
0929 * only if the specified object is a set containing exactly the same
0930 * object references as the returned set. The symmetry and transitivity
0931 * requirements of the <tt>Object.equals</tt> contract may be violated if
0932 * the set returned by this method is compared to a normal set. However,
0933 * the <tt>Object.equals</tt> contract is guaranteed to hold among sets
0934 * returned by this method.</b>
0935 *
0936 * <p>The <tt>hashCode</tt> method of the returned set returns the sum of
0937 * the <i>identity hashcodes</i> of the elements in the set, rather than
0938 * the sum of their hashcodes. This is mandated by the change in the
0939 * semantics of the <tt>equals</tt> method, in order to enforce the
0940 * general contract of the <tt>Object.hashCode</tt> method among sets
0941 * returned by this method.
0942 *
0943 * @return an identity-based set view of the keys contained in this map
0944 * @see Object#equals(Object)
0945 * @see System#identityHashCode(Object)
0946 */
0947 public Set<K> keySet() {
0948 Set<K> ks = keySet;
0949 if (ks != null)
0950 return ks;
0951 else
0952 return keySet = new KeySet();
0953 }
0954
0955 private class KeySet extends AbstractSet<K> {
0956 public Iterator<K> iterator() {
0957 return new KeyIterator();
0958 }
0959
0960 public int size() {
0961 return size;
0962 }
0963
0964 public boolean contains(Object o) {
0965 return containsKey(o);
0966 }
0967
0968 public boolean remove(Object o) {
0969 int oldSize = size;
0970 IdentityHashMap.this .remove(o);
0971 return size != oldSize;
0972 }
0973
0974 /*
0975 * Must revert from AbstractSet's impl to AbstractCollection's, as
0976 * the former contains an optimization that results in incorrect
0977 * behavior when c is a smaller "normal" (non-identity-based) Set.
0978 */
0979 public boolean removeAll(Collection<?> c) {
0980 boolean modified = false;
0981 for (Iterator i = iterator(); i.hasNext();) {
0982 if (c.contains(i.next())) {
0983 i.remove();
0984 modified = true;
0985 }
0986 }
0987 return modified;
0988 }
0989
0990 public void clear() {
0991 IdentityHashMap.this .clear();
0992 }
0993
0994 public int hashCode() {
0995 int result = 0;
0996 for (K key : this )
0997 result += System.identityHashCode(key);
0998 return result;
0999 }
1000 }
1001
1002 /**
1003 * Returns a {@link Collection} view of the values contained in this map.
1004 * The collection is backed by the map, so changes to the map are
1005 * reflected in the collection, and vice-versa. If the map is
1006 * modified while an iteration over the collection is in progress,
1007 * the results of the iteration are undefined. The collection
1008 * supports element removal, which removes the corresponding
1009 * mapping from the map, via the <tt>Iterator.remove</tt>,
1010 * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
1011 * <tt>retainAll</tt> and <tt>clear</tt> methods. It does not
1012 * support the <tt>add</tt> or <tt>addAll</tt> methods.
1013 *
1014 * <p><b>While the object returned by this method implements the
1015 * <tt>Collection</tt> interface, it does <i>not</i> obey
1016 * <tt>Collection's</tt> general contract. Like its backing map,
1017 * the collection returned by this method defines element equality as
1018 * reference-equality rather than object-equality. This affects the
1019 * behavior of its <tt>contains</tt>, <tt>remove</tt> and
1020 * <tt>containsAll</tt> methods.</b>
1021 */
1022 public Collection<V> values() {
1023 Collection<V> vs = values;
1024 if (vs != null)
1025 return vs;
1026 else
1027 return values = new Values();
1028 }
1029
1030 private class Values extends AbstractCollection<V> {
1031 public Iterator<V> iterator() {
1032 return new ValueIterator();
1033 }
1034
1035 public int size() {
1036 return size;
1037 }
1038
1039 public boolean contains(Object o) {
1040 return containsValue(o);
1041 }
1042
1043 public boolean remove(Object o) {
1044 for (Iterator i = iterator(); i.hasNext();) {
1045 if (i.next() == o) {
1046 i.remove();
1047 return true;
1048 }
1049 }
1050 return false;
1051 }
1052
1053 public void clear() {
1054 IdentityHashMap.this .clear();
1055 }
1056 }
1057
1058 /**
1059 * Returns a {@link Set} view of the mappings contained in this map.
1060 * Each element in the returned set is a reference-equality-based
1061 * <tt>Map.Entry</tt>. The set is backed by the map, so changes
1062 * to the map are reflected in the set, and vice-versa. If the
1063 * map is modified while an iteration over the set is in progress,
1064 * the results of the iteration are undefined. The set supports
1065 * element removal, which removes the corresponding mapping from
1066 * the map, via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1067 * <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt>
1068 * methods. It does not support the <tt>add</tt> or
1069 * <tt>addAll</tt> methods.
1070 *
1071 * <p>Like the backing map, the <tt>Map.Entry</tt> objects in the set
1072 * returned by this method define key and value equality as
1073 * reference-equality rather than object-equality. This affects the
1074 * behavior of the <tt>equals</tt> and <tt>hashCode</tt> methods of these
1075 * <tt>Map.Entry</tt> objects. A reference-equality based <tt>Map.Entry
1076 * e</tt> is equal to an object <tt>o</tt> if and only if <tt>o</tt> is a
1077 * <tt>Map.Entry</tt> and <tt>e.getKey()==o.getKey() &&
1078 * e.getValue()==o.getValue()</tt>. To accommodate these equals
1079 * semantics, the <tt>hashCode</tt> method returns
1080 * <tt>System.identityHashCode(e.getKey()) ^
1081 * System.identityHashCode(e.getValue())</tt>.
1082 *
1083 * <p><b>Owing to the reference-equality-based semantics of the
1084 * <tt>Map.Entry</tt> instances in the set returned by this method,
1085 * it is possible that the symmetry and transitivity requirements of
1086 * the {@link Object#equals(Object)} contract may be violated if any of
1087 * the entries in the set is compared to a normal map entry, or if
1088 * the set returned by this method is compared to a set of normal map
1089 * entries (such as would be returned by a call to this method on a normal
1090 * map). However, the <tt>Object.equals</tt> contract is guaranteed to
1091 * hold among identity-based map entries, and among sets of such entries.
1092 * </b>
1093 *
1094 * @return a set view of the identity-mappings contained in this map
1095 */
1096 public Set<Map.Entry<K, V>> entrySet() {
1097 Set<Map.Entry<K, V>> es = entrySet;
1098 if (es != null)
1099 return es;
1100 else
1101 return entrySet = new EntrySet();
1102 }
1103
1104 private class EntrySet extends AbstractSet<Map.Entry<K, V>> {
1105 public Iterator<Map.Entry<K, V>> iterator() {
1106 return new EntryIterator();
1107 }
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
1116 public boolean remove(Object o) {
1117 if (!(o instanceof Map.Entry))
1118 return false;
1119 Map.Entry entry = (Map.Entry) o;
1120 return removeMapping(entry.getKey(), entry.getValue());
1121 }
1122
1123 public int size() {
1124 return size;
1125 }
1126
1127 public void clear() {
1128 IdentityHashMap.this .clear();
1129 }
1130
1131 /*
1132 * Must revert from AbstractSet's impl to AbstractCollection's, as
1133 * the former contains an optimization that results in incorrect
1134 * behavior when c is a smaller "normal" (non-identity-based) Set.
1135 */
1136 public boolean removeAll(Collection<?> c) {
1137 boolean modified = false;
1138 for (Iterator i = iterator(); i.hasNext();) {
1139 if (c.contains(i.next())) {
1140 i.remove();
1141 modified = true;
1142 }
1143 }
1144 return modified;
1145 }
1146
1147 public Object[] toArray() {
1148 int size = size();
1149 Object[] result = new Object[size];
1150 Iterator<Map.Entry<K, V>> it = iterator();
1151 for (int i = 0; i < size; i++)
1152 result[i] = new AbstractMap.SimpleEntry<K, V>(it.next());
1153 return result;
1154 }
1155
1156 @SuppressWarnings("unchecked")
1157 public <T> T[] toArray(T[] a) {
1158 int size = size();
1159 if (a.length < size)
1160 a = (T[]) java.lang.reflect.Array.newInstance(a
1161 .getClass().getComponentType(), size);
1162 Iterator<Map.Entry<K, V>> it = iterator();
1163 for (int i = 0; i < size; i++)
1164 a[i] = (T) new AbstractMap.SimpleEntry<K, V>(it.next());
1165 if (a.length > size)
1166 a[size] = null;
1167 return a;
1168 }
1169 }
1170
1171 private static final long serialVersionUID = 8188218128353913216L;
1172
1173 /**
1174 * Save the state of the <tt>IdentityHashMap</tt> instance to a stream
1175 * (i.e., serialize it).
1176 *
1177 * @serialData The <i>size</i> of the HashMap (the number of key-value
1178 * mappings) (<tt>int</tt>), followed by the key (Object) and
1179 * value (Object) for each key-value mapping represented by the
1180 * IdentityHashMap. The key-value mappings are emitted in no
1181 * particular order.
1182 */
1183 private void writeObject(java.io.ObjectOutputStream s)
1184 throws java.io.IOException {
1185 // Write out and any hidden stuff
1186 s.defaultWriteObject();
1187
1188 // Write out size (number of Mappings)
1189 s.writeInt(size);
1190
1191 // Write out keys and values (alternating)
1192 Object[] tab = table;
1193 for (int i = 0; i < tab.length; i += 2) {
1194 Object key = tab[i];
1195 if (key != null) {
1196 s.writeObject(unmaskNull(key));
1197 s.writeObject(tab[i + 1]);
1198 }
1199 }
1200 }
1201
1202 /**
1203 * Reconstitute the <tt>IdentityHashMap</tt> instance from a stream (i.e.,
1204 * deserialize it).
1205 */
1206 private void readObject(java.io.ObjectInputStream s)
1207 throws java.io.IOException, ClassNotFoundException {
1208 // Read in any hidden stuff
1209 s.defaultReadObject();
1210
1211 // Read in size (number of Mappings)
1212 int size = s.readInt();
1213
1214 // Allow for 33% growth (i.e., capacity is >= 2* size()).
1215 init(capacity((size * 4) / 3));
1216
1217 // Read the keys and values, and put the mappings in the table
1218 for (int i = 0; i < size; i++) {
1219 K key = (K) s.readObject();
1220 V value = (V) s.readObject();
1221 putForCreate(key, value);
1222 }
1223 }
1224
1225 /**
1226 * The put method for readObject. It does not resize the table,
1227 * update modCount, etc.
1228 */
1229 private void putForCreate(K key, V value) throws IOException {
1230 K k = (K) maskNull(key);
1231 Object[] tab = table;
1232 int len = tab.length;
1233 int i = hash(k, len);
1234
1235 Object item;
1236 while ((item = tab[i]) != null) {
1237 if (item == k)
1238 throw new java.io.StreamCorruptedException();
1239 i = nextKeyIndex(i, len);
1240 }
1241 tab[i] = k;
1242 tab[i + 1] = value;
1243 }
1244 }
|