Maps, Ordering, and Collection Algorithms

Introduction

Maps associate keys with values. They are central to Java applications because many real systems need to retrieve information by an identifier: a student number identifies a student, a product code identifies inventory, and a database column name identifies a value. Java’s Collections Framework provides several map implementations, each optimized for a different notion of organization: hashing, insertion order, sorted order, or restricted key types.

This chapter examines HashMap, LinkedHashMap, TreeMap, and EnumMap; explains the relationship among equals(), hashCode(), and hashing; develops ordering with Comparable and Comparator; and applies sorting, searching, filtering, and immutable collection factories. The emphasis is not merely on syntax, but on selecting a collection whose behavioral and performance properties match the application.

Learning Objectives

By the end of this chapter, you should be able to:

• Select an appropriate Java Map implementation.
• Explain hashing, collisions, equality, and the equals()/hashCode() contract.
• Implement natural ordering with Comparable and alternative orderings with Comparator.
• Sort, search, filter, and transform collections using modern Java APIs.
• Create and use immutable collections safely.
• Identify common collection errors involving mutable keys, nulls, ordering, and concurrency.
• Design a map-based solution for a realistic programming problem.

1. The Map Abstraction

A map stores mappings of the form key → value. A key normally occurs at most once, while multiple keys may refer to equal values. The principal operations are:

V put(K key, V value);       // associates key with value
V get(Object key);           // retrieves value or null
V remove(Object key);        // removes mapping
boolean containsKey(Object key);
Set<K> keySet();
Collection<V> values();
Set<Map.Entry<K,V>> entrySet();

A map is not a subtype of Collection, because a mapping is a pair rather than a single element. However, maps provide collection views such as keySet(), values(), and entrySet().

The key question is what “organized” means in a particular application:

The complexity statements assume a well-distributed hash function and, for tree operations, a balanced tree. Big-O describes growth as the number of entries, n, increases; it does not guarantee a particular elapsed time on every machine.

2. Hash-Based Maps

2.1 Hashing and buckets

A hash table uses a hash value to choose a bucket in which a mapping may be stored. Java first obtains a key’s hash code through hashCode(), then the map uses an implementation-specific process to locate a table position. If different keys select the same bucket, a collision occurs. Collisions are normal and are resolved internally, traditionally through linked nodes and, in suitable cases, tree-based structures.

The expected constant-time behavior of HashMap depends on two conditions: keys should distribute reasonably across buckets, and the map should maintain an adequate table capacity. Java automatically resizes a HashMap when its size passes a threshold based on capacity and load factor. The default load factor is commonly 0.75, but application code should normally rely on the documented implementation defaults rather than assuming internal details.

Map<String, Integer> stock = new HashMap<>();
stock.put("P100", 42);
stock.put("P200", 18);

int quantity = stock.getOrDefault("P100", 0);
stock.merge("P100", 5, Integer::sum);

HashMap permits one null key and multiple null values. It does not guarantee iteration order. Code that depends on the order produced by one execution is defective, even if that order appears stable during testing.

2.2 The equals() and hashCode() contract

A map must determine whether a searched key is equal to a stored key. The essential contract is:

1. If a.equals(b) is true, then a.hashCode() == b.hashCode() must also be true.
2. If two objects have different hash codes, they cannot be equal.
3. Equal objects must remain equal while they are being used as keys, unless the map is updated consistently.
4. Unequal objects may have the same hash code; this is a collision, not a contract violation.

The reverse implication is not required: equal hash codes do not prove equality.

A correct value object might be written as follows:

public final class StudentId {
    private final String value;

    public StudentId(String value) {
        this.value = java.util.Objects.requireNonNull(value);
    }

    public String value() {
        return value;
    }

    @Override
    public boolean equals(Object other) {
        if (this == other) return true;
        if (!(other instanceof StudentId that)) return false;
        return value.equals(that.value);
    }

    @Override
    public int hashCode() {
        return value.hashCode();
    }
}

