Irvin Gil

Posted on Nov 1

A comprehensive guide to Map in Java

#java #programming

In this post, we take a closer look at Maps in Java, examining each implementation of the Map interface 🔍. By the end, you'll have a clearer understanding of the use cases for each class—and when to use ✅ or avoid them 🙅‍♂️.

A Map is an object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value.

The interface provides 3 collection views which allows it's contents to be viewed as:

set of keys
collection of values
or set of key-value mappings

The order of a map is defined as the order in which the iterators on the map's collection views return their elements.
Implementations such as TreeMap make specific guarantees to their order; others, like HashMap does not.
⚠️ Great care must be exercised if mutable objects are used as map keys. The behavior of a map is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is a key in the map.

Unmodifiable Map

Unmodifiable maps are immutable map instances created using static factory methods like Map.of(), Map.ofEntries(), and Map.copyOf(). These provide a convenient way to create read-only maps.

Key Characteristics

1. Immutability

Keys and values cannot be added, removed, or updated
Any mutator method calls will throw UnsupportedOperationException
However, if contained keys/values are themselves mutable, the map behavior may appear inconsistent

2. Null Restrictions

Null keys and values are disallowed
Attempts to create with null keys/values result in NullPointerException
This is stricter than regular HashMap which allows nulls

3. Duplicate Key Prevention

Duplicate keys are rejected at creation time
Results in IllegalArgumentException
Ensures map integrity from the start

4. Iteration Order

Iteration order is unspecified and subject to change
Don't rely on any particular ordering
Different from LinkedHashMap which maintains insertion order

5. Value-Based Nature

Instances are value-based - treat equal instances as interchangeable
Don't use for synchronization - unpredictable behavior may occur
Don't make assumptions about instance identity
Factories may create new instances or reuse existing ones

Best Practices

✅ Good Use Cases

Configuration data that shouldn't change
Constant lookup tables
API responses that should remain immutable
Default values or fallback data

❌ Avoid When

You need to modify the map after creation
You need null keys or values
You require specific iteration order
You need to use the map for synchronization

Common Pitfalls

Assuming mutability: Remember these maps are completely immutable
Null handling: Unlike HashMap, nulls will cause exceptions
Iteration order: Don't rely on any specific order
Synchronization: Don't use for thread synchronization primitives
Identity assumptions: Don't rely on object identity, use .equals()

Performance Notes

Generally more memory-efficient than regular HashMap for small, fixed datasets
Optimized for read operations
No overhead for modification tracking since they're immutable
Iteration performance is predictable: O(size) rather than O(capacity)

Common known implementation classes of Map Interface

HashMap

HashTable implementation of the Map interface
provides all of the optional map operations and permits null values and the null key. It's the roughly the equivalent to HashTable, except that it's unsynchronized and permits null)
Note that this implementation is not synchronized. If multiple threads access a hash map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more mappings; merely changing the value associated with a key that an instance already contains is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the map. If no such object exists, the map should be "wrapped" using the Collections.synchronizedMap method. This is best done at creation time, to prevent accidental unsynchronized access to the map:

  Map m = Collections.synchronizedMap(new HashMap(...));

Makes no guarantees as to the order of the map; and does guarantee that the order will remain constant over time.
provides constant time performance for operations: get and put (O(1)).
Iteration over collections view requires time proportional to the "capacity" of the instance (number of buckets) plus the size (the number of key-value mapping).
- Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.

TreeMap

A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.
This implementation provides log(n) time cost for the containsKey, get, put and remove operations
This map implementation is not synchronized. But can be synchronized by wrapping it with Collections.synchronizedSortedMap method, which is best done at creation time, to prevent accidental unsynchronized access to the map.

  SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

Works best if sorting is important in the implementation use case. But trades some performance for put, get and remove operations

HashTable

