Data StructuresFebruary 12, 2025·8 min read

Hash Maps: When and Why

The Secret Weapon for O(1) Lookups

Founder

What is a Hash Map?

A hash map (also called hash table, dictionary, or associative array) stores key-value pairs with O(1) average lookup, insert, and delete.

It's one of the most powerful data structures in interviews because it can turn O(n²) brute-force solutions into O(n) optimized ones.

Different Names, Same Concept

JavaScript: Map or plain object {}
Python: dict
Java: HashMap
C++: unordered_map
Go: map

How Hash Maps Work

1. Hash Function

Converts keys into array indices. Good hash functions:

Are deterministic: same key always → same hash
Are fast: O(1) to compute
Distribute evenly to minimize collisions

// Simplified hash function (real ones are more complex)
function hash(key, arraySize) {
  let hash = 0;
  for (let char of key) {
    hash = (hash + char.charCodeAt(0)) % arraySize;
  }
  return hash;
}

// Example
hash("apple", 10);  // Returns index 0-9
hash("banana", 10); // Returns different index
// Modulo (%) keeps result within array bounds

2. Internal Structure

// Conceptual representation
const hashMap = [
  null,                    // Index 0: empty
  { key: "apple", value: 5 },  // Index 1
  null,
  [                        // Index 3: collision! (chaining)
    { key: "banana", value: 3 },
    { key: "cherry", value: 7 }
  ],
  // ...
];

// Usage
map.set("apple", 5);     // Hash "apple" → index 1
map.get("apple");        // Returns 5
map.set("banana", 3);    // Hash "banana" → index 3
map.set("cherry", 7);    // Hash collision! → also index 3

Collision Resolution

Collision: Two keys hash to the same index. Two main strategies:

1. Chaining (Most Common)

Each array slot holds a linked list or array of entries.

class HashMap {
  constructor() {
    this.buckets = new Array(10).fill(null).map(() => []);
    this.size = 0;
  }

  hash(key) {
    return key.length % this.buckets.length;
  }

  set(key, value) {
    const index = this.hash(key);
    const bucket = this.buckets[index];
    
    // Check if key exists, update
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        bucket[i][1] = value;
        return;
      }
    }
    
    // Add new entry
    bucket.push([key, value]);
    this.size++;
  }

  get(key) {
    const index = this.hash(key);
    const bucket = this.buckets[index];
    
    for (let [k, v] of bucket) {
      if (k === key) return v;
    }
    return undefined;
  }
}

// Usage
const map = new HashMap();
map.set("apple", 5);
map.set("banana", 3);  // Might collide with apple
map.get("apple");      // Still fast: scan short chain

2. Open Addressing (Linear Probing)

Find the next empty slot sequentially.

class HashMapProbing {
  constructor() {
    this.buckets = new Array(10).fill(null);
    this.size = 0;
  }

  hash(key) {
    return key.length % this.buckets.length;
  }

  set(key, value) {
    let index = this.hash(key);
    
    // Find next empty slot
    while (this.buckets[index] !== null) {
      if (this.buckets[index][0] === key) {
        this.buckets[index][1] = value; // Update existing
        return;
      }
      index = (index + 1) % this.buckets.length; // Wrap around
    }
    
    this.buckets[index] = [key, value];
    this.size++;
  }

  get(key) {
    let index = this.hash(key);
    
    while (this.buckets[index] !== null) {
      if (this.buckets[index][0] === key) {
        return this.buckets[index][1];
      }
      index = (index + 1) % this.buckets.length;
    }
    return undefined;
  }
}

Load Factor and Resizing

Load factor = size / capacity

When load factor exceeds threshold (typically 0.75), hash map automatically resizes (usually doubles) and rehashes all entries.

// Before resize: capacity 10, size 8 → load factor 0.8
// Triggers resize!

// After resize: capacity 20, size 8 → load factor 0.4
// All entries rehashed with new capacity

// Why? Keeps chains short → maintains O(1) performance

Interview Tip

Resizing is O(n) but happens rarely. Amortized O(1) insert means: averaging over many inserts, each costs O(1).

When to Use Hash Maps

Use When You Need:

Fast lookups: "Have I seen this before?"
Counting frequencies: "How many times does X appear?"
Pairing/grouping: "Match values that satisfy condition"
Caching: Memoization for expensive computations
Remove duplicates: Track unique items
Two-way mapping: Bidirectional lookup

Don't Use When You Need:

Sorted data: Use TreeMap (O(log n) but maintains order)
Range queries: "Find all keys between X and Y"
Smallest/largest: Use heap or sorted structure
Order preservation: Use array or linked list
Memory is tight: Hash maps have overhead

Classic Interview Problems

Problem 1: Two Sum

Given array and target, return indices of two numbers that add to target.

//  Brute Force: O(n²)
function twoSumBrute(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
  return null;
}

//  Hash Map: O(n)
function twoSum(nums, target) {
  const map = new Map(); // value → index
  
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    
    if (map.has(complement)) {
      return [map.get(complement), i];
    }
    
    map.set(nums[i], i);
  }
  
  return null;
}

// Example
twoSum([2, 7, 11, 15], 9); // Returns [0, 1] (2 + 7 = 9)

// How it works:
// i=0: looking for 7 (9-2), not found, store 2→0
// i=1: looking for 2 (9-7), FOUND at index 0! Return [0, 1]

Problem 2: Group Anagrams

Given array of strings, group anagrams together.

function groupAnagrams(strs) {
  const map = new Map(); // sorted → [words]
  
  for (let str of strs) {
    // Key: sorted version (anagrams have same sorted form)
    const key = str.split('').sort().join('');
    
    if (!map.has(key)) {
      map.set(key, []);
    }
    map.get(key).push(str);
  }
  
  return Array.from(map.values());
}

