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 28 import java.io.*; 29 import java.util.function.BiConsumer; 30 import java.util.function.Function; 31 import java.util.function.BiFunction; 32 33 /** 34 * This class implements a hash table, which maps keys to values. Any 35 * non-<code>null</code> object can be used as a key or as a value. <p> 36 * 37 * To successfully store and retrieve objects from a hashtable, the 38 * objects used as keys must implement the <code>hashCode</code> 39 * method and the <code>equals</code> method. <p> 40 * 41 * An instance of <code>Hashtable</code> has two parameters that affect its 42 * performance: <i>initial capacity</i> and <i>load factor</i>. The 43 * <i>capacity</i> is the number of <i>buckets</i> in the hash table, and the 44 * <i>initial capacity</i> is simply the capacity at the time the hash table 45 * is created. Note that the hash table is <i>open</i>: in the case of a "hash 46 * collision", a single bucket stores multiple entries, which must be searched 47 * sequentially. The <i>load factor</i> is a measure of how full the hash 48 * table is allowed to get before its capacity is automatically increased. 49 * The initial capacity and load factor parameters are merely hints to 50 * the implementation. The exact details as to when and whether the rehash 51 * method is invoked are implementation-dependent.<p> 52 * 53 * Generally, the default load factor (.75) offers a good tradeoff between 54 * time and space costs. Higher values decrease the space overhead but 55 * increase the time cost to look up an entry (which is reflected in most 56 * <tt>Hashtable</tt> operations, including <tt>get</tt> and <tt>put</tt>).<p> 57 * 58 * The initial capacity controls a tradeoff between wasted space and the 59 * need for <code>rehash</code> operations, which are time-consuming. 60 * No <code>rehash</code> operations will <i>ever</i> occur if the initial 61 * capacity is greater than the maximum number of entries the 62 * <tt>Hashtable</tt> will contain divided by its load factor. However, 63 * setting the initial capacity too high can waste space.<p> 64 * 65 * If many entries are to be made into a <code>Hashtable</code>, 66 * creating it with a sufficiently large capacity may allow the 67 * entries to be inserted more efficiently than letting it perform 68 * automatic rehashing as needed to grow the table. <p> 69 * 70 * This example creates a hashtable of numbers. It uses the names of 71 * the numbers as keys: 72 * <pre> {@code 73 * Hashtable<String, Integer> numbers 74 * = new Hashtable<String, Integer>(); 75 * numbers.put("one", 1); 76 * numbers.put("two", 2); 77 * numbers.put("three", 3);}</pre> 78 * 79 * <p>To retrieve a number, use the following code: 80 * <pre> {@code 81 * Integer n = numbers.get("two"); 82 * if (n != null) { 83 * System.out.println("two = " + n); 84 * }}</pre> 85 * 86 * <p>The iterators returned by the <tt>iterator</tt> method of the collections 87 * returned by all of this class's "collection view methods" are 88 * <em>fail-fast</em>: if the Hashtable is structurally modified at any time 89 * after the iterator is created, in any way except through the iterator's own 90 * <tt>remove</tt> method, the iterator will throw a {@link 91 * ConcurrentModificationException}. Thus, in the face of concurrent 92 * modification, the iterator fails quickly and cleanly, rather than risking 93 * arbitrary, non-deterministic behavior at an undetermined time in the future. 94 * The Enumerations returned by Hashtable's {@link #keys keys} and 95 * {@link #elements elements} methods are <em>not</em> fail-fast; if the 96 * Hashtable is structurally modified at any time after the enumeration is 97 * created then the results of enumerating are undefined. 98 * 99 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed 100 * as it is, generally speaking, impossible to make any hard guarantees in the 101 * presence of unsynchronized concurrent modification. Fail-fast iterators 102 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis. 103 * Therefore, it would be wrong to write a program that depended on this 104 * exception for its correctness: <i>the fail-fast behavior of iterators 105 * should be used only to detect bugs.</i> 106 * 107 * <p>As of the Java 2 platform v1.2, this class was retrofitted to 108 * implement the {@link Map} interface, making it a member of the 109 * <a href="{@docRoot}/../technotes/guides/collections/index.html"> 110 * 111 * Java Collections Framework</a>. Unlike the new collection 112 * implementations, {@code Hashtable} is synchronized. If a 113 * thread-safe implementation is not needed, it is recommended to use 114 * {@link HashMap} in place of {@code Hashtable}. If a thread-safe 115 * highly-concurrent implementation is desired, then it is recommended 116 * to use {@link java.util.concurrent.ConcurrentHashMap} in place of 117 * {@code Hashtable}. 118 * 119 * @param <K> the type of keys maintained by this map 120 * @param <V> the type of mapped values 121 * 122 * @author Arthur van Hoff 224 * @throws NullPointerException if the specified map is null. 225 * @since 1.2 226 */ 227 public Hashtable(Map<? extends K, ? extends V> t) { 228 this(Math.max(2*t.size(), 11), 0.75f); 229 putAll(t); 230 } 231 232 /** 233 * Returns the number of keys in this hashtable. 234 * 235 * @return the number of keys in this hashtable. 236 */ 237 public synchronized int size() { 238 return count; 239 } 240 241 /** 242 * Tests if this hashtable maps no keys to values. 243 * 244 * @return <code>true</code> if this hashtable maps no keys to values; 245 * <code>false</code> otherwise. 246 */ 247 public synchronized boolean isEmpty() { 248 return count == 0; 249 } 250 251 /** 252 * Returns an enumeration of the keys in this hashtable. 253 * Use the Enumeration methods on the returned object to fetch the keys 254 * sequentially. If the hashtable is structurally modified while enumerating 255 * over the keys then the results of enumerating are undefined. 256 * 257 * @return an enumeration of the keys in this hashtable. 258 * @see Enumeration 259 * @see #elements() 260 * @see #keySet() 261 * @see Map 262 */ 263 public synchronized Enumeration<K> keys() { 264 return this.<K>getEnumeration(KEYS); 265 } 273 * @return an enumeration of the values in this hashtable. 274 * @see java.util.Enumeration 275 * @see #keys() 276 * @see #values() 277 * @see Map 278 */ 279 public synchronized Enumeration<V> elements() { 280 return this.<V>getEnumeration(VALUES); 281 } 282 283 /** 284 * Tests if some key maps into the specified value in this hashtable. 285 * This operation is more expensive than the {@link #containsKey 286 * containsKey} method. 287 * 288 * <p>Note that this method is identical in functionality to 289 * {@link #containsValue containsValue}, (which is part of the 290 * {@link Map} interface in the collections framework). 291 * 292 * @param value a value to search for 293 * @return <code>true</code> if and only if some key maps to the 294 * <code>value</code> argument in this hashtable as 295 * determined by the <tt>equals</tt> method; 296 * <code>false</code> otherwise. 297 * @exception NullPointerException if the value is <code>null</code> 298 */ 299 public synchronized boolean contains(Object value) { 300 if (value == null) { 301 throw new NullPointerException(); 302 } 303 304 Entry<?,?> tab[] = table; 305 for (int i = tab.length ; i-- > 0 ;) { 306 for (Entry<?,?> e = tab[i] ; e != null ; e = e.next) { 307 if (e.value.equals(value)) { 308 return true; 309 } 310 } 311 } 312 return false; 313 } 314 315 /** 316 * Returns true if this hashtable maps one or more keys to this value. 317 * 318 * <p>Note that this method is identical in functionality to {@link 319 * #contains contains} (which predates the {@link Map} interface). 320 * 321 * @param value value whose presence in this hashtable is to be tested 322 * @return <tt>true</tt> if this map maps one or more keys to the 323 * specified value 324 * @throws NullPointerException if the value is <code>null</code> 325 * @since 1.2 326 */ 327 public boolean containsValue(Object value) { 328 return contains(value); 329 } 330 331 /** 332 * Tests if the specified object is a key in this hashtable. 333 * 334 * @param key possible key 335 * @return <code>true</code> if and only if the specified object 336 * is a key in this hashtable, as determined by the 337 * <tt>equals</tt> method; <code>false</code> otherwise. 338 * @throws NullPointerException if the key is <code>null</code> 339 * @see #contains(Object) 340 */ 341 public synchronized boolean containsKey(Object key) { 342 Entry<?,?> tab[] = table; 343 int hash = key.hashCode(); 344 int index = (hash & 0x7FFFFFFF) % tab.length; 345 for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) { 346 if ((e.hash == hash) && e.key.equals(key)) { 347 return true; 348 } 349 } 350 return false; 351 } 352 353 /** 354 * Returns the value to which the specified key is mapped, 355 * or {@code null} if this map contains no mapping for the key. 356 * 357 * <p>More formally, if this map contains a mapping from a key 358 * {@code k} to a value {@code v} such that {@code (key.equals(k))}, 427 private void addEntry(int hash, K key, V value, int index) { 428 Entry<?,?> tab[] = table; 429 if (count >= threshold) { 430 // Rehash the table if the threshold is exceeded 431 rehash(); 432 433 tab = table; 434 hash = key.hashCode(); 435 index = (hash & 0x7FFFFFFF) % tab.length; 436 } 437 438 // Creates the new entry. 439 @SuppressWarnings("unchecked") 440 Entry<K,V> e = (Entry<K,V>) tab[index]; 441 tab[index] = new Entry<>(hash, key, value, e); 442 count++; 443 modCount++; 444 } 445 446 /** 447 * Maps the specified <code>key</code> to the specified 448 * <code>value</code> in this hashtable. Neither the key nor the 449 * value can be <code>null</code>. <p> 450 * 451 * The value can be retrieved by calling the <code>get</code> method 452 * with a key that is equal to the original key. 453 * 454 * @param key the hashtable key 455 * @param value the value 456 * @return the previous value of the specified key in this hashtable, 457 * or <code>null</code> if it did not have one 458 * @exception NullPointerException if the key or value is 459 * <code>null</code> 460 * @see Object#equals(Object) 461 * @see #get(Object) 462 */ 463 public synchronized V put(K key, V value) { 464 // Make sure the value is not null 465 if (value == null) { 466 throw new NullPointerException(); 467 } 468 469 // Makes sure the key is not already in the hashtable. 470 Entry<?,?> tab[] = table; 471 int hash = key.hashCode(); 472 int index = (hash & 0x7FFFFFFF) % tab.length; 473 @SuppressWarnings("unchecked") 474 Entry<K,V> entry = (Entry<K,V>)tab[index]; 475 for(; entry != null ; entry = entry.next) { 476 if ((entry.hash == hash) && entry.key.equals(key)) { 477 V old = entry.value; 478 entry.value = value; 479 return old; 480 } 481 } 482 483 addEntry(hash, key, value, index); 484 return null; 485 } 486 487 /** 488 * Removes the key (and its corresponding value) from this 489 * hashtable. This method does nothing if the key is not in the hashtable. 490 * 491 * @param key the key that needs to be removed 492 * @return the value to which the key had been mapped in this hashtable, 493 * or <code>null</code> if the key did not have a mapping 494 * @throws NullPointerException if the key is <code>null</code> 495 */ 496 public synchronized V remove(Object key) { 497 Entry<?,?> tab[] = table; 498 int hash = key.hashCode(); 499 int index = (hash & 0x7FFFFFFF) % tab.length; 500 @SuppressWarnings("unchecked") 501 Entry<K,V> e = (Entry<K,V>)tab[index]; 502 for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) { 503 if ((e.hash == hash) && e.key.equals(key)) { 504 if (prev != null) { 505 prev.next = e.next; 506 } else { 507 tab[index] = e.next; 508 } 509 modCount++; 510 count--; 511 V oldValue = e.value; 512 e.value = null; 513 return oldValue; 514 } 551 public synchronized Object clone() { 552 try { 553 Hashtable<?,?> t = (Hashtable<?,?>)super.clone(); 554 t.table = new Entry<?,?>[table.length]; 555 for (int i = table.length ; i-- > 0 ; ) { 556 t.table[i] = (table[i] != null) 557 ? (Entry<?,?>) table[i].clone() : null; 558 } 559 t.keySet = null; 560 t.entrySet = null; 561 t.values = null; 562 t.modCount = 0; 563 return t; 564 } catch (CloneNotSupportedException e) { 565 // this shouldn't happen, since we are Cloneable 566 throw new InternalError(e); 567 } 568 } 569 570 /** 571 * Returns a string representation of this <tt>Hashtable</tt> object 572 * in the form of a set of entries, enclosed in braces and separated 573 * by the ASCII characters "<tt>, </tt>" (comma and space). Each 574 * entry is rendered as the key, an equals sign <tt>=</tt>, and the 575 * associated element, where the <tt>toString</tt> method is used to 576 * convert the key and element to strings. 577 * 578 * @return a string representation of this hashtable 579 */ 580 public synchronized String toString() { 581 int max = size() - 1; 582 if (max == -1) 583 return "{}"; 584 585 StringBuilder sb = new StringBuilder(); 586 Iterator<Map.Entry<K,V>> it = entrySet().iterator(); 587 588 sb.append('{'); 589 for (int i = 0; ; i++) { 590 Map.Entry<K,V> e = it.next(); 591 K key = e.getKey(); 592 V value = e.getValue(); 593 sb.append(key == this ? "(this Map)" : key.toString()); 594 sb.append('='); 595 sb.append(value == this ? "(this Map)" : value.toString()); 616 return new Enumerator<>(type, true); 617 } 618 } 619 620 // Views 621 622 /** 623 * Each of these fields are initialized to contain an instance of the 624 * appropriate view the first time this view is requested. The views are 625 * stateless, so there's no reason to create more than one of each. 626 */ 627 private transient volatile Set<K> keySet; 628 private transient volatile Set<Map.Entry<K,V>> entrySet; 629 private transient volatile Collection<V> values; 630 631 /** 632 * Returns a {@link Set} view of the keys contained in this map. 633 * The set is backed by the map, so changes to the map are 634 * reflected in the set, and vice-versa. If the map is modified 635 * while an iteration over the set is in progress (except through 636 * the iterator's own <tt>remove</tt> operation), the results of 637 * the iteration are undefined. The set supports element removal, 638 * which removes the corresponding mapping from the map, via the 639 * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, 640 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> 641 * operations. It does not support the <tt>add</tt> or <tt>addAll</tt> 642 * operations. 643 * 644 * @since 1.2 645 */ 646 public Set<K> keySet() { 647 if (keySet == null) 648 keySet = Collections.synchronizedSet(new KeySet(), this); 649 return keySet; 650 } 651 652 private class KeySet extends AbstractSet<K> { 653 public Iterator<K> iterator() { 654 return getIterator(KEYS); 655 } 656 public int size() { 657 return count; 658 } 659 public boolean contains(Object o) { 660 return containsKey(o); 661 } 662 public boolean remove(Object o) { 663 return Hashtable.this.remove(o) != null; 664 } 665 public void clear() { 666 Hashtable.this.clear(); 667 } 668 } 669 670 /** 671 * Returns a {@link Set} view of the mappings contained in this map. 672 * The set is backed by the map, so changes to the map are 673 * reflected in the set, and vice-versa. If the map is modified 674 * while an iteration over the set is in progress (except through 675 * the iterator's own <tt>remove</tt> operation, or through the 676 * <tt>setValue</tt> operation on a map entry returned by the 677 * iterator) the results of the iteration are undefined. The set 678 * supports element removal, which removes the corresponding 679 * mapping from the map, via the <tt>Iterator.remove</tt>, 680 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and 681 * <tt>clear</tt> operations. It does not support the 682 * <tt>add</tt> or <tt>addAll</tt> operations. 683 * 684 * @since 1.2 685 */ 686 public Set<Map.Entry<K,V>> entrySet() { 687 if (entrySet==null) 688 entrySet = Collections.synchronizedSet(new EntrySet(), this); 689 return entrySet; 690 } 691 692 private class EntrySet extends AbstractSet<Map.Entry<K,V>> { 693 public Iterator<Map.Entry<K,V>> iterator() { 694 return getIterator(ENTRIES); 695 } 696 697 public boolean add(Map.Entry<K,V> o) { 698 return super.add(o); 699 } 700 701 public boolean contains(Object o) { 702 if (!(o instanceof Map.Entry)) 737 return true; 738 } 739 } 740 return false; 741 } 742 743 public int size() { 744 return count; 745 } 746 747 public void clear() { 748 Hashtable.this.clear(); 749 } 750 } 751 752 /** 753 * Returns a {@link Collection} view of the values contained in this map. 754 * The collection is backed by the map, so changes to the map are 755 * reflected in the collection, and vice-versa. If the map is 756 * modified while an iteration over the collection is in progress 757 * (except through the iterator's own <tt>remove</tt> operation), 758 * the results of the iteration are undefined. The collection 759 * supports element removal, which removes the corresponding 760 * mapping from the map, via the <tt>Iterator.remove</tt>, 761 * <tt>Collection.remove</tt>, <tt>removeAll</tt>, 762 * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not 763 * support the <tt>add</tt> or <tt>addAll</tt> operations. 764 * 765 * @since 1.2 766 */ 767 public Collection<V> values() { 768 if (values==null) 769 values = Collections.synchronizedCollection(new ValueCollection(), 770 this); 771 return values; 772 } 773 774 private class ValueCollection extends AbstractCollection<V> { 775 public Iterator<V> iterator() { 776 return getIterator(VALUES); 777 } 778 public int size() { 779 return count; 780 } 781 public boolean contains(Object o) { 782 return containsValue(o); 783 } | 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 28 import java.io.*; 29 import java.util.function.BiConsumer; 30 import java.util.function.Function; 31 import java.util.function.BiFunction; 32 33 /** 34 * This class implements a hash table, which maps keys to values. Any 35 * non-{@code null} object can be used as a key or as a value. <p> 36 * 37 * To successfully store and retrieve objects from a hashtable, the 38 * objects used as keys must implement the {@code hashCode} 39 * method and the {@code equals} method. <p> 40 * 41 * An instance of {@code Hashtable} has two parameters that affect its 42 * performance: <i>initial capacity</i> and <i>load factor</i>. The 43 * <i>capacity</i> is the number of <i>buckets</i> in the hash table, and the 44 * <i>initial capacity</i> is simply the capacity at the time the hash table 45 * is created. Note that the hash table is <i>open</i>: in the case of a "hash 46 * collision", a single bucket stores multiple entries, which must be searched 47 * sequentially. The <i>load factor</i> is a measure of how full the hash 48 * table is allowed to get before its capacity is automatically increased. 49 * The initial capacity and load factor parameters are merely hints to 50 * the implementation. The exact details as to when and whether the rehash 51 * method is invoked are implementation-dependent.<p> 52 * 53 * Generally, the default load factor (.75) offers a good tradeoff between 54 * time and space costs. Higher values decrease the space overhead but 55 * increase the time cost to look up an entry (which is reflected in most 56 * {@code Hashtable} operations, including {@code get} and {@code put}).<p> 57 * 58 * The initial capacity controls a tradeoff between wasted space and the 59 * need for {@code rehash} operations, which are time-consuming. 60 * No {@code rehash} operations will <i>ever</i> occur if the initial 61 * capacity is greater than the maximum number of entries the 62 * {@code Hashtable} will contain divided by its load factor. However, 63 * setting the initial capacity too high can waste space.<p> 64 * 65 * If many entries are to be made into a {@code Hashtable}, 66 * creating it with a sufficiently large capacity may allow the 67 * entries to be inserted more efficiently than letting it perform 68 * automatic rehashing as needed to grow the table. <p> 69 * 70 * This example creates a hashtable of numbers. It uses the names of 71 * the numbers as keys: 72 * <pre> {@code 73 * Hashtable<String, Integer> numbers 74 * = new Hashtable<String, Integer>(); 75 * numbers.put("one", 1); 76 * numbers.put("two", 2); 77 * numbers.put("three", 3);}</pre> 78 * 79 * <p>To retrieve a number, use the following code: 80 * <pre> {@code 81 * Integer n = numbers.get("two"); 82 * if (n != null) { 83 * System.out.println("two = " + n); 84 * }}</pre> 85 * 86 * <p>The iterators returned by the {@code iterator} method of the collections 87 * returned by all of this class's "collection view methods" are 88 * <em>fail-fast</em>: if the Hashtable is structurally modified at any time 89 * after the iterator is created, in any way except through the iterator's own 90 * {@code remove} method, the iterator will throw a {@link 91 * ConcurrentModificationException}. Thus, in the face of concurrent 92 * modification, the iterator fails quickly and cleanly, rather than risking 93 * arbitrary, non-deterministic behavior at an undetermined time in the future. 94 * The Enumerations returned by Hashtable's {@link #keys keys} and 95 * {@link #elements elements} methods are <em>not</em> fail-fast; if the 96 * Hashtable is structurally modified at any time after the enumeration is 97 * created then the results of enumerating are undefined. 98 * 99 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed 100 * as it is, generally speaking, impossible to make any hard guarantees in the 101 * presence of unsynchronized concurrent modification. Fail-fast iterators 102 * throw {@code ConcurrentModificationException} on a best-effort basis. 103 * Therefore, it would be wrong to write a program that depended on this 104 * exception for its correctness: <i>the fail-fast behavior of iterators 105 * should be used only to detect bugs.</i> 106 * 107 * <p>As of the Java 2 platform v1.2, this class was retrofitted to 108 * implement the {@link Map} interface, making it a member of the 109 * <a href="{@docRoot}/../technotes/guides/collections/index.html"> 110 * 111 * Java Collections Framework</a>. Unlike the new collection 112 * implementations, {@code Hashtable} is synchronized. If a 113 * thread-safe implementation is not needed, it is recommended to use 114 * {@link HashMap} in place of {@code Hashtable}. If a thread-safe 115 * highly-concurrent implementation is desired, then it is recommended 116 * to use {@link java.util.concurrent.ConcurrentHashMap} in place of 117 * {@code Hashtable}. 118 * 119 * @param <K> the type of keys maintained by this map 120 * @param <V> the type of mapped values 121 * 122 * @author Arthur van Hoff 224 * @throws NullPointerException if the specified map is null. 225 * @since 1.2 226 */ 227 public Hashtable(Map<? extends K, ? extends V> t) { 228 this(Math.max(2*t.size(), 11), 0.75f); 229 putAll(t); 230 } 231 232 /** 233 * Returns the number of keys in this hashtable. 234 * 235 * @return the number of keys in this hashtable. 236 */ 237 public synchronized int size() { 238 return count; 239 } 240 241 /** 242 * Tests if this hashtable maps no keys to values. 243 * 244 * @return {@code true} if this hashtable maps no keys to values; 245 * {@code false} otherwise. 246 */ 247 public synchronized boolean isEmpty() { 248 return count == 0; 249 } 250 251 /** 252 * Returns an enumeration of the keys in this hashtable. 253 * Use the Enumeration methods on the returned object to fetch the keys 254 * sequentially. If the hashtable is structurally modified while enumerating 255 * over the keys then the results of enumerating are undefined. 256 * 257 * @return an enumeration of the keys in this hashtable. 258 * @see Enumeration 259 * @see #elements() 260 * @see #keySet() 261 * @see Map 262 */ 263 public synchronized Enumeration<K> keys() { 264 return this.<K>getEnumeration(KEYS); 265 } 273 * @return an enumeration of the values in this hashtable. 274 * @see java.util.Enumeration 275 * @see #keys() 276 * @see #values() 277 * @see Map 278 */ 279 public synchronized Enumeration<V> elements() { 280 return this.<V>getEnumeration(VALUES); 281 } 282 283 /** 284 * Tests if some key maps into the specified value in this hashtable. 285 * This operation is more expensive than the {@link #containsKey 286 * containsKey} method. 287 * 288 * <p>Note that this method is identical in functionality to 289 * {@link #containsValue containsValue}, (which is part of the 290 * {@link Map} interface in the collections framework). 291 * 292 * @param value a value to search for 293 * @return {@code true} if and only if some key maps to the 294 * {@code value} argument in this hashtable as 295 * determined by the {@code equals} method; 296 * {@code false} otherwise. 297 * @exception NullPointerException if the value is {@code null} 298 */ 299 public synchronized boolean contains(Object value) { 300 if (value == null) { 301 throw new NullPointerException(); 302 } 303 304 Entry<?,?> tab[] = table; 305 for (int i = tab.length ; i-- > 0 ;) { 306 for (Entry<?,?> e = tab[i] ; e != null ; e = e.next) { 307 if (e.value.equals(value)) { 308 return true; 309 } 310 } 311 } 312 return false; 313 } 314 315 /** 316 * Returns true if this hashtable maps one or more keys to this value. 317 * 318 * <p>Note that this method is identical in functionality to {@link 319 * #contains contains} (which predates the {@link Map} interface). 320 * 321 * @param value value whose presence in this hashtable is to be tested 322 * @return {@code true} if this map maps one or more keys to the 323 * specified value 324 * @throws NullPointerException if the value is {@code null} 325 * @since 1.2 326 */ 327 public boolean containsValue(Object value) { 328 return contains(value); 329 } 330 331 /** 332 * Tests if the specified object is a key in this hashtable. 333 * 334 * @param key possible key 335 * @return {@code true} if and only if the specified object 336 * is a key in this hashtable, as determined by the 337 * {@code equals} method; {@code false} otherwise. 338 * @throws NullPointerException if the key is {@code null} 339 * @see #contains(Object) 340 */ 341 public synchronized boolean containsKey(Object key) { 342 Entry<?,?> tab[] = table; 343 int hash = key.hashCode(); 344 int index = (hash & 0x7FFFFFFF) % tab.length; 345 for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) { 346 if ((e.hash == hash) && e.key.equals(key)) { 347 return true; 348 } 349 } 350 return false; 351 } 352 353 /** 354 * Returns the value to which the specified key is mapped, 355 * or {@code null} if this map contains no mapping for the key. 356 * 357 * <p>More formally, if this map contains a mapping from a key 358 * {@code k} to a value {@code v} such that {@code (key.equals(k))}, 427 private void addEntry(int hash, K key, V value, int index) { 428 Entry<?,?> tab[] = table; 429 if (count >= threshold) { 430 // Rehash the table if the threshold is exceeded 431 rehash(); 432 433 tab = table; 434 hash = key.hashCode(); 435 index = (hash & 0x7FFFFFFF) % tab.length; 436 } 437 438 // Creates the new entry. 439 @SuppressWarnings("unchecked") 440 Entry<K,V> e = (Entry<K,V>) tab[index]; 441 tab[index] = new Entry<>(hash, key, value, e); 442 count++; 443 modCount++; 444 } 445 446 /** 447 * Maps the specified {@code key} to the specified 448 * {@code value} in this hashtable. Neither the key nor the 449 * value can be {@code null}. <p> 450 * 451 * The value can be retrieved by calling the {@code get} method 452 * with a key that is equal to the original key. 453 * 454 * @param key the hashtable key 455 * @param value the value 456 * @return the previous value of the specified key in this hashtable, 457 * or {@code null} if it did not have one 458 * @exception NullPointerException if the key or value is 459 * {@code null} 460 * @see Object#equals(Object) 461 * @see #get(Object) 462 */ 463 public synchronized V put(K key, V value) { 464 // Make sure the value is not null 465 if (value == null) { 466 throw new NullPointerException(); 467 } 468 469 // Makes sure the key is not already in the hashtable. 470 Entry<?,?> tab[] = table; 471 int hash = key.hashCode(); 472 int index = (hash & 0x7FFFFFFF) % tab.length; 473 @SuppressWarnings("unchecked") 474 Entry<K,V> entry = (Entry<K,V>)tab[index]; 475 for(; entry != null ; entry = entry.next) { 476 if ((entry.hash == hash) && entry.key.equals(key)) { 477 V old = entry.value; 478 entry.value = value; 479 return old; 480 } 481 } 482 483 addEntry(hash, key, value, index); 484 return null; 485 } 486 487 /** 488 * Removes the key (and its corresponding value) from this 489 * hashtable. This method does nothing if the key is not in the hashtable. 490 * 491 * @param key the key that needs to be removed 492 * @return the value to which the key had been mapped in this hashtable, 493 * or {@code null} if the key did not have a mapping 494 * @throws NullPointerException if the key is {@code null} 495 */ 496 public synchronized V remove(Object key) { 497 Entry<?,?> tab[] = table; 498 int hash = key.hashCode(); 499 int index = (hash & 0x7FFFFFFF) % tab.length; 500 @SuppressWarnings("unchecked") 501 Entry<K,V> e = (Entry<K,V>)tab[index]; 502 for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) { 503 if ((e.hash == hash) && e.key.equals(key)) { 504 if (prev != null) { 505 prev.next = e.next; 506 } else { 507 tab[index] = e.next; 508 } 509 modCount++; 510 count--; 511 V oldValue = e.value; 512 e.value = null; 513 return oldValue; 514 } 551 public synchronized Object clone() { 552 try { 553 Hashtable<?,?> t = (Hashtable<?,?>)super.clone(); 554 t.table = new Entry<?,?>[table.length]; 555 for (int i = table.length ; i-- > 0 ; ) { 556 t.table[i] = (table[i] != null) 557 ? (Entry<?,?>) table[i].clone() : null; 558 } 559 t.keySet = null; 560 t.entrySet = null; 561 t.values = null; 562 t.modCount = 0; 563 return t; 564 } catch (CloneNotSupportedException e) { 565 // this shouldn't happen, since we are Cloneable 566 throw new InternalError(e); 567 } 568 } 569 570 /** 571 * Returns a string representation of this {@code Hashtable} object 572 * in the form of a set of entries, enclosed in braces and separated 573 * by the ASCII characters "<code> , </code>" (comma and space). Each 574 * entry is rendered as the key, an equals sign {@code =}, and the 575 * associated element, where the {@code toString} method is used to 576 * convert the key and element to strings. 577 * 578 * @return a string representation of this hashtable 579 */ 580 public synchronized String toString() { 581 int max = size() - 1; 582 if (max == -1) 583 return "{}"; 584 585 StringBuilder sb = new StringBuilder(); 586 Iterator<Map.Entry<K,V>> it = entrySet().iterator(); 587 588 sb.append('{'); 589 for (int i = 0; ; i++) { 590 Map.Entry<K,V> e = it.next(); 591 K key = e.getKey(); 592 V value = e.getValue(); 593 sb.append(key == this ? "(this Map)" : key.toString()); 594 sb.append('='); 595 sb.append(value == this ? "(this Map)" : value.toString()); 616 return new Enumerator<>(type, true); 617 } 618 } 619 620 // Views 621 622 /** 623 * Each of these fields are initialized to contain an instance of the 624 * appropriate view the first time this view is requested. The views are 625 * stateless, so there's no reason to create more than one of each. 626 */ 627 private transient volatile Set<K> keySet; 628 private transient volatile Set<Map.Entry<K,V>> entrySet; 629 private transient volatile Collection<V> values; 630 631 /** 632 * Returns a {@link Set} view of the keys contained in this map. 633 * The set is backed by the map, so changes to the map are 634 * reflected in the set, and vice-versa. If the map is modified 635 * while an iteration over the set is in progress (except through 636 * the iterator's own {@code remove} operation), the results of 637 * the iteration are undefined. The set supports element removal, 638 * which removes the corresponding mapping from the map, via the 639 * {@code Iterator.remove}, {@code Set.remove}, 640 * {@code removeAll}, {@code retainAll}, and {@code clear} 641 * operations. It does not support the {@code add} or {@code addAll} 642 * operations. 643 * 644 * @since 1.2 645 */ 646 public Set<K> keySet() { 647 if (keySet == null) 648 keySet = Collections.synchronizedSet(new KeySet(), this); 649 return keySet; 650 } 651 652 private class KeySet extends AbstractSet<K> { 653 public Iterator<K> iterator() { 654 return getIterator(KEYS); 655 } 656 public int size() { 657 return count; 658 } 659 public boolean contains(Object o) { 660 return containsKey(o); 661 } 662 public boolean remove(Object o) { 663 return Hashtable.this.remove(o) != null; 664 } 665 public void clear() { 666 Hashtable.this.clear(); 667 } 668 } 669 670 /** 671 * Returns a {@link Set} view of the mappings contained in this map. 672 * The set is backed by the map, so changes to the map are 673 * reflected in the set, and vice-versa. If the map is modified 674 * while an iteration over the set is in progress (except through 675 * the iterator's own {@code remove} operation, or through the 676 * {@code setValue} operation on a map entry returned by the 677 * iterator) the results of the iteration are undefined. The set 678 * supports element removal, which removes the corresponding 679 * mapping from the map, via the {@code Iterator.remove}, 680 * {@code Set.remove}, {@code removeAll}, {@code retainAll} and 681 * {@code clear} operations. It does not support the 682 * {@code add} or {@code addAll} operations. 683 * 684 * @since 1.2 685 */ 686 public Set<Map.Entry<K,V>> entrySet() { 687 if (entrySet==null) 688 entrySet = Collections.synchronizedSet(new EntrySet(), this); 689 return entrySet; 690 } 691 692 private class EntrySet extends AbstractSet<Map.Entry<K,V>> { 693 public Iterator<Map.Entry<K,V>> iterator() { 694 return getIterator(ENTRIES); 695 } 696 697 public boolean add(Map.Entry<K,V> o) { 698 return super.add(o); 699 } 700 701 public boolean contains(Object o) { 702 if (!(o instanceof Map.Entry)) 737 return true; 738 } 739 } 740 return false; 741 } 742 743 public int size() { 744 return count; 745 } 746 747 public void clear() { 748 Hashtable.this.clear(); 749 } 750 } 751 752 /** 753 * Returns a {@link Collection} view of the values contained in this map. 754 * The collection is backed by the map, so changes to the map are 755 * reflected in the collection, and vice-versa. If the map is 756 * modified while an iteration over the collection is in progress 757 * (except through the iterator's own {@code remove} operation), 758 * the results of the iteration are undefined. The collection 759 * supports element removal, which removes the corresponding 760 * mapping from the map, via the {@code Iterator.remove}, 761 * {@code Collection.remove}, {@code removeAll}, 762 * {@code retainAll} and {@code clear} operations. It does not 763 * support the {@code add} or {@code addAll} operations. 764 * 765 * @since 1.2 766 */ 767 public Collection<V> values() { 768 if (values==null) 769 values = Collections.synchronizedCollection(new ValueCollection(), 770 this); 771 return values; 772 } 773 774 private class ValueCollection extends AbstractCollection<V> { 775 public Iterator<V> iterator() { 776 return getIterator(VALUES); 777 } 778 public int size() { 779 return count; 780 } 781 public boolean contains(Object o) { 782 return containsValue(o); 783 } |