Java and Object-Oriented Programming FoundationLesson 69 / 115

Algorithms and Problem Solving with Java

Hashing and Fast Lookup

ReadingPreview

You are viewing a free preview lesson.

Lesson Overview

আগের lessons-এ আমরা searching-এর কয়েকটি approach দেখেছি।

Linear Search:

O(n)

Binary Search:

O(log n)

কিন্তু Binary Search-এর জন্য data sorted হতে হয়।

এখন আমরা এমন একটি technique দেখব যেখানে exact lookup সাধারণত আরও দ্রুত হতে পারে:

Hashing

Java-তে hashing heavily used হয়:

HashMap
HashSet

Typical operations যেমন:

map.get(key)
set.contains(value)

সাধারণভাবে average case-এ:

O(1)

হতে পারে।

কিন্তু এর পেছনে important concepts আছে:

  • Hash function
  • Hash code
  • Bucket
  • Collision
  • Equality
  • Resizing
  • Mutable keys

এই lesson-এ আমরা শিখব:

  • What hashing means
  • Hash tables
  • Hash functions
  • Buckets
  • Collisions
  • Average O(1) lookup
  • Why worst-case behavior differs
  • HashMap
  • HashSet
  • How HashSet uses hashing
  • equals() and hashCode()
  • The equality/hash contract
  • Mutable keys
  • Load factor intuition
  • Resizing intuition
  • Duplicate detection
  • Counting frequencies
  • Fast lookup by key
  • Hashing vs Linear Search
  • Hashing vs Binary Search
  • When hashing is a good choice

The Lookup Problem

Suppose we have one million course codes:

JAVA
BACKEND
SYSTEM-DESIGN
ALGORITHMS
...

We repeatedly need to answer:

Does course code "JAVA" exist?

If data is in a List, we may need to scan:

O(n)

If data is sorted, Binary Search can reduce that to:

O(log n)

But hashing gives us another strategy।

Instead of searching through values one by one, we compute where the value should approximately live।

What Is Hashing?

Hashing converts a value into a numeric representation called a:

hash code

Conceptually:

"JAVA"
↓
hash function
↓
some integer

That integer helps determine where the value should be stored inside a hash table।

Simplified Example

Suppose a fake hash function produces:

JAVA    → 42
BACKEND → 17
OOP     → 35

And suppose our table has:

10 buckets

We might map using:

bucket = hash % 10

Then:

JAVA
42 % 10
→ bucket 2

BACKEND
17 % 10
→ bucket 7

OOP
35 % 10
→ bucket 5

Now when searching for:

JAVA

we calculate its hash again and go directly toward:

bucket 2

instead of scanning every stored value।

Important: Real HashMap Is More Sophisticated

Java's actual HashMap implementation is more sophisticated than:

hash % bucketCount

This simplified model is only for understanding the concept।

Do not depend on internal bucket calculations in application code।

What Is a Hash Table?

A hash table stores values in an internal structure organized into:

buckets

Conceptually:

Bucket 0 → ...
Bucket 1 → ...
Bucket 2 → JAVA
Bucket 3 → ...
Bucket 4 → ...

The hash code helps determine which bucket should be inspected।

Why Lookup Can Be Fast

Without hashing:

Search every value

With hashing:

Calculate location
Go near the expected value
Check a small number of candidates

Under good conditions, this gives average:

O(1)

lookup।

O(1) Is Average, Not Magic

When we say:

HashMap.get()
→ average O(1)

we do not mean:

Exactly one CPU instruction

or:

Guaranteed constant work in every possible case

We mean that with:

Good hash distribution
Reasonable table size
Normal collision behavior

lookup does not normally grow proportionally with the total number of elements।

What Is a Hash Function?

A hash function transforms some input into an integer-like hash value।

For Java objects, the relevant method is:

hashCode()

Example:

String code =
        "JAVA";

int hash =
        code.hashCode();

Same Value, Same Hash During Normal Use

For a stable object's state, repeated calls should consistently return the same hash code during that execution context unless equality-relevant state changes।

Example:

String value =
        "JAVA";

System.out.println(
        value.hashCode()
);

System.out.println(
        value.hashCode()
);

You should get the same result during that normal object state।

Hash Code Is Not an ID

Do not treat:

hashCode()

as:

Database ID
Unique identifier
Security token
Persistent identifier

Different objects can have the same hash code।

This leads us to:

collision

What Is a Collision?

A collision happens when different values map to the same hash location or hash code region।

Simplified example:

JAVA    → bucket 3
BACKEND → bucket 3