A key class that overrides equals() but not hashCode() can place equal objects in different buckets. A key whose fields change after insertion can become effectively lost: the map searches using a new hash code, while the entry remains in the old bucket. Immutable keys are therefore strongly preferred.

Objects.hash(field1, field2) is convenient for multiple fields. For performance-sensitive classes, an IDE-generated implementation or a carefully designed calculation may be preferable, but correctness must come first.

3. Preserving Order with LinkedHashMap

LinkedHashMap combines hash-based lookup with links between entries. Its default iteration order is insertion order:

Map<String, Integer> scores = new LinkedHashMap<>();
scores.put("Ana", 81);
scores.put("Bo", 74);
scores.put("Chen", 90);
// Iteration: Ana, Bo, Chen

Replacing the value of an existing key does not create a second entry. In insertion-order mode, the key retains its original position. A special constructor enables access-order mode:

Map<String, String> cache = new LinkedHashMap<>(16, 0.75f, true);

In access-order mode, successful access generally moves an entry toward the end. This supports a simple least-recently-used cache, although production caches may require synchronization, maximum-size enforcement, and more specialized libraries.

LinkedHashMap uses more memory than HashMap because each entry maintains link information. Its value is deterministic iteration, not faster lookup.

4. Sorted Maps with TreeMap

TreeMap stores keys in sorted order, using either their natural ordering or a supplied Comparator.

NavigableMap<Integer, String> rooms = new TreeMap<>();
rooms.put(101, "Networks");
rooms.put(205, "Java");
rooms.put(310, "Database");

Map.Entry<Integer, String> next = rooms.ceilingEntry(200);
NavigableMap<Integer, String> morning = rooms.headMap(250, true);

Tree operations such as get, put, and remove have O(log n) time under the balanced-tree model. The class also supports firstKey, lastKey, lowerKey, floorKey, ceilingKey, higherKey, and range views.

A crucial distinction is that a sorted map uses its comparator to decide key equivalence. If compare(a, b) == 0, the tree treats the keys as occupying the same map position, even if a.equals(b) is false. Therefore, comparator consistency with equals() is strongly recommended unless this behavior is deliberate and documented.

TreeMap permits one null value but normally cannot order a null key using natural ordering. A comparator that explicitly handles nulls can change that behavior, but null handling should be intentional.

5. EnumMap

EnumMap<K extends Enum<K>, V> is designed for keys from one enum type. It is compact, fast, and naturally iterates in enum declaration order.

enum Priority { LOW, NORMAL, HIGH, CRITICAL }

EnumMap<Priority, String> actions = new EnumMap<>(Priority.class);
actions.put(Priority.HIGH, "Notify supervisor");
actions.put(Priority.LOW, "Process later");

An EnumMap is preferable to a general-purpose map when the key domain is a single enum. It communicates the domain constraint in the type system and avoids string-based category errors.

6. Natural and External Ordering

6.1 Comparable

A class implements Comparable<T> when one ordering is its natural, default ordering:

public record Student(String id, String name, double average)
        implements Comparable<Student> {
    @Override
    public int compareTo(Student other) {
        return this.id.compareTo(other.id);
    }
}

The result of compareTo is negative, zero, or positive according to whether the receiver precedes, is equivalent in ordering to, or follows the argument. Code should test the sign, not expect exactly -1 or 1.

The ordering should be transitive and consistent. If a.compareTo(b) == 0, sorted collections may treat the objects as duplicates even when a.equals(b) is false. For value classes, consistency with equals() is usually the safest design.

6.2 Comparator

Comparator<T> supplies an ordering outside the class. It is ideal when users need several views of the same data.

Comparator<Student> byAverageDescending =
    Comparator.comparingDouble(Student::average)
              .reversed()
              .thenComparing(Student::name)
              .thenComparing(Student::id);

List<Student> ordered = new ArrayList<>(students);
ordered.sort(byAverageDescending);

