Java Programming

Collection Ordering, Hashing, Iterators and Object Contracts

PGCP-BDA

Comparable

Comparable defines a type's natural ordering through compareTo and must be consistent, transitive and preferably compatible with equals.

Comparator

Comparator is an external ordering strategy that can compose keys, reverse order and define multiple orderings without changing the element class.

sorting

Java sorting orders arrays or collections according to natural Comparable order or an explicit Comparator and the comparison contract must be consistent.

hashCode and equals

Equal Java objects must return equal hash codes; hash collections use the hash to choose a bucket and equals to confirm key identity.

hash table

A structure that maps a key’s hash to a bucket and then uses equality to locate the matching key within that bucket.

ordered collection

A collection with a defined iteration order, which may be insertion order, natural order or comparator order.

iterator contract

An iterator traverses elements through hasNext and next; remove is optional and structural changes may invalidate traversal.

fail-fast iteration

Iteration that detects unsupported structural modification on a best-effort basis and throws ConcurrentModificationException.

Object methods

Methods inherited from Object, including equals, hashCode, toString, getClass, clone, finalize and thread-monitor methods.

Implementing equals and hashCode

Equal objects must have equal hash codes. Unequal objects may share a hash code; collisions are expected and resolved by hash-based collections.

final class StudentId {
    private final int value;
    StudentId(int value) { this.value = value; }

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

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

Use the same equality-defining fields in both methods. A record generates component-based equals, hashCode and toString, making it suitable for transparent data values:

record StudentId(int value) {}

Inheritance complicates value equality because adding fields can break symmetry between base and subtype objects. Immutable value classes are often final or records.

Hashing and key correctness

A hash structure first uses hashCode to find a region and then equals to distinguish candidates. Equal objects must have equal hash codes. Unequal objects may collide.

record ProductCode(String value) {}

Map<ProductCode, Integer> stock = new HashMap<>();
stock.put(new ProductCode("P10"), 8);
System.out.println(stock.get(new ProductCode("P10"))); // 8

Records derive value equality and matching hashes from components. For ordinary key classes, override both methods using the same stable fields. A mutable key can become unreachable through normal lookup after its hash-relevant state changes.

HashMap iteration order must never be treated as insertion or sorted order, even if a small example appears stable.

The Object class contract

Every Java object inherits methods from Object, including equals, hashCode, toString and getClass. The default equals behaves like identity unless a class overrides it.

Value equality should represent the domain. Two student identifiers with the same number may be equal even if created separately. Two mutable service objects may intentionally retain identity equality. The choice must remain consistent with the class's purpose.

The equals contract requires:

  • reflexive: x.equals(x) is true;
  • symmetric: x.equals(y) agrees with y.equals(x);
  • transitive: if x equals y and y equals z, then x equals z;
  • consistent: repeated calls agree while relevant state is unchanged;
  • non-null: x.equals(null) is false.

Comparable and natural ordering

Comparable<T> defines a type's natural ordering:

record Student(int rollNumber, String name)
        implements Comparable<Student> {
    @Override
    public int compareTo(Student other) {
        return Integer.compare(rollNumber, other.rollNumber);
    }
}

A comparison returns a negative value, zero or a positive value. Do not subtract numeric fields because overflow can reverse the result. A natural ordering should be antisymmetric, transitive and consistent in sign. Ideally, comparison zero agrees with equals, especially when values enter sorted sets or maps.

Natural order should represent the most obvious stable ordering for the type. A class need not implement Comparable if no single order is natural.

Iteration and modification

The enhanced for loop uses an iterator. Many ordinary collection iterators are fail-fast: unsupported structural modification outside the iterator may trigger ConcurrentModificationException.

Iterator<String> iterator = names.iterator();
while (iterator.hasNext()) {
    if (iterator.next().isBlank()) {
        iterator.remove();
    }
}

Fail-fast behaviour is a bug-detection aid, not a concurrency guarantee. removeIf expresses common filtering more directly. Concurrent collections define their own iterator consistency rules.

ListIterator supports bidirectional traversal and controlled addition or replacement. Index-based removal in a forward loop can skip shifted elements unless the index is adjusted.

Comparator strategies

Comparator<T> defines an external ordering without changing the class:

Comparator<Student> byNameThenRoll =
        Comparator.comparing(Student::name)
                  .thenComparingInt(Student::rollNumber);

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

Useful methods include reversed, thenComparing, naturalOrder, nullsFirst and nullsLast. A comparator used by TreeSet or TreeMap must remain stable while elements or keys are stored. If comparison depends on a mutable field, changing it can violate tree placement.

A PriorityQueue uses a comparator to keep its head as the least element, but iteration over the queue is not sorted. Repeated poll() operations reveal priority order.

Set implementations

HashSet offers hash-based membership without an iteration-order guarantee. It uses equals and hashCode, so elements must obey their contract and should not mutate equality-defining state while stored.

LinkedHashSet adds predictable encounter order, normally insertion order, while preserving hash-based uniqueness. It is useful when deduplication must retain the first-seen sequence.

TreeSet maintains sorted order with a balanced tree. Its add, remove and lookup operations are typically O(log n). It uses natural ordering or a supplied Comparator. A comparison result of zero means the set considers the values equivalent for its operations, even if equals says otherwise.

Set<String> codes = new LinkedHashSet<>();
codes.add("B");
codes.add("A");
codes.add("B");
System.out.println(codes); // [B, A]

Mutable hash keys

A hash collection uses a key's hash code to choose a bucket. If an equality-defining field changes while the key is stored, a later lookup may search a different bucket:

Map<Person, String> roles = new HashMap<>();
Person key = new Person("Asha");
roles.put(key, "admin");
key.setName("Meera"); // dangerous if name defines hashCode

The entry still exists internally but may no longer be found by the mutated key. Prefer immutable keys. If mutation is unavoidable, remove the key before changing equality state and insert it again afterward.

Map implementations

HashMap supplies expected constant-time basic operations with sound hashing. It permits one null key and multiple null values, but it promises no iteration order.

LinkedHashMap maintains a linked encounter order. Its default is insertion order; an access-order configuration can support least-recently-used cache logic when combined with controlled eviction.

TreeMap maintains keys in natural or comparator order and supports range views such as subMap, headMap and tailMap. Comparison equality determines key equivalence.

Hashtable is a legacy synchronized map that rejects null keys and values. ConcurrentHashMap also rejects nulls, but provides concurrency-oriented operations and better parallel access rather than simply copying Hashtable's locking model.

Worked collection trace

List<Integer> numbers = new ArrayList<>();
numbers.add(3);
numbers.add(1);
numbers.add(3);
numbers.sort(Integer::compareTo);
System.out.println(numbers);

List permits duplicates and retains all three elements. The comparator orders integers ascending, so the result is [1, 3, 3]. If the values were placed in a TreeSet instead, comparison equality would eliminate the duplicate and iteration would produce [1, 3].

Worked trace

String a = "42";
String b = new String("42");
Integer x = Integer.valueOf(a);
Integer y = Integer.valueOf(b);

System.out.println(a == b);
System.out.println(a.equals(b));
System.out.println(x.equals(y));

a == b is false because the explicit constructor creates a separate String object. a.equals(b) is true because both contain the same characters. Parsing or value conversion produces numerically equal Integer values, so x.equals(y) is true. The analysis does not depend on whether a wrapper cache reuses an instance because value comparison is used.

Important String operations

String indexes begin at zero. Common methods include:

OperationMeaning
length()Number of UTF-16 code units
charAt(i)Character code unit at index i
substring(begin, end)Begin inclusive, end exclusive
indexOf(value)First position or -1
contains(value)Whether a character sequence occurs
replace(a, b)Literal replacement
replaceAll(regex, value)Regular-expression replacement
trim()Removes leading and trailing characters up to U+0020
strip()Removes Unicode-aware surrounding whitespace
String language = "Java";
System.out.println(language.substring(1, 3)); // av

An invalid index causes StringIndexOutOfBoundsException. The exclusive end convention makes the substring length equal to end - begin.

Parsing and conversion

Parsing converts text to a primitive value:

int count = Integer.parseInt("125");
double rate = Double.parseDouble("7.5");

Integer.valueOf("125") returns an Integer object. Invalid numeric syntax causes NumberFormatException. Leading or trailing whitespace is not universally ignored; normalize deliberately when the input format permits it.

Radix-aware methods parse other bases:

int binary = Integer.parseInt("1010", 2); // 10
String hex = Integer.toHexString(255);     // ff

Parsing user input should report the invalid value and expected format at the application boundary instead of allowing a low-level exception to become an unclear user message.

Designing toString

toString should provide a concise, useful representation for logs and diagnostics:

@Override
public String toString() {
    return "Invoice{id=" + id + ", status=" + status + "}";
}

Do not expose passwords, tokens, personal data or full payment details. Do not assume the output is a stable machine-readable serialization unless an explicit documented format provides that guarantee.

Continue learning

Related notes

Big Data Characteristics, Adoption, Sources and Data Curation
Big Data Technologies
Java Platform, JVM, JDK, Types, Operators and Control Flow
Java Programming
Linux Evolution, GNU, GPL and System Architecture
Linux Programming and Cloud Computing
Python Syntax, Types, Input, Operators and Control Flow
Python and R Programming

Put this topic into timed practice

Open mock tests when you want full-exam pacing, or keep drilling in practice mode.

Mock testsView plans