This class implements a hash table, which maps keys to values. Any non-null object can be used as a key or as a value (null objects are not allowed to be used as keys or values).
To successfully store and retrieve objects from a hashtable, the objects used as keys must implement the hashCode method and the equals method.
An instance of Hashtable has two parameters that affect its performance: initial capacity and load factor.
- Capacity
  - The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created.
  - Note that the hash table is open: in the case of a "hash collision", where a single bucket stores multiple entries, which must be searched sequentially.
- Load factor
  - The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.
- The initial capacity and load factor parameters are merely hints to the implementation. The exact details as to when and whether the rehash method is invoked are implementation-dependent.
Unlike the new collection implementations, Hashtable is synchronized.
- If a thread-safe implementation is not needed, it is recommended to use HashMap in place of Hashtable.
- If a thread-safe highly-concurrent implementation is desired, then it is recommended to use ConcurrentHashMap in place of Hashtable.

SortedMap

A Map that further provides a total ordering on its keys. The map is ordered according to the natural ordering of its keys, or by a Comparator typically provided at sorted map creation time.
All keys inserted into a sorted map must implement the Comparable interface (or be accepted by the specified comparator).
SortedMap does not allow null keys or null values. If we insert a null key or value it will throw an error.
The primary class that implements SortedMap is TreeMap.

LinkedHashMap

Differs from HashMap implementation as it maintains doubly-linked list running through it's entries.This linked list defines the encounter order (the order of iteration), which is normally the order in which keys were inserted into the map (insertion-order).
- This linked list defines the encounter order (the order of iteration), which is normally the order in which keys were inserted into the map (insertion-order).
The reverse-ordered view of this map is in the opposite order, with the youngest entry appearing first and the eldest entry appearing last (use or reversed() method).
The encounter order of entries already in the map can be changed by using the putFirst and putLast methods.
This class provides all of the optional Map and SequencedMap operations, and it permits null elements.
It is not thread-safe; to synchronize it, use Collections.synchronizedMap().
It provides constant-time performance (O(1)) for the basic operations (add, contains and remove)
Performance is likely to be just slightly below that of HashMap, this is due to the expense of maintaining a linked list.

Re-insertion in LinkedHashMap

Refers to the action of calling the put(key, value) method with a key that already exists in the map.

When you call map.put(existingKey, newValue), the map checks if the existingKey is already present.

If it is, the old value associated with that key is replaced by the newValue.
The put() method actually returns the previous value that was associated with the key, or null if the key was new.

  Map<String, Integer> scores = new HashMap<>();
  scores.put("Alice", 90); // Key is "Alice", value is 90

  // Key Re-insertion (Update)
  Integer oldValue = scores.put("Alice", 95); // Key "Alice" exists, value is updated to 95 
  System.out.println(oldValue) // oldValue will be 90

  // The map now contains: {"Alice": 95}

By default, if you call put() with an existing key in a LinkedHashMap, the value is replaced, but the insertion order is NOT affected. The key remains in its original position in the iteration order.

Comparison of LinkedHashMap and HashMap in terms of iteration

The HashMap Iteration: Proportional to Capacity (Buckets)

A HashMap is a classic Hash Table. It is internally implemented as an array of buckets (also called slots or an entry table).

Iteration Process: To iterate over a HashMap, the iterator must:
1. Traverse the entire array of buckets (i.e., iterate from index 0 to capacity - 1).
2. Check if a bucket is empty or contains an entry.
3. If a bucket contains a linked list or tree of entries (due to hash collisions), it must then traverse that internal structure to find the actual key-value pairs.
Complexity: The time required is proportional to:

  O(Capacity + Size)

The Problem with Overcapacity: If you create a HashMap with a large capacity but only insert a few entries (a low load factor), the iterator still has to check all those empty buckets. This makes iteration inefficient.

Terms

Capacity - The total size of the underlying array (number of buckets).

Size - The actual number of key-value pairs stored in the map.

The LinkedHashMap Iteration: Proportional to Size (Entries)

A LinkedHashMap is a subclass of HashMap that adds an extra structure to solve the iteration problem and guarantee order.

