121 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
122 * Java Collections Framework</a>.
123 *
124 * @param <K> the type of keys maintained by this map
125 * @param <V> the type of mapped values
126 *
127 * @author Doug Lea
128 * @author Josh Bloch
129 * @author Arthur van Hoff
130 * @author Neal Gafter
131 * @see Object#hashCode()
132 * @see Collection
133 * @see Map
134 * @see TreeMap
135 * @see Hashtable
136 * @since 1.2
137 */
138 public class HashMap<K,V> extends AbstractMap<K,V>
139 implements Map<K,V>, Cloneable, Serializable {
140
141 private static final long serialVersionUID = 362498820763181265L;
142
143 /*
144 * Implementation notes.
145 *
146 * This map usually acts as a binned (bucketed) hash table, but
147 * when bins get too large, they are transformed into bins of
148 * TreeNodes, each structured similarly to those in
149 * java.util.TreeMap. Most methods try to use normal bins, but
150 * relay to TreeNode methods when applicable (simply by checking
151 * instanceof a node). Bins of TreeNodes may be traversed and
152 * used like any others, but additionally support faster lookup
153 * when overpopulated. However, since the vast majority of bins in
154 * normal use are not overpopulated, checking for existence of
155 * tree bins may be delayed in the course of table methods.
156 *
157 * Tree bins (i.e., bins whose elements are all TreeNodes) are
158 * ordered primarily by hashCode, but in the case of ties, if two
159 * elements are of the same "class C implements Comparable<C>",
160 * type then their compareTo method is used for ordering. (We
1472 // These methods are also used when serializing HashSets
1473 final float loadFactor() { return loadFactor; }
1474 final int capacity() {
1475 return (table != null) ? table.length :
1476 (threshold > 0) ? threshold :
1477 DEFAULT_INITIAL_CAPACITY;
1478 }
1479
1480 /**
1481 * Saves this map to a stream (that is, serializes it).
1482 *
1483 * @param s the stream
1484 * @throws IOException if an I/O error occurs
1485 * @serialData The <i>capacity</i> of the HashMap (the length of the
1486 * bucket array) is emitted (int), followed by the
1487 * <i>size</i> (an int, the number of key-value
1488 * mappings), followed by the key (Object) and value (Object)
1489 * for each key-value mapping. The key-value mappings are
1490 * emitted in no particular order.
1491 */
1492 private void writeObject(java.io.ObjectOutputStream s)
1493 throws IOException {
1494 int buckets = capacity();
1495 // Write out the threshold, loadfactor, and any hidden stuff
1496 s.defaultWriteObject();
1497 s.writeInt(buckets);
1498 s.writeInt(size);
1499 internalWriteEntries(s);
1500 }
1501
1502 /**
1503 * Reconstitutes this map from a stream (that is, deserializes it).
1504 * @param s the stream
1505 * @throws ClassNotFoundException if the class of a serialized object
1506 * could not be found
1507 * @throws IOException if an I/O error occurs
1508 */
1509 private void readObject(java.io.ObjectInputStream s)
1510 throws IOException, ClassNotFoundException {
1511 // Read in the threshold (ignored), loadfactor, and any hidden stuff
1512 s.defaultReadObject();
1513 reinitialize();
1514 if (loadFactor <= 0 || Float.isNaN(loadFactor))
1515 throw new InvalidObjectException("Illegal load factor: " +
1516 loadFactor);
1517 s.readInt(); // Read and ignore number of buckets
1518 int mappings = s.readInt(); // Read number of mappings (size)
1519 if (mappings < 0)
1520 throw new InvalidObjectException("Illegal mappings count: " +
1521 mappings);
1522 else if (mappings > 0) { // (if zero, use defaults)
1523 // Size the table using given load factor only if within
1524 // range of 0.25...4.0
1525 float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);
1526 float fc = (float)mappings / lf + 1.0f;
1527 int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ?
1528 DEFAULT_INITIAL_CAPACITY :
|
121 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
122 * Java Collections Framework</a>.
123 *
124 * @param <K> the type of keys maintained by this map
125 * @param <V> the type of mapped values
126 *
127 * @author Doug Lea
128 * @author Josh Bloch
129 * @author Arthur van Hoff
130 * @author Neal Gafter
131 * @see Object#hashCode()
132 * @see Collection
133 * @see Map
134 * @see TreeMap
135 * @see Hashtable
136 * @since 1.2
137 */
138 public class HashMap<K,V> extends AbstractMap<K,V>
139 implements Map<K,V>, Cloneable, Serializable {
140
141 @java.io.Serial
142 private static final long serialVersionUID = 362498820763181265L;
143
144 /*
145 * Implementation notes.
146 *
147 * This map usually acts as a binned (bucketed) hash table, but
148 * when bins get too large, they are transformed into bins of
149 * TreeNodes, each structured similarly to those in
150 * java.util.TreeMap. Most methods try to use normal bins, but
151 * relay to TreeNode methods when applicable (simply by checking
152 * instanceof a node). Bins of TreeNodes may be traversed and
153 * used like any others, but additionally support faster lookup
154 * when overpopulated. However, since the vast majority of bins in
155 * normal use are not overpopulated, checking for existence of
156 * tree bins may be delayed in the course of table methods.
157 *
158 * Tree bins (i.e., bins whose elements are all TreeNodes) are
159 * ordered primarily by hashCode, but in the case of ties, if two
160 * elements are of the same "class C implements Comparable<C>",
161 * type then their compareTo method is used for ordering. (We
1473 // These methods are also used when serializing HashSets
1474 final float loadFactor() { return loadFactor; }
1475 final int capacity() {
1476 return (table != null) ? table.length :
1477 (threshold > 0) ? threshold :
1478 DEFAULT_INITIAL_CAPACITY;
1479 }
1480
1481 /**
1482 * Saves this map to a stream (that is, serializes it).
1483 *
1484 * @param s the stream
1485 * @throws IOException if an I/O error occurs
1486 * @serialData The <i>capacity</i> of the HashMap (the length of the
1487 * bucket array) is emitted (int), followed by the
1488 * <i>size</i> (an int, the number of key-value
1489 * mappings), followed by the key (Object) and value (Object)
1490 * for each key-value mapping. The key-value mappings are
1491 * emitted in no particular order.
1492 */
1493 @java.io.Serial
1494 private void writeObject(java.io.ObjectOutputStream s)
1495 throws IOException {
1496 int buckets = capacity();
1497 // Write out the threshold, loadfactor, and any hidden stuff
1498 s.defaultWriteObject();
1499 s.writeInt(buckets);
1500 s.writeInt(size);
1501 internalWriteEntries(s);
1502 }
1503
1504 /**
1505 * Reconstitutes this map from a stream (that is, deserializes it).
1506 * @param s the stream
1507 * @throws ClassNotFoundException if the class of a serialized object
1508 * could not be found
1509 * @throws IOException if an I/O error occurs
1510 */
1511 @java.io.Serial
1512 private void readObject(java.io.ObjectInputStream s)
1513 throws IOException, ClassNotFoundException {
1514 // Read in the threshold (ignored), loadfactor, and any hidden stuff
1515 s.defaultReadObject();
1516 reinitialize();
1517 if (loadFactor <= 0 || Float.isNaN(loadFactor))
1518 throw new InvalidObjectException("Illegal load factor: " +
1519 loadFactor);
1520 s.readInt(); // Read and ignore number of buckets
1521 int mappings = s.readInt(); // Read number of mappings (size)
1522 if (mappings < 0)
1523 throw new InvalidObjectException("Illegal mappings count: " +
1524 mappings);
1525 else if (mappings > 0) { // (if zero, use defaults)
1526 // Size the table using given load factor only if within
1527 // range of 0.25...4.0
1528 float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);
1529 float fc = (float)mappings / lf + 1.0f;
1530 int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ?
1531 DEFAULT_INITIAL_CAPACITY :
|