1 /*
2 * Copyright (c) 1994, 2012, 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>
438 newCapacity = MAX_ARRAY_SIZE;
439 }
440 Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
441
442 modCount++;
443 threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
444 table = newMap;
445
446 for (int i = oldCapacity ; i-- > 0 ;) {
447 for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
448 Entry<K,V> e = old;
449 old = old.next;
450
451 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
452 e.next = (Entry<K,V>)newMap[index];
453 newMap[index] = e;
454 }
455 }
456 }
457
458 /**
459 * Maps the specified <code>key</code> to the specified
460 * <code>value</code> in this hashtable. Neither the key nor the
461 * value can be <code>null</code>. <p>
462 *
463 * The value can be retrieved by calling the <code>get</code> method
464 * with a key that is equal to the original key.
465 *
466 * @param key the hashtable key
467 * @param value the value
468 * @return the previous value of the specified key in this hashtable,
469 * or <code>null</code> if it did not have one
470 * @exception NullPointerException if the key or value is
471 * <code>null</code>
472 * @see Object#equals(Object)
473 * @see #get(Object)
474 */
475 public synchronized V put(K key, V value) {
476 // Make sure the value is not null
477 if (value == null) {
478 throw new NullPointerException();
479 }
480
481 // Makes sure the key is not already in the hashtable.
482 Entry<?,?> tab[] = table;
483 int hash = hash(key);
484 int index = (hash & 0x7FFFFFFF) % tab.length;
485 @SuppressWarnings("unchecked")
486 Entry<K,V> entry = (Entry<K,V>)tab[index];
487 for(; entry != null ; entry = entry.next) {
488 if ((entry.hash == hash) && entry.key.equals(key)) {
489 V old = entry.value;
490 entry.value = value;
491 return old;
492 }
493 }
494
495 modCount++;
496 if (count >= threshold) {
497 // Rehash the table if the threshold is exceeded
498 rehash();
499
500 tab = table;
501 hash = hash(key);
502 index = (hash & 0x7FFFFFFF) % tab.length;
503 }
504
505 // Creates the new entry.
506 @SuppressWarnings("unchecked")
507 Entry<K,V> e = (Entry<K,V>)tab[index];
508 tab[index] = new Entry<>(hash, key, value, e);
509 count++;
510 return null;
511 }
512
513 /**
514 * Removes the key (and its corresponding value) from this
515 * hashtable. This method does nothing if the key is not in the hashtable.
516 *
517 * @param key the key that needs to be removed
518 * @return the value to which the key had been mapped in this hashtable,
519 * or <code>null</code> if the key did not have a mapping
520 * @throws NullPointerException if the key is <code>null</code>
521 */
522 public synchronized V remove(Object key) {
523 Entry<?,?> tab[] = table;
524 int hash = hash(key);
525 int index = (hash & 0x7FFFFFFF) % tab.length;
526 @SuppressWarnings("unchecked")
527 Entry<K,V> e = (Entry<K,V>)tab[index];
528 for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
529 if ((e.hash == hash) && e.key.equals(key)) {
873 * in progress flag, so as not to worsen the space performance.
874 * A negative load factor indicates that hash code computation is
875 * in progress.
876 */
877 int h = 0;
878 if (count == 0 || loadFactor < 0)
879 return h; // Returns zero
880
881 loadFactor = -loadFactor; // Mark hashCode computation in progress
882 Entry<?,?>[] tab = table;
883 for (Entry<?,?> entry : tab) {
884 while (entry != null) {
885 h += entry.hashCode();
886 entry = entry.next;
887 }
888 }
889
890 loadFactor = -loadFactor; // Mark hashCode computation complete
891
892 return h;
893 }
894
895 /**
896 * Save the state of the Hashtable to a stream (i.e., serialize it).
897 *
898 * @serialData The <i>capacity</i> of the Hashtable (the length of the
899 * bucket array) is emitted (int), followed by the
900 * <i>size</i> of the Hashtable (the number of key-value
901 * mappings), followed by the key (Object) and value (Object)
902 * for each key-value mapping represented by the Hashtable
903 * The key-value mappings are emitted in no particular order.
904 */
905 private void writeObject(java.io.ObjectOutputStream s)
906 throws IOException {
907 Entry<Object, Object> entryStack = null;
908
909 synchronized (this) {
910 // Write out the length, threshold, loadfactor
911 s.defaultWriteObject();
912
|
1 /*
2 * Copyright (c) 1994, 2013, 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
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>
442 newCapacity = MAX_ARRAY_SIZE;
443 }
444 Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
445
446 modCount++;
447 threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
448 table = newMap;
449
450 for (int i = oldCapacity ; i-- > 0 ;) {
451 for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
452 Entry<K,V> e = old;
453 old = old.next;
454
455 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
456 e.next = (Entry<K,V>)newMap[index];
457 newMap[index] = e;
458 }
459 }
460 }
461
462 private void addEntry(int hash, K key, V value, int index) {
463 modCount++;
464
465 Entry<?,?> tab[] = table;
466 if (count >= threshold) {
467 // Rehash the table if the threshold is exceeded
468 rehash();
469
470 tab = table;
471 hash = hash(key);
472 index = (hash & 0x7FFFFFFF) % tab.length;
473 }
474
475 // Creates the new entry.
476 @SuppressWarnings("unchecked")
477 Entry<K,V> e = (Entry<K,V>) tab[index];
478 tab[index] = new Entry<>(hash, key, value, e);
479 count++;
480 }
481
482 /**
483 * Maps the specified <code>key</code> to the specified
484 * <code>value</code> in this hashtable. Neither the key nor the
485 * value can be <code>null</code>. <p>
486 *
487 * The value can be retrieved by calling the <code>get</code> method
488 * with a key that is equal to the original key.
489 *
490 * @param key the hashtable key
491 * @param value the value
492 * @return the previous value of the specified key in this hashtable,
493 * or <code>null</code> if it did not have one
494 * @exception NullPointerException if the key or value is
495 * <code>null</code>
496 * @see Object#equals(Object)
497 * @see #get(Object)
498 */
499 public synchronized V put(K key, V value) {
500 // Make sure the value is not null
501 if (value == null) {
502 throw new NullPointerException();
503 }
504
505 // Makes sure the key is not already in the hashtable.
506 Entry<?,?> tab[] = table;
507 int hash = hash(key);
508 int index = (hash & 0x7FFFFFFF) % tab.length;
509 @SuppressWarnings("unchecked")
510 Entry<K,V> entry = (Entry<K,V>)tab[index];
511 for(; entry != null ; entry = entry.next) {
512 if ((entry.hash == hash) && entry.key.equals(key)) {
513 V old = entry.value;
514 entry.value = value;
515 return old;
516 }
517 }
518
519 addEntry(hash, key, value, index);
520 return null;
521 }
522
523 /**
524 * Removes the key (and its corresponding value) from this
525 * hashtable. This method does nothing if the key is not in the hashtable.
526 *
527 * @param key the key that needs to be removed
528 * @return the value to which the key had been mapped in this hashtable,
529 * or <code>null</code> if the key did not have a mapping
530 * @throws NullPointerException if the key is <code>null</code>
531 */
532 public synchronized V remove(Object key) {
533 Entry<?,?> tab[] = table;
534 int hash = hash(key);
535 int index = (hash & 0x7FFFFFFF) % tab.length;
536 @SuppressWarnings("unchecked")
537 Entry<K,V> e = (Entry<K,V>)tab[index];
538 for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
539 if ((e.hash == hash) && e.key.equals(key)) {
883 * in progress flag, so as not to worsen the space performance.
884 * A negative load factor indicates that hash code computation is
885 * in progress.
886 */
887 int h = 0;
888 if (count == 0 || loadFactor < 0)
889 return h; // Returns zero
890
891 loadFactor = -loadFactor; // Mark hashCode computation in progress
892 Entry<?,?>[] tab = table;
893 for (Entry<?,?> entry : tab) {
894 while (entry != null) {
895 h += entry.hashCode();
896 entry = entry.next;
897 }
898 }
899
900 loadFactor = -loadFactor; // Mark hashCode computation complete
901
902 return h;
903 }
904
905 @Override
906 public synchronized V getOrDefault(Object key, V defaultValue) {
907 V result = get(key);
908 return (null == result) ? defaultValue : result;
909 }
910
911 @Override
912 public synchronized void forEach(BiConsumer<? super K, ? super V> action) {
913 Objects.requireNonNull(action); // explicit check required in case
914 // table is empty.
915 Entry<?,?>[] tab = table;
916 for (Entry<?,?> entry : tab) {
917 while (entry != null) {
918 action.accept((K)entry.key, (V)entry.value);
919 entry = entry.next;
920 }
921 }
922 }
923
924 @Override
925 public synchronized void replaceAll(
926 BiFunction<? super K, ? super V, ? extends V> function) {
927 Map.super.replaceAll(function);
928 }
929
930 @Override
931 public synchronized V putIfAbsent(K key, V value) {
932 Objects.requireNonNull(value);
933
934 // Makes sure the key is not already in the hashtable.
935 Entry<?,?> tab[] = table;
936 int hash = hash(key);
937 int index = (hash & 0x7FFFFFFF) % tab.length;
938 @SuppressWarnings("unchecked")
939 Entry<K,V> entry = (Entry<K,V>)tab[index];
940 for (; entry != null; entry = entry.next) {
941 if ((entry.hash == hash) && entry.key.equals(key)) {
942 V old = entry.value;
943 if (old == null) {
944 entry.value = value;
945 }
946 return old;
947 }
948 }
949
950 addEntry(hash, key, value, index);
951 return null;
952 }
953
954 @Override
955 public synchronized boolean remove(Object key, Object value) {
956 Objects.requireNonNull(value);
957
958 Entry<?,?> tab[] = table;
959 int hash = hash(key);
960 int index = (hash & 0x7FFFFFFF) % tab.length;
961 @SuppressWarnings("unchecked")
962 Entry<K,V> e = (Entry<K,V>)tab[index];
963 for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
964 if ((e.hash == hash) && e.key.equals(key) && e.value.equals(value)) {
965 modCount++;
966 if (prev != null) {
967 prev.next = e.next;
968 } else {
969 tab[index] = e.next;
970 }
971 count--;
972 e.value = null;
973 return true;
974 }
975 }
976 return false;
977 }
978
979 @Override
980 public synchronized boolean replace(K key, V oldValue, V newValue) {
981 Entry<?,?> tab[] = table;
982 int hash = hash(key);
983 int index = (hash & 0x7FFFFFFF) % tab.length;
984 @SuppressWarnings("unchecked")
985 Entry<K,V> e = (Entry<K,V>)tab[index];
986 for (; e != null; e = e.next) {
987 if ((e.hash == hash) && e.key.equals(key)) {
988 if (e.value.equals(oldValue)) {
989 e.value = newValue;
990 return true;
991 } else {
992 return false;
993 }
994 }
995 }
996 return false;
997 }
998
999 @Override
1000 public synchronized V replace(K key, V value) {
1001 Entry<?,?> tab[] = table;
1002 int hash = hash(key);
1003 int index = (hash & 0x7FFFFFFF) % tab.length;
1004 @SuppressWarnings("unchecked")
1005 Entry<K,V> e = (Entry<K,V>)tab[index];
1006 for (; e != null; e = e.next) {
1007 if ((e.hash == hash) && e.key.equals(key)) {
1008 V oldValue = e.value;
1009 e.value = value;
1010 return oldValue;
1011 }
1012 }
1013 return null;
1014 }
1015
1016 @Override
1017 public synchronized V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
1018 Objects.requireNonNull(mappingFunction);
1019
1020 Entry<?,?> tab[] = table;
1021 int hash = hash(key);
1022 int index = (hash & 0x7FFFFFFF) % tab.length;
1023 @SuppressWarnings("unchecked")
1024 Entry<K,V> e = (Entry<K,V>)tab[index];
1025 for (; e != null; e = e.next) {
1026 if (e.hash == hash && e.key.equals(key)) {
1027 // Hashtable not accept null value
1028 return e.value;
1029 }
1030 }
1031
1032 V newValue = mappingFunction.apply(key);
1033 if (newValue != null) {
1034 addEntry(hash, key, newValue, index);
1035 }
1036
1037 return newValue;
1038 }
1039
1040 @Override
1041 public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1042 Objects.requireNonNull(remappingFunction);
1043
1044 Entry<?,?> tab[] = table;
1045 int hash = hash(key);
1046 int index = (hash & 0x7FFFFFFF) % tab.length;
1047 @SuppressWarnings("unchecked")
1048 Entry<K,V> e = (Entry<K,V>)tab[index];
1049 for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
1050 if (e.hash == hash && e.key.equals(key)) {
1051 V newValue = remappingFunction.apply(key, e.value);
1052 if (newValue == null) {
1053 modCount++;
1054 if (prev != null) {
1055 prev.next = e.next;
1056 } else {
1057 tab[index] = e.next;
1058 }
1059 count--;
1060 } else {
1061 e.value = newValue;
1062 }
1063 return newValue;
1064 }
1065 }
1066 return null;
1067 }
1068
1069 @Override
1070 public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1071 Objects.requireNonNull(remappingFunction);
1072
1073 Entry<?,?> tab[] = table;
1074 int hash = hash(key);
1075 int index = (hash & 0x7FFFFFFF) % tab.length;
1076 @SuppressWarnings("unchecked")
1077 Entry<K,V> e = (Entry<K,V>)tab[index];
1078 for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
1079 if (e.hash == hash && Objects.equals(e.key, key)) {
1080 V newValue = remappingFunction.apply(key, e.value);
1081 if (newValue == null) {
1082 modCount++;
1083 if (prev != null) {
1084 prev.next = e.next;
1085 } else {
1086 tab[index] = e.next;
1087 }
1088 count--;
1089 } else {
1090 e.value = newValue;
1091 }
1092 return newValue;
1093 }
1094 }
1095
1096 V newValue = remappingFunction.apply(key, null);
1097 if (newValue != null) {
1098 addEntry(hash, key, newValue, index);
1099 }
1100
1101 return newValue;
1102 }
1103
1104 @Override
1105 public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
1106 Objects.requireNonNull(remappingFunction);
1107
1108 Entry<?,?> tab[] = table;
1109 int hash = hash(key);
1110 int index = (hash & 0x7FFFFFFF) % tab.length;
1111 @SuppressWarnings("unchecked")
1112 Entry<K,V> e = (Entry<K,V>)tab[index];
1113 for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
1114 if (e.hash == hash && e.key.equals(key)) {
1115 V newValue = remappingFunction.apply(e.value, value);
1116 if (newValue == null) {
1117 modCount++;
1118 if (prev != null) {
1119 prev.next = e.next;
1120 } else {
1121 tab[index] = e.next;
1122 }
1123 count--;
1124 } else {
1125 e.value = newValue;
1126 }
1127 return newValue;
1128 }
1129 }
1130
1131 if (value != null) {
1132 addEntry(hash, key, value, index);
1133 }
1134
1135 return value;
1136 }
1137
1138 /**
1139 * Save the state of the Hashtable to a stream (i.e., serialize it).
1140 *
1141 * @serialData The <i>capacity</i> of the Hashtable (the length of the
1142 * bucket array) is emitted (int), followed by the
1143 * <i>size</i> of the Hashtable (the number of key-value
1144 * mappings), followed by the key (Object) and value (Object)
1145 * for each key-value mapping represented by the Hashtable
1146 * The key-value mappings are emitted in no particular order.
1147 */
1148 private void writeObject(java.io.ObjectOutputStream s)
1149 throws IOException {
1150 Entry<Object, Object> entryStack = null;
1151
1152 synchronized (this) {
1153 // Write out the length, threshold, loadfactor
1154 s.defaultWriteObject();
1155
|