Java Reference ยท Collections
The HashMap class
Reference for java.util.HashMap: constant-time lookups, how hashing and buckets work, null handling, load factor, and why iteration order is unspecified.
HashMap<K, V> is the default Map. It stores entries in an array of buckets chosen by the key's hashCode(), so get and put take expected constant time. It allows one null key and any number of null values, and it is not synchronized.
Lookup finds the bucket from the hash, then compares keys with equals(). A key class must therefore follow the contract: equal keys have equal hash codes. Since Java 8, a bucket with many collisions turns into a balanced tree (for comparable keys), which caps the worst case at O(log n).
Map<String, Integer> counts = new HashMap<>(); Map<String, List<String>> index = new HashMap<>(64); // initial capacity
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.
Syntax
public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, java.io.Serializable
| Constructor | Description |
|---|---|
HashMap() |
Default capacity 16, load factor 0.75. |
HashMap(int initialCapacity) |
Table sized for that capacity. Throws IllegalArgumentException if negative. |
HashMap(int initialCapacity, float loadFactor) |
Also sets the load factor. |
HashMap(Map<? extends K, ? extends V> m) |
Copy of m. Throws NullPointerException if m is null. |
static <K,V> HashMap<K,V> newHashMap(int numMappings) |
Sized to hold that many mappings without resizing (Java 19). |
All Map methods are available; see Map.
Usage notes
- Complexity:
get,put,remove,containsKeyare expectedO(1);containsValueisO(n). Iteration isO(capacity + size). - Resizing: when size exceeds
capacity * loadFactor, the table doubles and entries are redistributed. Pre-size to avoid repeated rehashing. - Order is unspecified and may change after resizing; use
LinkedHashMaporTreeMapif order matters. - Keys: immutable keys such as
String, boxed numbers, records and enums are safest. Never mutate a key's hash-relevant state while it is in the map. - Nulls: one
nullkey (always in bucket 0) and manynullvalues are allowed, butget()cannot distinguish anullvalue from absence. - Not thread-safe. Concurrent modification can corrupt data; use
ConcurrentHashMapor external locking. - Fail-fast iterators: structural modification during iteration throws
ConcurrentModificationExceptionon a best-effort basis. - Memory: every entry is a node object; boxed primitives add more. For large primitive-keyed data consider specialized libraries or arrays.
Related
- Map, LinkedHashMap, TreeMap, HashSet, Map.merge()
- Lessons: HashMap, How HashMap works