Both need to be stored in the same bucket area।

Collisions Are Normal

A common beginner mistake is:

Collision means hashing failed.

Not true।

Collisions are expected and hash tables are designed to handle them।

The goal is not:

Never collide

The goal is:

Distribute values well enough
that collisions remain manageable.

Why Collisions Must Exist

Java hash codes use:

int

An int has a finite number of possible values।

But there can be far more possible objects than possible integer hash codes।

Therefore different objects must sometimes share hash codes।

This is unavoidable।

Hashing Still Needs Equality

Suppose bucket 3 contains:

JAVA
BACKEND

When searching for:

JAVA

the hash table cannot simply say:

Anything in bucket 3 is JAVA.

It must compare actual keys।

That is where:

equals()

matters।

Hashing Uses Two Ideas

Conceptually:

hashCode()
→ find likely bucket

equals()
→ identify the actual matching key

Both are important।

HashMap

A HashMap stores:

key → value

Example:

Map<String, String> courses =
        new HashMap<>();

courses.put(
        "JAVA",
        "Java Foundation"
);

courses.put(
        "BACKEND",
        "Backend Development"
);

Lookup:

String course =
        courses.get(
                "JAVA"
        );

Typical HashMap Operations

Common operations:

put(...)
get(...)
containsKey(...)
remove(...)

Typical average complexity:

O(1)

for hash-based key access।

Example

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

public class Main {

    public static void main(String[] args) {
        Map<String, String> courses =
                new HashMap<>();

        courses.put(
                "JAVA",
                "Java Foundation"
        );

        courses.put(
                "BACKEND",
                "Backend Development"
        );

        System.out.println(
                courses.get(
                        "JAVA"
                )
        );

        System.out.println(
                courses.containsKey(
                        "BACKEND"
                )
        );
    }
}

Output:

Java Foundation
true

Why a Map Is Better Than Repeated List Search

Suppose:

List<Course> courses

and every request needs:

find Course by code

A list may require:

O(n)

linear scanning।

A HashMap:

Map<String, Course>

can provide expected average:

O(1)

lookup by code।

Example Domain Model

record Course(
        String code,
        String title
) {
}

Map:

Map<String, Course> coursesByCode =
        new HashMap<>();

Insert:

Course course =
        new Course(
                "JAVA",
                "Java Foundation"
        );

coursesByCode.put(
        course.code(),
        course
);

Lookup:

Course found =
        coursesByCode.get(
                "JAVA"
        );

HashSet

A HashSet stores unique values।

Example:

Set<String> courseCodes =
        new HashSet<>();

Add:

courseCodes.add(
        "JAVA"
);

Check membership:

courseCodes.contains(
        "JAVA"
);

Typical average:

O(1)

HashSet and Duplicates

Set<String> codes =
        new HashSet<>();

System.out.println(
        codes.add(
                "JAVA"
        )
);

System.out.println(
        codes.add(
                "JAVA"
        )
);

Output:

true
false

The second insertion is rejected because the set already contains an equal value।

HashSet Uses Hashing for Membership

Conceptually:

hashCode()
↓
find bucket
↓
equals()
↓
already present or not?

This allows expected fast membership checking।

Duplicate Detection

Suppose:

String[] emails

We want to know whether any email appears twice।

Naive approach:

Compare every pair

Worst-case:

O(n²)

HashSet Approach

static boolean hasDuplicate(
        String[] emails
) {
    Set<String> seen =
            new HashSet<>();

    for (
            String email
            : emails
    ) {
        if (
                !seen.add(
                        email
                )
        ) {
            return true;
        }
    }

    return false;
}

Expected time:

O(n)

Extra space:

O(n)

Why add() Is Useful Here

Set.add() returns:

true

when the value was newly added।

It returns:

false

when an equal value was already present।

So:

if (
        !seen.add(
                email
        )
)

means:

We found a duplicate.

Frequency Counting with HashMap

Suppose scores are:

80
90
80
70
90
80

We want:

80 → 3
90 → 2
70 → 1

A HashMap is ideal।

Frequency Counter

static Map<Integer, Integer> frequencies(
        int[] values
) {
    Map<Integer, Integer> counts =
            new HashMap<>();

    for (
            int value
            : values
    ) {
        int current =
                counts.getOrDefault(
                        value,
                        0
                );

        counts.put(
                value,
                current + 1
        );
    }

    return counts;
}

getOrDefault()

This:

counts.getOrDefault(
        value,
        0
);

means:

If key exists
→ return current value

Otherwise
→ return 0

Very useful for counting।

Example

Input:

