DSA in Java: Hashing — HashMap & HashSet (Beginner Guide)

If there's one data structure that shows up in coding interviews more than any other, it's the hash map. Hashing is the trick that lets you look things up in O(1) — constant time, and it's the secret behind converting slow O(n²) brute-force solutions into fast O(n) ones. Master HashMap and HashSet and you'll have the single most powerful tool in your DSA toolkit.

The problem hashing solves

Imagine you have a list of a million names and you want to check "is 'Alice' in here?" With an array or list, you'd have to scan through — up to a million checks, O(n). A hash-based structure answers the same question in one step, on average, no matter how big it is. That's the magic.

How hashing works (the intuition)

A hash function takes your key (a name, a number, anything) and converts it into an array index — a number telling it exactly which "slot" to store the value in. To store something: hash the key → get a slot → put it there. To look it up: hash the same key → get the same slot → read it. No scanning; you jump straight to the right place.

You don't have to write hash functions yourself — Java does it for you (via each object's hashCode() method, which you may remember from the Core Java course). You just use the ready-made structures.

HashMap: key → value pairs

A HashMap stores key-value pairs — like a dictionary where you look up a word (key) to get its definition (value). All the core operations are O(1) on average:

Map<String, Integer> ages = new HashMap<>();

ages.put("Alice", 30);         // store a pair
ages.put("Bob", 25);

int a = ages.get("Alice");       // 30 — instant lookup
boolean has = ages.containsKey("Bob");  // true
ages.getOrDefault("Zoe", 0);      // 0 — handy default if missing

HashSet: unique values, fast membership

A HashSet stores unique values with no duplicates, and answers "does this exist?" in O(1). Use it whenever you need to track "have I seen this before?":

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

seen.add("Alice");
seen.add("Alice");        // ignored — no duplicates
seen.contains("Alice");   // true — O(1)
seen.size();               // 1

The killer pattern: Two Sum in O(n)

Here's the interview classic that shows why hashing matters. Given an array and a target, find two numbers that add up to the target. The brute-force way checks every pair — O(n²). With a HashMap, you do it in a single pass, O(n):

int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();  // value → index
    for (int i = 0; i < nums.length; i++) {
        int need = target - nums[i];       // what number would complete the pair?
        if (seen.containsKey(need)) {
            return new int[]{ seen.get(need), i };  // found it!
        }
        seen.put(nums[i], i);              // remember this number for later
    }
    return new int[]{}; // no pair found
}

The idea: as you walk the array, for each number ask "have I already seen the number that would complete this pair?" The HashMap answers instantly. This "remember what you've seen in a map" trick appears in a huge number of problems — anagrams, duplicates, subarrays, and more.

Need sorted order? Use TreeMap/TreeSet

HashMap and HashSet are fast but store items in no particular order. If you need keys kept sorted, Java offers TreeMap and TreeSet (backed by the trees you'll meet next lesson) — they're O(log n) instead of O(1), trading a little speed for order. And LinkedHashMap preserves insertion order. Pick based on what you need.

If I could give my past self one DSA tip, it would be: when a problem feels slow, ask "can a HashMap help?" Nine times out of ten, the leap from a brute-force O(n²) solution to an elegant O(n) one is exactly a hash map remembering what you've already seen. It became my reflex — the first tool I reach for. Practise the Two Sum pattern until it's automatic, because once "use a map to remember what I've seen" clicks, a whole tier of interview problems opens up to you.

Key takeaways

• Hashing converts a key into a slot index, giving O(1) average lookup, insert, and delete.
• HashMap stores key→value pairs; HashSet stores unique values for fast membership checks.
• The "remember what you've seen in a map" pattern turns many O(n²) problems into O(n) — e.g. Two Sum.
• Need sorted order instead of speed? Use TreeMap/TreeSet (O(log n)).

← Previous: DSA Lesson 8 — Stacks & Queues
Next: DSA Lesson 10 — Trees & Binary Search Trees →
↑ Back to the DSA roadmap