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