[80, 90, 80]

First 80:

missing
→ default 0
→ store 1

Then 90:

missing
→ store 1

Next 80:

existing count 1
→ store 2

merge() for Frequency Counting

Java also provides:

Map.merge(...)

A concise frequency counter:

static Map<Integer, Integer> frequencies(
        int[] values
) {
    Map<Integer, Integer> counts =
            new HashMap<>();

    for (
            int value
            : values
    ) {
        counts.merge(
                value,
                1,
                Integer::sum
        );
    }

    return counts;
}

We'll understand method references more deeply in Modern Java।

For now, know that:

Integer::sum

combines the old count and new 1।

Hashing Custom Objects

Suppose:

final class CourseCode {

    private final String value;

    CourseCode(
            String value
    ) {
        this.value =
                value;
    }
}

Now we want:

Set<CourseCode>

to treat two logically identical codes as duplicates।

Example:

new CourseCode(
        "JAVA"
)

new CourseCode(
        "JAVA"
)

Should these be considered the same?

Usually yes।

Then we need meaningful:

equals()
hashCode()

Identity vs Logical Equality

Without overriding equals(), ordinary classes inherit identity-based behavior from Object।

That means two separate objects may not compare equal even if they hold the same data।

Example conceptually:

CourseCode("JAVA")
CourseCode("JAVA")

Different objects।

But domain-wise:

same course code

So value objects often require logical equality।

Proper Value Object Example

import java.util.Objects;

final class CourseCode {

    private final String value;

    CourseCode(
            String value
    ) {
        this.value =
                Objects.requireNonNull(
                        value
                );
    }

    String value() {
        return value;
    }

    @Override
    public boolean equals(
            Object other
    ) {
        if (
                this == other
        ) {
            return true;
        }

        if (
                !(other instanceof CourseCode that)
        ) {
            return false;
        }

        return value.equals(
                that.value
        );
    }

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

Equality and Hashing Contract

The most important rule:

If two objects are equal according to equals(),
they must return the same hashCode().

Formally:

a.equals(
        b
)

being true requires:

a.hashCode()
==
b.hashCode()

Reverse Is Not Required

This is important।

Same hash code does not require equality।

Possible:

a.hashCode() == b.hashCode()

but:

a.equals(b) == false

That is simply a collision।

Correct Relationship

Required:

equals true
→ same hashCode

Not required:

same hashCode
→ equals true

What Happens If Contract Is Broken?

Suppose two objects are logically equal:

first.equals(
        second
)

returns:

true

but they produce different hash codes।

A HashSet or HashMap may place them in different bucket regions।

Then operations such as:

contains
get
remove

can behave incorrectly relative to your logical equality expectation।

Example Broken Class

Bad:

final class CourseCode {

    private final String value;

    CourseCode(
            String value
    ) {
        this.value =
                value;
    }

    @Override
    public boolean equals(
            Object other
    ) {
        if (
                !(other instanceof CourseCode that)
        ) {
            return false;
        }

        return value.equals(
                that.value
        );
    }
}

It overrides:

equals()

but not:

hashCode()

This is dangerous for hash-based collections।

Rule of Thumb

If you override:

equals()

you should normally also override:

hashCode()

using the same equality-relevant fields।

Records Make Value Equality Easier

Java records automatically provide:

equals()
hashCode()
toString()

based on record components।

Example:

record CourseCode(
        String value
) {
}

Then:

new CourseCode(
        "JAVA"
)

and another:

new CourseCode(
        "JAVA"
)

compare equal automatically।

Their hash codes are also consistent with that equality।

Example with HashSet and Record

Set<CourseCode> codes =
        new HashSet<>();

codes.add(
        new CourseCode(
                "JAVA"
        )
);

boolean found =
        codes.contains(
                new CourseCode(
                        "JAVA"
                )
);

Result:

true

because record equality is value-based।

Equality Fields Must Match Hash Fields

Suppose equality uses:

code

only।

Then hashCode should also be derived consistently from:

code

Do not use:

code in equals
but title in hashCode

That can violate the contract।

Objects.hash()

A common implementation:

@Override
public int hashCode() {
    return Objects.hash(
            code,
            title
    );
}

If equals() compares both:

code
title

this can be appropriate।

For a single field, direct hashing is also fine:

return value.hashCode();

Mutable Keys

This is one of the most important practical hazards in hashing।

Suppose:

class UserKey {

    private String email;

