HashMap & HashSet

How Hashing Actually Works

Finding a name in an unsorted list of a million entries means checking up to a million entries. A HashMap finds it in what is effectively one step, and understanding how turns it from magic into something you can reason about.

Internally a HashMap keeps an array of slots called buckets. When you store a key, Java calls that key's hashCode() method — a method every object has — which returns an int. The map converts that int into a bucket index and puts the entry there. To look the key up again, it repeats exactly the same calculation, goes straight to that bucket, and finds the entry. No scanning.

Two different keys can land in the same bucket, which is called a collision. The map handles it by keeping several entries in that bucket and comparing them with equals() to find the right one. Collisions are normal; a good hashCode() simply keeps them rare. When a single bucket becomes badly overcrowded, modern Java reorganises it into a balanced tree so that even the worst case stays reasonable.

Two consequences follow immediately, and both are examined. First, lookups are effectively constant time regardless of size, which is why a HashMap beats a List for any "look this up by key" job. Second, a HashMap has no order. Printing one may not show keys in the order you inserted them, and that order can even change as the map grows and redistributes its entries. Never write code that depends on it.

import java.util.*;

Map<String, Integer> marks = new HashMap<>();
marks.put("Maths", 92);
marks.put("Physics", 87);
marks.put("Chemistry", 78);

System.out.println(marks.get("Physics"));    // 87 — straight to the bucket
System.out.println(marks);
// {Physics=87, Chemistry=78, Maths=92}  — order is NOT insertion order

// Keys are unique: put() with an existing key REPLACES the value
marks.put("Maths", 95);
System.out.println(marks.get("Maths"));      // 95, not a second entry
System.out.println(marks.size());            // 3

// hashCode is what makes it fast
System.out.println("Maths".hashCode());      // a stable int for this String

// A missing key returns null, not an exception
System.out.println(marks.get("Hindi"));      // null

// which is why this line can throw on unboxing:
// int hindi = marks.get("Hindi");           // NullPointerException
int hindi = marks.getOrDefault("Hindi", 0);  // 0 — safe

The Map Methods Worth Knowing

Beyond put, get, remove and containsKey, a handful of methods added in Java 8 replace patterns that beginners write out longhand. Learning them makes your code both shorter and correct in cases you might not have thought about.

getOrDefault(key, fallback) returns the fallback instead of null when a key is missing, which removes both a null check and the unboxing crash. putIfAbsent stores a value only when the key is not already there.

merge(key, value, function) is the counting workhorse. The classic word-frequency loop — get the current count, handle the null case, add one, put it back — becomes a single line: counts.merge(word, 1, Integer::sum). If the key is absent it stores 1; if present it combines the old and new values with the function you gave.

computeIfAbsent(key, function) is the grouping workhorse. When your map's values are themselves lists — students grouped by city, marks grouped by subject — you would normally check whether the list exists, create it if not, then add. computeIfAbsent does all three, and the pattern map.computeIfAbsent(k, x -> new ArrayList<>()).add(item) is worth memorising as one unit.

For iteration, prefer entrySet() when you need both key and value, since looping over keySet() and calling get() for each key does the hashing work twice.

import java.util.*;

// ---- Counting: the longhand way ----
Map<String, Integer> counts = new HashMap<>();
String[] words = "the quick the lazy the dog".split(" ");

for (String w : words) {
    if (counts.containsKey(w)) {
        counts.put(w, counts.get(w) + 1);
    } else {
        counts.put(w, 1);
    }
}

// ---- The same thing, two better ways ----
Map<String, Integer> c2 = new HashMap<>();
for (String w : words) {
    c2.put(w, c2.getOrDefault(w, 0) + 1);
}

Map<String, Integer> c3 = new HashMap<>();
for (String w : words) {
    c3.merge(w, 1, Integer::sum);          // absent -> 1, present -> old + 1
}
System.out.println(c3);                    // {the=3, quick=1, lazy=1, dog=1}

// ---- Grouping: computeIfAbsent ----
Map<String, List<String>> byCity = new HashMap<>();
byCity.computeIfAbsent("Pune",  k -> new ArrayList<>()).add("Ananya");
byCity.computeIfAbsent("Pune",  k -> new ArrayList<>()).add("Rahul");
byCity.computeIfAbsent("Kochi", k -> new ArrayList<>()).add("Meera");
System.out.println(byCity);   // {Pune=[Ananya, Rahul], Kochi=[Meera]}