The final tie-breaker is important. If a comparator compares only average, two students with the same average compare as zero. That may be correct for sorting, but it can cause one student to replace another in a TreeSet or TreeMap.

Useful factory methods include Comparator.comparing, comparingInt, comparingLong, comparingDouble, reversed, thenComparing, nullsFirst, and nullsLast.

7. Collection Algorithms

7.1 Sorting

Lists can be sorted in place:

students.sort(Comparator.comparing(Student::name));

If the original list must remain unchanged, copy it first or use a stream:

List<Student> sorted = students.stream()
    .sorted(byAverageDescending)
    .toList();

Stream.toList() returns an unmodifiable list in current Java APIs. It is not the same as Collectors.toList(), whose mutability is not guaranteed by the collector contract.

7.2 Searching

For an unsorted list, a sequential search generally examines elements from beginning to end and has O(n) worst-case time. List.contains and indexOf use equality.

Binary search requires a list sorted according to the same ordering used for the search:

List<String> names = new ArrayList<>(List.of("Ana", "Bo", "Chen"));
int position = Collections.binarySearch(names, "Bo");

With random access and a valid sorted order, binary search has O(log n) comparisons. If the precondition is violated, the result is meaningless. For linked lists, repeated positional access can make a binary-search strategy unsuitable in practice; a tree or another indexed structure may be better.

7.3 Filtering and grouping

Streams express selection and aggregation declaratively:

Map<String, List<Student>> byNameInitial = students.stream()
    .collect(Collectors.groupingBy(s -> s.name().substring(0, 1)));

List<Student> highPerformers = students.stream()
    .filter(s -> s.average() >= 70.0)
    .toList();

filter does not mutate its source. groupingBy normally creates a mutable map, while groupingByConcurrent is a specialized option for suitable concurrent workloads. Parallel streams should not be adopted automatically: task-splitting overhead, shared state, ordering requirements, and data size must be evaluated.

8. Immutable Collection Factories

Java provides concise factories:

List<String> modules = List.of("Java", "Python", "Databases");
Set<Integer> levels = Set.of(1, 2, 3);
Map<String, Integer> credits = Map.of("Java", 15, "Python", 15);

These collections reject structural modification and reject null elements or keys/values. Map.of supports a limited number of key-value pairs; Map.ofEntries supports larger declarations:

Map<String, Integer> marks = Map.ofEntries(
    Map.entry("A", 80),
    Map.entry("B", 74),
    Map.entry("C", 91)
);

List.copyOf, Set.copyOf, and Map.copyOf create unmodifiable copies. They are valuable at API boundaries because callers cannot modify the returned collection through its interface. “Unmodifiable” does not necessarily mean deeply immutable: if a collection contains mutable objects, those objects may still change.

When a mutable result is required, use an explicit copy:

List<String> editable = new ArrayList<>(List.of("Java", "Python"));

9. Applied Case: Course Registration Index

Background

This illustrative case models a diploma department that displays student registrations, searches students by identifier, and produces reports ordered by academic average.

Problem

The department needs fast identifier lookup, stable display order, and a report sorted by descending average and then name. It must also prevent accidental modification of a published report.

Analysis

A HashMap<StudentId, Student> is suitable for primary lookup because identifiers are immutable value objects. A LinkedHashMap is useful for a registration screen that should preserve entry order. A sorted report needs a Comparator, not a different map implementation. If the department later needs range queries by average or date, a TreeMap could index those ordered keys.

Approach and solution

Map<StudentId, Student> index = new HashMap<>();
index.put(new StudentId("D101"),
          new Student("D101", "Mina", 78.5));
index.put(new StudentId("D102"),
          new Student("D102", "Omar", 84.0));

Student found = index.get(new StudentId("D101"));

Comparator<Student> reportOrder =
    Comparator.comparingDouble(Student::average)
              .reversed()
              .thenComparing(Student::name)
              .thenComparing(Student::id);

