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