Collections Framework Part 2: Map and Queue

Executive Summary

Map and Queue split the work, and a Map keys values by unique objects: HashMap for O(1) lookups with no order, LinkedHashMap for insertion (or access) order, TreeMap for sorted keys and range queries at O(log n). Keys must be immutable and honor the equals and hashCode contract from the Object article, because a mutated key becomes unfindable. Also, the modern Map API replaces the contains-then-put dance: getOrDefault for defaults, putIfAbsent for write-once, computeIfAbsent for grouping, merge for counting. Queues model processing order: ArrayDeque is the default engine for both FIFO queues and LIFO stacks (the legacy Stack class is dead; never write it again). Also, PriorityQueue is a binary heap that always polls the smallest element first, though its iteration order is unspecified. The next article prices every collection against each other. Then, Part 5 shows the concurrent versions your thread pools will feed.

Map in Java: Keys to Values

A Map stores key-to-value pairs, with unique keys and free values. The Map interface defines the contract. Also, HashMap implements it with the same bucket machinery HashSet uses, which is no accident: HashSet is a HashMap where every key points at the same placeholder value.

import java.util.HashMap;
import java.util.Map;

Map<String, Integer> stock = new HashMap<>();   // declare Map, construct HashMap
stock.put("pen", 12);
stock.put("book", 3);

Integer pen = stock.get("pen");        // 12
Integer marker = stock.get("marker");  // null: absent, distinguishable from 0
int markers = stock.getOrDefault("marker", 0);   // 0: default without null checks

stock.put("pen", 20);                    // keys are unique: replaces, size stays 2
System.out.println(stock.containsKey("book"));   // true
System.out.println(stock.remove("pen"));        // 20: returns the old value

Map<String, Integer> fixed = Map.of("a", 1, "b", 2);   // immutable map

Iteration goes over entrySet, which exposes both key and value. However, iterating keySet and calling get inside the loop is the classic two-lookups mistake:

for (var entry : stock.entrySet()) {
    System.out.println(entry.getKey() + " -> " + entry.getValue());
}

stock.forEach((key, value) ->
        System.out.println(key + " -> " + value));   // same idea, lambda form

HashMap, LinkedHashMap, TreeMap: Same Contract, Three Orders

Implementation	get / put	Iteration order	Nulls	Notes
HashMap	O(1)	Unspecified	One null key, null values	The default
LinkedHashMap	O(1)	Insertion, or access order	Same as HashMap	Can evict eldest entry: tiny caches
TreeMap	O(log n)	Sorted by key	No null keys	NavigableMap: floorKey, ceilingKey, ranges

Also, the key discipline carries over directly from the Object article: keys must be immutable and their equals/hashCode pair correct, or lookups fail silently. In fact, records are the best key type you can choose, correct by construction. Similarly, for enum keys, EnumMap from the enums article beats all three rows above with its ordinal array.

The Methods That Retired the contains-then-put Dance

Wrong code first. Still, this shape is in every legacy codebase, and each line is a separate hash lookup:

// WRONG: three lookups, three chances to be wrong, and a race under threads
if (stock.containsKey("marker")) {
    stock.put("marker", stock.get("marker") + 1);
} else {
    stock.put("marker", 1);
}

// RIGHT: one call, one lookup, one intention
stock.merge("marker", 1, Integer::sum);        // counting: add 1, sum on conflict
stock.putIfAbsent("marker", 0);               // write-once defaults
stock.computeIfAbsent("m1", k -> new ArrayList<>()).add("task");
                                              // grouping: build the list on first touch

The delta: the modern API says what you want instead of how to check for it. Integer::sum is a method reference, a taste of Part 3’s lambdas article. So, read it as “on conflict, sum the old and new values”. The computeIfAbsent line is the grouping idiom: it creates the list only when the key is absent, then appends. Also, it is the single most reused line in this article.

Queue in Java: Processing Order as a Contract

A Queue models what gets handled next, per the Queue interface: offer adds, poll retrieves and removes from the front, peek looks without removing. The general-purpose engine is ArrayDeque, a resizable circular array that implements both Queue (FIFO) and Deque (double-ended, so it doubles as a stack):

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Deque;

Queue<String> tasks = new ArrayDeque<>();
tasks.offer("ingest");      // add to the tail
tasks.offer("process");
tasks.offer("report");
System.out.println(tasks.peek());   // ingest: next up, still in the queue
System.out.println(tasks.poll());   // ingest: retrieved and removed
System.out.println(tasks.size());   // 2