List<Student> report = index.values().stream()
    .sorted(reportOrder)
    .toList();

The lookup succeeds because two StudentId objects containing the same identifier are equal and have the same hash code. The report is independent of the unspecified iteration order of HashMap. Its returned list cannot be structurally modified through ordinary list operations.

Outcome and learning points

The design separates responsibilities: the map provides identity lookup, the comparator provides presentation order, and the immutable result protects a published view. This separation makes future changes easier. For example, a registrar can add a name-based report without changing the Student class or lookup index.

10. Limitations, Safety, and Professional Practice

Collections are not automatically thread-safe. Concurrent modification of a HashMap by multiple threads can produce incorrect behavior. For shared mutable maps, consider ConcurrentHashMap, external synchronization, or confinement to one thread. Even concurrent collections do not make compound operations automatically atomic; use methods such as compute, merge, or putIfAbsent where appropriate.

Do not expose internal mutable collections directly from a class. Return an unmodifiable view or an immutable copy according to the required semantics. Validate external data before using it as a key, and avoid placing sensitive personal information unnecessarily into diagnostic output or logs.

Ordering also has governance implications. A comparator used for ranking students, employees, or customers should be documented and reviewed for fairness. If multiple records compare equally, tie-breaking must be explicit so that an apparently stable ranking does not silently discard entries in a sorted set or map.

Modern Java development increasingly combines records, pattern matching, streams, immutable factories, and static analysis. These features improve clarity but do not remove the need to understand equality, mutability, performance, and API contracts. AI-assisted code generation can suggest collection pipelines, but developers must test edge cases: empty inputs, duplicate keys, null values, comparator ties, mutable keys, and concurrent access.

Best-Practice Checklist

• Use HashMap for general key lookup when no order is required.
• Use LinkedHashMap when deterministic insertion or access order matters.
• Use TreeMap for sorted keys and range navigation.
• Use EnumMap for keys from one enum type.
• Make map keys immutable whenever possible.
• Override equals() and hashCode() together.
• Ensure comparator ordering is transitive and preferably consistent with equals().
• Add tie-breakers when distinct records must remain distinct in sorted collections.
• Sort before binary searching, using the same ordering.
• Use immutable factories at ownership boundaries, but remember shallow immutability.
• Choose concurrent collections deliberately rather than assuming ordinary collections are thread-safe.

Chapter Summary

Maps represent key-to-value associations and support identity-based retrieval. HashMap offers expected constant-time lookup without an ordering guarantee; LinkedHashMap adds predictable insertion or access order; TreeMap maintains sorted keys and provides logarithmic navigation; and EnumMap efficiently represents mappings whose keys belong to one enum type. Hash-based correctness depends on the equals()/hashCode() contract and on keys remaining stable after insertion. Comparable defines a class’s natural ordering, while Comparator supplies alternative orderings and tie-breaking rules. Sorting, sequential search, binary search, filtering, grouping, and immutable collection factories form a practical toolkit for professional Java programs. Good designs select collections according to required semantics, performance, mutability, and safety rather than habit.

Key Terms

Map: An object that associates keys with values.

Key: An object used to identify a mapping.

Value: The object associated with a key.

Hashing: Transforming an object into a hash code used to locate a table position.

Collision: A situation in which different keys produce the same bucket location or hash code.

HashMap: A general-purpose hash-based map with no iteration-order guarantee.

LinkedHashMap: A hash-based map that maintains a linked iteration order.

TreeMap: A sorted map implemented using ordered tree structures.

EnumMap: A specialized map whose keys belong to one enum type.

Equality contract: Rules governing consistency between equals() and hashCode().

Immutable key: A key whose equality-relevant state does not change while stored.

Comparable: An interface defining a type’s natural ordering.

Comparator: An object that defines an external ordering.

Natural ordering: The default ordering associated with a class.

Tie-breaker: A secondary comparison used when primary values are equal.

