HashMap in Java

Here, ^ is bitwise XOR and >>> is unsigned right shift. The operation folds information from the high bits of the original hash into the low bits. This matters because bucket selection uses low bits of the mixed hash when the table capacity is a power of two.

The index calculation is conceptually equivalent to:

(table.length - 1) & hash

Because the capacity is a power of two, this mask selects the appropriate low bits. Mixing helps differences in high bits influence the selected bucket instead of relying only on the original low bits.

These details describe the widely used OpenJDK implementation strategy; the Map interface itself does not promise a particular internal hash-spreading expression.

6.1 Null key hashing

HashMap supports one null key. In the standard implementation, null is handled specially and assigned a hash of zero, so the null-key mapping is stored in the bucket selected by that hash. The implementation still handles the null key as a valid key rather than calling hashCode() on null.

7. Hash Collisions

A collision occurs when two distinct keys map to the same bucket index. Collisions are a normal property of hash tables: the set of possible keys is much larger than the finite number of buckets, so different keys can share a bucket.

A collision does not mean the keys are equal. The map must still compare candidate keys and distinguish them correctly. In a linked-list bucket, lookup examines nodes until it finds a matching key or reaches the end.

Good hash distribution keeps bucket chains short. If many keys cluster into one bucket, lookup and update operations must do more work. That is why a correct and reasonably distributed hashCode() implementation matters.

8. Treeification: From a List to a Red-Black Tree

In modern OpenJDK HashMap implementations, a bucket that becomes crowded can be converted from a linked list into a red-black tree. This is called treeification.

Common implementation constants include:

• TREEIFY_THRESHOLD: 8.
• MIN_TREEIFY_CAPACITY: 64.
• UNTREEIFY_THRESHOLD: 6.

These are implementation details, not requirements imposed by the Map interface. The exact transition depends on insertion path and implementation conditions; the thresholds should be understood as internal behavior rather than a universal API promise.

The minimum table-capacity condition is important. If the table is still small, growing the table may redistribute entries more effectively than building a tree. Once a bucket is treeified, searching that bucket can be logarithmic under suitable key-comparison conditions, rather than requiring a full linked-list scan. If a tree bin becomes small after removals, it may be converted back into a list.

Why use a red-black tree?

A linked list is simple and economical for a small number of entries. A balanced tree adds structural overhead, so it is not worthwhile for every bucket. When a bucket is unusually crowded, however, a balanced tree helps prevent the bucket from behaving like a very long list.

The tree structure is a defensive measure for poor hash distributions or unusual inputs, not something expected to happen frequently in a well-behaved general-purpose map.

9. Resizing and Rehashing

When the number of mappings exceeds the resize threshold, HashMap expands its table. In the standard doubling strategy, a new table with twice the previous capacity is created and existing entries are redistributed.

For the default capacity of 16 and load factor of 0.75:

These values illustrate the usual default growth pattern. The table may be allocated lazily, and explicit constructor sizing can change when the first growth occurs.

9.1 Why doubling is efficient

When the capacity doubles, the standard implementation can determine whether an entry stays at its old bucket index or moves to the old index plus the old capacity by examining a relevant hash bit. This avoids calculating each new index from scratch using a completely different method.

9.2 Cost of resizing

A resize must process the existing mappings, so an individual resize is O(n) in the number of entries. Most ordinary insertions do not trigger a resize. Across a long sequence of insertions, the average or amortized insertion cost remains constant-time under typical conditions, even though the particular insertion that triggers a resize can be more expensive.

9.3 Pre-sizing a map

If the approximate number of mappings is known in advance, selecting an appropriate initial capacity can reduce repeated growth and redistribution. For example, a constructor argument such as new HashMap<>(64) requests an initial capacity of 64 under the API's capacity semantics. In standard implementations, capacity is rounded to a suitable power of two. Do not confuse the requested initial capacity with a promise that the internal array is allocated immediately.

Pre-sizing can be helpful when loading a large catalogue, importing records, or building a lookup table in one pass. It should be based on a reasonable estimate rather than an unnecessarily large guess, which wastes memory.

10. get(), put(), and remove() in Detail

These core operations share the same basic route: compute the key hash, find the bucket, and inspect the relevant bucket structure.

10.1 get(key)

get() finds the bucket associated with the key, then checks candidate entries. Implementations can compare stored hashes before invoking equality checks, avoiding some unnecessary comparisons. If a matching key is found, its value is returned. Otherwise, get() returns null.

