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 @Override 211 public synchronized Enumeration keys() { 212 return getEnumeration(KEYS); 213 } 214 215 @Override 216 public synchronized Enumeration elements() { 217 return getEnumeration(VALUES); 218 } 219 220 public synchronized boolean contains(Object value) { 221 if (value == null) { 222 throw new NullPointerException(); 223 } 224 225 Entry tab[] = table; 226 for (int i = tab.length ; i-- > 0 ;) { 227 for (Entry e = tab[i] ; e != null ; e = e.next) { 228 if (e.value.equals(value)) { 229 return true; 230 } 231 } 232 } 233 return false; 234 } 235 236 @Override 237 public boolean containsValue(Object value) { 238 return contains(value); 239 } 240 241 @Override 242 public synchronized boolean containsKey(Object key) { 243 Entry tab[] = table; 244 int hash = key.hashCode(); 245 int index = (hash & 0x7FFFFFFF) % tab.length; 246 for (Entry e = tab[index] ; e != null ; e = e.next) { 247 if ((e.hash == hash) && e.key.equals(key)) { 248 return true; 249 } 250 } 251 return false; 252 } 253 254 @Override 255 public synchronized Object get(Object key) { 256 Entry tab[] = table; 257 int hash = key.hashCode(); 258 int index = (hash & 0x7FFFFFFF) % tab.length; 259 for (Entry e = tab[index] ; e != null ; e = e.next) { 260 if ((e.hash == hash) && e.key.equals(key)) { 261 return e.value; 262 } 263 } 264 return null; 265 } 266 267 /** 268 * Increases the capacity of and internally reorganizes this 269 * hashtable, in order to accommodate and access its entries more 270 * efficiently. This method is called automatically when the 271 * number of keys in the hashtable exceeds this hashtable's capacity 272 * and load factor. 273 */ 274 protected void rehash() { 275 int oldCapacity = table.length; 276 Entry oldMap[] = table; 277 278 int newCapacity = oldCapacity * 2 + 1; 279 Entry newMap[] = new Entry[newCapacity]; 280 281 modCount++; 282 threshold = (int)(newCapacity * loadFactor); 283 table = newMap; 284 285 for (int i = oldCapacity ; i-- > 0 ;) { 286 for (Entry old = oldMap[i] ; old != null ; ) { 287 Entry e = old; 288 old = old.next; 289 290 int index = (e.hash & 0x7FFFFFFF) % newCapacity; 291 e.next = newMap[index]; 292 newMap[index] = e; 293 } 294 } 295 } 296 297 @Override 298 public synchronized Object put(Object key, Object value) { 299 // Make sure the value is not null 300 if (value == null) { 301 return remove(key); 302 } 303 304 // Makes sure the key is not already in the hashtable. 305 Entry tab[] = table; 306 int hash = key.hashCode(); 307 int index = (hash & 0x7FFFFFFF) % tab.length; 308 for (Entry e = tab[index] ; e != null ; e = e.next) { 309 if ((e.hash == hash) && e.key.equals(key)) { 310 Object old = e.value; 311 e.value = value; 312 return old; 313 } 314 } 315 316 modCount++; 317 if (count >= threshold) { 318 // Rehash the table if the threshold is exceeded 319 rehash(); 320 321 tab = table; 322 index = (hash & 0x7FFFFFFF) % tab.length; 323 } 324 325 // Creates the new entry. 326 Entry e = new Entry(hash, key, value, tab[index]); 327 tab[index] = e; 328 count++; 329 return null; 330 } 331 332 /** 333 * Removes the key (and its corresponding value) from this 334 * hashtable. This method does nothing if the key is not in the hashtable. 335 * 336 * @param key the key that needs to be removed. 337 * @return the value to which the key had been mapped in this hashtable, 338 * or <code>null</code> if the key did not have a mapping. 339 */ 340 public synchronized Object remove(Object key) { 341 Entry tab[] = table; 342 int hash = key.hashCode(); 343 int index = (hash & 0x7FFFFFFF) % tab.length; 344 for (Entry e = tab[index], prev = null ; e != null ; prev = e, e = e.next) { 345 if ((e.hash == hash) && e.key.equals(key)) { 346 modCount++; 347 if (prev != null) { 348 prev.next = e.next; 349 } else { 350 tab[index] = e.next; 351 } 352 count--; 353 Object oldValue = e.value; 354 e.value = null; 355 return oldValue; 356 } 357 } 358 return null; 359 } 360 361 /** 362 * Copies all of the mappings from the specified Map to this Hashtable 363 * These mappings will replace any mappings that this Hashtable had for any 364 * of the keys currently in the specified Map. 365 * 366 * @param t Mappings to be stored in this map. 367 * @throws NullPointerException if the specified map is null. 368 */ 369 public synchronized void putAll(Map t) { 370 Iterator i = t.entrySet().iterator(); 371 while (i.hasNext()) { 372 Map.Entry e = (Map.Entry) i.next(); 373 put(e.getKey(), e.getValue()); 374 } 375 } 376 377 /** 378 * Clears this hashtable so that it contains no keys. 379 */ 380 public synchronized void clear() { 381 Entry tab[] = table; 382 modCount++; 383 for (int index = tab.length; --index >= 0; ) 384 tab[index] = null; 385 count = 0; 386 } 387 388 /** 389 * Creates a shallow copy of this hashtable. All the structure of the 390 * hashtable itself is copied, but the keys and values are not cloned. 391 * This is a relatively expensive operation. 392 * 393 * @return a clone of the hashtable. 394 */ 395 public synchronized Object clone() { 396 try { 397 HashTable t = (HashTable)super.clone(); 398 t.table = new Entry[table.length]; 399 for (int i = table.length ; i-- > 0 ; ) { 400 t.table[i] = (table[i] != null) 401 ? (Entry)table[i].clone() : null; 402 } 403 t.keySet = null; 404 t.entrySet = null; 405 t.values = null; 406 t.modCount = 0; 407 return t; 408 } catch (CloneNotSupportedException e) { 409 // this shouldn't happen, since we are Cloneable 410 throw new InternalError(); 411 } 412 } 413 414 /** 415 * Returns a string representation of this <tt>Hashtable</tt> object 416 * in the form of a set of entries, enclosed in braces and separated 417 * by the ASCII characters "<tt>, </tt>" (comma and space). Each 418 * entry is rendered as the key, an equals sign <tt>=</tt>, and the 419 * associated element, where the <tt>toString</tt> method is used to 420 * convert the key and element to strings. <p>Overrides to 421 * <tt>toString</tt> method of <tt>Object</tt>. 422 * 423 * @return a string representation of this hashtable. 424 */ 425 public synchronized String toString() { 426 int max = size() - 1; 427 StringBuffer buf = new StringBuffer(); 428 Iterator it = entrySet().iterator(); 429 430 buf.append("{"); 431 for (int i = 0; i <= max; i++) { 432 Map.Entry e = (Map.Entry) (it.next()); 433 Object key = e.getKey(); 434 Object value = e.getValue(); 435 buf.append((key == this ? "(this Map)" : key) + "=" + 436 (value == this ? "(this Map)" : value)); 437 438 if (i < max) 439 buf.append(", "); 440 } 441 buf.append("}"); 442 return buf.toString(); 443 } 444 445 446 private Enumeration getEnumeration(int type) { 447 if (count == 0) { 448 return emptyEnumerator; 449 } 450 return new Enumerator(type, false); 451 452 } 453 454 private Iterator getIterator(int type) { 455 if (count == 0) { 456 return emptyIterator; 457 } 458 return new Enumerator(type, true); 459 } 460 461 // Views 462 463 /** 464 * Each of these fields are initialized to contain an instance of the 465 * appropriate view the first time this view is requested. The views are 466 * stateless, so there's no reason to create more than one of each. 467 */ 468 private transient volatile Set keySet = null; 469 private transient volatile Set entrySet = null; 470 private transient volatile Collection values = null; 471 472 /** 473 * Returns a Set view of the keys contained in this Hashtable. The Set 474 * is backed by the Hashtable, so changes to the Hashtable are reflected 475 * in the Set, and vice-versa. The Set supports element removal 476 * (which removes the corresponding entry from the Hashtable), but not 477 * element addition. 478 * 479 * @return a set view of the keys contained in this map. 480 */ 481 public Set keySet() { 482 if (keySet == null) 483 keySet = Collections.synchronizedSet(new KeySet(), this); 484 return keySet; 485 } 486 487 private class KeySet extends AbstractSet { 488 @Override 489 public Iterator iterator() { 490 return getIterator(KEYS); 491 } 492 @Override 493 public int size() { 494 return count; 495 } 496 @Override 497 public boolean contains(Object o) { 498 return containsKey(o); 499 } 500 @Override 501 public boolean remove(Object o) { 502 return HashTable.this.remove(o) != null; 503 } 504 @Override 505 public void clear() { 506 HashTable.this.clear(); 507 } 508 } 509 510 @Override 511 public Set entrySet() { 512 if (entrySet==null) 513 entrySet = Collections.synchronizedSet(new EntrySet(), this); 514 return entrySet; 515 } 516 517 private class EntrySet extends AbstractSet { 518 @Override 519 public Iterator iterator() { 520 return getIterator(ENTRIES); 521 } 522 523 @Override 524 public boolean contains(Object o) { 525 if (!(o instanceof Map.Entry)) 526 return false; 527 Map.Entry entry = (Map.Entry)o; 528 Object key = entry.getKey(); 529 Entry tab[] = table; 530 int hash = key.hashCode(); 531 int index = (hash & 0x7FFFFFFF) % tab.length; 532 533 for (Entry e = tab[index]; e != null; e = e.next) 534 if (e.hash==hash && e.equals(entry)) 535 return true; 536 return false; 537 } 538 539 @Override 540 public boolean remove(Object o) { 541 if (!(o instanceof Map.Entry)) 542 return false; 543 Map.Entry entry = (Map.Entry)o; 544 Object key = entry.getKey(); 545 Entry tab[] = table; 546 int hash = key.hashCode(); 547 int index = (hash & 0x7FFFFFFF) % tab.length; 548 549 for (Entry e = tab[index], prev = null; e != null; 550 prev = e, e = e.next) { 551 if (e.hash==hash && e.equals(entry)) { 552 modCount++; 553 if (prev != null) 554 prev.next = e.next; 555 else 556 tab[index] = e.next; 557 558 count--; 559 e.value = null; 560 return true; 561 } 562 } 563 return false; 564 } 565 566 @Override 567 public int size() { 568 return count; 569 } 570 571 @Override 572 public void clear() { 573 HashTable.this.clear(); 574 } 575 } 576 577 /** 578 * Returns a Collection view of the values contained in this Hashtable. 579 * The Collection is backed by the Hashtable, so changes to the Hashtable 580 * are reflected in the Collection, and vice-versa. The Collection 581 * supports element removal (which removes the corresponding entry from 582 * the Hashtable), but not element addition. 583 * 584 * @return a collection view of the values contained in this map. 585 * 586 */ 587 public Collection values() { 588 if (values==null) 589 values = Collections.synchronizedCollection(new ValueCollection(), 590 this); 591 return values; 592 } 593 594 private class ValueCollection extends AbstractCollection { 595 @Override 596 public Iterator iterator() { 597 return getIterator(VALUES); 598 } 599 @Override 600 public int size() { 601 return count; 602 } 603 @Override 604 public boolean contains(Object o) { 605 return containsValue(o); 606 } 607 @Override 608 public void clear() { 609 HashTable.this.clear(); 610 } 611 } 612 613 // Comparison and hashing 614 615 @Override 616 public synchronized boolean equals(Object o) { 617 if (o == this) 618 return true; 619 620 if (!(o instanceof Map)) 621 return false; 622 Map t = (Map) o; 623 if (t.size() != size()) 624 return false; 625 626 try { 627 Iterator i = entrySet().iterator(); 628 while (i.hasNext()) { 629 Map.Entry e = (Map.Entry) i.next(); 630 Object key = e.getKey(); 631 Object value = e.getValue(); 632 if (value == null) { 633 if (!(t.get(key)==null && t.containsKey(key))) 634 return false; 635 } else { 636 if (!value.equals(t.get(key))) 637 return false; 638 } 639 } 640 } catch(ClassCastException unused) { 641 return false; 642 } catch(NullPointerException unused) { 643 return false; 644 } 645 646 return true; 647 } 648 649 @Override 650 public synchronized int hashCode() { 651 /* 652 * This code detects the recursion caused by computing the hash code 653 * of a self-referential hash table and prevents the stack overflow 654 * that would otherwise result. This allows certain 1.1-era 655 * applets with self-referential hash tables to work. This code 656 * abuses the loadFactor field to do double-duty as a hashCode 657 * in progress flag, so as not to worsen the space performance. 658 * A negative load factor indicates that hash code computation is 659 * in progress. 660 */ 661 int h = 0; 662 if (count == 0 || loadFactor < 0) 663 return h; // Returns zero 664 665 loadFactor = -loadFactor; // Mark hashCode computation in progress 666 Entry tab[] = table; 667 for (int i = 0; i < tab.length; i++) 668 for (Entry e = tab[i]; e != null; e = e.next) 669 h += e.key.hashCode() ^ e.value.hashCode(); 670 loadFactor = -loadFactor; // Mark hashCode computation complete 671 672 return h; 673 } 674 675 /** 676 * Save the state of the Hashtable to a stream (i.e., serialize it). 677 * @param s 678 * @throws IOException 679 * 680 * @serialData The <i>capacity</i> of the Hashtable (the length of the 681 * bucket array) is emitted (int), followed by the 682 * <i>size</i> of the Hashtable (the number of key-value 683 * mappings), followed by the key (Object) and value (Object) 684 * for each key-value mapping represented by the Hashtable 685 * The key-value mappings are emitted in no particular order. 686 */ 687 private synchronized void writeObject(java.io.ObjectOutputStream s) 688 throws IOException 689 { 690 // Write out the length, threshold, loadfactor 691 s.defaultWriteObject(); 692 693 // Write out length, count of elements and then the key/value objects 694 s.writeInt(table.length); 695 s.writeInt(count); 696 for (int index = table.length-1; index >= 0; index--) { 697 Entry entry = table[index]; 698 699 while (entry != null) { 700 s.writeObject(entry.key); 701 s.writeObject(entry.value); 702 entry = entry.next; 703 } 704 } 705 } 706 707 /** 708 * Reconstitute the Hashtable from a stream (i.e., deserialize it). 709 * @param s 710 * @throws IOException 711 * @throws ClassNotFoundException 712 */ 713 private synchronized void readObject(java.io.ObjectInputStream s) 714 throws IOException, ClassNotFoundException 715 { 716 // Read in the length, threshold, and loadfactor 717 s.defaultReadObject(); 718 719 // Read the original length of the array and number of elements 720 int origlength = s.readInt(); 721 int elements = s.readInt(); 722 723 // Compute new size with a bit of room 5% to grow but 724 // No larger than the original size. Make the length 725 // odd if it's large enough, this helps distribute the entries. 726 // Guard against the length ending up zero, that's not valid. 727 int length = (int)(elements * loadFactor) + (elements / 20) + 3; 728 if (length > elements && (length & 1) == 0) 729 length--; 730 if (origlength > 0 && length > origlength) 731 length = origlength; 732 733 table = new Entry[length]; 734 count = 0; 735 736 // Read the number of elements and then all the key/value objects 737 for (; elements > 0; elements--) { 738 Object key = s.readObject(); 739 Object value = s.readObject(); 740 put(key, value); 741 } 742 } 743 744 745 /** 746 * Hashtable collision list. 747 */ 748 private static class Entry implements Map.Entry,Sizeable { 749 int hash; 750 Object key; 751 Object value; 752 Entry next; 753 754 /** 755 * @param hash 756 * @param key 757 * @param value 758 * @param next 759 */ 760 protected Entry(int hash, Object key, Object value, Entry next) { 761 this.hash = hash; 762 this.key = key; 763 this.value = value; 764 this.next = next; 765 } 766 767 @Override 768 protected Object clone() { 769 return new Entry(hash, key, value, 770 (next==null ? null : (Entry)next.clone())); 771 } 772 773 // Map.Entry Ops 774 775 @Override 776 public Object getKey() { 777 return key; 778 } 779 780 @Override 781 public Object getValue() { 782 return value; 783 } 784 785 @Override 786 public Object setValue(Object value) { 787 if (value == null) 788 throw new NullPointerException(); 789 790 Object oldValue = this.value; 791 this.value = value; 792 return oldValue; 793 } 794 795 @Override 796 public boolean equals(Object o) { 797 if (!(o instanceof Map.Entry)) 798 return false; 799 Map.Entry e = (Map.Entry)o; 800 801 return (key==null ? e.getKey()==null : key.equals(e.getKey())) && 802 (value==null ? e.getValue()==null : value.equals(e.getValue())); 803 } 804 805 @Override 806 public int hashCode() { 807 return hash ^ (value==null ? 0 : value.hashCode()); 808 } 809 810 @Override 811 public String toString() { 812 return key.toString()+"="+value.toString(); 813 } 814 815 @Override 816 public long sizeOf() { 817 return SizeOf.size(this.key) 818 +SizeOf.size(this.value) 819 +SizeOf.size(this.hash); 820 } 821 } 822 823 // Types of Enumerations/Iterations 824 private static final int KEYS = 0; 825 private static final int VALUES = 1; 826 private static final int ENTRIES = 2; 827 828 /** 829 * A hashtable enumerator class. This class implements both the 830 * Enumeration and Iterator interfaces, but individual instances 831 * can be created with the Iterator methods disabled. This is necessary 832 * to avoid unintentionally increasing the capabilities granted a user 833 * by passing an Enumeration. 834 */ 835 private class Enumerator implements Enumeration, Iterator { 836 Entry[] table = HashTable.this.table; 837 int index = table.length; 838 Entry entry = null; 839 Entry lastReturned = null; 840 int type; 841 842 /** 843 * Indicates whether this Enumerator is serving as an Iterator 844 * or an Enumeration. (true -> Iterator). 845 */ 846 boolean iterator; 847 848 /** 849 * The modCount value that the iterator believes that the backing 850 * List should have. If this expectation is violated, the iterator 851 * has detected concurrent modification. 852 */ 853 protected int expectedModCount = modCount; 854 855 Enumerator(int type, boolean iterator) { 856 this.type = type; 857 this.iterator = iterator; 858 } 859 860 @Override 861 public boolean hasMoreElements() { 862 Entry e = entry; 863 int i = index; 864 Entry t[] = table; 865 /* Use locals for faster loop iteration */ 866 while (e == null && i > 0) { 867 e = t[--i]; 868 } 869 entry = e; 870 index = i; 871 return e != null; 872 } 873 874 @Override 875 public Object nextElement() { 876 Entry et = entry; 877 int i = index; 878 Entry t[] = table; 879 /* Use locals for faster loop iteration */ 880 while (et == null && i > 0) { 881 et = t[--i]; 882 } 883 entry = et; 884 index = i; 885 if (et != null) { 886 Entry e = lastReturned = entry; 887 entry = e.next; 888 return type == KEYS ? e.key : (type == VALUES ? e.value : e); 889 } 890 throw new NoSuchElementException("Hashtable Enumerator"); 891 } 892 893 @Override 894 // Iterator methods 895 public boolean hasNext() { 896 return hasMoreElements(); 897 } 898 899 @Override 900 public Object next() { 901 if (modCount != expectedModCount) 902 throw new ConcurrentModificationException(); 903 return nextElement(); 904 } 905 906 @Override 907 public void remove() { 908 if (!iterator) 909 throw new UnsupportedOperationException(); 910 if (lastReturned == null) 911 throw new IllegalStateException("Hashtable Enumerator"); 912 if (modCount != expectedModCount) 913 throw new ConcurrentModificationException(); 914 915 synchronized(HashTable.this) { 916 Entry[] tab = HashTable.this.table; 917 int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length; 918 919 for (Entry e = tab[index], prev = null; e != null; 920 prev = e, e = e.next) { 921 if (e == lastReturned) { 922 modCount++; 923 expectedModCount++; 924 if (prev == null) 925 tab[index] = e.next; 926 else 927 prev.next = e.next; 928 count--; 929 lastReturned = null; 930 return; 931 } 932 } 933 throw new ConcurrentModificationException(); 934 } 935 } 936 } 937 938 939 private static EmptyEnumerator emptyEnumerator = new EmptyEnumerator(); 940 private static EmptyIterator emptyIterator = new EmptyIterator(); 941 942 /** 943 * A hashtable enumerator class for empty hash tables, specializes 944 * the general Enumerator 945 */ 946 private static class EmptyEnumerator implements Enumeration { 947 948 EmptyEnumerator() { 949 } 950 951 @Override 952 public boolean hasMoreElements() { 953 return false; 954 } 955 956 @Override 957 public Object nextElement() { 958 throw new NoSuchElementException("Hashtable Enumerator"); 959 } 960 } 961 962 963 /** 964 * A hashtable iterator class for empty hash tables 965 */ 966 private static class EmptyIterator implements Iterator { 967 968 EmptyIterator() { 969 } 970 971 @Override 972 public boolean hasNext() { 973 return false; 974 } 975 976 @Override 977 public Object next() { 978 throw new NoSuchElementException("Hashtable Iterator"); 979 } 980 981 @Override 982 public void remove() { 983 throw new IllegalStateException("Hashtable Iterator"); 984 } 985 986 } 987 988 @Override 989 public long sizeOf() { 990 return SizeOf.size(this.count) 991 +SizeOf.size(this.loadFactor) 992 +SizeOf.size(this.modCount) 993 +SizeOf.size(this.table) 994 +SizeOf.size(this.threshold); 995 } 996 997 }