1.2 Hashing (Hash Sets & Hash Maps)

1. What Are Hash Sets & Hash Maps?

In Submodule 1.1, we learned that an Array is fast when you know the index (arr[3]), but slow (O(N)) when you only know the value ("Is the number 42 in this array?").

A Hash Table (called a Hash Set or Hash Map) is a data structure that lets you look up items by value or key in O(1) average time:

• Hash Set (set / unordered_set / HashSet): A collection of unique keys with no duplicates. It answers one question instantly: "Is x in the set?"
• Hash Map (dict / unordered_map / HashMap): A collection of key -> value pairs (like a phone book mapping name -> phone_number, or number -> count_of_times_seen).

2. Why Do We Need Hashing & How Does It Work Under the Hood?

The Pain Without Hashing (O(N^2))

Suppose you have 100,000 numbers and want to find two numbers that add up to 10 (Two Sum), or check if any number appears twice (Contains Duplicate). If you use a plain array:

• For the 1st number, you scan the other 99,999 numbers.
• For the 2nd number, you scan the other 99,998 numbers.
• Total comparisons: roughly 5,000,000,000 (O(N^2)), which times out in every interview!

How a Hash Table Works in 3 Simple Steps

1. ** Underlying Array of Buckets:** Inside memory, a Hash Table is actually just an array of M buckets.
2. The Hash Function (hash(key) % M): When you insert "apple", a mathematical hash function scrambles "apple" into a big integer and takes % M to pick a bucket index (say, Bucket #1) in O(1) time.
3. Collision Handling: What if "avocado" also lands on Bucket #1? That's called a collision. The bucket simply stores a tiny chain of items that landed there. Whenever the table gets ~70% full, it automatically doubles its buckets so every bucket stays tiny (O(1) average lookup).

Step Through the Visual Drawing: One-Pass Two Sum with a Hash Map

Click Next below to watch how a Hash Map turns an O(N^2) pair search into a single O(N) pass:

3. Basic Operations & Syntax (All 4 Languages)

Every operation below—insert, delete, check existence, and read value—runs in O(1) average time:

# 1. Hash Set: Unique items & O(1) membership check
seen = set()
seen.add(25)
exists = 25 in seen      # True (O(1))
seen.discard(25)         # Remove safely (O(1))

# 2. Hash Map (dict): key -> value pairs
counts = {}
counts["apple"] = 1
counts["apple"] = counts.get("apple", 0) + 1  # 2
has_key = "apple" in counts                   # True (O(1))

# 3. 26-Slot Array (Even faster than a Hash Map for 'a'..'z'!)
char_freq = [0] * 26
for ch in "anagram":
  char_freq[ord(ch) - ord('a')] += 1

4. Core Interview Patterns

Pattern A: One-Pass Complement Lookup (Two Sum)

As you loop through nums, you are standing at x and need need = target - x. Instead of scanning the rest of the array, ask your Hash Map: "Have I already seen need earlier in this loop?"

• If yes: return [seen[need], current_index] immediately!
• If no: record seen[x] = current_index and keep walking.

Pattern B: Canonical Signature Grouping (Group Anagrams)

Two words are anagrams ("eat", "tea", "ate") if and only if they have the exact same 26-letter frequency count. Use their 26-count signature (or sorted string) as the key in a Hash Map where the value is the list of words sharing that signature!

Pattern C: Sequence Start Detection (Longest Consecutive Sequence)

Put all numbers in a Hash Set. When standing at x, how do you know if x is the very beginning of a streak like 1, 2, 3, 4? Check if (x - 1) not in num_set! Only start counting x + 1, x + 2... when x - 1 is missing. That guarantees each number is visited at most twice (O(N) total time).

# 1. Complement Lookup (Two Sum):
seen = {}
for i, x in enumerate(nums):
  if target - x in seen:
      return [seen[target - x], i]
  seen[x] = i

# 2. Sequence Start Check (Longest Consecutive):
num_set = set(nums)
for x in num_set:
  if (x - 1) not in num_set:  # Only start at the beginning of a run!
      length = 1
      while (x + length) in num_set:
          length += 1

5. Practice On Your Own (Curated Submodule Problems)