10.2 put(key, value)

put() searches the selected bucket for an equal key. If it finds one, it replaces the associated value and returns the old value. If no matching key exists, it adds a new mapping, updates the size, and checks the resize threshold.

Replacing a value for an existing key does not increase the number of mappings. Adding a new distinct key does.

10.3 remove(key)

remove() locates the matching entry and unlinks it from the bucket structure. It reduces the map's size and returns the removed value. If no mapping is found, it returns null. When null values are permitted, the return value alone may not distinguish a missing key from a removed mapping whose value was null.

11. Null Keys and Null Values

HashMap permits one null key and any number of null values. The single-null-key rule follows from key uniqueness: the same null key cannot represent multiple separate mappings.

A null value creates an important ambiguity. Suppose a map has no mapping for "alex@example.com". get() returns null. If the map does contain that key but its stored value is null, get() also returns null.

To distinguish the cases, use containsKey(key):

• get(key) == null and containsKey(key) == false: no mapping exists.
• get(key) == null and containsKey(key) == true: a mapping exists with a null value.

Storing null values is legal, but it can force every caller to perform additional checks. In many application designs, representing “not present” by the absence of a mapping is simpler than storing null as a value.

12. equals() and hashCode() Contract

Correct key behavior is essential to HashMap.

The key's hashCode() helps locate a bucket, while equals() determines whether a candidate key is logically equal to the key being searched for. The contract requires:

1. If a.equals(b) is true, then a.hashCode() must equal b.hashCode().
2. Equal hash codes do not prove that two objects are equal; collisions are allowed.
3. The results of these methods should remain consistent while the fields relevant to equality and hashing remain unchanged.

Standard value types such as String implement these methods appropriately. For custom key classes, override both methods consistently when equality is based on the object's value rather than its identity.

12.1 What goes wrong with a broken contract?

If two objects are considered equal by equals() but return different hash codes, the map may route them to different buckets. It may then fail to recognize that they represent the same logical key. A larger table does not fix this contract violation.

A poor hash function that returns the same value for many unequal keys is a different problem. The map can still distinguish the keys through equality checks, but many entries may cluster into one bucket and operations become slower.

13. Why Mutable Keys Cause Lookup Problems

A key should not change its equality- or hash-related state while stored in a hash-based map. If a key is inserted and then a field used by hashCode() changes, a later lookup calculates a new bucket index, while the existing entry may still reside in the bucket selected by the old hash.

The entry can therefore remain in the map but become difficult or impossible to find through normal lookup using that changed key. This is why immutable key objects, or objects whose equality-related state stays stable, are safer map keys.

The issue is not simply that an object is mutable. It is specifically dangerous to change the state used by equals() or hashCode() after insertion.

14. Iteration Order

A HashMap does not guarantee insertion order or sorted-key order. Iteration order depends on bucket placement, hashes, table capacity, and resizing. A resize can change the order in which entries are encountered.

Do not rely on the order observed in a single run, even if it appears stable during development. If order is a requirement, select an implementation that documents the needed behavior:

• Use LinkedHashMap for a defined encounter order, commonly insertion order.
• Use TreeMap for sorted key order.

Iteration is commonly performed through entrySet(), keySet(), or values(), depending on whether the code needs pairs, keys, or values.

15. Fail-Fast Iterators

HashMap iterators are fail-fast on a best-effort basis. If the map is structurally modified during iteration by something other than the iterator's own supported removal operation, the iterator may throw ConcurrentModificationException when it detects the change.

Structural modifications include adding a new mapping or removing a mapping. Replacing the value for an existing key is generally not a structural change, because the number and identity of mappings remain the same.

When removing entries during an iterator-based traversal, use the iterator's remove() method rather than directly calling map.remove(key) from the loop. Another safe pattern is to collect keys for later removal after iteration has finished.

Fail-fast behavior is a debugging aid, not a thread-safety guarantee. It does not reliably detect every concurrent access, and it does not make a HashMap safe for multiple writers.

16. Thread Safety and Concurrent Access

HashMap is not thread-safe for concurrent modification. If multiple threads access a shared map and at least one thread modifies it without suitable coordination, the application can encounter race conditions, lost updates, inconsistent observations, or other unexpected behavior.

Choose a strategy that matches the workload:

