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
28 import java.io.*;
29 import java.util.concurrent.ThreadLocalRandom;
30 import java.util.function.BiConsumer;
31 import java.util.function.Function;
32 import java.util.function.BiFunction;
33
34 /**
35 * This class implements a hash table, which maps keys to values. Any
36 * non-<code>null</code> object can be used as a key or as a value. <p>
37 *
38 * To successfully store and retrieve objects from a hashtable, the
39 * objects used as keys must implement the <code>hashCode</code>
40 * method and the <code>equals</code> method. <p>
41 *
42 * An instance of <code>Hashtable</code> has two parameters that affect its
43 * performance: <i>initial capacity</i> and <i>load factor</i>. The
44 * <i>capacity</i> is the number of <i>buckets</i> in the hash table, and the
45 * <i>initial capacity</i> is simply the capacity at the time the hash table
46 * is created. Note that the hash table is <i>open</i>: in the case of a "hash
47 * collision", a single bucket stores multiple entries, which must be searched
48 * sequentially. The <i>load factor</i> is a measure of how full the hash
49 * table is allowed to get before its capacity is automatically increased.
75 * = new Hashtable<String, Integer>();
76 * numbers.put("one", 1);
77 * numbers.put("two", 2);
78 * numbers.put("three", 3);}</pre>
79 *
80 * <p>To retrieve a number, use the following code:
81 * <pre> {@code
82 * Integer n = numbers.get("two");
83 * if (n != null) {
84 * System.out.println("two = " + n);
85 * }}</pre>
86 *
87 * <p>The iterators returned by the <tt>iterator</tt> method of the collections
88 * returned by all of this class's "collection view methods" are
89 * <em>fail-fast</em>: if the Hashtable is structurally modified at any time
90 * after the iterator is created, in any way except through the iterator's own
91 * <tt>remove</tt> method, the iterator will throw a {@link
92 * ConcurrentModificationException}. Thus, in the face of concurrent
93 * modification, the iterator fails quickly and cleanly, rather than risking
94 * arbitrary, non-deterministic behavior at an undetermined time in the future.
95 * The Enumerations returned by Hashtable's keys and elements methods are
96 * <em>not</em> fail-fast.
97 *
98 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
99 * as it is, generally speaking, impossible to make any hard guarantees in the
100 * presence of unsynchronized concurrent modification. Fail-fast iterators
101 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
102 * Therefore, it would be wrong to write a program that depended on this
103 * exception for its correctness: <i>the fail-fast behavior of iterators
104 * should be used only to detect bugs.</i>
105 *
106 * <p>As of the Java 2 platform v1.2, this class was retrofitted to
107 * implement the {@link Map} interface, making it a member of the
108 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
109 *
110 * Java Collections Framework</a>. Unlike the new collection
111 * implementations, {@code Hashtable} is synchronized. If a
112 * thread-safe implementation is not needed, it is recommended to use
113 * {@link HashMap} in place of {@code Hashtable}. If a thread-safe
114 * highly-concurrent implementation is desired, then it is recommended
115 * to use {@link java.util.concurrent.ConcurrentHashMap} in place of
116 * {@code Hashtable}.
400 }
401 Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
402
403 modCount++;
404 threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
405 table = newMap;
406
407 for (int i = oldCapacity ; i-- > 0 ;) {
408 for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
409 Entry<K,V> e = old;
410 old = old.next;
411
412 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
413 e.next = (Entry<K,V>)newMap[index];
414 newMap[index] = e;
415 }
416 }
417 }
418
419 private void addEntry(int hash, K key, V value, int index) {
420 modCount++;
421
422 Entry<?,?> tab[] = table;
423 if (count >= threshold) {
424 // Rehash the table if the threshold is exceeded
425 rehash();
426
427 tab = table;
428 hash = key.hashCode();
429 index = (hash & 0x7FFFFFFF) % tab.length;
430 }
431
432 // Creates the new entry.
433 @SuppressWarnings("unchecked")
434 Entry<K,V> e = (Entry<K,V>) tab[index];
435 tab[index] = new Entry<>(hash, key, value, e);
436 count++;
437 }
438
439 /**
440 * Maps the specified <code>key</code> to the specified
441 * <code>value</code> in this hashtable. Neither the key nor the
442 * value can be <code>null</code>. <p>
443 *
444 * The value can be retrieved by calling the <code>get</code> method
445 * with a key that is equal to the original key.
446 *
447 * @param key the hashtable key
448 * @param value the value
449 * @return the previous value of the specified key in this hashtable,
450 * or <code>null</code> if it did not have one
451 * @exception NullPointerException if the key or value is
452 * <code>null</code>
453 * @see Object#equals(Object)
454 * @see #get(Object)
455 */
456 public synchronized V put(K key, V value) {
477 return null;
478 }
479
480 /**
481 * Removes the key (and its corresponding value) from this
482 * hashtable. This method does nothing if the key is not in the hashtable.
483 *
484 * @param key the key that needs to be removed
485 * @return the value to which the key had been mapped in this hashtable,
486 * or <code>null</code> if the key did not have a mapping
487 * @throws NullPointerException if the key is <code>null</code>
488 */
489 public synchronized V remove(Object key) {
490 Entry<?,?> tab[] = table;
491 int hash = key.hashCode();
492 int index = (hash & 0x7FFFFFFF) % tab.length;
493 @SuppressWarnings("unchecked")
494 Entry<K,V> e = (Entry<K,V>)tab[index];
495 for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
496 if ((e.hash == hash) && e.key.equals(key)) {
497 modCount++;
498 if (prev != null) {
499 prev.next = e.next;
500 } else {
501 tab[index] = e.next;
502 }
503 count--;
504 V oldValue = e.value;
505 e.value = null;
506 return oldValue;
507 }
508 }
509 return null;
510 }
511
512 /**
513 * Copies all of the mappings from the specified map to this hashtable.
514 * These mappings will replace any mappings that this hashtable had for any
515 * of the keys currently in the specified map.
516 *
517 * @param t mappings to be stored in this map
518 * @throws NullPointerException if the specified map is null
519 * @since 1.2
520 */
521 public synchronized void putAll(Map<? extends K, ? extends V> t) {
522 for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
523 put(e.getKey(), e.getValue());
524 }
525
526 /**
527 * Clears this hashtable so that it contains no keys.
528 */
529 public synchronized void clear() {
530 Entry<?,?> tab[] = table;
531 modCount++;
532 for (int index = tab.length; --index >= 0; )
533 tab[index] = null;
534 count = 0;
535 }
536
537 /**
538 * Creates a shallow copy of this hashtable. All the structure of the
539 * hashtable itself is copied, but the keys and values are not cloned.
540 * This is a relatively expensive operation.
541 *
542 * @return a clone of the hashtable
543 */
544 public synchronized Object clone() {
545 try {
546 Hashtable<?,?> t = (Hashtable<?,?>)super.clone();
547 t.table = new Entry<?,?>[table.length];
548 for (int i = table.length ; i-- > 0 ; ) {
549 t.table[i] = (table[i] != null)
550 ? (Entry<?,?>) table[i].clone() : null;
551 }
552 t.keySet = null;
553 t.entrySet = null;
702
703 for (Entry<?,?> e = tab[index]; e != null; e = e.next)
704 if (e.hash==hash && e.equals(entry))
705 return true;
706 return false;
707 }
708
709 public boolean remove(Object o) {
710 if (!(o instanceof Map.Entry))
711 return false;
712 Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
713 Object key = entry.getKey();
714 Entry<?,?>[] tab = table;
715 int hash = key.hashCode();
716 int index = (hash & 0x7FFFFFFF) % tab.length;
717
718 @SuppressWarnings("unchecked")
719 Entry<K,V> e = (Entry<K,V>)tab[index];
720 for(Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
721 if (e.hash==hash && e.equals(entry)) {
722 modCount++;
723 if (prev != null)
724 prev.next = e.next;
725 else
726 tab[index] = e.next;
727
728 count--;
729 e.value = null;
730 return true;
731 }
732 }
733 return false;
734 }
735
736 public int size() {
737 return count;
738 }
739
740 public void clear() {
741 Hashtable.this.clear();
742 }
743 }
744
745 /**
746 * Returns a {@link Collection} view of the values contained in this map.
747 * The collection is backed by the map, so changes to the map are
748 * reflected in the collection, and vice-versa. If the map is
749 * modified while an iteration over the collection is in progress
922 }
923 return old;
924 }
925 }
926
927 addEntry(hash, key, value, index);
928 return null;
929 }
930
931 @Override
932 public synchronized boolean remove(Object key, Object value) {
933 Objects.requireNonNull(value);
934
935 Entry<?,?> tab[] = table;
936 int hash = key.hashCode();
937 int index = (hash & 0x7FFFFFFF) % tab.length;
938 @SuppressWarnings("unchecked")
939 Entry<K,V> e = (Entry<K,V>)tab[index];
940 for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
941 if ((e.hash == hash) && e.key.equals(key) && e.value.equals(value)) {
942 modCount++;
943 if (prev != null) {
944 prev.next = e.next;
945 } else {
946 tab[index] = e.next;
947 }
948 count--;
949 e.value = null;
950 return true;
951 }
952 }
953 return false;
954 }
955
956 @Override
957 public synchronized boolean replace(K key, V oldValue, V newValue) {
958 Objects.requireNonNull(oldValue);
959 Objects.requireNonNull(newValue);
960 Entry<?,?> tab[] = table;
961 int hash = key.hashCode();
962 int index = (hash & 0x7FFFFFFF) % tab.length;
963 @SuppressWarnings("unchecked")
964 Entry<K,V> e = (Entry<K,V>)tab[index];
965 for (; e != null; e = e.next) {
966 if ((e.hash == hash) && e.key.equals(key)) {
967 if (e.value.equals(oldValue)) {
968 e.value = newValue;
969 return true;
1013 if (newValue != null) {
1014 addEntry(hash, key, newValue, index);
1015 }
1016
1017 return newValue;
1018 }
1019
1020 @Override
1021 public synchronized V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1022 Objects.requireNonNull(remappingFunction);
1023
1024 Entry<?,?> tab[] = table;
1025 int hash = key.hashCode();
1026 int index = (hash & 0x7FFFFFFF) % tab.length;
1027 @SuppressWarnings("unchecked")
1028 Entry<K,V> e = (Entry<K,V>)tab[index];
1029 for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
1030 if (e.hash == hash && e.key.equals(key)) {
1031 V newValue = remappingFunction.apply(key, e.value);
1032 if (newValue == null) {
1033 modCount++;
1034 if (prev != null) {
1035 prev.next = e.next;
1036 } else {
1037 tab[index] = e.next;
1038 }
1039 count--;
1040 } else {
1041 e.value = newValue;
1042 }
1043 return newValue;
1044 }
1045 }
1046 return null;
1047 }
1048
1049 @Override
1050 public synchronized V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1051 Objects.requireNonNull(remappingFunction);
1052
1053 Entry<?,?> tab[] = table;
1054 int hash = key.hashCode();
1055 int index = (hash & 0x7FFFFFFF) % tab.length;
1056 @SuppressWarnings("unchecked")
1057 Entry<K,V> e = (Entry<K,V>)tab[index];
1058 for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
1059 if (e.hash == hash && Objects.equals(e.key, key)) {
1060 V newValue = remappingFunction.apply(key, e.value);
1061 if (newValue == null) {
1062 modCount++;
1063 if (prev != null) {
1064 prev.next = e.next;
1065 } else {
1066 tab[index] = e.next;
1067 }
1068 count--;
1069 } else {
1070 e.value = newValue;
1071 }
1072 return newValue;
1073 }
1074 }
1075
1076 V newValue = remappingFunction.apply(key, null);
1077 if (newValue != null) {
1078 addEntry(hash, key, newValue, index);
1079 }
1080
1081 return newValue;
1082 }
1083
1084 @Override
1085 public synchronized V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
1086 Objects.requireNonNull(remappingFunction);
1087
1088 Entry<?,?> tab[] = table;
1089 int hash = key.hashCode();
1090 int index = (hash & 0x7FFFFFFF) % tab.length;
1091 @SuppressWarnings("unchecked")
1092 Entry<K,V> e = (Entry<K,V>)tab[index];
1093 for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
1094 if (e.hash == hash && e.key.equals(key)) {
1095 V newValue = remappingFunction.apply(e.value, value);
1096 if (newValue == null) {
1097 modCount++;
1098 if (prev != null) {
1099 prev.next = e.next;
1100 } else {
1101 tab[index] = e.next;
1102 }
1103 count--;
1104 } else {
1105 e.value = newValue;
1106 }
1107 return newValue;
1108 }
1109 }
1110
1111 if (value != null) {
1112 addEntry(hash, key, value, index);
1113 }
1114
1115 return value;
1116 }
1117
1118 /**
1119 * Save the state of the Hashtable to a stream (i.e., serialize it).
1120 *
1121 * @serialData The <i>capacity</i> of the Hashtable (the length of the
1122 * bucket array) is emitted (int), followed by the
1281 }
1282
1283 public String toString() {
1284 return key.toString()+"="+value.toString();
1285 }
1286 }
1287
1288 // Types of Enumerations/Iterations
1289 private static final int KEYS = 0;
1290 private static final int VALUES = 1;
1291 private static final int ENTRIES = 2;
1292
1293 /**
1294 * A hashtable enumerator class. This class implements both the
1295 * Enumeration and Iterator interfaces, but individual instances
1296 * can be created with the Iterator methods disabled. This is necessary
1297 * to avoid unintentionally increasing the capabilities granted a user
1298 * by passing an Enumeration.
1299 */
1300 private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
1301 Entry<?,?>[] table = Hashtable.this.table;
1302 int index = table.length;
1303 Entry<?,?> entry;
1304 Entry<?,?> lastReturned;
1305 int type;
1306
1307 /**
1308 * Indicates whether this Enumerator is serving as an Iterator
1309 * or an Enumeration. (true -> Iterator).
1310 */
1311 boolean iterator;
1312
1313 /**
1314 * The modCount value that the iterator believes that the backing
1315 * Hashtable should have. If this expectation is violated, the iterator
1316 * has detected concurrent modification.
1317 */
1318 protected int expectedModCount = modCount;
1319
1320 Enumerator(int type, boolean iterator) {
1321 this.type = type;
1322 this.iterator = iterator;
1323 }
1324
1325 public boolean hasMoreElements() {
1326 Entry<?,?> e = entry;
1327 int i = index;
1328 Entry<?,?>[] t = table;
1329 /* Use locals for faster loop iteration */
1330 while (e == null && i > 0) {
1331 e = t[--i];
1332 }
1333 entry = e;
1334 index = i;
1335 return e != null;
1336 }
1337
1338 @SuppressWarnings("unchecked")
1343 /* Use locals for faster loop iteration */
1344 while (et == null && i > 0) {
1345 et = t[--i];
1346 }
1347 entry = et;
1348 index = i;
1349 if (et != null) {
1350 Entry<?,?> e = lastReturned = entry;
1351 entry = e.next;
1352 return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
1353 }
1354 throw new NoSuchElementException("Hashtable Enumerator");
1355 }
1356
1357 // Iterator methods
1358 public boolean hasNext() {
1359 return hasMoreElements();
1360 }
1361
1362 public T next() {
1363 if (modCount != expectedModCount)
1364 throw new ConcurrentModificationException();
1365 return nextElement();
1366 }
1367
1368 public void remove() {
1369 if (!iterator)
1370 throw new UnsupportedOperationException();
1371 if (lastReturned == null)
1372 throw new IllegalStateException("Hashtable Enumerator");
1373 if (modCount != expectedModCount)
1374 throw new ConcurrentModificationException();
1375
1376 synchronized(Hashtable.this) {
1377 Entry<?,?>[] tab = Hashtable.this.table;
1378 int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;
1379
1380 @SuppressWarnings("unchecked")
1381 Entry<K,V> e = (Entry<K,V>)tab[index];
1382 for(Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
1383 if (e == lastReturned) {
1384 modCount++;
1385 expectedModCount++;
1386 if (prev == null)
1387 tab[index] = e.next;
1388 else
1389 prev.next = e.next;
1390 count--;
1391 lastReturned = null;
1392 return;
1393 }
1394 }
1395 throw new ConcurrentModificationException();
1396 }
1397 }
1398 }
1399 }
|
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
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.
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 {@code #keys keys} and
95 * {@code #elements elements} methods are <em>not</em> fail-fast.
96 *
97 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
98 * as it is, generally speaking, impossible to make any hard guarantees in the
99 * presence of unsynchronized concurrent modification. Fail-fast iterators
100 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
101 * Therefore, it would be wrong to write a program that depended on this
102 * exception for its correctness: <i>the fail-fast behavior of iterators
103 * should be used only to detect bugs.</i>
104 *
105 * <p>As of the Java 2 platform v1.2, this class was retrofitted to
106 * implement the {@link Map} interface, making it a member of the
107 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
108 *
109 * Java Collections Framework</a>. Unlike the new collection
110 * implementations, {@code Hashtable} is synchronized. If a
111 * thread-safe implementation is not needed, it is recommended to use
112 * {@link HashMap} in place of {@code Hashtable}. If a thread-safe
113 * highly-concurrent implementation is desired, then it is recommended
114 * to use {@link java.util.concurrent.ConcurrentHashMap} in place of
115 * {@code Hashtable}.
399 }
400 Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
401
402 modCount++;
403 threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
404 table = newMap;
405
406 for (int i = oldCapacity ; i-- > 0 ;) {
407 for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
408 Entry<K,V> e = old;
409 old = old.next;
410
411 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
412 e.next = (Entry<K,V>)newMap[index];
413 newMap[index] = e;
414 }
415 }
416 }
417
418 private void addEntry(int hash, K key, V value, int index) {
419 Entry<?,?> tab[] = table;
420 if (count >= threshold) {
421 // Rehash the table if the threshold is exceeded
422 rehash();
423
424 tab = table;
425 hash = key.hashCode();
426 index = (hash & 0x7FFFFFFF) % tab.length;
427 }
428
429 // Creates the new entry.
430 @SuppressWarnings("unchecked")
431 Entry<K,V> e = (Entry<K,V>) tab[index];
432 tab[index] = new Entry<>(hash, key, value, e);
433 count++;
434 modCount++;
435 }
436
437 /**
438 * Maps the specified <code>key</code> to the specified
439 * <code>value</code> in this hashtable. Neither the key nor the
440 * value can be <code>null</code>. <p>
441 *
442 * The value can be retrieved by calling the <code>get</code> method
443 * with a key that is equal to the original key.
444 *
445 * @param key the hashtable key
446 * @param value the value
447 * @return the previous value of the specified key in this hashtable,
448 * or <code>null</code> if it did not have one
449 * @exception NullPointerException if the key or value is
450 * <code>null</code>
451 * @see Object#equals(Object)
452 * @see #get(Object)
453 */
454 public synchronized V put(K key, V value) {
475 return null;
476 }
477
478 /**
479 * Removes the key (and its corresponding value) from this
480 * hashtable. This method does nothing if the key is not in the hashtable.
481 *
482 * @param key the key that needs to be removed
483 * @return the value to which the key had been mapped in this hashtable,
484 * or <code>null</code> if the key did not have a mapping
485 * @throws NullPointerException if the key is <code>null</code>
486 */
487 public synchronized V remove(Object key) {
488 Entry<?,?> tab[] = table;
489 int hash = key.hashCode();
490 int index = (hash & 0x7FFFFFFF) % tab.length;
491 @SuppressWarnings("unchecked")
492 Entry<K,V> e = (Entry<K,V>)tab[index];
493 for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
494 if ((e.hash == hash) && e.key.equals(key)) {
495 if (prev != null) {
496 prev.next = e.next;
497 } else {
498 tab[index] = e.next;
499 }
500 modCount++;
501 count--;
502 V oldValue = e.value;
503 e.value = null;
504 return oldValue;
505 }
506 }
507 return null;
508 }
509
510 /**
511 * Copies all of the mappings from the specified map to this hashtable.
512 * These mappings will replace any mappings that this hashtable had for any
513 * of the keys currently in the specified map.
514 *
515 * @param t mappings to be stored in this map
516 * @throws NullPointerException if the specified map is null
517 * @since 1.2
518 */
519 public synchronized void putAll(Map<? extends K, ? extends V> t) {
520 for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
521 put(e.getKey(), e.getValue());
522 }
523
524 /**
525 * Clears this hashtable so that it contains no keys.
526 */
527 public synchronized void clear() {
528 Entry<?,?> tab[] = table;
529 for (int index = tab.length; --index >= 0; )
530 tab[index] = null;
531 modCount++;
532 count = 0;
533 }
534
535 /**
536 * Creates a shallow copy of this hashtable. All the structure of the
537 * hashtable itself is copied, but the keys and values are not cloned.
538 * This is a relatively expensive operation.
539 *
540 * @return a clone of the hashtable
541 */
542 public synchronized Object clone() {
543 try {
544 Hashtable<?,?> t = (Hashtable<?,?>)super.clone();
545 t.table = new Entry<?,?>[table.length];
546 for (int i = table.length ; i-- > 0 ; ) {
547 t.table[i] = (table[i] != null)
548 ? (Entry<?,?>) table[i].clone() : null;
549 }
550 t.keySet = null;
551 t.entrySet = null;
700
701 for (Entry<?,?> e = tab[index]; e != null; e = e.next)
702 if (e.hash==hash && e.equals(entry))
703 return true;
704 return false;
705 }
706
707 public boolean remove(Object o) {
708 if (!(o instanceof Map.Entry))
709 return false;
710 Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
711 Object key = entry.getKey();
712 Entry<?,?>[] tab = table;
713 int hash = key.hashCode();
714 int index = (hash & 0x7FFFFFFF) % tab.length;
715
716 @SuppressWarnings("unchecked")
717 Entry<K,V> e = (Entry<K,V>)tab[index];
718 for(Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
719 if (e.hash==hash && e.equals(entry)) {
720 if (prev != null)
721 prev.next = e.next;
722 else
723 tab[index] = e.next;
724
725 e.value = null; // clear for gc.
726 modCount++;
727 count--;
728 return true;
729 }
730 }
731 return false;
732 }
733
734 public int size() {
735 return count;
736 }
737
738 public void clear() {
739 Hashtable.this.clear();
740 }
741 }
742
743 /**
744 * Returns a {@link Collection} view of the values contained in this map.
745 * The collection is backed by the map, so changes to the map are
746 * reflected in the collection, and vice-versa. If the map is
747 * modified while an iteration over the collection is in progress
920 }
921 return old;
922 }
923 }
924
925 addEntry(hash, key, value, index);
926 return null;
927 }
928
929 @Override
930 public synchronized boolean remove(Object key, Object value) {
931 Objects.requireNonNull(value);
932
933 Entry<?,?> tab[] = table;
934 int hash = key.hashCode();
935 int index = (hash & 0x7FFFFFFF) % tab.length;
936 @SuppressWarnings("unchecked")
937 Entry<K,V> e = (Entry<K,V>)tab[index];
938 for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
939 if ((e.hash == hash) && e.key.equals(key) && e.value.equals(value)) {
940 if (prev != null) {
941 prev.next = e.next;
942 } else {
943 tab[index] = e.next;
944 }
945 e.value = null; // clear for gc
946 modCount++;
947 count--;
948 return true;
949 }
950 }
951 return false;
952 }
953
954 @Override
955 public synchronized boolean replace(K key, V oldValue, V newValue) {
956 Objects.requireNonNull(oldValue);
957 Objects.requireNonNull(newValue);
958 Entry<?,?> tab[] = table;
959 int hash = key.hashCode();
960 int index = (hash & 0x7FFFFFFF) % tab.length;
961 @SuppressWarnings("unchecked")
962 Entry<K,V> e = (Entry<K,V>)tab[index];
963 for (; e != null; e = e.next) {
964 if ((e.hash == hash) && e.key.equals(key)) {
965 if (e.value.equals(oldValue)) {
966 e.value = newValue;
967 return true;
1011 if (newValue != null) {
1012 addEntry(hash, key, newValue, index);
1013 }
1014
1015 return newValue;
1016 }
1017
1018 @Override
1019 public synchronized V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1020 Objects.requireNonNull(remappingFunction);
1021
1022 Entry<?,?> tab[] = table;
1023 int hash = key.hashCode();
1024 int index = (hash & 0x7FFFFFFF) % tab.length;
1025 @SuppressWarnings("unchecked")
1026 Entry<K,V> e = (Entry<K,V>)tab[index];
1027 for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
1028 if (e.hash == hash && e.key.equals(key)) {
1029 V newValue = remappingFunction.apply(key, e.value);
1030 if (newValue == null) {
1031 if (prev != null) {
1032 prev.next = e.next;
1033 } else {
1034 tab[index] = e.next;
1035 }
1036 modCount++;
1037 count--;
1038 } else {
1039 e.value = newValue;
1040 }
1041 return newValue;
1042 }
1043 }
1044 return null;
1045 }
1046
1047 @Override
1048 public synchronized V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1049 Objects.requireNonNull(remappingFunction);
1050
1051 Entry<?,?> tab[] = table;
1052 int hash = key.hashCode();
1053 int index = (hash & 0x7FFFFFFF) % tab.length;
1054 @SuppressWarnings("unchecked")
1055 Entry<K,V> e = (Entry<K,V>)tab[index];
1056 for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
1057 if (e.hash == hash && Objects.equals(e.key, key)) {
1058 V newValue = remappingFunction.apply(key, e.value);
1059 if (newValue == null) {
1060 if (prev != null) {
1061 prev.next = e.next;
1062 } else {
1063 tab[index] = e.next;
1064 }
1065 modCount++;
1066 count--;
1067 } else {
1068 e.value = newValue;
1069 }
1070 return newValue;
1071 }
1072 }
1073
1074 V newValue = remappingFunction.apply(key, null);
1075 if (newValue != null) {
1076 addEntry(hash, key, newValue, index);
1077 }
1078
1079 return newValue;
1080 }
1081
1082 @Override
1083 public synchronized V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
1084 Objects.requireNonNull(remappingFunction);
1085
1086 Entry<?,?> tab[] = table;
1087 int hash = key.hashCode();
1088 int index = (hash & 0x7FFFFFFF) % tab.length;
1089 @SuppressWarnings("unchecked")
1090 Entry<K,V> e = (Entry<K,V>)tab[index];
1091 for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
1092 if (e.hash == hash && e.key.equals(key)) {
1093 V newValue = remappingFunction.apply(e.value, value);
1094 if (newValue == null) {
1095 if (prev != null) {
1096 prev.next = e.next;
1097 } else {
1098 tab[index] = e.next;
1099 }
1100 modCount++;
1101 count--;
1102 } else {
1103 e.value = newValue;
1104 }
1105 return newValue;
1106 }
1107 }
1108
1109 if (value != null) {
1110 addEntry(hash, key, value, index);
1111 }
1112
1113 return value;
1114 }
1115
1116 /**
1117 * Save the state of the Hashtable to a stream (i.e., serialize it).
1118 *
1119 * @serialData The <i>capacity</i> of the Hashtable (the length of the
1120 * bucket array) is emitted (int), followed by the
1279 }
1280
1281 public String toString() {
1282 return key.toString()+"="+value.toString();
1283 }
1284 }
1285
1286 // Types of Enumerations/Iterations
1287 private static final int KEYS = 0;
1288 private static final int VALUES = 1;
1289 private static final int ENTRIES = 2;
1290
1291 /**
1292 * A hashtable enumerator class. This class implements both the
1293 * Enumeration and Iterator interfaces, but individual instances
1294 * can be created with the Iterator methods disabled. This is necessary
1295 * to avoid unintentionally increasing the capabilities granted a user
1296 * by passing an Enumeration.
1297 */
1298 private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
1299 final Entry<?,?>[] table = Hashtable.this.table;
1300 int index = table.length;
1301 Entry<?,?> entry;
1302 Entry<?,?> lastReturned;
1303 final int type;
1304
1305 /**
1306 * Indicates whether this Enumerator is serving as an Iterator
1307 * or an Enumeration. (true -> Iterator).
1308 */
1309 final boolean iterator;
1310
1311 /**
1312 * The modCount value that the iterator believes that the backing
1313 * Hashtable should have. If this expectation is violated, the iterator
1314 * has detected concurrent modification.
1315 */
1316 protected int expectedModCount = Hashtable.this.modCount;
1317
1318 Enumerator(int type, boolean iterator) {
1319 this.type = type;
1320 this.iterator = iterator;
1321 }
1322
1323 public boolean hasMoreElements() {
1324 Entry<?,?> e = entry;
1325 int i = index;
1326 Entry<?,?>[] t = table;
1327 /* Use locals for faster loop iteration */
1328 while (e == null && i > 0) {
1329 e = t[--i];
1330 }
1331 entry = e;
1332 index = i;
1333 return e != null;
1334 }
1335
1336 @SuppressWarnings("unchecked")
1341 /* Use locals for faster loop iteration */
1342 while (et == null && i > 0) {
1343 et = t[--i];
1344 }
1345 entry = et;
1346 index = i;
1347 if (et != null) {
1348 Entry<?,?> e = lastReturned = entry;
1349 entry = e.next;
1350 return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
1351 }
1352 throw new NoSuchElementException("Hashtable Enumerator");
1353 }
1354
1355 // Iterator methods
1356 public boolean hasNext() {
1357 return hasMoreElements();
1358 }
1359
1360 public T next() {
1361 if (Hashtable.this.modCount != expectedModCount)
1362 throw new ConcurrentModificationException();
1363 return nextElement();
1364 }
1365
1366 public void remove() {
1367 if (!iterator)
1368 throw new UnsupportedOperationException();
1369 if (lastReturned == null)
1370 throw new IllegalStateException("Hashtable Enumerator");
1371 if (modCount != expectedModCount)
1372 throw new ConcurrentModificationException();
1373
1374 synchronized(Hashtable.this) {
1375 Entry<?,?>[] tab = Hashtable.this.table;
1376 int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;
1377
1378 @SuppressWarnings("unchecked")
1379 Entry<K,V> e = (Entry<K,V>)tab[index];
1380 for(Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
1381 if (e == lastReturned) {
1382 if (prev == null)
1383 tab[index] = e.next;
1384 else
1385 prev.next = e.next;
1386 expectedModCount++;
1387 lastReturned = null;
1388 Hashtable.this.modCount++;
1389 Hashtable.this.count--;
1390 return;
1391 }
1392 }
1393 throw new ConcurrentModificationException();
1394 }
1395 }
1396 }
1397 }
|