Review & Cheat Sheet

This is a review and cheat sheet for Hashing and Maps.

Key Takeaways

  1. Hashing is the technique of mapping a large data set to a smaller range of indices (buckets) using a Hash Function.
  2. Collisions occur when two different keys map to the same index. They are handled via Separate Chaining (Linked List) or Open Addressing (Probing).
  3. Hash Map (Key-Value) and Hash Set (Unique Keys) are the most versatile data structures.
  4. Time Complexity: Average Case O(1) for Insert, Delete, and Search. Worst Case O(N) (collisions).
  5. Common Patterns:
    • Frequency Map: Counting occurrences (Anagrams).
    • Difference Lookup: target - current (Two Sum).
    • Prefix Sum + Hash Map: Subarray Sum Equals K.

Interactive Flashcards

Collision

When two different keys hash to the same index/bucket.

Load Factor

Ratio of elements to buckets. High load factor = more collisions. Usually resize at 0.75.

Chaining

Handling collisions by storing a linked list of items in each bucket.

LRU Cache

Least Recently Used. Uses Hash Map + Doubly Linked List for O(1) operations.

Cheat Sheet

Operation Average Case Worst Case
Insert O(1) O(N)
Delete O(1) O(N)
Search O(1) O(N)
Space O(N) O(N)

Java & Go Reference

Java

// HashMap
Map<String, String> map = new HashMap<>();
map.put("key", "val");      // Put
String val = map.get("key"); // Get
if (map.containsKey("key")) { // ContainsKey
  map.remove("key");        // Remove
}

// HashSet
Set<Integer> set = new HashSet<>();
set.add(1);                 // Add
if (set.contains(1)) {      // Contains
  set.remove(1);            // Remove
}

Go

// Map
m := make(map[string]string)
m["key"] = "val"             // Put
val := m["key"]              // Get
if _, exists := m["key"]; exists { // ContainsKey
  delete(m, "key")           // Remove
}

// Set (using map with empty struct)
s := make(map[int]struct{})
s[1] = struct{}{}            // Add
if _, exists := s[1]; exists { // Contains
  delete(s, 1)               // Remove
}

Next Steps

Now that you’ve mastered Hashing, it’s time to dive into Recursion, where functions call themselves!

For practice, head over to the Problem Vault.