A synchronized wrapper does not automatically make a multi-step sequence atomic. Iteration over a synchronized map also requires following the wrapper's documented synchronization guidance. ConcurrentHashMap is often a better starting point for concurrent lookup and update workloads, but its semantics and supported operations should still be checked against the application requirements.

A common misconception is that a map is thread-safe because a test with multiple threads happened to pass. Race conditions can be intermittent and may only appear under different timing or load.

17. Time Complexity Summary

The following table gives the usual high-level expectations, not guarantees for every possible key distribution.

For crowded buckets, tree bins can improve lookup behavior compared with long linked lists. However, exact worst-case behavior also depends on key ordering and comparison details. The table's average-case description should not be read as a promise that every operation always takes constant time.

18. Common Mistakes

Mistake 1: Assuming HashMap preserves insertion order

It does not promise insertion order. Use LinkedHashMap when a defined encounter order is required.

Mistake 2: Assuming a collision means two keys are equal

Different keys can share a bucket. Equality checks distinguish a matching key from a different key in the same bucket.

Mistake 3: Implementing equals() without a compatible hashCode()

Equal keys must produce equal hash codes. Otherwise, logically equal keys can be routed to different buckets.

Mistake 4: Changing a key after inserting it

Changing equality- or hash-related fields can make the mapping difficult to retrieve. Prefer stable key objects.

Mistake 5: Treating a null result as proof that a key is absent

A null result may mean the key is missing or that a null value is stored. Use containsKey() when the distinction matters.

Mistake 6: Ignoring resize costs

Resizing is occasional but can be expensive for a large map. Consider a reasonable initial capacity when the approximate size is known.

Mistake 7: Removing directly from the map inside an enhanced for loop

This can trigger fail-fast behavior. Use an iterator's remove() method or collect entries for removal later.

Mistake 8: Sharing a mutable HashMap across threads without coordination

Fail-fast iterators do not provide thread safety. Use a suitable synchronization strategy or a concurrent map implementation.

19. Best Practices

1. Choose HashMap when fast key-based lookup is needed and no ordering guarantee is required.
2. Use keys with stable, well-defined equals() and hashCode() implementations.
3. Avoid mutating equality-related key fields while a key is stored in the map.
4. Do not rely on observed iteration order.
5. Prefer not to store null values unless the application genuinely needs to distinguish a null mapping from an absent mapping.
6. Use containsKey() when a null result from get() is ambiguous.
7. Pre-size the map when a realistic estimate of the number of entries is available.
8. Use iterator-supported removal while iterating.
9. Do not use fail-fast behavior as a concurrency control mechanism.
10. Select a concurrent collection or synchronization strategy for shared mutable maps.
11. Treat internal constants and hash-spreading details as implementation details, not Map API guarantees.
12. Profile realistic workloads before changing load factors or capacities.

20. Quick Revision

• HashMap implements Map<K,V> and stores unique keys with associated values.
• Its table is an array of buckets; collisions are handled within the bucket.
• The standard implementation mixes hash bits and uses a power-of-two table capacity to calculate indices.
• The conventional default capacity is 16 and default load factor is 0.75.
• In the usual default setup, the threshold is 12 and the 13th distinct insertion triggers growth.
• Crowded buckets can be converted from lists to red-black trees in modern OpenJDK implementations.
• Resizing redistributes entries and costs O(n) for that resize; insertion remains amortized O(1) under typical conditions.
• HashMap permits one null key and multiple null values.
• Correct equals() and hashCode() behavior is essential for custom keys.
• Mutating a key's hash-related state after insertion can break lookups.
• Iteration order is not guaranteed.
• Iterators are fail-fast on a best-effort basis, not thread-safe.
• HashMap is not safe for unsynchronized concurrent modification.
• Consider LinkedHashMap, TreeMap, or ConcurrentHashMap when their ordering or concurrency characteristics better fit the task.

21. Conclusion

HashMap is a foundational Java data structure because it offers convenient key-value storage with expected constant-time lookup, insertion, and removal under typical conditions. Understanding buckets, hashing, collisions, treeification, resizing, and the null-handling rules helps explain both its strengths and its limitations.

Correct key design is just as important as choosing the right collection. Keys should have consistent equals() and hashCode() implementations and should remain stable while stored. Finally, HashMap should be used for single-threaded or properly coordinated access, not as an unprotected shared map for concurrent updates. When ordering or concurrency is required, choose an implementation designed for that requirement.