// ---- Iterating ----
for (Map.Entry<String, Integer> e : c3.entrySet()) {   // both at once
    System.out.println(e.getKey() + " appears " + e.getValue() + " time(s)");
}

c3.forEach((word, n) -> System.out.println(word + " -> " + n));

// Sorting a map's entries by value, highest first
c3.entrySet().stream()
  .sorted(Map.Entry.<String, Integer>comparingByValue().reversed())
  .forEach(e -> System.out.println(e.getKey() + ": " + e.getValue()));

The equals and hashCode Contract

Everything above works because the map can compute a hash code for a key and compare keys for equality. For String and the wrapper classes, both are already correct. For your own classes they are not, and this produces one of the most confusing bugs in Java.

Suppose you write a Student class and override equals() so that two students with the same roll number count as equal — a reasonable thing to do. You put a student into a HashSet, then ask whether an equal student is in the set, and it says no. Every field matches. equals() returns true if you call it directly. The set still says no.

The cause is that you did not override hashCode(). The inherited version returns a value based on the object's memory address, so two equal objects get completely different hash codes, land in different buckets, and the set never even reaches the point of calling equals(). It looked in the wrong bucket and correctly found nothing there.

Hence the contract, which you should be able to state in an interview: if two objects are equal according to equals(), they must return the same hashCode(). The reverse is not required — unequal objects may share a hash code, which is just a collision. And both methods must use the same fields.

In practice, never write them by hand. Let your editor generate them, use Objects.hash(...) and Objects.equals(...), or — best of all — make the class a record, which generates a correct pair for you automatically.

import java.util.*;

// ---- BROKEN: equals overridden, hashCode forgotten ----
class BadStudent {
    final int rollNo;
    BadStudent(int rollNo) { this.rollNo = rollNo; }

    @Override public boolean equals(Object o) {
        return o instanceof BadStudent s && s.rollNo == this.rollNo;
    }
    // no hashCode()!
}

Set<BadStudent> set = new HashSet<>();
set.add(new BadStudent(101));

System.out.println(new BadStudent(101).equals(new BadStudent(101)));  // true
System.out.println(set.contains(new BadStudent(101)));                // FALSE

set.add(new BadStudent(101));
System.out.println(set.size());     // 2 — duplicates in a Set!

// ---- FIXED ----
class GoodStudent {
    final int rollNo;
    GoodStudent(int rollNo) { this.rollNo = rollNo; }

    @Override public boolean equals(Object o) {
        return o instanceof GoodStudent s && s.rollNo == this.rollNo;
    }
    @Override public int hashCode() {
        return Objects.hash(rollNo);        // SAME field as equals()
    }
}

Set<GoodStudent> good = new HashSet<>();
good.add(new GoodStudent(101));
System.out.println(good.contains(new GoodStudent(101)));   // true
good.add(new GoodStudent(101));
System.out.println(good.size());                            // 1 — correct

// ---- Simplest of all ----
record StudentId(int rollNo, String batch) { }   // equals + hashCode generated

Mutable Keys: the Object That Vanishes

Here is the second half of the same problem, and it is subtler because all your methods are correct.

Put an object into a HashMap as a key. The map computes its hash code once, at insertion time, and files it in the corresponding bucket. Now change one of the fields that hashCode() is based on. The object's hash code changes — but it is still sitting in the bucket chosen by the old one.

Look it up now and the map computes the new hash, goes to a different bucket, and finds nothing. The entry is still in the map: size() counts it, and iterating over the map shows it. It is simply unreachable by lookup. Even remove() fails, because removal also starts by hashing. You have created an entry that exists and cannot be got at.

The rules that follow are simple. Prefer immutable keys — String, Integer, an enum, a record whose components never change. This is a large part of why String is immutable in the first place: it is the most-used map key in the language, and it can never go stale. If you must use a mutable object as a key, base hashCode() only on fields that never change after construction, such as an ID assigned at creation.

The same applies to HashSet, which is a HashMap underneath: mutating an object after adding it to a set can make it undiscoverable and can allow a duplicate to be added alongside it.

import java.util.*;

class Student {
    String name;                    // mutable, and used in hashCode — dangerous
    Student(String name) { this.name = name; }

    @Override public boolean equals(Object o) {
        return o instanceof Student s && Objects.equals(s.name, this.name);
    }
    @Override public int hashCode() { return Objects.hash(name); }
    @Override public String toString() { return name; }
}

