001 /* 002 * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved. 003 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. 004 * 005 * 006 * 007 * 008 * 009 * 010 * 011 * 012 * 013 * 014 * 015 * 016 * 017 * 018 * 019 * 020 * 021 * 022 * 023 * 024 */ 025 026 package railo.commons.util.mod; 027 import java.io.IOException; 028 import java.io.InvalidObjectException; 029 import java.io.Serializable; 030 import java.util.Collection; 031 import java.util.ConcurrentModificationException; 032 import java.util.HashMap; 033 import java.util.Iterator; 034 import java.util.Map; 035 import java.util.NoSuchElementException; 036 import java.util.Set; 037 038 import railo.runtime.exp.PageException; 039 040 public class HashMapPro<K,V> 041 extends AbstractMapPro<K,V> 042 implements Map<K,V>, MapPro<K,V>, Cloneable, Serializable 043 { 044 045 /** 046 * The default initial capacity - MUST be a power of two. 047 */ 048 static final int DEFAULT_INITIAL_CAPACITY = 16; 049 050 /** 051 * The maximum capacity, used if a higher value is implicitly specified 052 * by either of the constructors with arguments. 053 * MUST be a power of two <= 1<<30. 054 */ 055 static final int MAXIMUM_CAPACITY = 1 << 30; 056 057 /** 058 * The load factor used when none specified in constructor. 059 */ 060 static final float DEFAULT_LOAD_FACTOR = 0.75f; 061 062 /** 063 * The table, resized as necessary. Length MUST Always be a power of two. 064 */ 065 transient Entry<K,V>[] table; 066 067 /** 068 * The number of key-value mappings contained in this map. 069 */ 070 transient int size; 071 072 /** 073 * The next size value at which to resize (capacity * load factor). 074 * @serial 075 */ 076 int threshold; 077 078 /** 079 * The load factor for the hash table. 080 * 081 * @serial 082 */ 083 final float loadFactor; 084 085 /** 086 * The number of times this HashMap has been structurally modified 087 * Structural modifications are those that change the number of mappings in 088 * the HashMap or otherwise modify its internal structure (e.g., 089 * rehash). This field is used to make iterators on Collection-views of 090 * the HashMap fail-fast. (See ConcurrentModificationException). 091 */ 092 transient int modCount; 093 094 /** 095 * The default threshold of map capacity above which alternative hashing is 096 * used for String keys. Alternative hashing reduces the incidence of 097 * collisions due to weak hash code calculation for String keys. 098 * <p/> 099 * This value may be overridden by defining the system property 100 * {@code jdk.map.althashing.threshold}. A property value of {@code 1} 101 * forces alternative hashing to be used at all times whereas 102 * {@code -1} value ensures that alternative hashing is never used. 103 */ 104 static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE; 105 106 /** 107 * holds values which can't be initialized until after VM is booted. 108 */ 109 private static class Holder { 110 111 // Unsafe mechanics 112 /** 113 * Unsafe utilities 114 */ 115 static final sun.misc.Unsafe UNSAFE; 116 117 /** 118 * Offset of "final" hashSeed field we must set in readObject() method. 119 */ 120 static final long HASHSEED_OFFSET; 121 122 /** 123 * Table capacity above which to switch to use alternative hashing. 124 */ 125 static final int ALTERNATIVE_HASHING_THRESHOLD; 126 127 static { 128 String altThreshold = java.security.AccessController.doPrivileged( 129 new sun.security.action.GetPropertyAction( 130 "jdk.map.althashing.threshold")); 131 132 int threshold; 133 try { 134 threshold = (null != altThreshold) 135 ? Integer.parseInt(altThreshold) 136 : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT; 137 138 // disable alternative hashing if -1 139 if (threshold == -1) { 140 threshold = Integer.MAX_VALUE; 141 } 142 143 if (threshold < 0) { 144 throw new IllegalArgumentException("value must be positive integer."); 145 } 146 } catch(IllegalArgumentException failed) { 147 throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed); 148 } 149 ALTERNATIVE_HASHING_THRESHOLD = threshold; 150 151 try { 152 UNSAFE = sun.misc.Unsafe.getUnsafe(); 153 HASHSEED_OFFSET = UNSAFE.objectFieldOffset( 154 HashMapPro.class.getDeclaredField("hashSeed")); 155 } 156 catch (NoSuchFieldException e) { 157 throw new Error("Failed to record hashSeed offset", e); 158 } 159 catch (SecurityException e) { 160 throw new Error("Failed to record hashSeed offset", e); 161 } 162 } 163 } 164 165 /** 166 * If {@code true} then perform alternative hashing of String keys to reduce 167 * the incidence of collisions due to weak hash code calculation. 168 */ 169 transient final boolean useAltHashing=false; 170 171 /** 172 * A randomizing value associated with this instance that is applied to 173 * hash code of keys to make hash collisions harder to find. 174 */ 175 transient final int hashSeed = Hashing.randomHashSeed(this); 176 177 /** 178 * Constructs an empty <tt>HashMap</tt> with the specified initial 179 * capacity and load factor. 180 * 181 * @param initialCapacity the initial capacity 182 * @param loadFactor the load factor 183 * @throws IllegalArgumentException if the initial capacity is negative 184 * or the load factor is nonpositive 185 */ 186 public HashMapPro(int initialCapacity, float loadFactor) { 187 if (initialCapacity < 0) 188 throw new IllegalArgumentException("Illegal initial capacity: " + 189 initialCapacity); 190 if (initialCapacity > MAXIMUM_CAPACITY) 191 initialCapacity = MAXIMUM_CAPACITY; 192 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 193 throw new IllegalArgumentException("Illegal load factor: " + 194 loadFactor); 195 196 // Find a power of 2 >= initialCapacity 197 int capacity = 1; 198 while (capacity < initialCapacity) 199 capacity <<= 1; 200 201 this.loadFactor = loadFactor; 202 threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); 203 table = new Entry[capacity]; 204 //useAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); 205 init(); 206 } 207 208 /** 209 * Constructs an empty <tt>HashMap</tt> with the specified initial 210 * capacity and the default load factor (0.75). 211 * 212 * @param initialCapacity the initial capacity. 213 * @throws IllegalArgumentException if the initial capacity is negative. 214 */ 215 public HashMapPro(int initialCapacity) { 216 this(initialCapacity, DEFAULT_LOAD_FACTOR); 217 } 218 219 /** 220 * Constructs an empty <tt>HashMap</tt> with the default initial capacity 221 * (16) and the default load factor (0.75). 222 */ 223 public HashMapPro() { 224 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); 225 } 226 227 /** 228 * Constructs a new <tt>HashMap</tt> with the same mappings as the 229 * specified <tt>Map</tt>. The <tt>HashMap</tt> is created with 230 * default load factor (0.75) and an initial capacity sufficient to 231 * hold the mappings in the specified <tt>Map</tt>. 232 * 233 * @param m the map whose mappings are to be placed in this map 234 * @throws NullPointerException if the specified map is null 235 */ 236 public HashMapPro(Map<? extends K, ? extends V> m) { 237 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, 238 DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); 239 putAllForCreate(m); 240 } 241 242 // internal utilities 243 244 /** 245 * Initialization hook for subclasses. This method is called 246 * in all constructors and pseudo-constructors (clone, readObject) 247 * after HashMap has been initialized but before any entries have 248 * been inserted. (In the absence of this method, readObject would 249 * require explicit knowledge of subclasses.) 250 */ 251 void init() { 252 } 253 254 /** 255 * Retrieve object hash code and applies a supplemental hash function to the 256 * result hash, which defends against poor quality hash functions. This is 257 * critical because HashMap uses power-of-two length hash tables, that 258 * otherwise encounter collisions for hashCodes that do not differ 259 * in lower bits. Note: Null keys always map to hash 0, thus index 0. 260 */ 261 final int hash(Object k) { 262 int h = 0; 263 /*if (useAltHashing) { 264 if (k instanceof String) { 265 return Hashing.stringHash32((String) k); 266 } 267 h = hashSeed; 268 }*/ 269 270 h ^= k.hashCode(); 271 272 // This function ensures that hashCodes that differ only by 273 // constant multiples at each bit position have a bounded 274 // number of collisions (approximately 8 at default load factor). 275 h ^= (h >>> 20) ^ (h >>> 12); 276 return h ^ (h >>> 7) ^ (h >>> 4); 277 } 278 279 /** 280 * Returns index for hash code h. 281 */ 282 static int indexFor(int h, int length) { 283 return h & (length-1); 284 } 285 286 /** 287 * Returns the number of key-value mappings in this map. 288 * 289 * @return the number of key-value mappings in this map 290 */ 291 public int size() { 292 return size; 293 } 294 295 /** 296 * Returns <tt>true</tt> if this map contains no key-value mappings. 297 * 298 * @return <tt>true</tt> if this map contains no key-value mappings 299 */ 300 public boolean isEmpty() { 301 return size == 0; 302 } 303 304 @Override 305 public V get(Object key) { 306 if (key == null) 307 return getForNullKey(); 308 Entry<K,V> entry = getEntry(key); 309 310 return null == entry ? null : entry.getValue(); 311 } 312 313 public V g(K key, V defaultValue) { 314 if (key == null) return getForNullKey(); 315 316 int hash = hash(key); 317 for (Entry<K,V> e = table[indexFor(hash, table.length)]; 318 e != null; 319 e = e.next) { 320 Object k; 321 if (e.hash == hash && 322 ((k = e.key) == key || key.equals(k))) 323 return e.getValue(); 324 } 325 return defaultValue; 326 } 327 328 public V g(K key) throws PageException { 329 if (key == null) return getForNullKey(); 330 331 int hash = hash(key); 332 for (Entry<K,V> e = table[indexFor(hash, table.length)]; 333 e != null; 334 e = e.next) { 335 Object k; 336 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) 337 return e.getValue(); 338 } 339 throw invalidKey(this, key,false); 340 } 341 342 /** 343 * Offloaded version of get() to look up null keys. Null keys map 344 * to index 0. This null case is split out into separate methods 345 * for the sake of performance in the two most commonly used 346 * operations (get and put), but incorporated with conditionals in 347 * others. 348 */ 349 private V getForNullKey() { 350 for (Entry<K,V> e = table[0]; e != null; e = e.next) { 351 if (e.key == null) 352 return e.value; 353 } 354 return null; 355 } 356 357 /** 358 * Returns <tt>true</tt> if this map contains a mapping for the 359 * specified key. 360 * 361 * @param key The key whose presence in this map is to be tested 362 * @return <tt>true</tt> if this map contains a mapping for the specified 363 * key. 364 */ 365 public boolean containsKey(Object key) { 366 return getEntry(key) != null; 367 } 368 369 /** 370 * Returns the entry associated with the specified key in the 371 * HashMap. Returns null if the HashMap contains no mapping 372 * for the key. 373 */ 374 final Entry<K,V> getEntry(Object key) { 375 int hash = (key == null) ? 0 : hash(key); 376 for (Entry<K,V> e = table[indexFor(hash, table.length)]; 377 e != null; 378 e = e.next) { 379 Object k; 380 if (e.hash == hash && 381 ((k = e.key) == key || (key != null && key.equals(k)))) 382 return e; 383 } 384 return null; 385 } 386 387 388 /** 389 * Associates the specified value with the specified key in this map. 390 * If the map previously contained a mapping for the key, the old 391 * value is replaced. 392 * 393 * @param key key with which the specified value is to be associated 394 * @param value value to be associated with the specified key 395 * @return the previous value associated with <tt>key</tt>, or 396 * <tt>null</tt> if there was no mapping for <tt>key</tt>. 397 * (A <tt>null</tt> return can also indicate that the map 398 * previously associated <tt>null</tt> with <tt>key</tt>.) 399 */ 400 public V put(K key, V value) { 401 if (key == null) 402 return putForNullKey(value); 403 int hash = hash(key); 404 int i = indexFor(hash, table.length); 405 for (Entry<K,V> e = table[i]; e != null; e = e.next) { 406 Object k; 407 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 408 V oldValue = e.value; 409 e.value = value; 410 e.recordAccess(this); 411 return oldValue; 412 } 413 } 414 415 modCount++; 416 addEntry(hash, key, value, i); 417 return null; 418 } 419 420 /** 421 * Offloaded version of put for null keys 422 */ 423 private V putForNullKey(V value) { 424 for (Entry<K,V> e = table[0]; e != null; e = e.next) { 425 if (e.key == null) { 426 V oldValue = e.value; 427 e.value = value; 428 e.recordAccess(this); 429 return oldValue; 430 } 431 } 432 modCount++; 433 addEntry(0, null, value, 0); 434 return null; 435 } 436 437 /** 438 * This method is used instead of put by constructors and 439 * pseudoconstructors (clone, readObject). It does not resize the table, 440 * check for comodification, etc. It calls createEntry rather than 441 * addEntry. 442 */ 443 private void putForCreate(K key, V value) { 444 int hash = null == key ? 0 : hash(key); 445 int i = indexFor(hash, table.length); 446 447 /** 448 * Look for preexisting entry for key. This will never happen for 449 * clone or deserialize. It will only happen for construction if the 450 * input Map is a sorted map whose ordering is inconsistent w/ equals. 451 */ 452 for (Entry<K,V> e = table[i]; e != null; e = e.next) { 453 Object k; 454 if (e.hash == hash && 455 ((k = e.key) == key || (key != null && key.equals(k)))) { 456 e.value = value; 457 return; 458 } 459 } 460 461 createEntry(hash, key, value, i); 462 } 463 464 private void putAllForCreate(Map<? extends K, ? extends V> m) { 465 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) 466 putForCreate(e.getKey(), e.getValue()); 467 } 468 469 /** 470 * Rehashes the contents of this map into a new array with a 471 * larger capacity. This method is called automatically when the 472 * number of keys in this map reaches its threshold. 473 * 474 * If current capacity is MAXIMUM_CAPACITY, this method does not 475 * resize the map, but sets threshold to Integer.MAX_VALUE. 476 * This has the effect of preventing future calls. 477 * 478 * @param newCapacity the new capacity, MUST be a power of two; 479 * must be greater than current capacity unless current 480 * capacity is MAXIMUM_CAPACITY (in which case value 481 * is irrelevant). 482 */ 483 void resize(int newCapacity) { 484 Entry[] oldTable = table; 485 int oldCapacity = oldTable.length; 486 if (oldCapacity == MAXIMUM_CAPACITY) { 487 threshold = Integer.MAX_VALUE; 488 return; 489 } 490 491 Entry[] newTable = new Entry[newCapacity]; 492 boolean oldAltHashing = useAltHashing; 493 //useAltHashing |= sun.misc.VM.isBooted() && (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); 494 boolean rehash = oldAltHashing ^ useAltHashing; 495 transfer(newTable, rehash); 496 table = newTable; 497 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); 498 } 499 500 /** 501 * Transfers all entries from current table to newTable. 502 */ 503 void transfer(Entry[] newTable, boolean rehash) { 504 int newCapacity = newTable.length; 505 for (Entry<K,V> e : table) { 506 while(null != e) { 507 Entry<K,V> next = e.next; 508 if (rehash) { 509 e.hash = null == e.key ? 0 : hash(e.key); 510 } 511 int i = indexFor(e.hash, newCapacity); 512 e.next = newTable[i]; 513 newTable[i] = e; 514 e = next; 515 } 516 } 517 } 518 519 /** 520 * Copies all of the mappings from the specified map to this map. 521 * These mappings will replace any mappings that this map had for 522 * any of the keys currently in the specified map. 523 * 524 * @param m mappings to be stored in this map 525 * @throws NullPointerException if the specified map is null 526 */ 527 public void putAll(Map<? extends K, ? extends V> m) { 528 int numKeysToBeAdded = m.size(); 529 if (numKeysToBeAdded == 0) 530 return; 531 532 /* 533 * Expand the map if the map if the number of mappings to be added 534 * is greater than or equal to threshold. This is conservative; the 535 * obvious condition is (m.size() + size) >= threshold, but this 536 * condition could result in a map with twice the appropriate capacity, 537 * if the keys to be added overlap with the keys already in this map. 538 * By using the conservative calculation, we subject ourself 539 * to at most one extra resize. 540 */ 541 if (numKeysToBeAdded > threshold) { 542 int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1); 543 if (targetCapacity > MAXIMUM_CAPACITY) 544 targetCapacity = MAXIMUM_CAPACITY; 545 int newCapacity = table.length; 546 while (newCapacity < targetCapacity) 547 newCapacity <<= 1; 548 if (newCapacity > table.length) 549 resize(newCapacity); 550 } 551 552 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) 553 put(e.getKey(), e.getValue()); 554 } 555 556 /** 557 * Removes the mapping for the specified key from this map if present. 558 * 559 * @param key key whose mapping is to be removed from the map 560 * @return the previous value associated with <tt>key</tt>, or 561 * <tt>null</tt> if there was no mapping for <tt>key</tt>. 562 * (A <tt>null</tt> return can also indicate that the map 563 * previously associated <tt>null</tt> with <tt>key</tt>.) 564 */ 565 public V remove(Object key) { 566 Entry<K,V> e = removeEntryForKey(key); 567 return (e == null ? null : e.value); 568 } 569 570 public V r(K key,V defaultValue) { 571 Entry<K,V> e = removeEntryForKey(key); 572 return (e == null ? defaultValue : e.value); 573 } 574 575 public V r(K key) throws PageException { 576 Entry<K,V> e = removeEntryForKey(key); 577 if(e==null) throw invalidKey(this, key,true); 578 return e.value; 579 } 580 581 582 583 584 585 /** 586 * Removes and returns the entry associated with the specified key 587 * in the HashMap. Returns null if the HashMap contains no mapping 588 * for this key. 589 */ 590 final Entry<K,V> removeEntryForKey(Object key) { 591 int hash = (key == null) ? 0 : hash(key); 592 int i = indexFor(hash, table.length); 593 Entry<K,V> prev = table[i]; 594 Entry<K,V> e = prev; 595 596 while (e != null) { 597 Entry<K,V> next = e.next; 598 Object k; 599 if (e.hash == hash && 600 ((k = e.key) == key || (key != null && key.equals(k)))) { 601 modCount++; 602 size--; 603 if (prev == e) 604 table[i] = next; 605 else 606 prev.next = next; 607 e.recordRemoval(this); 608 return e; 609 } 610 prev = e; 611 e = next; 612 } 613 614 return e; 615 } 616 617 /** 618 * Special version of remove for EntrySet using {@code Map.Entry.equals()} 619 * for matching. 620 */ 621 final Entry<K,V> removeMapping(Object o) { 622 if (!(o instanceof Map.Entry)) 623 return null; 624 625 Map.Entry<K,V> entry = (Map.Entry<K,V>) o; 626 Object key = entry.getKey(); 627 int hash = (key == null) ? 0 : hash(key); 628 int i = indexFor(hash, table.length); 629 Entry<K,V> prev = table[i]; 630 Entry<K,V> e = prev; 631 632 while (e != null) { 633 Entry<K,V> next = e.next; 634 if (e.hash == hash && e.equals(entry)) { 635 modCount++; 636 size--; 637 if (prev == e) 638 table[i] = next; 639 else 640 prev.next = next; 641 e.recordRemoval(this); 642 return e; 643 } 644 prev = e; 645 e = next; 646 } 647 648 return e; 649 } 650 651 /** 652 * Removes all of the mappings from this map. 653 * The map will be empty after this call returns. 654 */ 655 public void clear() { 656 modCount++; 657 Entry[] tab = table; 658 for (int i = 0; i < tab.length; i++) 659 tab[i] = null; 660 size = 0; 661 } 662 663 /** 664 * Returns <tt>true</tt> if this map maps one or more keys to the 665 * specified value. 666 * 667 * @param value value whose presence in this map is to be tested 668 * @return <tt>true</tt> if this map maps one or more keys to the 669 * specified value 670 */ 671 public boolean containsValue(Object value) { 672 if (value == null) 673 return containsNullValue(); 674 675 Entry[] tab = table; 676 for (int i = 0; i < tab.length ; i++) 677 for (Entry e = tab[i] ; e != null ; e = e.next) 678 if (value.equals(e.value)) 679 return true; 680 return false; 681 } 682 683 /** 684 * Special-case code for containsValue with null argument 685 */ 686 private boolean containsNullValue() { 687 Entry[] tab = table; 688 for (int i = 0; i < tab.length ; i++) 689 for (Entry e = tab[i] ; e != null ; e = e.next) 690 if (e.value == null) 691 return true; 692 return false; 693 } 694 695 /** 696 * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and 697 * values themselves are not cloned. 698 * 699 * @return a shallow copy of this map 700 */ 701 public Object clone() { 702 HashMapPro<K,V> result = null; 703 try { 704 result = (HashMapPro<K,V>)super.clone(); 705 } catch (CloneNotSupportedException e) { 706 // assert false; 707 } 708 result.table = new Entry[table.length]; 709 result.entrySet = null; 710 result.modCount = 0; 711 result.size = 0; 712 result.init(); 713 result.putAllForCreate(this); 714 715 return result; 716 } 717 718 static class Entry<K,V> implements Map.Entry<K,V> { 719 final K key; 720 V value; 721 Entry<K,V> next; 722 int hash; 723 724 /** 725 * Creates new entry. 726 */ 727 Entry(int h, K k, V v, Entry<K,V> n) { 728 value = v; 729 next = n; 730 key = k; 731 hash = h; 732 } 733 734 public final K getKey() { 735 return key; 736 } 737 738 public final V getValue() { 739 return value; 740 } 741 742 public final V setValue(V newValue) { 743 V oldValue = value; 744 value = newValue; 745 return oldValue; 746 } 747 748 public final boolean equals(Object o) { 749 if (!(o instanceof Map.Entry)) 750 return false; 751 Map.Entry e = (Map.Entry)o; 752 Object k1 = getKey(); 753 Object k2 = e.getKey(); 754 if (k1 == k2 || (k1 != null && k1.equals(k2))) { 755 Object v1 = getValue(); 756 Object v2 = e.getValue(); 757 if (v1 == v2 || (v1 != null && v1.equals(v2))) 758 return true; 759 } 760 return false; 761 } 762 763 public final int hashCode() { 764 return (key==null ? 0 : key.hashCode()) ^ 765 (value==null ? 0 : value.hashCode()); 766 } 767 768 public final String toString() { 769 return getKey() + "=" + getValue(); 770 } 771 772 /** 773 * This method is invoked whenever the value in an entry is 774 * overwritten by an invocation of put(k,v) for a key k that's already 775 * in the HashMap. 776 */ 777 void recordAccess(HashMapPro<K,V> m) { 778 } 779 780 /** 781 * This method is invoked whenever the entry is 782 * removed from the table. 783 */ 784 void recordRemoval(HashMapPro<K,V> m) { 785 } 786 } 787 788 /** 789 * Adds a new entry with the specified key, value and hash code to 790 * the specified bucket. It is the responsibility of this 791 * method to resize the table if appropriate. 792 * 793 * Subclass overrides this to alter the behavior of put method. 794 */ 795 void addEntry(int hash, K key, V value, int bucketIndex) { 796 if ((size >= threshold) && (null != table[bucketIndex])) { 797 resize(2 * table.length); 798 hash = (null != key) ? hash(key) : 0; 799 bucketIndex = indexFor(hash, table.length); 800 } 801 802 createEntry(hash, key, value, bucketIndex); 803 } 804 805 /** 806 * Like addEntry except that this version is used when creating entries 807 * as part of Map construction or "pseudo-construction" (cloning, 808 * deserialization). This version needn't worry about resizing the table. 809 * 810 * Subclass overrides this to alter the behavior of HashMap(Map), 811 * clone, and readObject. 812 */ 813 void createEntry(int hash, K key, V value, int bucketIndex) { 814 Entry<K,V> e = table[bucketIndex]; 815 table[bucketIndex] = new Entry<K,V>(hash, key, value, e); 816 size++; 817 } 818 819 private abstract class HashIterator<E> implements Iterator<E> { 820 Entry<K,V> next; // next entry to return 821 int expectedModCount; // For fast-fail 822 int index; // current slot 823 Entry<K,V> current; // current entry 824 825 HashIterator() { 826 expectedModCount = modCount; 827 if (size > 0) { // advance to first entry 828 Entry[] t = table; 829 while (index < t.length && (next = t[index++]) == null) 830 ; 831 } 832 } 833 834 public final boolean hasNext() { 835 return next != null; 836 } 837 838 final Entry<K,V> nextEntry() { 839 if (modCount != expectedModCount) 840 throw new ConcurrentModificationException(); 841 Entry<K,V> e = next; 842 if (e == null) 843 throw new NoSuchElementException(); 844 845 if ((next = e.next) == null) { 846 Entry[] t = table; 847 while (index < t.length && (next = t[index++]) == null) 848 ; 849 } 850 current = e; 851 return e; 852 } 853 854 public void remove() { 855 if (current == null) 856 throw new IllegalStateException(); 857 if (modCount != expectedModCount) 858 throw new ConcurrentModificationException(); 859 Object k = current.key; 860 current = null; 861 HashMapPro.this.removeEntryForKey(k); 862 expectedModCount = modCount; 863 } 864 } 865 866 private final class ValueIterator extends HashIterator<V> { 867 public V next() { 868 return nextEntry().value; 869 } 870 } 871 872 private final class KeyIterator extends HashIterator<K> { 873 public K next() { 874 return nextEntry().getKey(); 875 } 876 } 877 878 private final class EntryIterator extends HashIterator<Map.Entry<K,V>> { 879 public Map.Entry<K,V> next() { 880 return nextEntry(); 881 } 882 } 883 884 // Subclass overrides these to alter behavior of views' iterator() method 885 Iterator<K> newKeyIterator() { 886 return new KeyIterator(); 887 } 888 Iterator<V> newValueIterator() { 889 return new ValueIterator(); 890 } 891 Iterator<Map.Entry<K,V>> newEntryIterator() { 892 return new EntryIterator(); 893 } 894 895 896 // Views 897 898 private transient Set<Map.Entry<K,V>> entrySet = null; 899 900 /** 901 * Returns a {@link Set} view of the keys contained in this map. 902 * The set is backed by the map, so changes to the map are 903 * reflected in the set, and vice-versa. If the map is modified 904 * while an iteration over the set is in progress (except through 905 * the iterator's own <tt>remove</tt> operation), the results of 906 * the iteration are undefined. The set supports element removal, 907 * which removes the corresponding mapping from the map, via the 908 * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, 909 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> 910 * operations. It does not support the <tt>add</tt> or <tt>addAll</tt> 911 * operations. 912 */ 913 public Set<K> keySet() { 914 Set<K> ks = keySet; 915 return (ks != null ? ks : (keySet = new KeySet())); 916 } 917 918 private final class KeySet extends AbstractSet<K> { 919 public Iterator<K> iterator() { 920 return newKeyIterator(); 921 } 922 public int size() { 923 return size; 924 } 925 public boolean contains(Object o) { 926 return containsKey(o); 927 } 928 public boolean remove(Object o) { 929 return HashMapPro.this.removeEntryForKey(o) != null; 930 } 931 public void clear() { 932 HashMapPro.this.clear(); 933 } 934 } 935 936 /** 937 * Returns a {@link Collection} view of the values contained in this map. 938 * The collection is backed by the map, so changes to the map are 939 * reflected in the collection, and vice-versa. If the map is 940 * modified while an iteration over the collection is in progress 941 * (except through the iterator's own <tt>remove</tt> operation), 942 * the results of the iteration are undefined. The collection 943 * supports element removal, which removes the corresponding 944 * mapping from the map, via the <tt>Iterator.remove</tt>, 945 * <tt>Collection.remove</tt>, <tt>removeAll</tt>, 946 * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not 947 * support the <tt>add</tt> or <tt>addAll</tt> operations. 948 */ 949 public Collection<V> values() { 950 Collection<V> vs = values; 951 return (vs != null ? vs : (values = new Values())); 952 } 953 954 private final class Values extends AbstractCollection<V> { 955 public Iterator<V> iterator() { 956 return newValueIterator(); 957 } 958 public int size() { 959 return size; 960 } 961 public boolean contains(Object o) { 962 return containsValue(o); 963 } 964 public void clear() { 965 HashMapPro.this.clear(); 966 } 967 } 968 969 /** 970 * Returns a {@link Set} view of the mappings contained in this map. 971 * The set is backed by the map, so changes to the map are 972 * reflected in the set, and vice-versa. If the map is modified 973 * while an iteration over the set is in progress (except through 974 * the iterator's own <tt>remove</tt> operation, or through the 975 * <tt>setValue</tt> operation on a map entry returned by the 976 * iterator) the results of the iteration are undefined. The set 977 * supports element removal, which removes the corresponding 978 * mapping from the map, via the <tt>Iterator.remove</tt>, 979 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and 980 * <tt>clear</tt> operations. It does not support the 981 * <tt>add</tt> or <tt>addAll</tt> operations. 982 * 983 * @return a set view of the mappings contained in this map 984 */ 985 public Set<Map.Entry<K,V>> entrySet() { 986 return entrySet0(); 987 } 988 989 private Set<Map.Entry<K,V>> entrySet0() { 990 Set<Map.Entry<K,V>> es = entrySet; 991 return es != null ? es : (entrySet = new EntrySet()); 992 } 993 994 private final class EntrySet extends AbstractSet<Map.Entry<K,V>> { 995 public Iterator<Map.Entry<K,V>> iterator() { 996 return newEntryIterator(); 997 } 998 public boolean contains(Object o) { 999 if (!(o instanceof Map.Entry)) 1000 return false; 1001 Map.Entry<K,V> e = (Map.Entry<K,V>) o; 1002 Entry<K,V> candidate = getEntry(e.getKey()); 1003 return candidate != null && candidate.equals(e); 1004 } 1005 public boolean remove(Object o) { 1006 return removeMapping(o) != null; 1007 } 1008 public int size() { 1009 return size; 1010 } 1011 public void clear() { 1012 HashMapPro.this.clear(); 1013 } 1014 } 1015 1016 /** 1017 * Save the state of the <tt>HashMap</tt> instance to a stream (i.e., 1018 * serialize it). 1019 * 1020 * @serialData The <i>capacity</i> of the HashMap (the length of the 1021 * bucket array) is emitted (int), followed by the 1022 * <i>size</i> (an int, the number of key-value 1023 * mappings), followed by the key (Object) and value (Object) 1024 * for each key-value mapping. The key-value mappings are 1025 * emitted in no particular order. 1026 */ 1027 private void writeObject(java.io.ObjectOutputStream s) 1028 throws IOException 1029 { 1030 Iterator<Map.Entry<K,V>> i = 1031 (size > 0) ? entrySet0().iterator() : null; 1032 1033 // Write out the threshold, loadfactor, and any hidden stuff 1034 s.defaultWriteObject(); 1035 1036 // Write out number of buckets 1037 s.writeInt(table.length); 1038 1039 // Write out size (number of Mappings) 1040 s.writeInt(size); 1041 1042 // Write out keys and values (alternating) 1043 if (size > 0) { 1044 for(Map.Entry<K,V> e : entrySet0()) { 1045 s.writeObject(e.getKey()); 1046 s.writeObject(e.getValue()); 1047 } 1048 } 1049 } 1050 1051 private static final long serialVersionUID = 362498820763181265L; 1052 1053 /** 1054 * Reconstitute the {@code HashMap} instance from a stream (i.e., 1055 * deserialize it). 1056 */ 1057 private void readObject(java.io.ObjectInputStream s) 1058 throws IOException, ClassNotFoundException 1059 { 1060 // Read in the threshold (ignored), loadfactor, and any hidden stuff 1061 s.defaultReadObject(); 1062 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 1063 throw new InvalidObjectException("Illegal load factor: " + 1064 loadFactor); 1065 1066 // set hashSeed (can only happen after VM boot) 1067 Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET, 1068 Hashing.randomHashSeed(this)); 1069 1070 // Read in number of buckets and allocate the bucket array; 1071 s.readInt(); // ignored 1072 1073 // Read number of mappings 1074 int mappings = s.readInt(); 1075 if (mappings < 0) 1076 throw new InvalidObjectException("Illegal mappings count: " + 1077 mappings); 1078 1079 int initialCapacity = (int) Math.min( 1080 // capacity chosen by number of mappings 1081 // and desired load (if >= 0.25) 1082 mappings * Math.min(1 / loadFactor, 4.0f), 1083 // we have limits... 1084 HashMapPro.MAXIMUM_CAPACITY); 1085 int capacity = 1; 1086 // find smallest power of two which holds all mappings 1087 while (capacity < initialCapacity) { 1088 capacity <<= 1; 1089 } 1090 1091 table = new Entry[capacity]; 1092 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); 1093 //useAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); 1094 1095 init(); // Give subclass a chance to do its thing. 1096 1097 // Read the keys and values, and put the mappings in the HashMap 1098 for (int i=0; i<mappings; i++) { 1099 K key = (K) s.readObject(); 1100 V value = (V) s.readObject(); 1101 putForCreate(key, value); 1102 } 1103 } 1104 1105 // These methods are used when serializing HashSets 1106 int capacity() { return table.length; } 1107 float loadFactor() { return loadFactor; } 1108 1109 1110 1111 }