001 package railo.commons.collections; 002 003 import java.io.IOException; 004 import java.util.AbstractCollection; 005 import java.util.AbstractSet; 006 import java.util.Collection; 007 import java.util.ConcurrentModificationException; 008 import java.util.Dictionary; 009 import java.util.Enumeration; 010 import java.util.Iterator; 011 import java.util.Map; 012 import java.util.NoSuchElementException; 013 import java.util.Set; 014 015 /** 016 * This class implements a hashtable, which maps keys to values. Any 017 * non-<code>null</code> object can be used as a key or as a value. <p> 018 * 019 * To successfully store and retrieve objects from a hashtable, the 020 * objects used as keys must implement the <code>hashCode</code> 021 * method and the <code>equals</code> method. <p> 022 * 023 * An instance of <code>Hashtable</code> has two parameters that affect its 024 * performance: <i>initial capacity</i> and <i>load factor</i>. The 025 * <i>capacity</i> is the number of <i>buckets</i> in the hash table, and the 026 * <i>initial capacity</i> is simply the capacity at the time the hash table 027 * is created. Note that the hash table is <i>open</i>: in the case a "hash 028 * collision", a single bucket stores multiple entries, which must be searched 029 * sequentially. The <i>load factor</i> is a measure of how full the hash 030 * table is allowed to get before its capacity is automatically increased. 031 * When the number of entries in the hashtable exceeds the product of the load 032 * factor and the current capacity, the capacity is increased by calling the 033 * <code>rehash</code> method.<p> 034 * 035 * Generally, the default load factor (.75) offers a good tradeoff between 036 * time and space costs. Higher values decrease the space overhead but 037 * increase the time cost to look up an entry (which is reflected in most 038 * <tt>Hashtable</tt> operations, including <tt>get</tt> and <tt>put</tt>).<p> 039 * 040 * The initial capacity controls a tradeoff between wasted space and the 041 * need for <code>rehash</code> operations, which are time-consuming. 042 * No <code>rehash</code> operations will <i>ever</i> occur if the initial 043 * capacity is greater than the maximum number of entries the 044 * <tt>Hashtable</tt> will contain divided by its load factor. However, 045 * setting the initial capacity too high can waste space.<p> 046 * 047 * If many entries are to be made into a <code>Hashtable</code>, 048 * creating it with a sufficiently large capacity may allow the 049 * entries to be inserted more efficiently than letting it perform 050 * automatic rehashing as needed to grow the table. <p> 051 * 052 * This example creates a hashtable of numbers. It uses the names of 053 * the numbers as keys: 054 * <p><blockquote><pre> 055 * Hashtable numbers = new Hashtable(); 056 * numbers.put("one", new Integer(1)); 057 * numbers.put("two", new Integer(2)); 058 * numbers.put("three", new Integer(3)); 059 * </pre></blockquote> 060 * <p> 061 * To retrieve a number, use the following code: 062 * <p><blockquote><pre> 063 * Integer n = (Integer)numbers.get("two"); 064 * if (n != null) { 065 * System.out.println("two = " + n); 066 * } 067 * </pre></blockquote> 068 * <p> 069 * As of the Java 2 platform v1.2, this class has been retrofitted to 070 * implement Map, so that it becomes a part of Java's collection framework. 071 * Unlike the new collection implementations, Hashtable is synchronized.<p> 072 * 073 * The Iterators returned by the iterator and listIterator methods 074 * of the Collections returned by all of Hashtable's "collection view methods" 075 * are <em>fail-fast</em>: if the Hashtable is structurally modified 076 * at any time after the Iterator is created, in any way except through the 077 * Iterator's own remove or add methods, the Iterator will throw a 078 * ConcurrentModificationException. Thus, in the face of concurrent 079 * modification, the Iterator fails quickly and cleanly, rather than risking 080 * arbitrary, non-deterministic behavior at an undetermined time in the future. 081 * The Enumerations returned by Hashtable's keys and values methods are 082 * <em>not</em> fail-fast. 083 * 084 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed 085 * as it is, generally speaking, impossible to make any hard guarantees in the 086 * presence of unsynchronized concurrent modification. Fail-fast iterators 087 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis. 088 * Therefore, it would be wrong to write a program that depended on this 089 * exception for its correctness: <i>the fail-fast behavior of iterators 090 * should be used only to detect bugs.</i> 091 */ 092 public final class HashTableNotSync extends Dictionary implements Map, Cloneable, 093 java.io.Serializable { 094 /** 095 * The hash table data. 096 */ 097 private transient Entry table[]; 098 099 /** 100 * The total number of entries in the hash table. 101 */ 102 private transient int count; 103 104 /** 105 * The table is rehashed when its size exceeds this threshold. (The 106 * value of this field is (int)(capacity * loadFactor).) 107 * 108 * @serial 109 */ 110 private int threshold; 111 112 /** 113 * The load factor for the hashtable. 114 * 115 * @serial 116 */ 117 private float loadFactor; 118 119 /** 120 * The number of times this Hashtable has been structurally modified 121 * Structural modifications are those that change the number of entries in 122 * the Hashtable or otherwise modify its internal structure (e.g., 123 * rehash). This field is used to make iterators on Collection-views of 124 * the Hashtable fail-fast. (See ConcurrentModificationException). 125 */ 126 private transient int modCount = 0; 127 128 /** use serialVersionUID from JDK 1.0.2 for interoperability */ 129 private static final long serialVersionUID = 1421746759512286392L; 130 131 /** 132 * Constructs a new, empty hashtable with the specified initial 133 * capacity and the specified load factor. 134 * 135 * @param initialCapacity the initial capacity of the hashtable. 136 * @param loadFactor the load factor of the hashtable. 137 * @exception IllegalArgumentException if the initial capacity is less 138 * than zero, or if the load factor is nonpositive. 139 */ 140 public HashTableNotSync(int initialCapacity, float loadFactor) { 141 if (initialCapacity < 0) 142 throw new IllegalArgumentException("Illegal Capacity: "+ 143 initialCapacity); 144 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 145 throw new IllegalArgumentException("Illegal Load: "+loadFactor); 146 147 if (initialCapacity==0) 148 initialCapacity = 1; 149 this.loadFactor = loadFactor; 150 table = new Entry[initialCapacity]; 151 threshold = (int)(initialCapacity * loadFactor); 152 } 153 154 /** 155 * Constructs a new, empty hashtable with the specified initial capacity 156 * and default load factor, which is <tt>0.75</tt>. 157 * 158 * @param initialCapacity the initial capacity of the hashtable. 159 * @exception IllegalArgumentException if the initial capacity is less 160 * than zero. 161 */ 162 public HashTableNotSync(int initialCapacity) { 163 this(initialCapacity, 0.75f); 164 } 165 166 /** 167 * Constructs a new, empty hashtable with a default initial capacity (11) 168 * and load factor, which is <tt>0.75</tt>. 169 */ 170 public HashTableNotSync() { 171 this(11, 0.75f); 172 } 173 174 /** 175 * Constructs a new hashtable with the same mappings as the given 176 * Map. The hashtable is created with an initial capacity sufficient to 177 * hold the mappings in the given Map and a default load factor, which is 178 * <tt>0.75</tt>. 179 * 180 * @param t the map whose mappings are to be placed in this map. 181 * @throws NullPointerException if the specified map is null. 182 * 183 */ 184 public HashTableNotSync(Map t) { 185 this(Math.max(2*t.size(), 11), 0.75f); 186 putAll(t); 187 } 188 189 /** 190 * Returns the number of keys in this hashtable. 191 * 192 * @return the number of keys in this hashtable. 193 */ 194 public int size() { 195 return count; 196 } 197 198 /** 199 * Tests if this hashtable maps no keys to values. 200 * 201 * @return <code>true</code> if this hashtable maps no keys to values; 202 * <code>false</code> otherwise. 203 */ 204 public boolean isEmpty() { 205 return count == 0; 206 } 207 208 /** 209 * Returns an enumeration of the keys in this hashtable. 210 * 211 * @return an enumeration of the keys in this hashtable. 212 * @see Enumeration 213 * @see #elements() 214 * @see #keySet() 215 * @see Map 216 */ 217 public Enumeration keys() { 218 return getEnumeration(KEYS); 219 } 220 221 /** 222 * Returns an enumeration of the values in this hashtable. 223 * Use the Enumeration methods on the returned object to fetch the elements 224 * sequentially. 225 * 226 * @return an enumeration of the values in this hashtable. 227 * @see java.util.Enumeration 228 * @see #keys() 229 * @see #values() 230 * @see Map 231 */ 232 public Enumeration elements() { 233 return getEnumeration(VALUES); 234 } 235 236 /** 237 * Tests if some key maps into the specified value in this hashtable. 238 * This operation is more expensive than the <code>containsKey</code> 239 * method.<p> 240 * 241 * Note that this method is identical in functionality to containsValue, 242 * (which is part of the Map interface in the collections framework). 243 * 244 * @param value a value to search for. 245 * @return <code>true</code> if and only if some key maps to the 246 * <code>value</code> argument in this hashtable as 247 * determined by the <tt>equals</tt> method; 248 * <code>false</code> otherwise. 249 * @exception NullPointerException if the value is <code>null</code>. 250 * @see #containsKey(Object) 251 * @see #containsValue(Object) 252 * @see Map 253 */ 254 public boolean contains(Object value) { 255 if (value == null) { 256 throw new NullPointerException(); 257 } 258 259 Entry tab[] = table; 260 for (int i = tab.length ; i-- > 0 ;) { 261 for (Entry e = tab[i] ; e != null ; e = e.next) { 262 if (e.value.equals(value)) { 263 return true; 264 } 265 } 266 } 267 return false; 268 } 269 270 /** 271 * Returns true if this Hashtable maps one or more keys to this value.<p> 272 * 273 * Note that this method is identical in functionality to contains 274 * (which predates the Map interface). 275 * 276 * @param value value whose presence in this Hashtable is to be tested. 277 * @return <tt>true</tt> if this map maps one or more keys to the 278 * specified value. 279 * @see Map 280 * 281 */ 282 public boolean containsValue(Object value) { 283 return contains(value); 284 } 285 286 /** 287 * Tests if the specified object is a key in this hashtable. 288 * 289 * @param key possible key. 290 * @return <code>true</code> if and only if the specified object 291 * is a key in this hashtable, as determined by the 292 * <tt>equals</tt> method; <code>false</code> otherwise. 293 * @see #contains(Object) 294 */ 295 public boolean containsKey(Object key) { 296 Entry tab[] = table; 297 int hash = key.hashCode(); 298 int index = (hash & 0x7FFFFFFF) % tab.length; 299 for (Entry e = tab[index] ; e != null ; e = e.next) { 300 if ((e.hash == hash) && e.key.equals(key)) { 301 return true; 302 } 303 } 304 return false; 305 } 306 307 /** 308 * Returns the value to which the specified key is mapped in this hashtable. 309 * 310 * @param key a key in the hashtable. 311 * @return the value to which the key is mapped in this hashtable; 312 * <code>null</code> if the key is not mapped to any value in 313 * this hashtable. 314 * @see #put(Object, Object) 315 */ 316 public Object get(Object key) { 317 Entry tab[] = table; 318 int hash = key.hashCode(); 319 int index = (hash & 0x7FFFFFFF) % tab.length; 320 for (Entry e = tab[index] ; e != null ; e = e.next) { 321 if ((e.hash == hash) && e.key.equals(key)) { 322 return e.value; 323 } 324 } 325 return null; 326 } 327 328 /** 329 * Increases the capacity of and internally reorganizes this 330 * hashtable, in order to accommodate and access its entries more 331 * efficiently. This method is called automatically when the 332 * number of keys in the hashtable exceeds this hashtable's capacity 333 * and load factor. 334 */ 335 protected void rehash() { 336 int oldCapacity = table.length; 337 Entry oldMap[] = table; 338 339 int newCapacity = oldCapacity * 2 + 1; 340 Entry newMap[] = new Entry[newCapacity]; 341 342 modCount++; 343 threshold = (int)(newCapacity * loadFactor); 344 table = newMap; 345 346 for (int i = oldCapacity ; i-- > 0 ;) { 347 for (Entry old = oldMap[i] ; old != null ; ) { 348 Entry e = old; 349 old = old.next; 350 351 int index = (e.hash & 0x7FFFFFFF) % newCapacity; 352 e.next = newMap[index]; 353 newMap[index] = e; 354 } 355 } 356 } 357 358 /** 359 * Maps the specified <code>key</code> to the specified 360 * <code>value</code> in this hashtable. Neither the key nor the 361 * value can be <code>null</code>. <p> 362 * 363 * The value can be retrieved by calling the <code>get</code> method 364 * with a key that is equal to the original key. 365 * 366 * @param key the hashtable key. 367 * @param value the value. 368 * @return the previous value of the specified key in this hashtable, 369 * or <code>null</code> if it did not have one. 370 * @exception NullPointerException if the key or value is 371 * <code>null</code>. 372 * @see Object#equals(Object) 373 * @see #get(Object) 374 */ 375 public Object put(Object key, Object value) { 376 // Make sure the value is not null 377 if (value == null) { 378 return remove(key); 379 } 380 381 // Makes sure the key is not already in the hashtable. 382 Entry tab[] = table; 383 int hash = key.hashCode(); 384 int index = (hash & 0x7FFFFFFF) % tab.length; 385 for (Entry e = tab[index] ; e != null ; e = e.next) { 386 if ((e.hash == hash) && e.key.equals(key)) { 387 Object old = e.value; 388 e.value = value; 389 return old; 390 } 391 } 392 393 modCount++; 394 if (count >= threshold) { 395 // Rehash the table if the threshold is exceeded 396 rehash(); 397 398 tab = table; 399 index = (hash & 0x7FFFFFFF) % tab.length; 400 } 401 402 // Creates the new entry. 403 Entry e = new Entry(hash, key, value, tab[index]); 404 tab[index] = e; 405 count++; 406 return null; 407 } 408 409 /** 410 * Removes the key (and its corresponding value) from this 411 * hashtable. This method does nothing if the key is not in the hashtable. 412 * 413 * @param key the key that needs to be removed. 414 * @return the value to which the key had been mapped in this hashtable, 415 * or <code>null</code> if the key did not have a mapping. 416 */ 417 public Object remove(Object key) { 418 Entry tab[] = table; 419 int hash = key.hashCode(); 420 int index = (hash & 0x7FFFFFFF) % tab.length; 421 for (Entry e = tab[index], prev = null ; e != null ; prev = e, e = e.next) { 422 if ((e.hash == hash) && e.key.equals(key)) { 423 modCount++; 424 if (prev != null) { 425 prev.next = e.next; 426 } else { 427 tab[index] = e.next; 428 } 429 count--; 430 Object oldValue = e.value; 431 e.value = null; 432 return oldValue; 433 } 434 } 435 return null; 436 } 437 438 /** 439 * Copies all of the mappings from the specified Map to this Hashtable 440 * These mappings will replace any mappings that this Hashtable had for any 441 * of the keys currently in the specified Map. 442 * 443 * @param t Mappings to be stored in this map. 444 * @throws NullPointerException if the specified map is null. 445 * 446 */ 447 public void putAll(Map t) { 448 Iterator i = t.entrySet().iterator(); 449 while (i.hasNext()) { 450 Map.Entry e = (Map.Entry) i.next(); 451 put(e.getKey(), e.getValue()); 452 } 453 } 454 455 /** 456 * Clears this hashtable so that it contains no keys. 457 */ 458 public void clear() { 459 Entry tab[] = table; 460 modCount++; 461 for (int index = tab.length; --index >= 0; ) 462 tab[index] = null; 463 count = 0; 464 } 465 466 /** 467 * Creates a shallow copy of this hashtable. All the structure of the 468 * hashtable itself is copied, but the keys and values are not cloned. 469 * This is a relatively expensive operation. 470 * 471 * @return a clone of the hashtable. 472 */ 473 public Object clone() { 474 try { 475 HashTableNotSync t = (HashTableNotSync)super.clone(); 476 t.table = new Entry[table.length]; 477 for (int i = table.length ; i-- > 0 ; ) { 478 t.table[i] = (table[i] != null) 479 ? (Entry)table[i].clone() : null; 480 } 481 t.keySet = null; 482 t.entrySet = null; 483 t.values = null; 484 t.modCount = 0; 485 return t; 486 } catch (CloneNotSupportedException e) { 487 // this shouldn't happen, since we are Cloneable 488 throw new InternalError(); 489 } 490 } 491 492 /** 493 * Returns a string representation of this <tt>Hashtable</tt> object 494 * in the form of a set of entries, enclosed in braces and separated 495 * by the ASCII characters "<tt>, </tt>" (comma and space). Each 496 * entry is rendered as the key, an equals sign <tt>=</tt>, and the 497 * associated element, where the <tt>toString</tt> method is used to 498 * convert the key and element to strings. <p>Overrides to 499 * <tt>toString</tt> method of <tt>Object</tt>. 500 * 501 * @return a string representation of this hashtable. 502 */ 503 public String toString() { 504 int max = size() - 1; 505 StringBuffer buf = new StringBuffer(); 506 Iterator it = entrySet().iterator(); 507 508 buf.append("{"); 509 for (int i = 0; i <= max; i++) { 510 Map.Entry e = (Map.Entry) (it.next()); 511 Object key = e.getKey(); 512 Object value = e.getValue(); 513 buf.append((key == this ? "(this Map)" : key) + "=" + 514 (value == this ? "(this Map)" : value)); 515 516 if (i < max) 517 buf.append(", "); 518 } 519 buf.append("}"); 520 return buf.toString(); 521 } 522 523 524 private Enumeration getEnumeration(int type) { 525 if (count == 0) { 526 return emptyEnumerator; 527 } 528 return new Enumerator(type, false); 529 530 } 531 532 private Iterator getIterator(int type) { 533 if (count == 0) { 534 return emptyIterator; 535 } 536 return new Enumerator(type, true); 537 } 538 539 // Views 540 541 /** 542 * Each of these fields are initialized to contain an instance of the 543 * appropriate view the first time this view is requested. The views are 544 * stateless, so there's no reason to create more than one of each. 545 */ 546 private transient volatile Set keySet = null; 547 private transient volatile Set entrySet = null; 548 private transient volatile Collection values = null; 549 550 /** 551 * Returns a Set view of the keys contained in this Hashtable. The Set 552 * is backed by the Hashtable, so changes to the Hashtable are reflected 553 * in the Set, and vice-versa. The Set supports element removal 554 * (which removes the corresponding entry from the Hashtable), but not 555 * element addition. 556 * 557 * @return a set view of the keys contained in this map. 558 * 559 */ 560 public Set keySet() { 561 if (keySet == null) 562 keySet = Collections.synchronizedSet(new KeySet(), this); 563 return keySet; 564 } 565 566 private class KeySet extends AbstractSet { 567 /** 568 * @see java.util.Set#iterator() 569 */ 570 public Iterator iterator() { 571 return getIterator(KEYS); 572 } 573 /** 574 * @see java.util.Set#size() 575 */ 576 public int size() { 577 return count; 578 } 579 /** 580 * @see java.util.Set#contains(java.lang.Object) 581 */ 582 public boolean contains(Object o) { 583 return containsKey(o); 584 } 585 /** 586 * @see java.util.Set#remove(java.lang.Object) 587 */ 588 public boolean remove(Object o) { 589 return HashTableNotSync.this.remove(o) != null; 590 } 591 /** 592 * @see java.util.Set#clear() 593 */ 594 public void clear() { 595 HashTableNotSync.this.clear(); 596 } 597 } 598 599 /** 600 * Returns a Set view of the entries contained in this Hashtable. 601 * Each element in this collection is a Map.Entry. The Set is 602 * backed by the Hashtable, so changes to the Hashtable are reflected in 603 * the Set, and vice-versa. The Set supports element removal 604 * (which removes the corresponding entry from the Hashtable), 605 * but not element addition. 606 * 607 * @return a set view of the mappings contained in this map. 608 * @see Map.Entry 609 * 610 */ 611 public Set entrySet() { 612 if (entrySet==null) 613 entrySet = Collections.synchronizedSet(new EntrySet(), this); 614 return entrySet; 615 } 616 617 private class EntrySet extends AbstractSet { 618 /** 619 * @see java.util.Set#iterator() 620 */ 621 public Iterator iterator() { 622 return getIterator(ENTRIES); 623 } 624 625 /** 626 * @see java.util.Set#contains(java.lang.Object) 627 */ 628 public boolean contains(Object o) { 629 if (!(o instanceof Map.Entry)) 630 return false; 631 Map.Entry entry = (Map.Entry)o; 632 Object key = entry.getKey(); 633 Entry tab[] = table; 634 int hash = key.hashCode(); 635 int index = (hash & 0x7FFFFFFF) % tab.length; 636 637 for (Entry e = tab[index]; e != null; e = e.next) 638 if (e.hash==hash && e.equals(entry)) 639 return true; 640 return false; 641 } 642 643 /** 644 * @see java.util.Set#remove(java.lang.Object) 645 */ 646 public boolean remove(Object o) { 647 if (!(o instanceof Map.Entry)) 648 return false; 649 Map.Entry entry = (Map.Entry)o; 650 Object key = entry.getKey(); 651 Entry tab[] = table; 652 int hash = key.hashCode(); 653 int index = (hash & 0x7FFFFFFF) % tab.length; 654 655 for (Entry e = tab[index], prev = null; e != null; 656 prev = e, e = e.next) { 657 if (e.hash==hash && e.equals(entry)) { 658 modCount++; 659 if (prev != null) 660 prev.next = e.next; 661 else 662 tab[index] = e.next; 663 664 count--; 665 e.value = null; 666 return true; 667 } 668 } 669 return false; 670 } 671 672 /** 673 * @see java.util.Set#size() 674 */ 675 public int size() { 676 return count; 677 } 678 679 /** 680 * @see java.util.Set#clear() 681 */ 682 public void clear() { 683 HashTableNotSync.this.clear(); 684 } 685 } 686 687 /** 688 * Returns a Collection view of the values contained in this Hashtable. 689 * The Collection is backed by the Hashtable, so changes to the Hashtable 690 * are reflected in the Collection, and vice-versa. The Collection 691 * supports element removal (which removes the corresponding entry from 692 * the Hashtable), but not element addition. 693 * 694 * @return a collection view of the values contained in this map. 695 * 696 */ 697 public Collection values() { 698 if (values==null) 699 values = Collections.synchronizedCollection(new ValueCollection(), 700 this); 701 return values; 702 } 703 704 private class ValueCollection extends AbstractCollection { 705 /** 706 * @see java.util.AbstractCollection#iterator() 707 */ 708 public Iterator iterator() { 709 return getIterator(VALUES); 710 } 711 /** 712 * @see java.util.AbstractCollection#size() 713 */ 714 public int size() { 715 return count; 716 } 717 /** 718 * @see java.util.AbstractCollection#contains(java.lang.Object) 719 */ 720 public boolean contains(Object o) { 721 return containsValue(o); 722 } 723 /** 724 * @see java.util.AbstractCollection#clear() 725 */ 726 public void clear() { 727 HashTableNotSync.this.clear(); 728 } 729 } 730 731 // Comparison and hashing 732 733 /** 734 * Compares the specified Object with this Map for equality, 735 * as per the definition in the Map interface. 736 * 737 * @param o object to be compared for equality with this Hashtable 738 * @return true if the specified Object is equal to this Map. 739 * @see Map#equals(Object) 740 * 741 */ 742 public boolean equals(Object o) { 743 if (o == this) 744 return true; 745 746 if (!(o instanceof Map)) 747 return false; 748 Map t = (Map) o; 749 if (t.size() != size()) 750 return false; 751 752 try { 753 Iterator i = entrySet().iterator(); 754 while (i.hasNext()) { 755 Map.Entry e = (Map.Entry) i.next(); 756 Object key = e.getKey(); 757 Object value = e.getValue(); 758 if (value == null) { 759 if (!(t.get(key)==null && t.containsKey(key))) 760 return false; 761 } else { 762 if (!value.equals(t.get(key))) 763 return false; 764 } 765 } 766 } catch(ClassCastException unused) { 767 return false; 768 } catch(NullPointerException unused) { 769 return false; 770 } 771 772 return true; 773 } 774 775 /** 776 * Returns the hash code value for this Map as per the definition in the 777 * Map interface. 778 * 779 * @see Map#hashCode() 780 * 781 */ 782 public int hashCode() { 783 /* 784 * This code detects the recursion caused by computing the hash code 785 * of a self-referential hash table and prevents the stack overflow 786 * that would otherwise result. This allows certain 1.1-era 787 * applets with self-referential hash tables to work. This code 788 * abuses the loadFactor field to do double-duty as a hashCode 789 * in progress flag, so as not to worsen the space performance. 790 * A negative load factor indicates that hash code computation is 791 * in progress. 792 */ 793 int h = 0; 794 if (count == 0 || loadFactor < 0) 795 return h; // Returns zero 796 797 loadFactor = -loadFactor; // Mark hashCode computation in progress 798 Entry tab[] = table; 799 for (int i = 0; i < tab.length; i++) 800 for (Entry e = tab[i]; e != null; e = e.next) 801 h += e.key.hashCode() ^ e.value.hashCode(); 802 loadFactor = -loadFactor; // Mark hashCode computation complete 803 804 return h; 805 } 806 807 /** 808 * Save the state of the Hashtable to a stream (i.e., serialize it). 809 * @param s 810 * @throws IOException 811 * 812 * @serialData The <i>capacity</i> of the Hashtable (the length of the 813 * bucket array) is emitted (int), followed by the 814 * <i>size</i> of the Hashtable (the number of key-value 815 * mappings), followed by the key (Object) and value (Object) 816 * for each key-value mapping represented by the Hashtable 817 * The key-value mappings are emitted in no particular order. 818 */ 819 private void writeObject(java.io.ObjectOutputStream s) 820 throws IOException 821 { 822 // Write out the length, threshold, loadfactor 823 s.defaultWriteObject(); 824 825 // Write out length, count of elements and then the key/value objects 826 s.writeInt(table.length); 827 s.writeInt(count); 828 for (int index = table.length-1; index >= 0; index--) { 829 Entry entry = table[index]; 830 831 while (entry != null) { 832 s.writeObject(entry.key); 833 s.writeObject(entry.value); 834 entry = entry.next; 835 } 836 } 837 } 838 839 /** 840 * Reconstitute the Hashtable from a stream (i.e., deserialize it). 841 * @param s 842 * @throws IOException 843 * @throws ClassNotFoundException 844 */ 845 private void readObject(java.io.ObjectInputStream s) 846 throws IOException, ClassNotFoundException 847 { 848 // Read in the length, threshold, and loadfactor 849 s.defaultReadObject(); 850 851 // Read the original length of the array and number of elements 852 int origlength = s.readInt(); 853 int elements = s.readInt(); 854 855 // Compute new size with a bit of room 5% to grow but 856 // No larger than the original size. Make the length 857 // odd if it's large enough, this helps distribute the entries. 858 // Guard against the length ending up zero, that's not valid. 859 int length = (int)(elements * loadFactor) + (elements / 20) + 3; 860 if (length > elements && (length & 1) == 0) 861 length--; 862 if (origlength > 0 && length > origlength) 863 length = origlength; 864 865 table = new Entry[length]; 866 count = 0; 867 868 // Read the number of elements and then all the key/value objects 869 for (; elements > 0; elements--) { 870 Object key = s.readObject(); 871 Object value = s.readObject(); 872 put(key, value); 873 } 874 } 875 876 877 /** 878 * Hashtable collision list. 879 */ 880 private static class Entry implements Map.Entry { 881 int hash; 882 Object key; 883 Object value; 884 Entry next; 885 886 /** 887 * @param hash 888 * @param key 889 * @param value 890 * @param next 891 */ 892 protected Entry(int hash, Object key, Object value, Entry next) { 893 this.hash = hash; 894 this.key = key; 895 this.value = value; 896 this.next = next; 897 } 898 899 /** 900 * @see java.lang.Object#clone() 901 */ 902 protected Object clone() { 903 return new Entry(hash, key, value, 904 (next==null ? null : (Entry)next.clone())); 905 } 906 907 // Map.Entry Ops 908 909 /** 910 * @see java.util.Map.Entry#getKey() 911 */ 912 public Object getKey() { 913 return key; 914 } 915 916 /** 917 * @see java.util.Map.Entry#getValue() 918 */ 919 public Object getValue() { 920 return value; 921 } 922 923 /** 924 * @see java.util.Map.Entry#setValue(java.lang.Object) 925 */ 926 public Object setValue(Object value) { 927 if (value == null) 928 throw new NullPointerException(); 929 930 Object oldValue = this.value; 931 this.value = value; 932 return oldValue; 933 } 934 935 /** 936 * @see java.util.Map.Entry#equals(java.lang.Object) 937 */ 938 public boolean equals(Object o) { 939 if (!(o instanceof Map.Entry)) 940 return false; 941 Map.Entry e = (Map.Entry)o; 942 943 return (key==null ? e.getKey()==null : key.equals(e.getKey())) && 944 (value==null ? e.getValue()==null : value.equals(e.getValue())); 945 } 946 947 /** 948 * @see java.util.Map.Entry#hashCode() 949 */ 950 public int hashCode() { 951 return hash ^ (value==null ? 0 : value.hashCode()); 952 } 953 954 /** 955 * @see java.lang.Object#toString() 956 */ 957 public String toString() { 958 return key.toString()+"="+value.toString(); 959 } 960 } 961 962 // Types of Enumerations/Iterations 963 private static final int KEYS = 0; 964 private static final int VALUES = 1; 965 private static final int ENTRIES = 2; 966 967 /** 968 * A hashtable enumerator class. This class implements both the 969 * Enumeration and Iterator interfaces, but individual instances 970 * can be created with the Iterator methods disabled. This is necessary 971 * to avoid unintentionally increasing the capabilities granted a user 972 * by passing an Enumeration. 973 */ 974 private class Enumerator implements Enumeration, Iterator { 975 Entry[] table = HashTableNotSync.this.table; 976 int index = table.length; 977 Entry entry = null; 978 Entry lastReturned = null; 979 int type; 980 981 /** 982 * Indicates whether this Enumerator is serving as an Iterator 983 * or an Enumeration. (true -> Iterator). 984 */ 985 boolean iterator; 986 987 /** 988 * The modCount value that the iterator believes that the backing 989 * List should have. If this expectation is violated, the iterator 990 * has detected concurrent modification. 991 */ 992 protected int expectedModCount = modCount; 993 994 Enumerator(int type, boolean iterator) { 995 this.type = type; 996 this.iterator = iterator; 997 } 998 999 /** 1000 * @see java.util.Enumeration#hasMoreElements() 1001 */ 1002 public boolean hasMoreElements() { 1003 Entry e = entry; 1004 int i = index; 1005 Entry t[] = table; 1006 /* Use locals for faster loop iteration */ 1007 while (e == null && i > 0) { 1008 e = t[--i]; 1009 } 1010 entry = e; 1011 index = i; 1012 return e != null; 1013 } 1014 1015 /** 1016 * @see java.util.Enumeration#nextElement() 1017 */ 1018 public Object nextElement() { 1019 Entry et = entry; 1020 int i = index; 1021 Entry t[] = table; 1022 /* Use locals for faster loop iteration */ 1023 while (et == null && i > 0) { 1024 et = t[--i]; 1025 } 1026 entry = et; 1027 index = i; 1028 if (et != null) { 1029 Entry e = lastReturned = entry; 1030 entry = e.next; 1031 return type == KEYS ? e.key : (type == VALUES ? e.value : e); 1032 } 1033 throw new NoSuchElementException("Hashtable Enumerator"); 1034 } 1035 1036 /** 1037 * @see java.util.Iterator#hasNext() 1038 */ 1039 // Iterator methods 1040 public boolean hasNext() { 1041 return hasMoreElements(); 1042 } 1043 1044 /** 1045 * @see java.util.Iterator#next() 1046 */ 1047 public Object next() { 1048 if (modCount != expectedModCount) 1049 throw new ConcurrentModificationException(); 1050 return nextElement(); 1051 } 1052 1053 /** 1054 * @see java.util.Iterator#remove() 1055 */ 1056 public void remove() { 1057 if (!iterator) 1058 throw new UnsupportedOperationException(); 1059 if (lastReturned == null) 1060 throw new IllegalStateException("Hashtable Enumerator"); 1061 if (modCount != expectedModCount) 1062 throw new ConcurrentModificationException(); 1063 1064 synchronized(HashTableNotSync.this) { 1065 Entry[] tab = HashTableNotSync.this.table; 1066 int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length; 1067 1068 for (Entry e = tab[index], prev = null; e != null; 1069 prev = e, e = e.next) { 1070 if (e == lastReturned) { 1071 modCount++; 1072 expectedModCount++; 1073 if (prev == null) 1074 tab[index] = e.next; 1075 else 1076 prev.next = e.next; 1077 count--; 1078 lastReturned = null; 1079 return; 1080 } 1081 } 1082 throw new ConcurrentModificationException(); 1083 } 1084 } 1085 } 1086 1087 1088 private static EmptyEnumerator emptyEnumerator = new EmptyEnumerator(); 1089 private static EmptyIterator emptyIterator = new EmptyIterator(); 1090 1091 /** 1092 * A hashtable enumerator class for empty hash tables, specializes 1093 * the general Enumerator 1094 */ 1095 private static class EmptyEnumerator implements Enumeration { 1096 1097 EmptyEnumerator() { 1098 } 1099 1100 /** 1101 * @see java.util.Enumeration#hasMoreElements() 1102 */ 1103 public boolean hasMoreElements() { 1104 return false; 1105 } 1106 1107 /** 1108 * @see java.util.Enumeration#nextElement() 1109 */ 1110 public Object nextElement() { 1111 throw new NoSuchElementException("Hashtable Enumerator"); 1112 } 1113 } 1114 1115 1116 /** 1117 * A hashtable iterator class for empty hash tables 1118 */ 1119 private static class EmptyIterator implements Iterator { 1120 1121 EmptyIterator() { 1122 } 1123 1124 /** 1125 * @see java.util.Iterator#hasNext() 1126 */ 1127 public boolean hasNext() { 1128 return false; 1129 } 1130 1131 /** 1132 * @see java.util.Iterator#next() 1133 */ 1134 public Object next() { 1135 throw new NoSuchElementException("Hashtable Iterator"); 1136 } 1137 1138 /** 1139 * @see java.util.Iterator#remove() 1140 */ 1141 public void remove() { 1142 throw new IllegalStateException("Hashtable Iterator"); 1143 } 1144 1145 } 1146 1147 }