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 int arraySize = (int) (((long) threshold * 10000) / loadFactor) * 2; 271 // ensure arraySize is positive, the above cast from long to int type 272 // leads to overflow and negative arraySize if threshold is too big 273 return arraySize < 0 ? -arraySize : arraySize; 274 } 275 276 /** 277 * Create a new element array 278 * 279 * @param s 280 * the number of elements 281 * @return Reference to the element array 282 */ 283 private Object[] newElementArray(int s) { 284 return new Object[s]; 285 } 286 287 /** 288 * Creates an IdentityHashMap using the given map as initial values. 289 * 290 * @param map 291 * A map of (key,value) pairs to copy into the IdentityHashMap. 292 */ 293 public IdentityHashMap(Map<? extends K, ? extends V> map) { 294 this(map.size() < 6 ? 11 : map.size() * 2); 295 putAllImpl(map); 296 } 297 298 @SuppressWarnings("unchecked") 299 private V massageValue(Object value) { 300 return (V) ((value == NULL_OBJECT) ? null : value); 301 } 302 303 /** 304 * Removes all elements from this map, leaving it empty. 305 * 306 * @see #isEmpty() 307 * @see #size() 308 */ 309 @Override 310 public void clear() { 311 size = 0; 312 for (int i = 0; i < elementData.length; i++) { 313 elementData[i] = null; 314 } 315 modCount++; 316 } 317 318 /** 319 * Returns whether this map contains the specified key. 320 * 321 * @param key 322 * the key to search for. 323 * @return {@code true} if this map contains the specified key, 324 * {@code false} otherwise. 325 */ 326 @Override 327 public boolean containsKey(Object key) { 328 if (key == null) { 329 key = NULL_OBJECT; 330 } 331 332 int index = findIndex(key, elementData); 333 return elementData[index] == key; 334 } 335 336 /** 337 * Returns whether this map contains the specified value. 338 * 339 * @param value 340 * the value to search for. 341 * @return {@code true} if this map contains the specified value, 342 * {@code false} otherwise. 343 */ 344 @Override 345 public boolean containsValue(Object value) { 346 if (value == null) { 347 value = NULL_OBJECT; 348 } 349 350 for (int i = 1; i < elementData.length; i = i + 2) { 351 if (elementData[i] == value) { 352 return true; 353 } 354 } 355 return false; 356 } 357 358 /** 359 * Returns the value of the mapping with the specified key. 360 * 361 * @param key 362 * the key. 363 * @return the value of the mapping with the specified key. 364 */ 365 @Override 366 public V get(Object key) { 367 if (key == null) { 368 key = NULL_OBJECT; 369 } 370 371 int index = findIndex(key, elementData); 372 373 if (elementData[index] == key) { 374 Object result = elementData[index + 1]; 375 return massageValue(result); 376 } 377 378 return null; 379 } 380 381 private IdentityHashMapEntry<K, V> getEntry(Object key) { 382 if (key == null) { 383 key = NULL_OBJECT; 384 } 385 386 int index = findIndex(key, elementData); 387 if (elementData[index] == key) { 388 return getEntry(index); 389 } 390 391 return null; 392 } 393 394 /** 395 * Convenience method for getting the IdentityHashMapEntry without the 396 * NULL_OBJECT elements 397 */ 398 @SuppressWarnings("unchecked") 399 private IdentityHashMapEntry<K, V> getEntry(int index) { 400 Object key = elementData[index]; 401 Object value = elementData[index + 1]; 402 403 if (key == NULL_OBJECT) { 404 key = null; 405 } 406 if (value == NULL_OBJECT) { 407 value = null; 408 } 409 410 return new IdentityHashMapEntry<K, V>((K) key, (V) value); 411 } 412 413 /** 414 * Returns the index where the key is found at, or the index of the next 415 * empty spot if the key is not found in this table. 416 */ 417 private int findIndex(Object key, Object[] array) { 418 int length = array.length; 419 int index = getModuloHash(key, length); 420 int last = (index + length - 2) % length; 421 while (index != last) { 422 if (array[index] == key || (array[index] == null)) { 423 /* 424 * Found the key, or the next empty spot (which means key is not 425 * in the table) 426 */ 427 break; 428 } 429 index = (index + 2) % length; 430 } 431 return index; 432 } 433 434 private int getModuloHash(Object key, int length) { 435 return ((System.identityHashCode(key) & 0x7FFFFFFF) % (length / 2)) * 2; 436 } 437 438 /** 439 * Maps the specified key to the specified value. 440 * 441 * @param key 442 * the key. 443 * @param value 444 * the value. 445 * @return the value of any previous mapping with the specified key or 446 * {@code null} if there was no such mapping. 447 */ 448 @Override 449 public V put(K key, V value) { 450 Object _key = key; 451 Object _value = value; 452 if (_key == null) { 453 _key = NULL_OBJECT; 454 } 455 456 if (_value == null) { 457 _value = NULL_OBJECT; 458 } 459 460 int index = findIndex(_key, elementData); 461 462 // if the key doesn't exist in the table 463 if (elementData[index] != _key) { 464 modCount++; 465 if (++size > threshold) { 466 rehash(); 467 index = findIndex(_key, elementData); 468 } 469 470 // insert the key and assign the value to null initially 471 elementData[index] = _key; 472 elementData[index + 1] = null; 473 } 474 475 // insert value to where it needs to go, return the old value 476 Object result = elementData[index + 1]; 477 elementData[index + 1] = _value; 478 479 return massageValue(result); 480 } 481 482 /** 483 * Copies all the mappings in the specified map to this map. These mappings 484 * will replace all mappings that this map had for any of the keys currently 485 * in the given map. 486 * 487 * @param map 488 * the map to copy mappings from. 489 * @throws NullPointerException 490 * if {@code map} is {@code null}. 491 */ 492 @Override 493 public void putAll(Map<? extends K, ? extends V> map) { 494 putAllImpl(map); 495 } 496 497 private void rehash() { 498 int newlength = elementData.length << 1; 499 if (newlength == 0) { 500 newlength = 1; 501 } 502 Object[] newData = newElementArray(newlength); 503 for (int i = 0; i < elementData.length; i = i + 2) { 504 Object key = elementData[i]; 505 if (key != null) { 506 // if not empty 507 int index = findIndex(key, newData); 508 newData[index] = key; 509 newData[index + 1] = elementData[i + 1]; 510 } 511 } 512 elementData = newData; 513 computeMaxSize(); 514 } 515 516 private void computeMaxSize() { 517 threshold = (int) ((long) (elementData.length / 2) * loadFactor / 10000); 518 } 519 520 /** 521 * Removes the mapping with the specified key from this map. 522 * 523 * @param key 524 * the key of the mapping to remove. 525 * @return the value of the removed mapping, or {@code null} if no mapping 526 * for the specified key was found. 527 */ 528 @Override 529 public V remove(Object key) { 530 if (key == null) { 531 key = NULL_OBJECT; 532 } 533 534 boolean hashedOk; 535 int index, next, hash; 536 Object result, object; 537 index = next = findIndex(key, elementData); 538 539 if (elementData[index] != key) { 540 return null; 541 } 542 543 // store the value for this key 544 result = elementData[index + 1]; 545 546 // shift the following elements up if needed 547 // until we reach an empty spot 548 int length = elementData.length; 549 while (true) { 550 next = (next + 2) % length; 551 object = elementData[next]; 552 if (object == null) { 553 break; 554 } 555 556 hash = getModuloHash(object, length); 557 hashedOk = hash > index; 558 if (next < index) { 559 hashedOk = hashedOk || (hash <= next); 560 } else { 561 hashedOk = hashedOk && (hash <= next); 562 } 563 if (!hashedOk) { 564 elementData[index] = object; 565 elementData[index + 1] = elementData[next + 1]; 566 index = next; 567 } 568 } 569 570 size--; 571 modCount++; 572 573 // clear both the key and the value 574 elementData[index] = null; 575 elementData[index + 1] = null; 576 577 return massageValue(result); 578 } 579 580 /** 581 * Returns a set containing all of the mappings in this map. Each mapping is 582 * an instance of {@link Map.Entry}. As the set is backed by this map, 583 * changes in one will be reflected in the other. 584 * 585 * @return a set of the mappings. 586 */ 587 @Override 588 public Set<Map.Entry<K, V>> entrySet() { 589 return new IdentityHashMapEntrySet<K, V>(this); 590 } 591 592 /** 593 * Returns a set of the keys contained in this map. The set is backed by 594 * this map so changes to one are reflected by the other. The set does not 595 * support adding. 596 * 597 * @return a set of the keys. 598 */ 599 @Override 600 public Set<K> keySet() { 601 if (keySet == null) { 602 keySet = new AbstractSet<K>() { 603 @Override 604 public boolean contains(Object object) { 605 return containsKey(object); 606 } 607 608 @Override 609 public int size() { 610 return IdentityHashMap.this.size(); 611 } 612 613 @Override 614 public void clear() { 615 IdentityHashMap.this.clear(); 616 } 617 618 @Override 619 public boolean remove(Object key) { 620 if (containsKey(key)) { 621 IdentityHashMap.this.remove(key); 622 return true; 623 } 624 return false; 625 } 626 627 @Override 628 public Iterator<K> iterator() { 629 return new IdentityHashMapIterator<K, K, V>( 630 new MapEntry.Type<K, K, V>() { 631 public K get(MapEntry<K, V> entry) { 632 return entry.key; 633 } 634 }, IdentityHashMap.this); 635 } 636 }; 637 } 638 return keySet; 639 } 640 641 /** 642 * Returns a collection of the values contained in this map. The collection 643 * is backed by this map so changes to one are reflected by the other. The 644 * collection supports remove, removeAll, retainAll and clear operations, 645 * and it does not support add or addAll operations. 646 * <p> 647 * This method returns a collection which is the subclass of 648 * AbstractCollection. The iterator method of this subclass returns a 649 * "wrapper object" over the iterator of map's entrySet(). The {@code size} 650 * method wraps the map's size method and the {@code contains} method wraps 651 * the map's containsValue method. 652 * <p> 653 * The collection is created when this method is called for the first time 654 * and returned in response to all subsequent calls. This method may return 655 * different collections when multiple concurrent calls occur, since no 656 * synchronization is performed. 657 * 658 * @return a collection of the values contained in this map. 659 */ 660 @Override 661 public Collection<V> values() { 662 if (valuesCollection == null) { 663 valuesCollection = new AbstractCollection<V>() { 664 @Override 665 public boolean contains(Object object) { 666 return containsValue(object); 667 } 668 669 @Override 670 public int size() { 671 return IdentityHashMap.this.size(); 672 } 673 674 @Override 675 public void clear() { 676 IdentityHashMap.this.clear(); 677 } 678 679 @Override 680 public Iterator<V> iterator() { 681 return new IdentityHashMapIterator<V, K, V>( 682 new MapEntry.Type<V, K, V>() { 683 public V get(MapEntry<K, V> entry) { 684 return entry.value; 685 } 686 }, IdentityHashMap.this); 687 } 688 689 @Override 690 public boolean remove(Object object) { 691 Iterator<?> it = iterator(); 692 while (it.hasNext()) { 693 if (object == it.next()) { 694 it.remove(); 695 return true; 696 } 697 } 698 return false; 699 } 700 }; 701 } 702 return valuesCollection; 703 } 704 705 /** 706 * Compares this map with other objects. This map is equal to another map is 707 * it represents the same set of mappings. With this map, two mappings are 708 * the same if both the key and the value are equal by reference. When 709 * compared with a map that is not an IdentityHashMap, the equals method is 710 * neither necessarily symmetric (a.equals(b) implies b.equals(a)) nor 711 * transitive (a.equals(b) and b.equals(c) implies a.equals(c)). 712 * 713 * @param object 714 * the object to compare to. 715 * @return whether the argument object is equal to this object. 716 */ 717 @Override 718 public boolean equals(Object object) { 719 /* 720 * We need to override the equals method in AbstractMap because 721 * AbstractMap.equals will call ((Map) object).entrySet().contains() to 722 * determine equality of the entries, so it will defer to the argument 723 * for comparison, meaning that reference-based comparison will not take 724 * place. We must ensure that all comparison is implemented by methods 725 * in this class (or in one of our inner classes) for reference-based 726 * comparison to take place. 727 */ 728 if (this == object) { 729 return true; 730 } 731 if (object instanceof Map) { 732 Map<?, ?> map = (Map) object; 733 if (size() != map.size()) { 734 return false; 735 } 736 737 Set<Map.Entry<K, V>> set = entrySet(); 738 // ensure we use the equals method of the set created by "this" 739 return set.equals(map.entrySet()); 740 } 741 return false; 742 } 743 744 /** 745 * Returns a new IdentityHashMap with the same mappings and size as this 746 * one. 747 * 748 * @return a shallow copy of this IdentityHashMap. 749 * @see java.lang.Cloneable 750 */ 751 @Override 752 public Object clone() { 753 try { 754 IdentityHashMap<K, V> cloneHashMap = (IdentityHashMap<K, V>) super 755 .clone(); 756 cloneHashMap.elementData = newElementArray(elementData.length); 757 System.arraycopy(elementData, 0, cloneHashMap.elementData, 0, 758 elementData.length); 759 return cloneHashMap; 760 } catch (CloneNotSupportedException e) { 761 throw new AssertionError(e); // android-changed 762 } 763 } 764 765 /** 766 * Returns whether this IdentityHashMap has no elements. 767 * 768 * @return {@code true} if this IdentityHashMap has no elements, 769 * {@code false} otherwise. 770 * @see #size() 771 */ 772 @Override 773 public boolean isEmpty() { 774 return size == 0; 775 } 776 777 /** 778 * Returns the number of mappings in this IdentityHashMap. 779 * 780 * @return the number of mappings in this IdentityHashMap. 781 */ 782 @Override 783 public int size() { 784 return size; 785 } 786 787 private void writeObject(ObjectOutputStream stream) throws IOException { 788 stream.defaultWriteObject(); 789 stream.writeInt(size); 790 Iterator<?> iterator = entrySet().iterator(); 791 while (iterator.hasNext()) { 792 MapEntry<?, ?> entry = (MapEntry) iterator.next(); 793 stream.writeObject(entry.key); 794 stream.writeObject(entry.value); 795 } 796 } 797 798 @SuppressWarnings("unchecked") 799 private void readObject(ObjectInputStream stream) throws IOException, 800 ClassNotFoundException { 801 stream.defaultReadObject(); 802 int savedSize = stream.readInt(); 803 threshold = getThreshold(DEFAULT_MAX_SIZE); 804 elementData = newElementArray(computeElementArraySize()); 805 for (int i = savedSize; --i >= 0;) { 806 K key = (K) stream.readObject(); 807 put(key, (V) stream.readObject()); 808 } 809 size = savedSize; 810 } 811 812 private void putAllImpl(Map<? extends K, ? extends V> map) { 813 if (map.entrySet() != null) { 814 super.putAll(map); 815 } 816 } 817} 818