    // equals and hashCode use email
}

Insert:

map.put(
        key,
        user
);

Then mutate:

key.setEmail(
        "new@example.com"
);

Now the object's hash code may change।

Why Is That Dangerous?

The object was originally stored according to its old hash。

But lookup now computes:

new hash

The map does not automatically move the entry to a new bucket when you mutate the key object।

Result:

map.get(key)

may fail unexpectedly।

Hash Keys Should Be Stable

A strong rule:

Fields used in equals/hashCode
should generally not change
while the object is used as a hash key.

Immutable key types are ideal।

Examples:

String
Integer
Long
records with immutable components
immutable value objects

Example Good Key

record CourseCode(
        String value
) {
}

Assuming value itself is immutable, the key is stable।

HashSet Has the Same Mutation Problem

Suppose a mutable object is inside:

HashSet<User>

and you change a field used by:

equals()
hashCode()

Then:

set.contains(
        user
)

can behave unexpectedly।

So the rule applies to both:

HashMap keys
HashSet elements

Load Factor Intuition

A hash table has finite bucket capacity at any moment।

As more values are added, buckets become more crowded।

Too much crowding causes:

more collisions
more comparisons
slower lookup

Hash tables therefore monitor how full they become।

What Is Load Factor?

Conceptually:

load factor
≈
number of stored entries / number of buckets

When the structure becomes sufficiently full, it may resize।

You do not need to memorize exact implementation constants here।

The important idea:

Hash tables trade memory for fast access.

Resizing

When a HashMap grows beyond an internal threshold, it may allocate a larger internal table and redistribute entries।

This operation can be relatively expensive।

But it does not happen on every insertion।

Therefore put() is commonly described as:

average/amortized O(1)

under normal conditions।

Amortized Cost Intuition

Suppose most insertions are cheap:

cheap
cheap
cheap
cheap
expensive resize
cheap
cheap
cheap
...

The occasional expensive operation is spread across many cheap operations।

That is:

amortized analysis

We saw a similar idea with dynamic arrays such as ArrayList and ArrayDeque।

Initial Capacity

HashMap provides constructors that can accept an initial capacity।

Example:

Map<String, Course> courses =
        new HashMap<>(
                1_000
        );

For known large workloads, an appropriate initial capacity can reduce resizing।

But do not guess huge capacities without reason।

Memory also has a cost।

Do Not Prematurely Tune HashMap

Start with:

new HashMap<>()

unless you have:

Known data volume
Measured allocation pressure
Performance evidence

Correct data-structure choice matters more than premature internal tuning।

Collision Handling in Modern Java

Conceptually, a bucket may contain multiple entries।

Java's HashMap can manage collision-heavy buckets using internal structures that may evolve beyond a simple linear chain under certain conditions।

You do not need to depend on those details।

The important idea is:

Collisions increase work,
but HashMap has mechanisms to manage them.

Worst-Case Complexity

It is incorrect to say:

HashMap is guaranteed O(1).

Better:

Average expected lookup is O(1).

Worst-case behavior can degrade depending on:

Hash distribution
Collisions
Implementation details
Adversarial inputs

Modern Java includes mechanisms that improve collision-heavy behavior in some cases, but O(1) is still not an unconditional guarantee।

Good Hash Distribution

A useful hash function tries to spread common unequal values across the available hash space।

Bad conceptual hash:

@Override
public int hashCode() {
    return 1;
}

This technically satisfies:

equal objects have equal hash code

But every object collides।

Constant Hash Code

Suppose every CourseCode returns:

1

Then all keys land in the same collision region।

Lookup starts resembling:

search through many candidates

instead of efficient bucket selection।

So the contract alone is not enough।

We also want:

good distribution

for performance।

String.hashCode()

Java's String already provides a suitable hashCode() implementation for normal use।

You normally do not create your own string hashing logic।

Example:

Map<String, Course>

is extremely common and appropriate।

HashMap Allows One Null Key

Java's HashMap permits a null key and null values।

Example:

map.put(
        null,
        "value"
);

But whether you should use null as a domain key is another question।

Usually strong domain models avoid unclear null keys।

HashSet and Null

HashSet can also store a null element because of its underlying hash-based behavior।

Again, API capability does not mean:

null is good domain design.

Prefer explicit valid values where possible।

containsKey() vs get() == null

Suppose:

map.put(
        "JAVA",
        null
);

Then:

map.get(
        "JAVA"
)

returns:

null

But so does:

map.get(
        "UNKNOWN"
)

Therefore:

get(key) == null

cannot always distinguish:

missing key

from:

present key mapped to null

Use:

containsKey(
        key
)

when that distinction matters।

Stronger Design: Avoid Null Values

Often an even clearer design is:

Do not store null values in the map.

Then:

get(key) == null

can cleanly mean:

not found

But this is an application contract, not a HashMap requirement।

Frequency Counting Example

Let's build a complete example।

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

public class Main {