Map<Student, Integer> marks = new HashMap<>();
Student s = new Student("Ananya");
marks.put(s, 92);

System.out.println(marks.get(s));       // 92  — found

s.name = "Ananya Sharma";               // change a field used in hashCode

System.out.println(marks.get(s));       // null — same object, cannot be found
System.out.println(marks.size());       // 1    — but it IS still in there
System.out.println(marks);              // {Ananya Sharma=92}
System.out.println(marks.remove(s));    // null — cannot even be removed

// ---- Safe designs ----
// 1. Use an immutable key type
Map<String, Integer> byName = new HashMap<>();

// 2. Or hash only on a field fixed at creation
record StudentKey(int rollNo) { }       // rollNo never changes
Map<StudentKey, Integer> byRoll = new HashMap<>();
byRoll.put(new StudentKey(101), 92);
System.out.println(byRoll.get(new StudentKey(101)));   // 92, always

HashSet, Set Operations, and Choosing a Variant

A HashSet is a HashMap with the values ignored, so everything above applies to it unchanged. Its job is answering "have I seen this before?" instantly, and its add() returns false when the element was already present — a neat way to detect duplicates in a single pass.

Sets also give you the three operations from school mathematics, though the method names do not advertise it: addAll is union, retainAll is intersection, and removeAll is difference. Each modifies the set you call it on, so copy first if you want to keep the original.

The most valuable practical use of a set is replacing list.contains() inside a loop. Checking membership in a list scans it every time, so a loop over n items checking against a list of m items does n × m comparisons. Swap the list for a HashSet and each check becomes instant. On real data this is the difference between a program that finishes and one that appears to hang.

Finally, there are three flavours of both map and set, and the choice is about ordering. HashMap and HashSet are fastest and have no order. LinkedHashMap and LinkedHashSet keep insertion order for a small extra cost, which is what you want when the output will be shown to a user. TreeMap and TreeSet keep the keys sorted at all times and can answer range queries such as "all marks above 80", at the cost of logarithmic rather than constant lookups.

import java.util.*;

Set<String> tags = new HashSet<>();
System.out.println(tags.add("java"));         // true  — newly added
System.out.println(tags.add("java"));         // false — already present
tags.add("placement");
System.out.println(tags.size());              // 2

// Detecting duplicates in one pass
String[] rollNos = {"101", "102", "101", "103"};
Set<String> seen = new HashSet<>();
for (String r : rollNos) {
    if (!seen.add(r)) {
        System.out.println("Duplicate roll number: " + r);   // 101
    }
}

// Set operations (each modifies the receiver — copy first)
Set<Integer> a = new HashSet<>(Set.of(1, 2, 3, 4));
Set<Integer> b = new HashSet<>(Set.of(3, 4, 5, 6));

Set<Integer> union = new HashSet<>(a);
union.addAll(b);                              // [1, 2, 3, 4, 5, 6]

Set<Integer> intersection = new HashSet<>(a);
intersection.retainAll(b);                    // [3, 4]

Set<Integer> difference = new HashSet<>(a);
difference.removeAll(b);                      // [1, 2]

// The three flavours
Map<String, Integer> hash   = new HashMap<>();        // fastest, no order
Map<String, Integer> linked = new LinkedHashMap<>();  // insertion order
Map<String, Integer> tree   = new TreeMap<>();        // sorted by key

for (Map<String, Integer> m : List.of(hash, linked, tree)) {
    m.put("Physics", 87); m.put("Chemistry", 78); m.put("Maths", 92);
}
System.out.println(linked);   // {Physics=87, Chemistry=78, Maths=92}
System.out.println(tree);     // {Chemistry=78, Maths=92, Physics=87}

• HashMap / HashSet — the default. Fastest lookups, no ordering guarantee at all.
• LinkedHashMap / LinkedHashSet — same speed profile, plus predictable insertion order. Use it whenever output order matters.
• TreeMap / TreeSet — always sorted, with extras such as firstKey(), headMap() and tailMap(). Keys must be comparable.
• A TreeMap rejects a null key, because it has to compare keys to place them.
• None of these is thread-safe. Use ConcurrentHashMap when several threads share one map; do not use the legacy Hashtable.
• Replace list.contains() inside a loop with a HashSet — it is the single easiest performance win in beginner Java code.