Deque<String> stack = new ArrayDeque<>();   // the same class, LIFO usage
stack.push("bottom");       // push onto the head
stack.push("top");
System.out.println(stack.pop());     // top: last in, first out

Two naming conventions coexist on purpose. The Queue methods (offer, poll, peek) return special values on failure, false or null. In contrast, the Collection methods (add, remove, element) throw instead. So, prefer the offer and poll family in loops, where an empty queue is a normal event, not an exception.

Why Nobody Writes new Stack() Anymore

The java.util.Stack class predates the framework and is synchronized on every operation, which is a performance tax with no benefit for single-threaded code. In contrast, ArrayDeque does everything Stack does, faster, with no legacy interface. Consequently, the professional rule is a deletion rule: when you see new Stack() in code review, replace it with new ArrayDeque<>() and move on. LinkedList also implements Deque, but the List article‘s verdict applies here unchanged: ArrayDeque is the default.

PriorityQueue: The Heap, Not a Sorted List

PriorityQueue is a binary heap: offer and poll cost O(log n). Also, poll always returns the smallest element according to natural order or the Comparator you supply. However, what it does not do is maintain a sorted iteration; its iterator walks the heap array in internal order:

import java.util.PriorityQueue;

var urgent = new PriorityQueue<Integer>();
urgent.offer(5);
urgent.offer(1);
urgent.offer(3);
System.out.println(urgent.poll());   // 1: smallest first
System.out.println(urgent.poll());   // 3
System.out.println(urgent.poll());   // 5
// but urgent.iterator() is NOT sorted; only polling is ordered

Engine	Structure	offer / poll	Best for
ArrayDeque	Resizable circular array	O(1)	Stacks and FIFO queues: the default
LinkedList	Doubly-linked nodes	O(1)	Rarely; ArrayDeque wins almost always
PriorityQueue	Binary heap	O(log n)	Always handle the most urgent item first

The Complete Example: Counting and Scheduling

import java.util.ArrayDeque;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Queue;

public class MapQueueDemo {
    public static void main(String[] args) {
        // counting with merge
        String[] words = {"ada", "linus", "ada", "grace", "ada"};
        Map<String, Integer> counts = new LinkedHashMap<>();
        for (String word : words) {
            counts.merge(word, 1, Integer::sum);
        }
        counts.forEach((word, count) -> System.out.println(word + ": " + count));

        // grouping with computeIfAbsent
        Map<String, java.util.List<String>> byFirst = new LinkedHashMap<>();
        for (String word : words) {
            byFirst.computeIfAbsent(word.substring(0, 1), k -> new java.util.ArrayList<>())
                   .add(word);
        }
        System.out.println(byFirst);

        // a work queue
        Queue<String> pipeline = new ArrayDeque<>();
        pipeline.offer("ingest");
        pipeline.offer("process");
        pipeline.offer("report");
        while (!pipeline.isEmpty()) {
            System.out.println("running: " + pipeline.poll());
        }
    }
}

ada: 3
linus: 1
grace: 1
{a=[ada, ada, ada], l=[linus], g=[grace]}
running: ingest
running: process
running: report

Read the output as three idioms you will use for the rest of your career: merge for counting, computeIfAbsent for grouping, and a poll loop for ordered work. In fact, every aggregation pipeline you meet in Part 3’s streams articles is these three shapes, streamed.

How Real Systems Do This

Maps are the backbone of nearly every in-memory index: a service registry mapping instance IDs to connections, a cache mapping request signatures to responses, a configuration layer mapping keys to parsed values. The collections interfaces lesson describes exactly these roles, and the compute family is how production writes them: counting with merge, grouping with computeIfAbsent, defaults with getOrDefault.

Also, the counting and grouping idioms have a performance shadow worth knowing. In my experience profiling slow services, a hand-rolled contains-then-put loop over a hot map costs about three lookups per event. In contrast, the merge version costs one. On a pipeline doing tens of millions of lookups, that single-line change has been the difference between a CPU-bound service and one with headroom. Also, it reads better, which is the rare case where the fast code is also the clean code.

Queues front every worker system. The pattern is always the same: producers offer work, consumers poll it, and Part 5’s thread pools are consumers in that exact shape. Also, the ExecutorService article shows pools with their own internal queues. One caution now, before Part 5 arrives: the plain queues in this article are not thread-safe. So, sharing one across threads produces lost or duplicated work. The concurrent collections article covers the versions that are.

Finally, caches need bounds. A HashMap used as a cache with no eviction policy grows until the heap does. Then, the OutOfMemoryError arrives on the busiest day of the year. LinkedHashMap’s access-order mode with an eviction override is the smallest bounded cache. In fact, it is exactly how production teams build one before reaching for a cache library.