    public static void main(String[] args) {
        String[] courseCodes = {
                "JAVA",
                "BACKEND",
                "JAVA",
                "ALGORITHMS",
                "JAVA",
                "BACKEND"
        };

        Map<String, Integer> counts =
                count(
                        courseCodes
                );

        System.out.println(
                counts
        );
    }

    static Map<String, Integer> count(
            String[] values
    ) {
        Map<String, Integer> counts =
                new HashMap<>();

        for (
                String value
                : values
        ) {
            counts.merge(
                    value,
                    1,
                    Integer::sum
            );
        }

        return counts;
    }
}

Conceptual result:

JAVA → 3
BACKEND → 2
ALGORITHMS → 1

Do not depend on HashMap iteration order unless you explicitly use a map implementation with ordering guarantees।

HashMap Does Not Guarantee Insertion Order

This:

HashMap<String, Integer>

does not promise:

iteration in insertion order

If insertion order matters, a different implementation such as:

LinkedHashMap

may be appropriate।

If sorted-key order matters:

TreeMap

may be appropriate।

Different map types optimize different behavior।

HashSet Does Not Guarantee Insertion Order

Likewise:

HashSet

does not guarantee insertion-order iteration।

If you need:

uniqueness + insertion order

consider:

LinkedHashSet

This lesson focuses on hashing and lookup, not ordered variants।

Hashing vs Linear Search

Suppose we perform one search on:

20 unsorted values

A linear scan may be entirely sufficient।

No need to build:

HashSet

just for one tiny lookup।

Repeated Membership Checks

Suppose:

1 million allowed IDs

and every request checks:

Is this ID allowed?

A HashSet can be much more appropriate than repeated:

O(n)

list scanning।

Hashing vs Binary Search

Binary Search:

O(log n)

requires:

sorted data

Hash lookup:

average O(1)

does not require sorted ordering।

But hashing uses additional memory and does not naturally provide sorted traversal।

When Binary Search Is Better

If data must already remain:

sorted

and memory overhead matters, Binary Search can be an excellent choice।

Also, Binary Search supports useful ordered operations such as:

insertion points
boundaries
ranges

Hashing does not naturally provide those।

When Hashing Is Better

Hashing is often ideal when the main questions are:

Does this exact key exist?

What value belongs to this exact key?

and ordering is not important।

Hashing vs Tree-Based Structures

A structure such as:

TreeMap

typically provides:

O(log n)

operations and sorted key ordering।

A HashMap typically provides:

average O(1)

key operations but no sorted order।

Tradeoff:

HashMap
→ faster expected exact lookup

TreeMap
→ ordered keys and range-style operations

We do not need to deeply study balanced trees in this course।

Practical Example — Enrollment Lookup

Suppose:

record Enrollment(
        long id,
        String learner
) {
}

If application constantly does:

find enrollment by ID

use:

Map<Long, Enrollment>

Example

Map<Long, Enrollment> enrollmentsById =
        new HashMap<>();

Enrollment enrollment =
        new Enrollment(
                1001,
                "Sakib"
        );

enrollmentsById.put(
        enrollment.id(),
        enrollment
);

Enrollment found =
        enrollmentsById.get(
                1001L
        );

This directly models:

ID → Enrollment

Indexing Concept

A HashMap can be thought of as an in-memory index।

Suppose we have:

List<Learner> learners

for ordered iteration।

We may additionally build:

Map<Long, Learner> learnersById

for fast lookup।

This duplicates some structural information but optimizes another access pattern।

Multiple Indexes

Real systems often maintain multiple lookup structures।

Example:

Learner by ID
Learner by email
Learners in registration order

Conceptually:

Map<Long, Learner> byId;
Map<String, Learner> byEmail;
List<Learner> orderedLearners;

But multiple indexes create consistency responsibilities।

If you add or remove data, all relevant indexes must stay synchronized।

Data Structure Choice Has Maintenance Cost

Faster lookup may mean:

More memory
More code
More consistency work

This is an important engineering tradeoff।

Hash-Based Join Intuition

Suppose we have:

Learners
Enrollments

and need to match many enrollment learner IDs to learners।

Naive nested loop:

for each enrollment
    scan all learners

could become:

O(n × m)

Build a Map First

Instead:

Build learnerById map
→ O(n)

For each enrollment:
    lookup learner
→ average O(1)

Total expected work:

O(n + m)

rather than:

O(n × m)

This pattern is extremely important।

Example

static Map<Long, Learner> indexById(
        List<Learner> learners
) {
    Map<Long, Learner> byId =
            new HashMap<>();

    for (
            Learner learner
            : learners
    ) {
        byId.put(
                learner.id(),
                learner
        );
    }

    return byId;
}

Then:

Learner learner =
        byId.get(
                enrollment.learnerId()
        );

Preprocessing Again

Remember sorting before repeated Binary Search?

Hash indexing is another form of:

preprocessing

We spend:

O(n)

time and:

O(n)

space to build a hash table।

Then future lookups become expected:

O(1)

Common Mistake 1 — Hash Code Means Unique

False।

Different objects can have the same hash code।

Always rely on:

hashCode + equals

together।

Common Mistake 2 — Override equals() Only

If a type is used in hash-based collections and you override equals(), you should also implement consistent hashCode()।

Common Mistake 3 — Equal Objects with Different Hash Codes

This breaks the hash contract and can make lookup behavior incorrect।

Required:

equals true
→ same hash code

Common Mistake 4 — Same Hash Means Equal

False।

Same hash may simply be a collision।

Common Mistake 5 — Mutable HashMap Key

Do not mutate equality/hash-relevant key fields after insertion।

Immutable keys are much safer।

Common Mistake 6 — Expecting HashMap Ordering

Do not assume:

Insertion order
Sorted order

from HashMap।

Use an ordered implementation when order is actually a requirement।

Common Mistake 7 — Calling Hash Lookup Guaranteed O(1)

Say:

average expected O(1)

not:

guaranteed O(1)

Common Mistake 8 — Constant hashCode()

Technically legal for equality correctness but disastrous for performance because every value collides։

Common Mistake 9 — HashSet for Ordered Range Queries

If you need questions such as:

All values between 100 and 200

a hash table is not naturally ordered for that query।

A sorted structure may fit better।

Common Mistake 10 — Building a HashSet for One Tiny Search

For:

5 values
one lookup

a simple loop may be clearer than constructing an additional hash structure।

Always consider scale and frequency।

Common Mistake 11 — get() == null Always Means Missing

Not if the map allows stored null values।

Use containsKey() when presence and null-value distinction matters।

Common Mistake 12 — Duplicate Indexes Without Consistency

If you maintain:

List
Map by ID
Map by email

all must represent the same underlying logical data।

Updating only one structure creates bugs।

Practical Example — Unique Course Codes

import java.util.HashSet;
import java.util.Set;

public class Main {

