IdentityHashMap.java revision 51b1b6997fd3f980076b8081f7f1165ccc2a4008
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 26package java.util; 27import 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 134public 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() && 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} 1244