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