    public static void main(String[] args) {
        String[] codes = {
                "JAVA",
                "BACKEND",
                "JAVA",
                "ALGORITHMS"
        };

        System.out.println(
                hasDuplicate(
                        codes
                )
        );
    }

    static boolean hasDuplicate(
            String[] codes
    ) {
        Set<String> seen =
                new HashSet<>();

        for (
                String code
                : codes
        ) {
            if (
                    !seen.add(
                            code
                    )
            ) {
                return true;
            }
        }

        return false;
    }
}

Output:

true

Practical Example — Course Lookup Index

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

public class Main {

    public static void main(String[] args) {
        List<Course> courses =
                List.of(
                        new Course(
                                "JAVA",
                                "Java Foundation"
                        ),
                        new Course(
                                "BACKEND",
                                "Backend Development"
                        ),
                        new Course(
                                "ALGORITHMS",
                                "Algorithms"
                        )
                );

        Map<String, Course> byCode =
                indexByCode(
                        courses
                );

        Course course =
                byCode.get(
                        "BACKEND"
                );

        System.out.println(
                course.title()
        );
    }

    static Map<String, Course> indexByCode(
            List<Course> courses
    ) {
        Map<String, Course> result =
                new HashMap<>();

        for (
                Course course
                : courses
        ) {
            result.put(
                    course.code(),
                    course
            );
        }

        return result;
    }

