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