1 /* IdentityHashMap.java -- a class providing a hashtable data structure, 2 mapping Object --> Object, which uses object identity for hashing. 3 Copyright (C) 2001, 2002, 2004, 2005 Free Software Foundation, Inc. 4 5 This file is part of GNU Classpath. 6 7 GNU Classpath is free software; you can redistribute it and/or modify 8 it under the terms of the GNU General Public License as published by 9 the Free Software Foundation; either version 2, or (at your option) 10 any later version. 11 12 GNU Classpath is distributed in the hope that it will be useful, but 13 WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15 General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GNU Classpath; see the file COPYING. If not, write to the 19 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 20 02110-1301 USA. 21 22 Linking this library statically or dynamically with other modules is 23 making a combined work based on this library. Thus, the terms and 24 conditions of the GNU General Public License cover the whole 25 combination. 26 27 As a special exception, the copyright holders of this library give you 28 permission to link this library with independent modules to produce an 29 executable, regardless of the license terms of these independent 30 modules, and to copy and distribute the resulting executable under 31 terms of your choice, provided that you also meet, for each linked 32 independent module, the terms and conditions of the license of that 33 module. An independent module is a module which is not derived from 34 or based on this library. If you modify this library, you may extend 35 this exception to your version of the library, but you are not 36 obligated to do so. If you do not wish to do so, delete this 37 exception statement from your version. */ 38 39 package java.util; 40 41 import java.io.IOException; 42 import java.io.ObjectInputStream; 43 import java.io.ObjectOutputStream; 44 import java.io.Serializable; 45 46 /** 47 * This class provides a hashtable-backed implementation of the 48 * Map interface, but uses object identity to do its hashing. In fact, 49 * it uses object identity for comparing values, as well. It uses a 50 * linear-probe hash table, which may have faster performance 51 * than the chaining employed by HashMap. 52 * <p> 53 * 54 * <em>WARNING: This is not a general purpose map. Because it uses 55 * System.identityHashCode and ==, instead of hashCode and equals, for 56 * comparison, it violated Map's general contract, and may cause 57 * undefined behavior when compared to other maps which are not 58 * IdentityHashMaps. This is designed only for the rare cases when 59 * identity semantics are needed.</em> An example use is 60 * topology-preserving graph transformations, such as deep cloning, 61 * or as proxy object mapping such as in debugging. 62 * <p> 63 * 64 * This map permits <code>null</code> keys and values, and does not 65 * guarantee that elements will stay in the same order over time. The 66 * basic operations (<code>get</code> and <code>put</code>) take 67 * constant time, provided System.identityHashCode is decent. You can 68 * tune the behavior by specifying the expected maximum size. As more 69 * elements are added, the map may need to allocate a larger table, 70 * which can be expensive. 71 * <p> 72 * 73 * This implementation is unsynchronized. If you want multi-thread 74 * access to be consistent, you must synchronize it, perhaps by using 75 * <code>Collections.synchronizedMap(new IdentityHashMap(...));</code>. 76 * The iterators are <i>fail-fast</i>, meaning that a structural modification 77 * made to the map outside of an iterator's remove method cause the 78 * iterator, and in the case of the entrySet, the Map.Entry, to 79 * fail with a {@link ConcurrentModificationException}. 80 * 81 * @author Tom Tromey (tromey@redhat.com) 82 * @author Eric Blake (ebb9@email.byu.edu) 83 * @see System#identityHashCode(Object) 84 * @see Collection 85 * @see Map 86 * @see HashMap 87 * @see TreeMap 88 * @see LinkedHashMap 89 * @see WeakHashMap 90 * @since 1.4 91 * @status updated to 1.4 92 */ 93 public class IdentityHashMap extends AbstractMap 94 implements Map, Serializable, Cloneable 95 { 96 /** The default capacity. */ 97 private static final int DEFAULT_CAPACITY = 21; 98 99 /** 100 * This object is used to mark deleted items. Package visible for use by 101 * nested classes. 102 */ 103 static final Object tombstone = new Object(); 104 105 /** 106 * This object is used to mark empty slots. We need this because 107 * using null is ambiguous. Package visible for use by nested classes. 108 */ 109 static final Object emptyslot = new Object(); 110 111 /** 112 * Compatible with JDK 1.4. 113 */ 114 private static final long serialVersionUID = 8188218128353913216L; 115 116 /** 117 * The number of mappings in the table. Package visible for use by nested 118 * classes. 119 * @serial 120 */ 121 int size; 122 123 /** 124 * The table itself. Package visible for use by nested classes. 125 */ 126 transient Object[] table; 127 128 /** 129 * The number of structural modifications made so far. Package visible for 130 * use by nested classes. 131 */ 132 transient int modCount; 133 134 /** 135 * The cache for {@link #entrySet()}. 136 */ 137 private transient Set entries; 138 139 /** 140 * The threshold for rehashing, which is 75% of (table.length / 2). 141 */ 142 private transient int threshold; 143 144 /** 145 * Create a new IdentityHashMap with the default capacity (21 entries). 146 */ IdentityHashMap()147 public IdentityHashMap() 148 { 149 this(DEFAULT_CAPACITY); 150 } 151 152 /** 153 * Create a new IdentityHashMap with the indicated number of 154 * entries. If the number of elements added to this hash map 155 * exceeds this maximum, the map will grow itself; however, that 156 * incurs a performance penalty. 157 * 158 * @param max initial size 159 * @throws IllegalArgumentException if max is negative 160 */ IdentityHashMap(int max)161 public IdentityHashMap(int max) 162 { 163 if (max < 0) 164 throw new IllegalArgumentException(); 165 // Need at least two slots, or hash() will break. 166 if (max < 2) 167 max = 2; 168 table = new Object[max << 1]; 169 Arrays.fill(table, emptyslot); 170 threshold = (max >> 2) * 3; 171 } 172 173 /** 174 * Create a new IdentityHashMap whose contents are taken from the 175 * given Map. 176 * 177 * @param m The map whose elements are to be put in this map 178 * @throws NullPointerException if m is null 179 */ IdentityHashMap(Map m)180 public IdentityHashMap(Map m) 181 { 182 this(Math.max(m.size() << 1, DEFAULT_CAPACITY)); 183 putAll(m); 184 } 185 186 /** 187 * Remove all mappings from this map. 188 */ clear()189 public void clear() 190 { 191 if (size != 0) 192 { 193 modCount++; 194 Arrays.fill(table, emptyslot); 195 size = 0; 196 } 197 } 198 199 /** 200 * Creates a shallow copy where keys and values are not cloned. 201 */ clone()202 public Object clone() 203 { 204 try 205 { 206 IdentityHashMap copy = (IdentityHashMap) super.clone(); 207 copy.table = (Object[]) table.clone(); 208 copy.entries = null; // invalidate the cache 209 return copy; 210 } 211 catch (CloneNotSupportedException e) 212 { 213 // Can't happen. 214 return null; 215 } 216 } 217 218 /** 219 * Tests whether the specified key is in this map. Unlike normal Maps, 220 * this test uses <code>entry == key</code> instead of 221 * <code>entry == null ? key == null : entry.equals(key)</code>. 222 * 223 * @param key the key to look for 224 * @return true if the key is contained in the map 225 * @see #containsValue(Object) 226 * @see #get(Object) 227 */ containsKey(Object key)228 public boolean containsKey(Object key) 229 { 230 return key == table[hash(key)]; 231 } 232 233 /** 234 * Returns true if this HashMap contains the value. Unlike normal maps, 235 * this test uses <code>entry == value</code> instead of 236 * <code>entry == null ? value == null : entry.equals(value)</code>. 237 * 238 * @param value the value to search for in this HashMap 239 * @return true if at least one key maps to the value 240 * @see #containsKey(Object) 241 */ containsValue(Object value)242 public boolean containsValue(Object value) 243 { 244 for (int i = table.length - 1; i > 0; i -= 2) 245 if (table[i] == value) 246 return true; 247 return false; 248 } 249 250 /** 251 * Returns a "set view" of this Map's entries. The set is backed by 252 * the Map, so changes in one show up in the other. The set supports 253 * element removal, but not element addition. 254 * <p> 255 * 256 * <em>The semantics of this set, and of its contained entries, are 257 * different from the contract of Set and Map.Entry in order to make 258 * IdentityHashMap work. This means that while you can compare these 259 * objects between IdentityHashMaps, comparing them with regular sets 260 * or entries is likely to have undefined behavior.</em> The entries 261 * in this set are reference-based, rather than the normal object 262 * equality. Therefore, <code>e1.equals(e2)</code> returns 263 * <code>e1.getKey() == e2.getKey() && e1.getValue() == e2.getValue()</code>, 264 * and <code>e.hashCode()</code> returns 265 * <code>System.identityHashCode(e.getKey()) ^ 266 * System.identityHashCode(e.getValue())</code>. 267 * <p> 268 * 269 * Note that the iterators for all three views, from keySet(), entrySet(), 270 * and values(), traverse the Map in the same sequence. 271 * 272 * @return a set view of the entries 273 * @see #keySet() 274 * @see #values() 275 * @see Map.Entry 276 */ entrySet()277 public Set entrySet() 278 { 279 if (entries == null) 280 entries = new AbstractSet() 281 { 282 public int size() 283 { 284 return size; 285 } 286 287 public Iterator iterator() 288 { 289 return new IdentityIterator(ENTRIES); 290 } 291 292 public void clear() 293 { 294 IdentityHashMap.this.clear(); 295 } 296 297 public boolean contains(Object o) 298 { 299 if (! (o instanceof Map.Entry)) 300 return false; 301 Map.Entry m = (Map.Entry) o; 302 return m.getValue() == table[hash(m.getKey()) + 1]; 303 } 304 305 public int hashCode() 306 { 307 return IdentityHashMap.this.hashCode(); 308 } 309 310 public boolean remove(Object o) 311 { 312 if (! (o instanceof Map.Entry)) 313 return false; 314 Object key = ((Map.Entry) o).getKey(); 315 int h = hash(key); 316 if (table[h] == key) 317 { 318 size--; 319 modCount++; 320 table[h] = tombstone; 321 table[h + 1] = tombstone; 322 return true; 323 } 324 return false; 325 } 326 }; 327 return entries; 328 } 329 330 /** 331 * Compares two maps for equality. This returns true only if both maps 332 * have the same reference-identity comparisons. While this returns 333 * <code>this.entrySet().equals(m.entrySet())</code> as specified by Map, 334 * this will not work with normal maps, since the entry set compares 335 * with == instead of .equals. 336 * 337 * @param o the object to compare to 338 * @return true if it is equal 339 */ equals(Object o)340 public boolean equals(Object o) 341 { 342 // Why did Sun specify this one? The superclass does the right thing. 343 return super.equals(o); 344 } 345 346 /** 347 * Return the value in this Map associated with the supplied key, or 348 * <code>null</code> if the key maps to nothing. 349 * 350 * <p>NOTE: Since the value could also be null, you must use 351 * containsKey to see if this key actually maps to something. 352 * Unlike normal maps, this tests for the key with <code>entry == 353 * key</code> instead of <code>entry == null ? key == null : 354 * entry.equals(key)</code>. 355 * 356 * @param key the key for which to fetch an associated value 357 * @return what the key maps to, if present 358 * @see #put(Object, Object) 359 * @see #containsKey(Object) 360 */ get(Object key)361 public Object get(Object key) 362 { 363 int h = hash(key); 364 return table[h] == key ? table[h + 1] : null; 365 } 366 367 /** 368 * Returns the hashcode of this map. This guarantees that two 369 * IdentityHashMaps that compare with equals() will have the same hash code, 370 * but may break with comparison to normal maps since it uses 371 * System.identityHashCode() instead of hashCode(). 372 * 373 * @return the hash code 374 */ hashCode()375 public int hashCode() 376 { 377 int hash = 0; 378 for (int i = table.length - 2; i >= 0; i -= 2) 379 { 380 Object key = table[i]; 381 if (key == emptyslot || key == tombstone) 382 continue; 383 hash += (System.identityHashCode(key) 384 ^ System.identityHashCode(table[i + 1])); 385 } 386 return hash; 387 } 388 389 /** 390 * Returns true if there are no key-value mappings currently in this Map 391 * @return <code>size() == 0</code> 392 */ isEmpty()393 public boolean isEmpty() 394 { 395 return size == 0; 396 } 397 398 /** 399 * Returns a "set view" of this Map's keys. The set is backed by the 400 * Map, so changes in one show up in the other. The set supports 401 * element removal, but not element addition. 402 * <p> 403 * 404 * <em>The semantics of this set are different from the contract of Set 405 * in order to make IdentityHashMap work. This means that while you can 406 * compare these objects between IdentityHashMaps, comparing them with 407 * regular sets is likely to have undefined behavior.</em> The hashCode 408 * of the set is the sum of the identity hash codes, instead of the 409 * regular hashCodes, and equality is determined by reference instead 410 * of by the equals method. 411 * <p> 412 * 413 * @return a set view of the keys 414 * @see #values() 415 * @see #entrySet() 416 */ keySet()417 public Set keySet() 418 { 419 if (keys == null) 420 keys = new AbstractSet() 421 { 422 public int size() 423 { 424 return size; 425 } 426 427 public Iterator iterator() 428 { 429 return new IdentityIterator(KEYS); 430 } 431 432 public void clear() 433 { 434 IdentityHashMap.this.clear(); 435 } 436 437 public boolean contains(Object o) 438 { 439 return containsKey(o); 440 } 441 442 public int hashCode() 443 { 444 int hash = 0; 445 for (int i = table.length - 2; i >= 0; i -= 2) 446 { 447 Object key = table[i]; 448 if (key == emptyslot || key == tombstone) 449 continue; 450 hash += System.identityHashCode(key); 451 } 452 return hash; 453 454 } 455 456 public boolean remove(Object o) 457 { 458 int h = hash(o); 459 if (table[h] == o) 460 { 461 size--; 462 modCount++; 463 table[h] = tombstone; 464 table[h + 1] = tombstone; 465 return true; 466 } 467 return false; 468 } 469 }; 470 return keys; 471 } 472 473 /** 474 * Puts the supplied value into the Map, mapped by the supplied key. 475 * The value may be retrieved by any object which <code>equals()</code> 476 * this key. NOTE: Since the prior value could also be null, you must 477 * first use containsKey if you want to see if you are replacing the 478 * key's mapping. Unlike normal maps, this tests for the key 479 * with <code>entry == key</code> instead of 480 * <code>entry == null ? key == null : entry.equals(key)</code>. 481 * 482 * @param key the key used to locate the value 483 * @param value the value to be stored in the HashMap 484 * @return the prior mapping of the key, or null if there was none 485 * @see #get(Object) 486 */ put(Object key, Object value)487 public Object put(Object key, Object value) 488 { 489 // Rehash if the load factor is too high. 490 if (size > threshold) 491 { 492 Object[] old = table; 493 // This isn't necessarily prime, but it is an odd number of key/value 494 // slots, which has a higher probability of fewer collisions. 495 table = new Object[(old.length * 2) + 2]; 496 Arrays.fill(table, emptyslot); 497 size = 0; 498 threshold = (table.length >>> 3) * 3; 499 500 for (int i = old.length - 2; i >= 0; i -= 2) 501 { 502 Object oldkey = old[i]; 503 if (oldkey != tombstone && oldkey != emptyslot) 504 // Just use put. This isn't very efficient, but it is ok. 505 put(oldkey, old[i + 1]); 506 } 507 } 508 509 int h = hash(key); 510 if (table[h] == key) 511 { 512 Object r = table[h + 1]; 513 table[h + 1] = value; 514 return r; 515 } 516 517 // At this point, we add a new mapping. 518 modCount++; 519 size++; 520 table[h] = key; 521 table[h + 1] = value; 522 return null; 523 } 524 525 /** 526 * Copies all of the mappings from the specified map to this. If a key 527 * is already in this map, its value is replaced. 528 * 529 * @param m the map to copy 530 * @throws NullPointerException if m is null 531 */ putAll(Map m)532 public void putAll(Map m) 533 { 534 // Why did Sun specify this one? The superclass does the right thing. 535 super.putAll(m); 536 } 537 538 /** 539 * Removes from the HashMap and returns the value which is mapped by 540 * the supplied key. If the key maps to nothing, then the HashMap 541 * remains unchanged, and <code>null</code> is returned. 542 * 543 * NOTE: Since the value could also be null, you must use 544 * containsKey to see if you are actually removing a mapping. 545 * Unlike normal maps, this tests for the key with <code>entry == 546 * key</code> instead of <code>entry == null ? key == null : 547 * entry.equals(key)</code>. 548 * 549 * @param key the key used to locate the value to remove 550 * @return whatever the key mapped to, if present 551 */ remove(Object key)552 public Object remove(Object key) 553 { 554 int h = hash(key); 555 if (table[h] == key) 556 { 557 modCount++; 558 size--; 559 Object r = table[h + 1]; 560 table[h] = tombstone; 561 table[h + 1] = tombstone; 562 return r; 563 } 564 return null; 565 } 566 567 /** 568 * Returns the number of kay-value mappings currently in this Map 569 * @return the size 570 */ size()571 public int size() 572 { 573 return size; 574 } 575 576 /** 577 * Returns a "collection view" (or "bag view") of this Map's values. 578 * The collection is backed by the Map, so changes in one show up 579 * in the other. The collection supports element removal, but not element 580 * addition. 581 * <p> 582 * 583 * <em>The semantics of this set are different from the contract of 584 * Collection in order to make IdentityHashMap work. This means that 585 * while you can compare these objects between IdentityHashMaps, comparing 586 * them with regular sets is likely to have undefined behavior.</em> 587 * Likewise, contains and remove go by == instead of equals(). 588 * <p> 589 * 590 * @return a bag view of the values 591 * @see #keySet() 592 * @see #entrySet() 593 */ values()594 public Collection values() 595 { 596 if (values == null) 597 values = new AbstractCollection() 598 { 599 public int size() 600 { 601 return size; 602 } 603 604 public Iterator iterator() 605 { 606 return new IdentityIterator(VALUES); 607 } 608 609 public void clear() 610 { 611 IdentityHashMap.this.clear(); 612 } 613 614 public boolean remove(Object o) 615 { 616 for (int i = table.length - 1; i > 0; i -= 2) 617 if (table[i] == o) 618 { 619 modCount++; 620 table[i - 1] = tombstone; 621 table[i] = tombstone; 622 size--; 623 return true; 624 } 625 return false; 626 } 627 }; 628 return values; 629 } 630 631 /** 632 * Helper method which computes the hash code, then traverses the table 633 * until it finds the key, or the spot where the key would go. 634 * 635 * @param key the key to check 636 * @return the index where the key belongs 637 * @see #IdentityHashMap(int) 638 * @see #put(Object, Object) 639 */ 640 // Package visible for use by nested classes. hash(Object key)641 int hash(Object key) 642 { 643 // Implementation note: it is feasible for the table to have no 644 // emptyslots, if it is full with entries and tombstones, so we must 645 // remember where we started. If we encounter the key or an emptyslot, 646 // we are done. If we encounter a tombstone, the key may still be in 647 // the array. If we don't encounter the key, we use the first emptyslot 648 // or tombstone we encountered as the location where the key would go. 649 // By requiring at least 2 key/value slots, and rehashing at 75% 650 // capacity, we guarantee that there will always be either an emptyslot 651 // or a tombstone somewhere in the table. 652 int h = Math.abs(System.identityHashCode(key) % (table.length >> 1)) << 1; 653 int del = -1; 654 int save = h; 655 656 do 657 { 658 if (table[h] == key) 659 return h; 660 if (table[h] == emptyslot) 661 break; 662 if (table[h] == tombstone && del < 0) 663 del = h; 664 h -= 2; 665 if (h < 0) 666 h = table.length - 2; 667 } 668 while (h != save); 669 670 return del < 0 ? h : del; 671 } 672 673 /** 674 * This class allows parameterized iteration over IdentityHashMaps. Based 675 * on its construction, it returns the key or value of a mapping, or 676 * creates the appropriate Map.Entry object with the correct fail-fast 677 * semantics and identity comparisons. 678 * 679 * @author Tom Tromey (tromey@redhat.com) 680 * @author Eric Blake (ebb9@email.byu.edu) 681 */ 682 private class IdentityIterator implements Iterator 683 { 684 /** 685 * The type of this Iterator: {@link #KEYS}, {@link #VALUES}, 686 * or {@link #ENTRIES}. 687 */ 688 final int type; 689 /** The number of modifications to the backing Map that we know about. */ 690 int knownMod = modCount; 691 /** The number of elements remaining to be returned by next(). */ 692 int count = size; 693 /** Location in the table. */ 694 int loc = table.length; 695 696 /** 697 * Construct a new Iterator with the supplied type. 698 * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES} 699 */ IdentityIterator(int type)700 IdentityIterator(int type) 701 { 702 this.type = type; 703 } 704 705 /** 706 * Returns true if the Iterator has more elements. 707 * @return true if there are more elements 708 * @throws ConcurrentModificationException if the Map was modified 709 */ hasNext()710 public boolean hasNext() 711 { 712 if (knownMod != modCount) 713 throw new ConcurrentModificationException(); 714 return count > 0; 715 } 716 717 /** 718 * Returns the next element in the Iterator's sequential view. 719 * @return the next element 720 * @throws ConcurrentModificationException if the Map was modified 721 * @throws NoSuchElementException if there is none 722 */ next()723 public Object next() 724 { 725 if (knownMod != modCount) 726 throw new ConcurrentModificationException(); 727 if (count == 0) 728 throw new NoSuchElementException(); 729 count--; 730 731 Object key; 732 do 733 { 734 loc -= 2; 735 key = table[loc]; 736 } 737 while (key == emptyslot || key == tombstone); 738 739 return type == KEYS ? key : (type == VALUES ? table[loc + 1] 740 : new IdentityEntry(loc)); 741 } 742 743 /** 744 * Removes from the backing Map the last element which was fetched 745 * with the <code>next()</code> method. 746 * 747 * @throws ConcurrentModificationException if the Map was modified 748 * @throws IllegalStateException if called when there is no last element 749 */ remove()750 public void remove() 751 { 752 if (knownMod != modCount) 753 throw new ConcurrentModificationException(); 754 if (loc == table.length || table[loc] == tombstone) 755 throw new IllegalStateException(); 756 modCount++; 757 size--; 758 table[loc] = tombstone; 759 table[loc + 1] = tombstone; 760 knownMod++; 761 } 762 } // class IdentityIterator 763 764 /** 765 * This class provides Map.Entry objects for IdentityHashMaps. The entry 766 * is fail-fast, and will throw a ConcurrentModificationException if 767 * the underlying map is modified, or if remove is called on the iterator 768 * that generated this object. It is identity based, so it violates 769 * the general contract of Map.Entry, and is probably unsuitable for 770 * comparison to normal maps; but it works among other IdentityHashMaps. 771 * 772 * @author Eric Blake (ebb9@email.byu.edu) 773 */ 774 private final class IdentityEntry implements Map.Entry 775 { 776 /** The location of this entry. */ 777 final int loc; 778 /** The number of modifications to the backing Map that we know about. */ 779 final int knownMod = modCount; 780 781 /** 782 * Constructs the Entry. 783 * 784 * @param loc the location of this entry in table 785 */ IdentityEntry(int loc)786 IdentityEntry(int loc) 787 { 788 this.loc = loc; 789 } 790 791 /** 792 * Compares the specified object with this entry, using identity 793 * semantics. Note that this can lead to undefined results with 794 * Entry objects created by normal maps. 795 * 796 * @param o the object to compare 797 * @return true if it is equal 798 * @throws ConcurrentModificationException if the entry was invalidated 799 * by modifying the Map or calling Iterator.remove() 800 */ equals(Object o)801 public boolean equals(Object o) 802 { 803 if (knownMod != modCount || table[loc] == tombstone) 804 throw new ConcurrentModificationException(); 805 if (! (o instanceof Map.Entry)) 806 return false; 807 Map.Entry e = (Map.Entry) o; 808 return table[loc] == e.getKey() && table[loc + 1] == e.getValue(); 809 } 810 811 /** 812 * Returns the key of this entry. 813 * 814 * @return the key 815 * @throws ConcurrentModificationException if the entry was invalidated 816 * by modifying the Map or calling Iterator.remove() 817 */ getKey()818 public Object getKey() 819 { 820 if (knownMod != modCount || table[loc] == tombstone) 821 throw new ConcurrentModificationException(); 822 return table[loc]; 823 } 824 825 /** 826 * Returns the value of this entry. 827 * 828 * @return the value 829 * @throws ConcurrentModificationException if the entry was invalidated 830 * by modifying the Map or calling Iterator.remove() 831 */ getValue()832 public Object getValue() 833 { 834 if (knownMod != modCount || table[loc] == tombstone) 835 throw new ConcurrentModificationException(); 836 return table[loc + 1]; 837 } 838 839 /** 840 * Returns the hashcode of the entry, using identity semantics. 841 * Note that this can lead to undefined results with Entry objects 842 * created by normal maps. 843 * 844 * @return the hash code 845 * @throws ConcurrentModificationException if the entry was invalidated 846 * by modifying the Map or calling Iterator.remove() 847 */ hashCode()848 public int hashCode() 849 { 850 if (knownMod != modCount || table[loc] == tombstone) 851 throw new ConcurrentModificationException(); 852 return (System.identityHashCode(table[loc]) 853 ^ System.identityHashCode(table[loc + 1])); 854 } 855 856 /** 857 * Replaces the value of this mapping, and returns the old value. 858 * 859 * @param value the new value 860 * @return the old value 861 * @throws ConcurrentModificationException if the entry was invalidated 862 * by modifying the Map or calling Iterator.remove() 863 */ setValue(Object value)864 public Object setValue(Object value) 865 { 866 if (knownMod != modCount || table[loc] == tombstone) 867 throw new ConcurrentModificationException(); 868 Object r = table[loc + 1]; 869 table[loc + 1] = value; 870 return r; 871 } 872 873 /** 874 * This provides a string representation of the entry. It is of the form 875 * "key=value", where string concatenation is used on key and value. 876 * 877 * @return the string representation 878 * @throws ConcurrentModificationException if the entry was invalidated 879 * by modifying the Map or calling Iterator.remove() 880 */ toString()881 public String toString() 882 { 883 if (knownMod != modCount || table[loc] == tombstone) 884 throw new ConcurrentModificationException(); 885 return table[loc] + "=" + table[loc + 1]; 886 } 887 } // class IdentityEntry 888 889 /** 890 * Reads the object from a serial stream. 891 * 892 * @param s the stream to read from 893 * @throws ClassNotFoundException if the underlying stream fails 894 * @throws IOException if the underlying stream fails 895 * @serialData expects the size (int), followed by that many key (Object) 896 * and value (Object) pairs, with the pairs in no particular 897 * order 898 */ readObject(ObjectInputStream s)899 private void readObject(ObjectInputStream s) 900 throws IOException, ClassNotFoundException 901 { 902 s.defaultReadObject(); 903 904 int num = s.readInt(); 905 table = new Object[Math.max(num << 1, DEFAULT_CAPACITY) << 1]; 906 // Read key/value pairs. 907 while (--num >= 0) 908 put(s.readObject(), s.readObject()); 909 } 910 911 /** 912 * Writes the object to a serial stream. 913 * 914 * @param s the stream to write to 915 * @throws IOException if the underlying stream fails 916 * @serialData outputs the size (int), followed by that many key (Object) 917 * and value (Object) pairs, with the pairs in no particular 918 * order 919 */ writeObject(ObjectOutputStream s)920 private void writeObject(ObjectOutputStream s) 921 throws IOException 922 { 923 s.defaultWriteObject(); 924 s.writeInt(size); 925 for (int i = table.length - 2; i >= 0; i -= 2) 926 { 927 Object key = table[i]; 928 if (key != tombstone && key != emptyslot) 929 { 930 s.writeObject(key); 931 s.writeObject(table[i + 1]); 932 } 933 } 934 } 935 } 936