// Example
groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]);
// Returns: [["eat","tea","ate"], ["tan","nat"], ["bat"]]

// How it works:
// "eat" → sorted "aet" → map["aet"] = ["eat"]
// "tea" → sorted "aet" → map["aet"] = ["eat", "tea"]
// "tan" → sorted "ant" → map["ant"] = ["tan"]
// etc.

Problem 3: Longest Substring Without Repeating Characters

function lengthOfLongestSubstring(s) {
  const map = new Map(); // char → last index
  let maxLen = 0;
  let start = 0;
  
  for (let end = 0; end < s.length; end++) {
    const char = s[end];
    
    // If seen and within current window, move start
    if (map.has(char) && map.get(char) >= start) {
      start = map.get(char) + 1;
    }
    
    map.set(char, end);
    maxLen = Math.max(maxLen, end - start + 1);
  }
  
  return maxLen;
}

// Example
lengthOfLongestSubstring("abcabcbb"); // Returns 3 ("abc")

// Trace "abcabcbb":
// a: map={a:0}, start=0, len=1
// b: map={a:0,b:1}, start=0, len=2
// c: map={a:0,b:1,c:2}, start=0, len=3
// a: duplicate at 0! start=1, map={a:3,b:1,c:2}, len=3
// b: duplicate at 1! start=2, map={a:3,b:4,c:2}, len=3
// c: duplicate at 2! start=3, map={a:3,b:4,c:5}, len=3
// ...

Problem 4: First Non-Repeating Character

function firstUniqChar(s) {
  // Two passes: count frequencies, then find first with count 1
  const freq = new Map();
  
  for (let char of s) {
    freq.set(char, (freq.get(char) || 0) + 1);
  }
  
  for (let i = 0; i < s.length; i++) {
    if (freq.get(s[i]) === 1) {
      return i;
    }
  }
  
  return -1;
}

// Example
firstUniqChar("leetcode"); // Returns 0 ('l')
firstUniqChar("loveleetcode"); // Returns 2 ('v')

// Why two passes?
// First pass: count all frequencies O(n)
// Second pass: find first with count 1 O(n)
// Total: O(n) time, O(1) space (max 26 letters)

Hash Map vs. Set

Hash Map (Map, dict)

Stores: Key-value pairs
Use for: Counting, associating data
Example: {word: count}
Methods: set(), get(), has()

Hash Set (Set)

Stores: Unique values only
Use for: Membership testing, deduplication
Example: {1, 2, 3}
Methods: add(), has(), delete()

// Using Set for unique values
function hasDuplicate(nums) {
  const seen = new Set();
  for (let num of nums) {
    if (seen.has(num)) return true;
    seen.add(num);
  }
  return false;
}

// Using Map for counting
function topKFrequent(nums, k) {
  const freq = new Map();
  for (let num of nums) {
    freq.set(num, (freq.get(num) || 0) + 1);
  }
  
  // Sort by frequency
  return [...freq.entries()]
    .sort((a, b) => b[1] - a[1])
    .slice(0, k)
    .map(([num]) => num);
}

Performance Considerations

Operation	Average	Worst Case
Lookup	O(1)	O(n)
Insert	O(1)	O(n)
Delete	O(1)	O(n)
Space	O(n)

Worst case O(n) happens when all keys collide (bad hash function or adversarial input). Real-world implementations use good hash functions making this extremely rare.

Interview Tips

1. Recognize Hash Map Patterns

Keywords: "find pair", "group by", "count occurrences", "first/last occurrence"

2. Communicate Trade-offs

"Using a hash map gives us O(1) lookup at the cost of O(n) extra space."

3. Consider Edge Cases

Empty input, single element, all duplicates, no duplicates

4. JavaScript: Map vs Object

Use Map for non-string keys or when order matters. Objects are faster for simple string keys.

Practice Problems

Easy: Valid Anagram, Contains Duplicate, Intersection of Two Arrays
Medium: Top K Frequent Elements, Group Anagrams, Subarray Sum Equals K
Hard: LRU Cache, Substring with Concatenation of All Words, Minimum Window Substring

Head to our practice section to solve these with hints and solutions!

Key Takeaways

Hash maps provide O(1) average lookup, insert, delete
Perfect for: counting, pairing, deduplication, caching
Understanding collisions and load factor shows deep knowledge
Many O(n²) brute force problems → O(n) with hash maps
Trade space for time: O(n) extra space for faster runtime
Sets are hash maps without values (only keys)

Continue Learning

Big O Notation Explained - Understand the complexity analysis behind hash maps
Two Pointers Pattern - Another technique for solving array problems
Sliding Window Technique - Often combined with hash maps for substring problems
Start Practicing - Apply hash map patterns to real problems

Article Details

ByElizabeth (Founder)•February 12, 2025•8 min read

This guide is part of HireReady's interview prep library and is maintained to reflect current hiring practices.

About the Author Contact Privacy Policy Terms Canonical URL

Keep Reading

Data Structures & Algorithms10 min read

Trie Data Structure: Complete Interview Guide

Master the trie (prefix tree) for solving autocomplete, spell checking, and word search problems. Learn implementation, variations, and common interview patterns.

Data Structures & Algorithms9 min read

Stack Pattern: Complete Interview Guide

Master stack patterns for coding interviews. Learn matching brackets, monotonic stack, expression evaluation, and common LeetCode problems.

Algorithm10 min read

Big O Notation Explained

Complete guide to Big O notation, algorithmic complexity, and performance analysis. Learn to calculate time and space complexity from code with real examples.