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