IdentityHashMap.java revision f5597e626ecf7949d249dea08c1a2964d890ec11
1/* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18package java.util; 19 20import java.io.IOException; 21import java.io.ObjectInputStream; 22import java.io.ObjectOutputStream; 23import java.io.Serializable; 24 25/** 26 * IdentityHashMap is a variant on HashMap which tests equality by reference 27 * instead of equality by value. Basically, keys and values are compared for 28 * equality by checking if their references are equal rather than by calling the 29 * "equals" function. 30 * <p> 31 * <b>Note: This class intentionally violates the general contract of {@code 32 * Map}'s on comparing objects by their {@code equals} method.</b> 33 * <p> 34 * IdentityHashMap uses open addressing (linear probing in particular) for 35 * collision resolution. This is different from HashMap which uses Chaining. 36 * <p> 37 * Like HashMap, IdentityHashMap is not thread safe, so access by multiple 38 * threads must be synchronized by an external mechanism such as 39 * Collections.synchronizedMap. 40 * 41 * @since 1.4 42 */ 43public class IdentityHashMap<K, V> extends AbstractMap<K, V> implements 44 Map<K, V>, Serializable, Cloneable { 45 46 private static final long serialVersionUID = 8188218128353913216L; 47 48 /* 49 * The internal data structure to hold key value pairs This array holds keys 50 * and values in an alternating fashion. 51 */ 52 transient Object[] elementData; 53 54 /* Actual number of key-value pairs. */ 55 int size; 56 57 /* 58 * maximum number of elements that can be put in this map before having to 59 * rehash. 60 */ 61 transient int threshold; 62 63 /* 64 * default threshold value that an IdentityHashMap created using the default 65 * constructor would have. 66 */ 67 private static final int DEFAULT_MAX_SIZE = 21; 68 69 /* Default load factor of 0.75; */ 70 private static final int loadFactor = 7500; 71 72 /* 73 * modification count, to keep track of structural modifications between the 74 * IdentityHashMap and the iterator 75 */ 76 transient int modCount = 0; 77 78 /* 79 * Object used to represent null keys and values. This is used to 80 * differentiate a literal 'null' key value pair from an empty spot in the 81 * map. 82 */ 83 private static final Object NULL_OBJECT = new Object(); //$NON-LOCK-1$ 84 85 static class IdentityHashMapEntry<K, V> extends MapEntry<K, V> { 86 IdentityHashMapEntry(K theKey, V theValue) { 87 super(theKey, theValue); 88 } 89 90 @Override 91 public Object clone() { 92 return super.clone(); 93 } 94 95 @Override 96 public boolean equals(Object object) { 97 if (this == object) { 98 return true; 99 } 100 if (object instanceof Map.Entry) { 101 Map.Entry<?, ?> entry = (Map.Entry) object; 102 return (key == entry.getKey()) && (value == entry.getValue()); 103 } 104 return false; 105 } 106 107 @Override 108 public int hashCode() { 109 return System.identityHashCode(key) 110 ^ System.identityHashCode(value); 111 } 112 113 @Override 114 public String toString() { 115 return key + "=" + value; //$NON-NLS-1$ 116 } 117 } 118 119 static class IdentityHashMapIterator<E, KT, VT> implements Iterator<E> { 120 private int position = 0; // the current position 121 122 // the position of the entry that was last returned from next() 123 private int lastPosition = 0; 124 125 final IdentityHashMap<KT, VT> associatedMap; 126 127 int expectedModCount; 128 129 final MapEntry.Type<E, KT, VT> type; 130 131 boolean canRemove = false; 132 133 IdentityHashMapIterator(MapEntry.Type<E, KT, VT> value, 134 IdentityHashMap<KT, VT> hm) { 135 associatedMap = hm; 136 type = value; 137 expectedModCount = hm.modCount; 138 } 139 140 public boolean hasNext() { 141 while (position < associatedMap.elementData.length) { 142 // if this is an empty spot, go to the next one 143 if (associatedMap.elementData[position] == null) { 144 position += 2; 145 } else { 146 return true; 147 } 148 } 149 return false; 150 } 151 152 void checkConcurrentMod() throws ConcurrentModificationException { 153 if (expectedModCount != associatedMap.modCount) { 154 throw new ConcurrentModificationException(); 155 } 156 } 157 158 public E next() { 159 checkConcurrentMod(); 160 if (!hasNext()) { 161 throw new NoSuchElementException(); 162 } 163 164 IdentityHashMapEntry<KT, VT> result = associatedMap 165 .getEntry(position); 166 lastPosition = position; 167 position += 2; 168 169 canRemove = true; 170 return type.get(result); 171 } 172 173 public void remove() { 174 checkConcurrentMod(); 175 if (!canRemove) { 176 throw new IllegalStateException(); 177 } 178 179 canRemove = false; 180 associatedMap.remove(associatedMap.elementData[lastPosition]); 181 position = lastPosition; 182 expectedModCount++; 183 } 184 } 185 186 static class IdentityHashMapEntrySet<KT, VT> extends 187 AbstractSet<Map.Entry<KT, VT>> { 188 private final IdentityHashMap<KT, VT> associatedMap; 189 190 public IdentityHashMapEntrySet(IdentityHashMap<KT, VT> hm) { 191 associatedMap = hm; 192 } 193 194 IdentityHashMap<KT, VT> hashMap() { 195 return associatedMap; 196 } 197 198 @Override 199 public int size() { 200 return associatedMap.size; 201 } 202 203 @Override 204 public void clear() { 205 associatedMap.clear(); 206 } 207 208 @Override 209 public boolean remove(Object object) { 210 if (contains(object)) { 211 associatedMap.remove(((Map.Entry) object).getKey()); 212 return true; 213 } 214 return false; 215 } 216 217 @Override 218 public boolean contains(Object object) { 219 if (object instanceof Map.Entry) { 220 IdentityHashMapEntry<?, ?> entry = associatedMap 221 .getEntry(((Map.Entry) object).getKey()); 222 // we must call equals on the entry obtained from "this" 223 return entry != null && entry.equals(object); 224 } 225 return false; 226 } 227 228 @Override 229 public Iterator<Map.Entry<KT, VT>> iterator() { 230 return new IdentityHashMapIterator<Map.Entry<KT, VT>, KT, VT>( 231 new MapEntry.Type<Map.Entry<KT, VT>, KT, VT>() { 232 public Map.Entry<KT, VT> get(MapEntry<KT, VT> entry) { 233 return entry; 234 } 235 }, associatedMap); 236 } 237 } 238 239 /** 240 * Creates an IdentityHashMap with default expected maximum size. 241 */ 242 public IdentityHashMap() { 243 this(DEFAULT_MAX_SIZE); 244 } 245 246 /** 247 * Creates an IdentityHashMap with the specified maximum size parameter. 248 * 249 * @param maxSize 250 * The estimated maximum number of entries that will be put in 251 * this map. 252 */ 253 public IdentityHashMap(int maxSize) { 254 if (maxSize >= 0) { 255 this.size = 0; 256 threshold = getThreshold(maxSize); 257 elementData = newElementArray(computeElementArraySize()); 258 } else { 259 throw new IllegalArgumentException(); 260 } 261 } 262 263 private int getThreshold(int maxSize) { 264 // assign the threshold to maxSize initially, this will change to a 265 // higher value if rehashing occurs. 266 return maxSize > 3 ? maxSize : 3; 267 } 268 269 private int computeElementArraySize() { 270 return (int) (((long) threshold * 10000) / loadFactor) * 2; 271 } 272 273 /** 274 * Create a new element array 275 * 276 * @param s 277 * the number of elements 278 * @return Reference to the element array 279 */ 280 private Object[] newElementArray(int s) { 281 return new Object[s]; 282 } 283 284 /** 285 * Creates an IdentityHashMap using the given map as initial values. 286 * 287 * @param map 288 * A map of (key,value) pairs to copy into the IdentityHashMap. 289 */ 290 public IdentityHashMap(Map<? extends K, ? extends V> map) { 291 this(map.size() < 6 ? 11 : map.size() * 2); 292 putAllImpl(map); 293 } 294 295 @SuppressWarnings("unchecked") 296 private V massageValue(Object value) { 297 return (V) ((value == NULL_OBJECT) ? null : value); 298 } 299 300 /** 301 * Removes all elements from this map, leaving it empty. 302 * 303 * @see #isEmpty() 304 * @see #size() 305 */ 306 @Override 307 public void clear() { 308 size = 0; 309 for (int i = 0; i < elementData.length; i++) { 310 elementData[i] = null; 311 } 312 modCount++; 313 } 314 315 /** 316 * Returns whether this map contains the specified key. 317 * 318 * @param key 319 * the key to search for. 320 * @return {@code true} if this map contains the specified key, 321 * {@code false} otherwise. 322 */ 323 @Override 324 public boolean containsKey(Object key) { 325 if (key == null) { 326 key = NULL_OBJECT; 327 } 328 329 int index = findIndex(key, elementData); 330 return elementData[index] == key; 331 } 332 333 /** 334 * Returns whether this map contains the specified value. 335 * 336 * @param value 337 * the value to search for. 338 * @return {@code true} if this map contains the specified value, 339 * {@code false} otherwise. 340 */ 341 @Override 342 public boolean containsValue(Object value) { 343 if (value == null) { 344 value = NULL_OBJECT; 345 } 346 347 for (int i = 1; i < elementData.length; i = i + 2) { 348 if (elementData[i] == value) { 349 return true; 350 } 351 } 352 return false; 353 } 354 355 /** 356 * Returns the value of the mapping with the specified key. 357 * 358 * @param key 359 * the key. 360 * @return the value of the mapping with the specified key. 361 */ 362 @Override 363 public V get(Object key) { 364 if (key == null) { 365 key = NULL_OBJECT; 366 } 367 368 int index = findIndex(key, elementData); 369 370 if (elementData[index] == key) { 371 Object result = elementData[index + 1]; 372 return massageValue(result); 373 } 374 375 return null; 376 } 377 378 private IdentityHashMapEntry<K, V> getEntry(Object key) { 379 if (key == null) { 380 key = NULL_OBJECT; 381 } 382 383 int index = findIndex(key, elementData); 384 if (elementData[index] == key) { 385 return getEntry(index); 386 } 387 388 return null; 389 } 390 391 /** 392 * Convenience method for getting the IdentityHashMapEntry without the 393 * NULL_OBJECT elements 394 */ 395 @SuppressWarnings("unchecked") 396 private IdentityHashMapEntry<K, V> getEntry(int index) { 397 Object key = elementData[index]; 398 Object value = elementData[index + 1]; 399 400 if (key == NULL_OBJECT) { 401 key = null; 402 } 403 if (value == NULL_OBJECT) { 404 value = null; 405 } 406 407 return new IdentityHashMapEntry<K, V>((K) key, (V) value); 408 } 409 410 /** 411 * Returns the index where the key is found at, or the index of the next 412 * empty spot if the key is not found in this table. 413 */ 414 private int findIndex(Object key, Object[] array) { 415 int length = array.length; 416 int index = getModuloHash(key, length); 417 int last = (index + length - 2) % length; 418 while (index != last) { 419 if (array[index] == key || (array[index] == null)) { 420 /* 421 * Found the key, or the next empty spot (which means key is not 422 * in the table) 423 */ 424 break; 425 } 426 index = (index + 2) % length; 427 } 428 return index; 429 } 430 431 private int getModuloHash(Object key, int length) { 432 return ((System.identityHashCode(key) & 0x7FFFFFFF) % (length / 2)) * 2; 433 } 434 435 /** 436 * Maps the specified key to the specified value. 437 * 438 * @param key 439 * the key. 440 * @param value 441 * the value. 442 * @return the value of any previous mapping with the specified key or 443 * {@code null} if there was no such mapping. 444 */ 445 @Override 446 public V put(K key, V value) { 447 Object _key = key; 448 Object _value = value; 449 if (_key == null) { 450 _key = NULL_OBJECT; 451 } 452 453 if (_value == null) { 454 _value = NULL_OBJECT; 455 } 456 457 int index = findIndex(_key, elementData); 458 459 // if the key doesn't exist in the table 460 if (elementData[index] != _key) { 461 modCount++; 462 if (++size > threshold) { 463 rehash(); 464 index = findIndex(_key, elementData); 465 } 466 467 // insert the key and assign the value to null initially 468 elementData[index] = _key; 469 elementData[index + 1] = null; 470 } 471 472 // insert value to where it needs to go, return the old value 473 Object result = elementData[index + 1]; 474 elementData[index + 1] = _value; 475 476 return massageValue(result); 477 } 478 479 /** 480 * Copies all the mappings in the specified map to this map. These mappings 481 * will replace all mappings that this map had for any of the keys currently 482 * in the given map. 483 * 484 * @param map 485 * the map to copy mappings from. 486 * @throws NullPointerException 487 * if {@code map} is {@code null}. 488 */ 489 @Override 490 public void putAll(Map<? extends K, ? extends V> map) { 491 putAllImpl(map); 492 } 493 494 private void rehash() { 495 int newlength = elementData.length << 1; 496 if (newlength == 0) { 497 newlength = 1; 498 } 499 Object[] newData = newElementArray(newlength); 500 for (int i = 0; i < elementData.length; i = i + 2) { 501 Object key = elementData[i]; 502 if (key != null) { 503 // if not empty 504 int index = findIndex(key, newData); 505 newData[index] = key; 506 newData[index + 1] = elementData[i + 1]; 507 } 508 } 509 elementData = newData; 510 computeMaxSize(); 511 } 512 513 private void computeMaxSize() { 514 threshold = (int) ((long) (elementData.length / 2) * loadFactor / 10000); 515 } 516 517 /** 518 * Removes the mapping with the specified key from this map. 519 * 520 * @param key 521 * the key of the mapping to remove. 522 * @return the value of the removed mapping, or {@code null} if no mapping 523 * for the specified key was found. 524 */ 525 @Override 526 public V remove(Object key) { 527 if (key == null) { 528 key = NULL_OBJECT; 529 } 530 531 boolean hashedOk; 532 int index, next, hash; 533 Object result, object; 534 index = next = findIndex(key, elementData); 535 536 if (elementData[index] != key) { 537 return null; 538 } 539 540 // store the value for this key 541 result = elementData[index + 1]; 542 543 // shift the following elements up if needed 544 // until we reach an empty spot 545 int length = elementData.length; 546 while (true) { 547 next = (next + 2) % length; 548 object = elementData[next]; 549 if (object == null) { 550 break; 551 } 552 553 hash = getModuloHash(object, length); 554 hashedOk = hash > index; 555 if (next < index) { 556 hashedOk = hashedOk || (hash <= next); 557 } else { 558 hashedOk = hashedOk && (hash <= next); 559 } 560 if (!hashedOk) { 561 elementData[index] = object; 562 elementData[index + 1] = elementData[next + 1]; 563 index = next; 564 } 565 } 566 567 size--; 568 modCount++; 569 570 // clear both the key and the value 571 elementData[index] = null; 572 elementData[index + 1] = null; 573 574 return massageValue(result); 575 } 576 577 /** 578 * Returns a set containing all of the mappings in this map. Each mapping is 579 * an instance of {@link Map.Entry}. As the set is backed by this map, 580 * changes in one will be reflected in the other. 581 * 582 * @return a set of the mappings. 583 */ 584 @Override 585 public Set<Map.Entry<K, V>> entrySet() { 586 return new IdentityHashMapEntrySet<K, V>(this); 587 } 588 589 /** 590 * Returns a set of the keys contained in this map. The set is backed by 591 * this map so changes to one are reflected by the other. The set does not 592 * support adding. 593 * 594 * @return a set of the keys. 595 */ 596 @Override 597 public Set<K> keySet() { 598 if (keySet == null) { 599 keySet = new AbstractSet<K>() { 600 @Override 601 public boolean contains(Object object) { 602 return containsKey(object); 603 } 604 605 @Override 606 public int size() { 607 return IdentityHashMap.this.size(); 608 } 609 610 @Override 611 public void clear() { 612 IdentityHashMap.this.clear(); 613 } 614 615 @Override 616 public boolean remove(Object key) { 617 if (containsKey(key)) { 618 IdentityHashMap.this.remove(key); 619 return true; 620 } 621 return false; 622 } 623 624 @Override 625 public Iterator<K> iterator() { 626 return new IdentityHashMapIterator<K, K, V>( 627 new MapEntry.Type<K, K, V>() { 628 public K get(MapEntry<K, V> entry) { 629 return entry.key; 630 } 631 }, IdentityHashMap.this); 632 } 633 }; 634 } 635 return keySet; 636 } 637 638 /** 639 * Returns a collection of the values contained in this map. The collection 640 * is backed by this map so changes to one are reflected by the other. The 641 * collection supports remove, removeAll, retainAll and clear operations, 642 * and it does not support add or addAll operations. 643 * <p> 644 * This method returns a collection which is the subclass of 645 * AbstractCollection. The iterator method of this subclass returns a 646 * "wrapper object" over the iterator of map's entrySet(). The {@code size} 647 * method wraps the map's size method and the {@code contains} method wraps 648 * the map's containsValue method. 649 * <p> 650 * The collection is created when this method is called for the first time 651 * and returned in response to all subsequent calls. This method may return 652 * different collections when multiple concurrent calls occur, since no 653 * synchronization is performed. 654 * 655 * @return a collection of the values contained in this map. 656 */ 657 @Override 658 public Collection<V> values() { 659 if (valuesCollection == null) { 660 valuesCollection = new AbstractCollection<V>() { 661 @Override 662 public boolean contains(Object object) { 663 return containsValue(object); 664 } 665 666 @Override 667 public int size() { 668 return IdentityHashMap.this.size(); 669 } 670 671 @Override 672 public void clear() { 673 IdentityHashMap.this.clear(); 674 } 675 676 @Override 677 public Iterator<V> iterator() { 678 return new IdentityHashMapIterator<V, K, V>( 679 new MapEntry.Type<V, K, V>() { 680 public V get(MapEntry<K, V> entry) { 681 return entry.value; 682 } 683 }, IdentityHashMap.this); 684 } 685 686 @Override 687 public boolean remove(Object object) { 688 Iterator<?> it = iterator(); 689 while (it.hasNext()) { 690 if (object == it.next()) { 691 it.remove(); 692 return true; 693 } 694 } 695 return false; 696 } 697 }; 698 } 699 return valuesCollection; 700 } 701 702 /** 703 * Compares this map with other objects. This map is equal to another map is 704 * it represents the same set of mappings. With this map, two mappings are 705 * the same if both the key and the value are equal by reference. When 706 * compared with a map that is not an IdentityHashMap, the equals method is 707 * neither necessarily symmetric (a.equals(b) implies b.equals(a)) nor 708 * transitive (a.equals(b) and b.equals(c) implies a.equals(c)). 709 * 710 * @param object 711 * the object to compare to. 712 * @return whether the argument object is equal to this object. 713 */ 714 @Override 715 public boolean equals(Object object) { 716 /* 717 * We need to override the equals method in AbstractMap because 718 * AbstractMap.equals will call ((Map) object).entrySet().contains() to 719 * determine equality of the entries, so it will defer to the argument 720 * for comparison, meaning that reference-based comparison will not take 721 * place. We must ensure that all comparison is implemented by methods 722 * in this class (or in one of our inner classes) for reference-based 723 * comparison to take place. 724 */ 725 if (this == object) { 726 return true; 727 } 728 if (object instanceof Map) { 729 Map<?, ?> map = (Map) object; 730 if (size() != map.size()) { 731 return false; 732 } 733 734 Set<Map.Entry<K, V>> set = entrySet(); 735 // ensure we use the equals method of the set created by "this" 736 return set.equals(map.entrySet()); 737 } 738 return false; 739 } 740 741 /** 742 * Returns a new IdentityHashMap with the same mappings and size as this 743 * one. 744 * 745 * @return a shallow copy of this IdentityHashMap. 746 * @see java.lang.Cloneable 747 */ 748 @Override 749 public Object clone() { 750 try { 751 return super.clone(); 752 } catch (CloneNotSupportedException e) { 753 return null; 754 } 755 } 756 757 /** 758 * Returns whether this IdentityHashMap has no elements. 759 * 760 * @return {@code true} if this IdentityHashMap has no elements, 761 * {@code false} otherwise. 762 * @see #size() 763 */ 764 @Override 765 public boolean isEmpty() { 766 return size == 0; 767 } 768 769 /** 770 * Returns the number of mappings in this IdentityHashMap. 771 * 772 * @return the number of mappings in this IdentityHashMap. 773 */ 774 @Override 775 public int size() { 776 return size; 777 } 778 779 private void writeObject(ObjectOutputStream stream) throws IOException { 780 stream.defaultWriteObject(); 781 stream.writeInt(size); 782 Iterator<?> iterator = entrySet().iterator(); 783 while (iterator.hasNext()) { 784 MapEntry<?, ?> entry = (MapEntry) iterator.next(); 785 stream.writeObject(entry.key); 786 stream.writeObject(entry.value); 787 } 788 } 789 790 @SuppressWarnings("unchecked") 791 private void readObject(ObjectInputStream stream) throws IOException, 792 ClassNotFoundException { 793 stream.defaultReadObject(); 794 int savedSize = stream.readInt(); 795 threshold = getThreshold(DEFAULT_MAX_SIZE); 796 elementData = newElementArray(computeElementArraySize()); 797 for (int i = savedSize; --i >= 0;) { 798 K key = (K) stream.readObject(); 799 put(key, (V) stream.readObject()); 800 } 801 size = savedSize; 802 } 803 804 private void putAllImpl(Map<? extends K, ? extends V> map) { 805 if (map.entrySet() != null) { 806 super.putAll(map); 807 } 808 } 809} 810