Decision Framework for Map and Queue

1. Is the data key-to-value by nature? Map. Enum keys? EnumMap. Sorted keys or range queries? TreeMap. Insertion order? LinkedHashMap. Otherwise HashMap.
2. Are keys mutable? Stop and make them immutable, or the map will lose entries the moment a key changes.
3. Counting, grouping, or defaulting? merge, computeIfAbsent, getOrDefault, in that order, never the contains-then-put dance.
4. FIFO or LIFO processing? ArrayDeque for both. Most-urgent-first? PriorityQueue with a Comparator.
5. Failure handling in loops? offer and poll, which return null and false, over add and remove, which throw on empty.
6. Fixed data at compile time? Map.of, immutable and defensive-copy-free.
7. Multiple threads at the door? Not these classes; Part 5’s concurrent collections are the next stop.

When NOT to Use This

• Also, do not use a Map to model a fixed set of named fields. A record with name, email, and role says what the data is; a Map<String, Object> says nothing and checks nothing.
• Similarly, do not use the legacy Stack or Hashtable classes in new code. ArrayDeque and HashMap are their modern replacements, and legacy synchronization taxes every operation.
• Finally, do not assume PriorityQueue iteration is sorted. Only poll is ordered; iterating gives heap order, and code that depends on sorted iteration must drain or sort instead.

Common Mistakes

• The containsKey-then-get-then-put dance: three lookups where merge or computeIfAbsent needs one, plus a race condition that Part 5 makes real.
• Mutating an object used as a map key. The key hashes to its old bucket and the entry becomes unreachable: the ghost-entry bug in its most expensive form.
• Iterating keySet and calling get inside the loop. Each value costs a second lookup; entrySet or forEach gives you both at once.
• Writing new Stack(). It is synchronized on every call and extends a legacy class; ArrayDeque is the modern answer for LIFO.
• Expecting PriorityQueue to iterate in order. The iterator walks the heap array; sorted output requires repeated poll.
• Assuming get returning null means “absent” while also storing null values. It cannot distinguish the two; getOrDefault or containsKey exist for exactly that boundary.

Key Takeaways

• Maps key values by unique objects: HashMap by default, LinkedHashMap for order, TreeMap for sorted keys and ranges, EnumMap for enums.
• Map keys must be immutable with a correct equals and hashCode pair; records are the ideal key type.
• merge counts, computeIfAbsent groups, getOrDefault defaults: one lookup each, replacing the contains-then-put dance.
• Iterate maps through entrySet or forEach; iterating keySet plus get doubles every lookup.
• ArrayDeque is the engine for both queues and stacks; the legacy Stack class is retired.
• PriorityQueue polls the most urgent element first, but its iteration is heap order, not sorted order.
• Plain collections are not thread-safe; Part 5 introduces the concurrent versions before threads need them.

FAQ

What is the difference between HashMap and TreeMap in Java?

HashMap hashes: O(1) get and put, unspecified iteration order, one null key allowed. TreeMap sorts: O(log n) operations, sorted iteration, and range methods like floorKey and ceilingKey, with no null keys.

How do I iterate a Map in Java?

Iterate entrySet with a for-each to get key and value together, or use forEach with a two-argument lambda. Iterating keySet and calling get inside the loop doubles every lookup for no benefit.

What does computeIfAbsent do in Java?

It returns the value for a key, computing and storing a new one only if the key is absent. It is the grouping idiom: computeIfAbsent(key, k -> new ArrayList<>()).add(item) builds and appends in one line.

Should I use Stack or Deque in Java?

Deque, implemented by ArrayDeque. Stack is a legacy class synchronized on every operation; ArrayDeque is faster, implements both LIFO and FIFO behavior, and is the framework’s intended replacement.

How does PriorityQueue work in Java?

It is a binary heap: offer and poll cost O(log n), and poll always returns the smallest element by natural order or your Comparator. Its iterator is not sorted; only the sequence of poll calls is.

Conclusion

Map and Queue complete the collection vocabulary: keyed lookup with three orders to choose from, and processing order as a first-class contract. The modern Map API alone retires a decade of boilerplate. Also, ArrayDeque quietly replaces two legacy classes with one good one.

The next article prices the entire framework against itself: a decision matrix that turns “which collection?” from habit into engineering, with the Big-O tables you now have for every interface.

Key it, merge it, queue it. The framework is now yours end to end.

Last updated on 5 September 2026.