Binary search: A search requiring sorted data and repeatedly narrowing the search interval.

Filtering: Selecting elements that satisfy a predicate.

Unmodifiable collection: A collection that rejects structural modification through its interface.

Deep immutability: Immutability of a collection and the objects reachable through it.

Review Questions

Short Answer Questions

1. Why does HashMap not guarantee iteration order?
2. State the essential relationship between equals() and hashCode().
3. When is EnumMap preferable to HashMap?
4. What precondition must hold before applying binary search?
5. Why are immutable objects preferred as map keys?

Long Answer Questions

1. Compare HashMap, LinkedHashMap, and TreeMap in terms of organization, performance, and appropriate use.
2. Explain the equals()/hashCode() contract and illustrate how violating it can break map lookup.
3. Discuss Comparable and Comparator, including consistency, tie-breaking, and sorted collections.
4. Explain immutable collection factories and distinguish unmodifiable collections from deeply immutable structures.
5. Describe how streams can be used to sort, filter, and group domain objects, including relevant limitations.

Analytical / Application Questions

1. Design a collection architecture for a library system requiring ISBN lookup, insertion-order display, and title-sorted reports. Justify each collection choice.
2. A TreeSet appears to lose employees who have the same salary but different identifiers. Diagnose the likely comparator problem and propose a correction.
3. A program inserts a mutable object as a HashMap key and later changes one of its fields. Explain the resulting lookup failure and redesign the key type.

Multiple Choice Questions with Answers

Question 1

Which map implementation preserves insertion order while retaining hash-based lookup?

A. HashMap

B. LinkedHashMap

C. TreeMap

D. EnumMap

Correct Answer: B. LinkedHashMap

Question 2

If two objects are equal according to equals(), what must be true?

A. They must have different hash codes

B. They must have the same hash code

C. They must be stored in different buckets

D. They must be the same object reference

Correct Answer: B. They must have the same hash code

Question 3

Which collection is specialized for keys from one enum type?

A. TreeMap

B. IdentityHashMap

C. EnumMap

D. WeakHashMap

Correct Answer: C. EnumMap

Question 4

What is required before using binary search on a list?

A. The list must contain no duplicates

B. The list must be sorted according to the search ordering

C. The list must be a LinkedList

D. Every element must be mutable

Correct Answer: B. The list must be sorted according to the search ordering

Question 5

Which interface defines a class’s natural ordering?

A. Iterable

B. Comparator

C. Comparable

D. Collection

Correct Answer: C. Comparable

Question 6

What may happen in a TreeMap when two keys compare as zero?

A. Both keys are always stored separately

B. The keys are treated as occupying the same sorted position

C. The map changes into a HashMap

D. An automatic null key is added

Correct Answer: B. The keys are treated as occupying the same sorted position

Question 7

Which statement about List.of() is correct?

A. It creates a list that accepts null elements

B. It creates an unmodifiable list

C. It always creates a LinkedList

D. It sorts the supplied elements

Correct Answer: B. It creates an unmodifiable list

Question 8

Which method is most suitable for adding a value to an existing numeric mapping?

A. merge

B. clone

C. notify

D. finalize

Correct Answer: A. merge

Question 9

Why can a mutable key cause a HashMap lookup to fail after mutation?

A. The map automatically deletes all values

B. The key may now produce a different hash code or equality result

C. HashMap permits only immutable values

D. The map converts the key to an enum

Correct Answer: B. The key may now produce a different hash code or equality result

Question 10

Which comparator construction sorts students by average descending and then by name?

A. Comparator.comparingDouble(Student::average).reversed().thenComparing(Student::name)

B. Comparator.comparing(Student::name).reversed().thenComparingDouble(Student::average)

C. Comparator.reverseOrder(Student::average)

D. Comparator.equals(Student::average, Student::name)

Correct Answer: A. Comparator.comparingDouble(Student::average).reversed().thenComparing(Student::name)