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