HashMap, equals, and hashCode
How hashing works, why you must override equals and hashCode together, and the load factor that keeps lookups O(1).
Runs on a sandboxed JVM via the public Piston API. Edit the code and hit Run.
Buckets and chains
A HashMap is an array of buckets. When you put(key, value), Java computes key.hashCode(), spreads the bits, and takes it modulo the array length to pick a bucket. Multiple keys can land in the same bucket — that's a *collision* — so each bucket holds a small linked list. Since Java 8, buckets with 8+ entries convert to a balanced tree, capping worst-case lookup at O(log n).
The equals/hashCode contract
Two rules, non-negotiable: if a.equals(b), then a.hashCode() == b.hashCode(). If you break this, keys silently vanish — the map hashes them into one bucket but equals sends them to another. Override both together, ideally with your IDE, Objects.hash(...), or a record.
Runs on a sandboxed JVM via the public Piston API. Edit the code and hit Run.
Load factor and resizing
Load factor (default 0.75) is the ratio of entries to buckets at which the map resizes. When exceeded, HashMap allocates a bucket array twice as large and rehashes every entry — an O(n) event. If you know how many entries you'll insert, size the map with new HashMap<>(expectedSize / 0.75 + 1) to skip resizes entirely.
The convenient methods
getOrDefault(k, d) avoids the null check. putIfAbsent(k, v) inserts only if the key is missing. computeIfAbsent(k, fn) lazily materializes a value — perfect for Map<K, List<V>>. merge(k, v, fn) combines existing and new values — the counting pattern above uses Integer::sum.
Runs on a sandboxed JVM via the public Piston API. Edit the code and hit Run.
Iteration order isn't guaranteed
HashMap iteration order depends on the hash distribution and can change between runs and JVM versions. If you need a predictable order, use LinkedHashMap (insertion order) or TreeMap (sorted keys). Never write code that assumes a particular iteration order out of HashMap.
Null keys and thread safety
HashMap allows one null key and any number of null values. It is not thread-safe — concurrent modifications can corrupt the internal structure and even cause an infinite loop. Use ConcurrentHashMap when multiple threads share a map.