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