Two Sum - A Easy difficulty question commonly asked at Google. Study Hashing patterns and Java implementation to solve this.

Home/Learn/DSA/Hashing

Hashing

Q: Group anagrams together

Group anagrams together - A Medium difficulty question commonly asked at Amazon. Study Hashing patterns and Java implementation to solve this.

Q: Longest substring without repeating characters

Longest substring without repeating characters - A Medium difficulty question commonly asked at Facebook. Study Hashing patterns and Java implementation to solve this.

Q: Subarray sum equals k

Subarray sum equals k - A Medium difficulty question commonly asked at Facebook. Study Hashing patterns and Java implementation to solve this.

Q: LRU Cache implementation using LinkedHashMap

LRU Cache implementation using LinkedHashMap - A Medium difficulty question commonly asked at Amazon. Study Hashing patterns and Java implementation to solve this.

Intermediate

O(1) average lookups power two-sum, anagram detection, and frequency counting — the most commonly used data structure in interviews.

Think of it this way

Think of a school cloakroom with numbered hooks. When you arrive, the teacher converts your name into a hook number using a quick formula (the hash function). Finding your coat is instant — no searching required — because you always know exactly which hook it is on. That instant lookup is what a HashMap gives you: O(1) average time for storing and retrieving anything.

In code, it looks like thisJava

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

locker.put("Alice", 42);  // Alice's coat → hook 42
locker.put("Bob",   17);  // Bob's coat   → hook 17

System.out.println(locker.get("Alice"));             // 42 — O(1), instant
System.out.println(locker.containsKey("Charlie"));   // false — O(1)
System.out.println(locker.getOrDefault("Dave", -1)); // -1 — safe default

Overview

Hashing maps keys to values using a hash function, providing O(1) average case for insert, delete, and lookup. Java provides HashMap, HashSet, and LinkedHashMap. Collisions are handled via chaining (Java's default) or open addressing. HashMaps are the most commonly used data structure in coding interviews — when you need to reduce time complexity from O(n²) to O(n), a HashMap is usually the tool.

Time & Space Complexity

Operation	Time	Space
Insert	`O(1) avg`	`O(1)`
Lookup	`O(1) avg`	`O(1)`
Delete	`O(1) avg`	`O(1)`
Worst case (all collisions)	`O(n)`	`O(n)`
Iteration	`O(n)`	`O(1)`

Java Implementation

Java

import java.util.*;

public class HashingPatterns {

    // Two Sum — O(n)
    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) return new int[]{map.get(complement), i};
            map.put(nums[i], i);
        }
        return new int[]{};
    }

    // Group anagrams — O(n * k log k) where k is max string length
    public static List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(map.values());
    }

    // Longest substring without repeating characters — O(n)
    public static int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> lastSeen = new HashMap<>();
        int maxLen = 0, left = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (lastSeen.containsKey(c)) {
                left = Math.max(left, lastSeen.get(c) + 1);
            }
            lastSeen.put(c, right);
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }

    // Subarray sum equals k — O(n)
    public static int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> prefixCount = new HashMap<>();
        prefixCount.put(0, 1);
        int count = 0, sum = 0;
        for (int num : nums) {
            sum += num;
            count += prefixCount.getOrDefault(sum - k, 0);
            prefixCount.merge(sum, 1, Integer::sum);
        }
        return count;
    }
}

Key Points to Remember

HashMap allows one null key; HashSet is just a HashMap where you only care about keys, not values

Use getOrDefault(), merge(), and computeIfAbsent() to write cleaner, null-safe code

map.getOrDefault(key, 0) + 1;                      // safe read with fallback
map.merge(key, 1, Integer::sum);                   // increment count idiom
map.computeIfAbsent(key, k -> new ArrayList<>()).add(val); // group into list

LinkedHashMap maintains insertion order; TreeMap maintains sorted key order

LinkedHashMap<String, Integer> lhm = new LinkedHashMap<>(); // iteration = insertion order
TreeMap<String, Integer> tm = new TreeMap<>();               // iteration = alphabetical order

For counting frequencies, Map.merge(key, 1, Integer::sum) is the idiomatic Java one-liner

// Count character frequencies
for (char c : s.toCharArray())
    freq.merge(c, 1, Integer::sum); // add 1 if absent, otherwise sum

To check if two strings are anagrams, sort them or use a 26-element frequency array

// Sort approach — O(k log k)
Arrays.sort(s.toCharArray()); // same sorted form = anagram

// Array approach — O(k), faster
int[] count = new int[26];
for (char c : s.toCharArray()) count[c - 'a']++;

Interview Questions

Two Sum

EasyGoogleSolve it

Group anagrams together

MediumAmazonSolve it

Longest substring without repeating characters

MediumFacebookSolve it

Subarray sum equals k

MediumFacebookSolve it

LRU Cache implementation using LinkedHashMap

MediumAmazonSolve it

Ask Aria about Hashing

Your personal AI tutor — ask anything about this concept

Dynamic Programming