Internal Structure:
- It has the same array of buckets (Hash Table) as HashMap for fast get() and put() operations.
- Crucially, it also maintains a separate, non-circular, doubly-linked list that connects every single entry in the map, in the order they were inserted (or accessed).
Iteration Process: To iterate over a LinkedHashMap, the iterator simply:
1. Starts at the head of the doubly-linked list.
2. Follows the next reference from one entry to the next until it reaches the end of the list.
Complexity: The iteration only involves visiting the actual entries, regardless of how large the underlying bucket array is or how many buckets are empty.

  O(Size)

Summary Table

Feature	`HashMap`	`LinkedHashMap`
Data Structure	Hash Table (array of buckets/lists/trees)	Hash Table PLUS a Doubly-Linked List
Guaranteed Order?	No (chaotic/unspecified)	Yes (Insertion Order or Access Order)
Iteration Time	O(Capacity+Size)	O(Size)
Cost of Overhead	Lower memory footprint	Slightly higher memory (to store the `before` and `after` pointers for the linked list)

Comparison and Summary

Visualization Map Hierarchy

# plantuml
interface Map<K,V>
class HashMap<K,V>
class HashTable<K,V>
interface SortedMap<K,V>
class LinkedHashMap<K,V>
class TreeMap<K,V>


HashMap ..|> Map : null allowed
HashTable --|> Map : synchronized. null not allowed
SortedMap --|> Map : sorted
LinkedHashMap ..|> HashMap
TreeMap ..|> SortedMap

Feature	HashMap	Hashtable	TreeMap	LinkedHashMap
Accessing map element that rely on sorting	❌ No sorting capability	❌ No sorting capability	✅ Best choice - Natural ordering or custom Comparator	❌ No sorting capability
Accessing map element that rely on ordering of elements	❌ No guaranteed order (chaotic)	❌ No guaranteed order	✅ Sorted order (ascending by default)	✅ Best choice - Insertion order or access order
Constant time performance for `get` and `put`	✅ O(1) average case	✅ O(1) average case	❌ O(log n) guaranteed	✅ O(1) average case
Cost of overhead	✅ Lowest - Basic hash table	✅ Low - Hash table + synchronization	❌ Highest - Red-Black tree structure	❌ Higher - Hash table + doubly-linked list
Iteration time	❌ O(Capacity + Size) - Can be expensive if capacity >> size	❌ O(Capacity + Size) - Can be expensive if capacity >> size	✅ O(Size) - Proportional to number of entries	✅ O(Size) - Proportional to number of entries
Synchronized	❌ Not synchronized - Manual synchronization required	✅ Fully synchronized - Thread-safe	❌ Not synchronized - Manual synchronization required	❌ Not synchronized - Manual synchronization required

HashMap

Best for: General-purpose mapping with fastest performance
Data Structure: Hash table (array of buckets)
Null support: Allows null keys and values
Thread safety: Not synchronized

Hashtable

Best for: Legacy applications requiring thread-safe maps
Data Structure: Hash table with synchronization
Null support: Does NOT allow null keys or values
Thread safety: Fully synchronized (all methods)

TreeMap

Best for: Sorted maps, range operations, navigation methods
Data Structure: Red-Black tree (self-balancing BST)
Null support: No null keys (but allows null values)
Special methods: firstKey(), lastKey(), headMap(), tailMap(), subMap()

LinkedHashMap

Best for: Maintaining insertion/access order with good performance
Data Structure: Hash table + doubly-linked list
Null support: Allows null keys and values
Order modes: Insertion-order (default) or access-order
Special feature: Can implement LRU cache with removeEldestEntry()

Recommendations:

For sorting requirements: Use TreeMap
For ordering requirements: Use LinkedHashMap
For maximum performance: Use HashMap
For thread safety: Use ConcurrentHashMap (modern) or Hashtable (legacy)
For LRU cache: Use LinkedHashMap with access-order mode

DEV Community