1 /* 2 * Copyright (c) 2000, 2012, 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 @Override 700 public IdentityHashMap<K,V> clone() { 701 try { 702 @SuppressWarnings("unchecked") 703 IdentityHashMap<K,V> m = (IdentityHashMap<K,V>) super.clone(); 704 m.entrySet = null; 705 m.table = table.clone(); 706 return m; 707 } catch (CloneNotSupportedException e) { 708 throw new InternalError(e); 709 } 710 } 711 712 private abstract class IdentityHashMapIterator<T> implements Iterator<T> { 713 int index = (size != 0 ? 0 : table.length); // current slot. 714 int expectedModCount = modCount; // to support fast-fail 715 int lastReturnedIndex = -1; // to allow remove() 716 boolean indexValid; // To avoid unnecessary next computation 717 Object[] traversalTable = table; // reference to main table or copy 718 719 public boolean hasNext() { 720 Object[] tab = traversalTable; 721 for (int i = index; i < tab.length; i+=2) { 722 Object key = tab[i]; 723 if (key != null) { 724 index = i; 725 return indexValid = true; 726 } 727 } 728 index = tab.length; 729 return false; 730 } 731 732 protected int nextIndex() { 733 if (modCount != expectedModCount) 734 throw new ConcurrentModificationException(); 735 if (!indexValid && !hasNext()) 736 throw new NoSuchElementException(); 737 738 indexValid = false; 739 lastReturnedIndex = index; 740 index += 2; 741 return lastReturnedIndex; 742 } 743 744 public void remove() { 745 if (lastReturnedIndex == -1) 746 throw new IllegalStateException(); 747 if (modCount != expectedModCount) 748 throw new ConcurrentModificationException(); 749 750 expectedModCount = ++modCount; 751 int deletedSlot = lastReturnedIndex; 752 lastReturnedIndex = -1; 753 // back up index to revisit new contents after deletion 754 index = deletedSlot; 755 indexValid = false; 756 757 // Removal code proceeds as in closeDeletion except that 758 // it must catch the rare case where an element already 759 // seen is swapped into a vacant slot that will be later 760 // traversed by this iterator. We cannot allow future 761 // next() calls to return it again. The likelihood of 762 // this occurring under 2/3 load factor is very slim, but 763 // when it does happen, we must make a copy of the rest of 764 // the table to use for the rest of the traversal. Since 765 // this can only happen when we are near the end of the table, 766 // even in these rare cases, this is not very expensive in 767 // time or space. 768 769 Object[] tab = traversalTable; 770 int len = tab.length; 771 772 int d = deletedSlot; 773 K key = (K) tab[d]; 774 tab[d] = null; // vacate the slot 775 tab[d + 1] = null; 776 777 // If traversing a copy, remove in real table. 778 // We can skip gap-closure on copy. 779 if (tab != IdentityHashMap.this.table) { 780 IdentityHashMap.this.remove(key); 781 expectedModCount = modCount; 782 return; 783 } 784 785 size--; 786 787 Object item; 788 for (int i = nextKeyIndex(d, len); (item = tab[i]) != null; 789 i = nextKeyIndex(i, len)) { 790 int r = hash(item, len); 791 // See closeDeletion for explanation of this conditional 792 if ((i < r && (r <= d || d <= i)) || 793 (r <= d && d <= i)) { 794 795 // If we are about to swap an already-seen element 796 // into a slot that may later be returned by next(), 797 // then clone the rest of table for use in future 798 // next() calls. It is OK that our copy will have 799 // a gap in the "wrong" place, since it will never 800 // be used for searching anyway. 801 802 if (i < deletedSlot && d >= deletedSlot && 803 traversalTable == IdentityHashMap.this.table) { 804 int remaining = len - deletedSlot; 805 Object[] newTable = new Object[remaining]; 806 System.arraycopy(tab, deletedSlot, 807 newTable, 0, remaining); 808 traversalTable = newTable; 809 index = 0; 810 } 811 812 tab[d] = item; 813 tab[d + 1] = tab[i + 1]; 814 tab[i] = null; 815 tab[i + 1] = null; 816 d = i; 817 } 818 } 819 } 820 } 821 822 private class KeyIterator extends IdentityHashMapIterator<K> { 823 public K next() { 824 return (K) unmaskNull(traversalTable[nextIndex()]); 825 } 826 } 827 828 private class ValueIterator extends IdentityHashMapIterator<V> { 829 public V next() { 830 return (V) traversalTable[nextIndex() + 1]; 831 } 832 } 833 834 private class EntryIterator 835 extends IdentityHashMapIterator<Map.Entry<K,V>> 836 { 837 private Entry lastReturnedEntry = null; 838 839 public Map.Entry<K,V> next() { 840 lastReturnedEntry = new Entry(nextIndex()); 841 return lastReturnedEntry; 842 } 843 844 public void remove() { 845 lastReturnedIndex = 846 ((null == lastReturnedEntry) ? -1 : lastReturnedEntry.index); 847 super.remove(); 848 lastReturnedEntry.index = lastReturnedIndex; 849 lastReturnedEntry = null; 850 } 851 852 private class Entry implements Map.Entry<K,V> { 853 private int index; 854 855 private Entry(int index) { 856 this.index = index; 857 } 858 859 public K getKey() { 860 checkIndexForEntryUse(); 861 return (K) unmaskNull(traversalTable[index]); 862 } 863 864 public V getValue() { 865 checkIndexForEntryUse(); 866 return (V) traversalTable[index+1]; 867 } 868 869 public V setValue(V value) { 870 checkIndexForEntryUse(); 871 V oldValue = (V) traversalTable[index+1]; 872 traversalTable[index+1] = value; 873 // if shadowing, force into main table 874 if (traversalTable != IdentityHashMap.this.table) 875 put((K) traversalTable[index], value); 876 return oldValue; 877 } 878 879 public boolean equals(Object o) { 880 if (index < 0) 881 return super.equals(o); 882 883 if (!(o instanceof Map.Entry)) 884 return false; 885 Map.Entry e = (Map.Entry)o; 886 return (e.getKey() == unmaskNull(traversalTable[index]) && 887 e.getValue() == traversalTable[index+1]); 888 } 889 890 public int hashCode() { 891 if (lastReturnedIndex < 0) 892 return super.hashCode(); 893 894 return (System.identityHashCode(unmaskNull(traversalTable[index])) ^ 895 System.identityHashCode(traversalTable[index+1])); 896 } 897 898 public String toString() { 899 if (index < 0) 900 return super.toString(); 901 902 return (unmaskNull(traversalTable[index]) + "=" 903 + traversalTable[index+1]); 904 } 905 906 private void checkIndexForEntryUse() { 907 if (index < 0) 908 throw new IllegalStateException("Entry was removed"); 909 } 910 } 911 } 912 913 // Views 914 915 /** 916 * This field is initialized to contain an instance of the entry set 917 * view the first time this view is requested. The view is stateless, 918 * so there's no reason to create more than one. 919 */ 920 private transient Set<Map.Entry<K,V>> entrySet = null; 921 922 /** 923 * Returns an identity-based set view of the keys contained in this map. 924 * The set is backed by the map, so changes to the map are reflected in 925 * the set, and vice-versa. If the map is modified while an iteration 926 * over the set is in progress, the results of the iteration are 927 * undefined. The set supports element removal, which removes the 928 * corresponding mapping from the map, via the <tt>Iterator.remove</tt>, 929 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and 930 * <tt>clear</tt> methods. It does not support the <tt>add</tt> or 931 * <tt>addAll</tt> methods. 932 * 933 * <p><b>While the object returned by this method implements the 934 * <tt>Set</tt> interface, it does <i>not</i> obey <tt>Set's</tt> general 935 * contract. Like its backing map, the set returned by this method 936 * defines element equality as reference-equality rather than 937 * object-equality. This affects the behavior of its <tt>contains</tt>, 938 * <tt>remove</tt>, <tt>containsAll</tt>, <tt>equals</tt>, and 939 * <tt>hashCode</tt> methods.</b> 940 * 941 * <p><b>The <tt>equals</tt> method of the returned set returns <tt>true</tt> 942 * only if the specified object is a set containing exactly the same 943 * object references as the returned set. The symmetry and transitivity 944 * requirements of the <tt>Object.equals</tt> contract may be violated if 945 * the set returned by this method is compared to a normal set. However, 946 * the <tt>Object.equals</tt> contract is guaranteed to hold among sets 947 * returned by this method.</b> 948 * 949 * <p>The <tt>hashCode</tt> method of the returned set returns the sum of 950 * the <i>identity hashcodes</i> of the elements in the set, rather than 951 * the sum of their hashcodes. This is mandated by the change in the 952 * semantics of the <tt>equals</tt> method, in order to enforce the 953 * general contract of the <tt>Object.hashCode</tt> method among sets 954 * returned by this method. 955 * 956 * @return an identity-based set view of the keys contained in this map 957 * @see Object#equals(Object) 958 * @see System#identityHashCode(Object) 959 */ 960 public Set<K> keySet() { 961 Set<K> ks = keySet; 962 if (ks != null) 963 return ks; 964 else 965 return keySet = new KeySet(); 966 } 967 968 private class KeySet extends AbstractSet<K> { 969 public Iterator<K> iterator() { 970 return new KeyIterator(); 971 } 972 public int size() { 973 return size; 974 } 975 public boolean contains(Object o) { 976 return containsKey(o); 977 } 978 public boolean remove(Object o) { 979 int oldSize = size; 980 IdentityHashMap.this.remove(o); 981 return size != oldSize; 982 } 983 /* 984 * Must revert from AbstractSet's impl to AbstractCollection's, as 985 * the former contains an optimization that results in incorrect 986 * behavior when c is a smaller "normal" (non-identity-based) Set. 987 */ 988 public boolean removeAll(Collection<?> c) { 989 boolean modified = false; 990 for (Iterator<K> i = iterator(); i.hasNext(); ) { 991 if (c.contains(i.next())) { 992 i.remove(); 993 modified = true; 994 } 995 } 996 return modified; 997 } 998 public void clear() { 999 IdentityHashMap.this.clear(); 1000 } 1001 public int hashCode() { 1002 int result = 0; 1003 for (K key : this) 1004 result += System.identityHashCode(key); 1005 return result; 1006 } 1007 } 1008 1009 /** 1010 * Returns a {@link Collection} view of the values contained in this map. 1011 * The collection is backed by the map, so changes to the map are 1012 * reflected in the collection, and vice-versa. If the map is 1013 * modified while an iteration over the collection is in progress, 1014 * the results of the iteration are undefined. The collection 1015 * supports element removal, which removes the corresponding 1016 * mapping from the map, via the <tt>Iterator.remove</tt>, 1017 * <tt>Collection.remove</tt>, <tt>removeAll</tt>, 1018 * <tt>retainAll</tt> and <tt>clear</tt> methods. It does not 1019 * support the <tt>add</tt> or <tt>addAll</tt> methods. 1020 * 1021 * <p><b>While the object returned by this method implements the 1022 * <tt>Collection</tt> interface, it does <i>not</i> obey 1023 * <tt>Collection's</tt> general contract. Like its backing map, 1024 * the collection returned by this method defines element equality as 1025 * reference-equality rather than object-equality. This affects the 1026 * behavior of its <tt>contains</tt>, <tt>remove</tt> and 1027 * <tt>containsAll</tt> methods.</b> 1028 */ 1029 public Collection<V> values() { 1030 Collection<V> vs = values; 1031 if (vs != null) 1032 return vs; 1033 else 1034 return values = new Values(); 1035 } 1036 1037 private class Values extends AbstractCollection<V> { 1038 public Iterator<V> iterator() { 1039 return new ValueIterator(); 1040 } 1041 public int size() { 1042 return size; 1043 } 1044 public boolean contains(Object o) { 1045 return containsValue(o); 1046 } 1047 public boolean remove(Object o) { 1048 for (Iterator<V> i = iterator(); i.hasNext(); ) { 1049 if (i.next() == o) { 1050 i.remove(); 1051 return true; 1052 } 1053 } 1054 return false; 1055 } 1056 public void clear() { 1057 IdentityHashMap.this.clear(); 1058 } 1059 } 1060 1061 /** 1062 * Returns a {@link Set} view of the mappings contained in this map. 1063 * Each element in the returned set is a reference-equality-based 1064 * <tt>Map.Entry</tt>. The set is backed by the map, so changes 1065 * to the map are reflected in the set, and vice-versa. If the 1066 * map is modified while an iteration over the set is in progress, 1067 * the results of the iteration are undefined. The set supports 1068 * element removal, which removes the corresponding mapping from 1069 * the map, via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, 1070 * <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt> 1071 * methods. It does not support the <tt>add</tt> or 1072 * <tt>addAll</tt> methods. 1073 * 1074 * <p>Like the backing map, the <tt>Map.Entry</tt> objects in the set 1075 * returned by this method define key and value equality as 1076 * reference-equality rather than object-equality. This affects the 1077 * behavior of the <tt>equals</tt> and <tt>hashCode</tt> methods of these 1078 * <tt>Map.Entry</tt> objects. A reference-equality based <tt>Map.Entry 1079 * e</tt> is equal to an object <tt>o</tt> if and only if <tt>o</tt> is a 1080 * <tt>Map.Entry</tt> and <tt>e.getKey()==o.getKey() && 1081 * e.getValue()==o.getValue()</tt>. To accommodate these equals 1082 * semantics, the <tt>hashCode</tt> method returns 1083 * <tt>System.identityHashCode(e.getKey()) ^ 1084 * System.identityHashCode(e.getValue())</tt>. 1085 * 1086 * <p><b>Owing to the reference-equality-based semantics of the 1087 * <tt>Map.Entry</tt> instances in the set returned by this method, 1088 * it is possible that the symmetry and transitivity requirements of 1089 * the {@link Object#equals(Object)} contract may be violated if any of 1090 * the entries in the set is compared to a normal map entry, or if 1091 * the set returned by this method is compared to a set of normal map 1092 * entries (such as would be returned by a call to this method on a normal 1093 * map). However, the <tt>Object.equals</tt> contract is guaranteed to 1094 * hold among identity-based map entries, and among sets of such entries. 1095 * </b> 1096 * 1097 * @return a set view of the identity-mappings contained in this map 1098 */ 1099 public Set<Map.Entry<K,V>> entrySet() { 1100 Set<Map.Entry<K,V>> es = entrySet; 1101 if (es != null) 1102 return es; 1103 else 1104 return entrySet = new EntrySet(); 1105 } 1106 1107 private class EntrySet extends AbstractSet<Map.Entry<K,V>> { 1108 public Iterator<Map.Entry<K,V>> iterator() { 1109 return new EntryIterator(); 1110 } 1111 public boolean contains(Object o) { 1112 if (!(o instanceof Map.Entry)) 1113 return false; 1114 Map.Entry entry = (Map.Entry)o; 1115 return containsMapping(entry.getKey(), entry.getValue()); 1116 } 1117 public boolean remove(Object o) { 1118 if (!(o instanceof Map.Entry)) 1119 return false; 1120 Map.Entry entry = (Map.Entry)o; 1121 return removeMapping(entry.getKey(), entry.getValue()); 1122 } 1123 public int size() { 1124 return size; 1125 } 1126 public void clear() { 1127 IdentityHashMap.this.clear(); 1128 } 1129 /* 1130 * Must revert from AbstractSet's impl to AbstractCollection's, as 1131 * the former contains an optimization that results in incorrect 1132 * behavior when c is a smaller "normal" (non-identity-based) Set. 1133 */ 1134 public boolean removeAll(Collection<?> c) { 1135 boolean modified = false; 1136 for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); ) { 1137 if (c.contains(i.next())) { 1138 i.remove(); 1139 modified = true; 1140 } 1141 } 1142 return modified; 1143 } 1144 1145 public Object[] toArray() { 1146 int size = size(); 1147 Object[] result = new Object[size]; 1148 Iterator<Map.Entry<K,V>> it = iterator(); 1149 for (int i = 0; i < size; i++) 1150 result[i] = new AbstractMap.SimpleEntry<>(it.next()); 1151 return result; 1152 } 1153 1154 @SuppressWarnings("unchecked") 1155 public <T> T[] toArray(T[] a) { 1156 int size = size(); 1157 if (a.length < size) 1158 a = (T[])java.lang.reflect.Array 1159 .newInstance(a.getClass().getComponentType(), size); 1160 Iterator<Map.Entry<K,V>> it = iterator(); 1161 for (int i = 0; i < size; i++) 1162 a[i] = (T) new AbstractMap.SimpleEntry<>(it.next()); 1163 if (a.length > size) 1164 a[size] = null; 1165 return a; 1166 } 1167 } 1168 1169 1170 private static final long serialVersionUID = 8188218128353913216L; 1171 1172 /** 1173 * Save the state of the <tt>IdentityHashMap</tt> instance to a stream 1174 * (i.e., serialize it). 1175 * 1176 * @serialData The <i>size</i> of the HashMap (the number of key-value 1177 * mappings) (<tt>int</tt>), followed by the key (Object) and 1178 * value (Object) for each key-value mapping represented by the 1179 * IdentityHashMap. The key-value mappings are emitted in no 1180 * particular order. 1181 */ 1182 private void writeObject(java.io.ObjectOutputStream s) 1183 throws java.io.IOException { 1184 // Write out and any hidden stuff 1185 s.defaultWriteObject(); 1186 1187 // Write out size (number of Mappings) 1188 s.writeInt(size); 1189 1190 // Write out keys and values (alternating) 1191 Object[] tab = table; 1192 for (int i = 0; i < tab.length; i += 2) { 1193 Object key = tab[i]; 1194 if (key != null) { 1195 s.writeObject(unmaskNull(key)); 1196 s.writeObject(tab[i + 1]); 1197 } 1198 } 1199 } 1200 1201 /** 1202 * Reconstitute the <tt>IdentityHashMap</tt> instance from a stream (i.e., 1203 * deserialize it). 1204 */ 1205 private void readObject(java.io.ObjectInputStream s) 1206 throws java.io.IOException, ClassNotFoundException { 1207 // Read in any hidden stuff 1208 s.defaultReadObject(); 1209 1210 // Read in size (number of Mappings) 1211 int size = s.readInt(); 1212 1213 // Allow for 33% growth (i.e., capacity is >= 2* size()). 1214 init(capacity((size*4)/3)); 1215 1216 // Read the keys and values, and put the mappings in the table 1217 for (int i=0; i<size; i++) { 1218 K key = (K) s.readObject(); 1219 V value = (V) s.readObject(); 1220 putForCreate(key, value); 1221 } 1222 } 1223 1224 /** 1225 * The put method for readObject. It does not resize the table, 1226 * update modCount, etc. 1227 */ 1228 private void putForCreate(K key, V value) 1229 throws IOException 1230 { 1231 K k = (K)maskNull(key); 1232 Object[] tab = table; 1233 int len = tab.length; 1234 int i = hash(k, len); 1235 1236 Object item; 1237 while ( (item = tab[i]) != null) { 1238 if (item == k) 1239 throw new java.io.StreamCorruptedException(); 1240 i = nextKeyIndex(i, len); 1241 } 1242 tab[i] = k; 1243 tab[i + 1] = value; 1244 } 1245 }