    record Course(
            String code,
            String title
    ) {
    }
}

Duplicate Keys in HashMap

Suppose:

map.put(
        "JAVA",
        firstCourse
);

map.put(
        "JAVA",
        secondCourse
);

The second value replaces the first value for that equal key।

This is different from:

HashSet

where duplicate values simply remain one set element।

Detecting Duplicate Map Keys

If replacement is not allowed:

if (
        result.put(
                course.code(),
                course
        ) != null
) {
    throw new IllegalArgumentException(
            "Duplicate course code."
    );
}

But this pattern assumes existing values themselves are not null।

Another clear approach:

if (
        result.containsKey(
                course.code()
        )
) {
    throw new IllegalArgumentException(
            "Duplicate course code."
    );
}

result.put(
        course.code(),
        course
);

putIfAbsent()

A useful Map operation:

putIfAbsent(
        key,
        value
);

Example:

Course existing =
        result.putIfAbsent(
                course.code(),
                course
        );

if (
        existing != null
) {
    throw new IllegalArgumentException(
            "Duplicate course code."
    );
}

Again, design gets simpler when null map values are not used।

Practice 1 — HashSet Membership

Create a set of course codes and check whether:

JAVA

exists।

Solution

Set<String> codes =
        new HashSet<>();

codes.add(
        "JAVA"
);

codes.add(
        "BACKEND"
);

boolean found =
        codes.contains(
                "JAVA"
        );

Practice 2 — Complexity

Typical average complexity of:

hashSet.contains(
        value
)

Answer

O(1)

average expected।

Practice 3 — HashMap Lookup

Given:

Map<Long, String> learners =
        new HashMap<>();

store:

100 → Sakib

Solution

learners.put(
        100L,
        "Sakib"
);

Lookup:

String learner =
        learners.get(
                100L
        );

Practice 4 — Collision

Can two unequal objects have the same hash code?

Answer

Yes।

That is a collision and hash-based collections must handle it।

Practice 5 — Equality Contract

If:

first.equals(
        second
)

returns true, what must be true about their hash codes?

Answer

first.hashCode()
==
second.hashCode()

Practice 6 — Reverse Contract

If two objects have equal hash codes, must they be equal?

Answer

No।

They may simply collide।

Practice 7 — Mutable Key

Why is this risky?

map.put(
        user,
        value
);

user.setEmail(
        "new@example.com"
);

Assume email participates in:

equals()
hashCode()

Answer

The user's hash code may change after insertion, so the map may search in a different bucket region and fail to locate the stored entry correctly।

Practice 8 — Duplicate Detection

What data structure is a strong choice for finding whether values repeat?

Answer

HashSet

because it provides expected fast membership/insertion checks।

Practice 9 — Frequency Counting

What structure fits:

word → count

Answer

HashMap<String, Integer>

Practice 10 — Search Strategy

You have one million unsorted IDs and perform millions of membership checks।

Better general choice:

List
Binary Search without preprocessing
HashSet

Answer

Usually:

HashSet

assuming ordering is not required and memory cost is acceptable।

Practice 11 — Sorted Range Query

You frequently need:

all keys between A and M

Would HashMap naturally be the best structure?

Answer

Not necessarily।

A sorted structure such as a tree-based map may fit ordered range queries better।

Practice 12 — Build an Index

Suppose:

List<Course> courses

and repeated lookup is:

code → Course

What preprocessing could you do?

Answer

Build:

Map<String, Course> coursesByCode

once and use expected fast lookups afterward।

True or False

  1. Hashing can support average O(1) exact lookup.
  2. A hash code is guaranteed unique.
  3. Collisions are possible.
  4. equals() is still required when hash codes collide.
  5. Equal objects must have equal hash codes.
  6. Equal hash codes guarantee equal objects.
  7. HashSet can be useful for duplicate detection.
  8. HashMap stores key-value pairs.
  9. HashMap guarantees insertion-order iteration.
  10. Mutable hash keys can cause lookup bugs.
  11. A constant hash code is good for performance.
  12. Hashing usually trades additional memory for faster expected lookup.
  13. Hashing naturally provides sorted range queries.
  14. HashMap.get() is guaranteed worst-case O(1).
  15. A map can act as an in-memory lookup index.

Answers

1. True
2. False
3. True
4. True
5. True
6. False
7. True
8. True
9. False
10. True
11. False
12. True
13. False
14. False
15. True

Knowledge Check

Question 1

What is hashing?

Question 2

What does a hash code help a hash table determine?

Question 3

What is a collision?

Question 4

Why does a hash table still need equals()?

Question 5

What is the most important equals()/hashCode() contract rule?

Question 6

Why is HashSet useful for duplicate detection?

Question 7

Why can HashMap lookup be faster than repeated List scanning?

Question 8

What is the danger of mutable hash keys?

Question 9

What does load factor describe conceptually?

Question 10

Why does a HashMap resize?

Question 11

Why should we say average O(1) rather than guaranteed O(1)?

Question 12

When might Binary Search or a tree-based structure be preferable to hashing?

Knowledge Check Answers

Answer 1

Hashing uses a hash function to map a value or key toward an internal storage location so exact lookup can avoid scanning the entire collection।

Answer 2

It helps determine which bucket or internal region is likely to contain the key।

Answer 3

A collision occurs when different values map to the same hash code or bucket region।

Answer 4

Because multiple unequal keys can collide. After reaching the relevant bucket, the table still needs logical equality to identify the actual matching key।

Answer 5

If:

a.equals(
        b
)

is true, then:

a.hashCode()
==
b.hashCode()

must also be true।

Answer 6

Because HashSet.add() and contains() provide expected fast membership checks, letting us detect repeated values while traversing input once।

Answer 7

A List may require scanning up to n elements, while hashing uses the key's hash to navigate toward a much smaller candidate region, giving average expected O(1) lookup।

Answer 8

If equality/hash-relevant state changes after insertion, the object's current hash may no longer point toward the internal location where it was originally stored।

Answer 9

Load factor conceptually represents how full the hash table is relative to its bucket capacity।

Answer 10

As the table becomes crowded, more collisions can occur. Resizing creates more internal capacity and redistributes entries to preserve efficient average lookup।

Answer 11

Because collisions, hash distribution, resizing, and worst-case conditions can make individual operations more expensive than constant time।

Answer 12

When ordered traversal, range queries, insertion points, or sorted ordering are important, an ordered structure or Binary Search may fit the access pattern better।

Practical Decision Guide

Use:

HashSet<T>

when the main question is:

Does this exact value exist?

or:

Have I seen this value before?

Use:

HashMap<K, V>

when the main question is:

What value belongs to this exact key?

Use:

Binary Search

when:

Data is already sorted
and ordered searching matters.

Use:

Tree-based ordered structure

when:

Sorted keys or range operations matter.

Use:

Linear Search

when:

Data is small
searches are infrequent
or preprocessing is unnecessary.

Complexity Summary

HashSet / HashMap

Typical average:

add / put
→ O(1)

contains / containsKey
→ O(1)

get
→ O(1)

remove
→ O(1)

With important caveat:

These are average expected complexities,
not unconditional worst-case guarantees.

Hashing Tradeoff

Hashing usually gives:

Faster expected exact lookup

in exchange for:

Additional memory
No natural sorted order
Hash/equality requirements
Resizing overhead
Potential collisions

Core Mental Model

Without hashing:

Where is this value?

Search through candidates.

With hashing:

Where should this value probably be?

Compute hash
↓
Go to relevant bucket
↓
Use equals to find exact match

That is the foundation of hash-based lookup।

Lesson Summary

এই lesson-এ আমরা hashing এবং fast lookup-এর foundation শিখেছি।

We learned:

  • Hashing maps keys toward internal storage locations
  • Hash tables organize entries into bucket-like regions
  • Hash codes help locate likely buckets
  • Different values can collide
  • Collisions are normal and must be handled
  • Hashing still requires logical equality checks
  • HashMap provides key-value lookup
  • HashSet provides unique-value membership
  • Typical hash operations are average O(1)
  • HashSet can reduce duplicate detection from O(n²) to expected O(n)
  • HashMap can build efficient in-memory indexes
  • Frequency counting is a natural HashMap use case
  • Equal objects must have equal hash codes
  • Equal hash codes do not imply equal objects
  • Overriding equals() without consistent hashCode() is dangerous
  • Records automatically provide value-based equality and hashing
  • Mutable hash keys can break lookup behavior
  • Hash tables resize to maintain efficient distribution
  • Load factor represents table fullness conceptually
  • HashMap does not guarantee insertion or sorted order
  • Hashing trades additional memory for faster expected exact lookup
  • Binary Search and ordered structures remain useful when ordering matters
  • Multiple indexes can improve lookup but create consistency responsibilities

The central relationship is:

hashCode()
→ where should we look?

equals()
→ is this actually the same key?

And the core engineering principle is:

Choose the data structure
based on the access pattern.

Exact lookup
→ HashMap / HashSet

Ordered search
→ sorted structure

Sequential one-off search
→ Linear Search

Next Lesson

পরবর্তী lesson:

Trees and Binary Search Tree Fundamentals

আমরা শিখব:

  • What a tree is
  • Root, parent, child, leaf
  • Depth and height intuition
  • Binary trees
  • Binary Search Trees
  • BST ordering property
  • Search
  • Insert
  • In-order traversal
  • Pre-order traversal
  • Post-order traversal
  • Recursive tree processing
  • Balanced vs unbalanced tree intuition
  • Average vs worst-case lookup
  • Why Java's ordered collections use more sophisticated balanced trees