Understanding Hash Tables

Your speed tool

Now that you've covered Introduction to Data Structures, Mastering Recursion, and Sorting Algorithms, you're ready for one of the most common interview tools: hash tables.

Hash tables power Python's:

• dict for key-value lookup
• set for fast membership checks
• many common patterns like counting, grouping, and detecting duplicates

In the last lesson, sorting helped us impose order. Hash tables often let us skip sorting and answer: "Have I seen this before?" in average constant time.

A key becomes an address

A hash table stores data by transforming a key into an internal location.

Think:

key -> hash function -> bucket/index -> stored value

Example idea:

"cat" -> hash("cat") -> bucket 4 -> 3
"dog" -> hash("dog") -> bucket 1 -> 5

In Python, you usually don't manage buckets yourself. You use dict or set, and Python handles the hashing machinery.

The practical promise is:

• lookup: average O(1)
• insert: average O(1)
• delete: average O(1)

That average-time speed is why hash tables appear constantly in easy and medium problems.

For a well-behaved Python dictionary, what is the average time complexity of checking whether a key exists?

Python's key-value hash table

Use a dict when each item has a key and an associated value.

Common operations:

• create: {}
• assign: scores["Ava"] = 91
• lookup: scores["Ava"]
• safe lookup: scores.get("Ava", 0)
• membership: "Ava" in scores
• delete: del scores["Ava"]

The key idea: if you can name something with a stable key, a dictionary can usually retrieve it fast.

```python
scores = {}

scores["Ava"] = 91
scores["Ben"] = 84
scores["Mia"] = 97

print("Ava's score:", scores["Ava"])
print("Is Ben recorded?", "Ben" in scores)
print("Noah's score:", scores.get("Noah", "missing"))

scores["Ben"] += 5
print("Updated Ben:", scores["Ben"])

print("All scores:", scores)
```

True or false: In Python, a list like [1, 2, 3] can be used directly as a dictionary key.

Different keys can land together

A collision happens when two different keys map to the same internal bucket.

"cat" -> bucket 4
"tac" -> bucket 4

This does not mean the dictionary breaks. A real hash table has a strategy to resolve collisions.

For problem solving, remember the balanced version:

• Average operations are O(1).
• Worst-case operations can degrade, but Python's implementation is highly optimized.
• You usually reason with average-case performance in coding interviews unless the problem says otherwise.

Also: hash tables use extra memory. You often trade space for speed.

In Python, the built-in hash table used for key-value pairs is called a ____.

Frequency maps

A very common hash table pattern is counting how many times each thing appears.

Use this when a problem asks about:

• duplicates
• most common item
• anagrams
• character counts
• inventory-style totals

The dictionary maps:

item -> count

This avoids repeatedly scanning the list for each item.

```python
words = ["apple", "banana", "apple", "pear", "banana", "apple"]
counts = {}

for word in words:
    counts[word] = counts.get(word, 0) + 1

print(counts)
print("apple appears", counts["apple"], "times")

most_common = max(counts, key=counts.get)
print("most common:", most_common)
```

Sets for fast membership

Use a set when you only care whether a value has appeared, not what value it maps to.

This pattern answers:

Have I seen this before?

It is especially useful for duplicate detection and complement-style problems.

Here is the classic idea behind Two Sum: for each number, ask whether the number you need has already appeared.

```python
def two_sum(nums, target):
    seen = {}  # number -> index

    for i, num in enumerate(nums):
        need = target - num
        if need in seen:
            return [seen[need], i]
        seen[num] = i

    return []

print(two_sum([2, 7, 11, 15], 9))
print(two_sum([3, 2, 4], 6))
```

You are given a list of strings and need to return True if any string appears more than once. Which structure is usually the best first choice?

Lock this in

For this crash course, hash tables should become automatic. Over the next review cycles, revisit these problem types every 2 days:

1. Contains Duplicate — use a set.
2. Valid Anagram — use character counts.
3. Two Sum — use a dictionary of seen values.
4. First Unique Character — count, then scan.

Your decision checklist:

Need fast lookup? -> hash table
Need key -> value? -> dict
Need membership only? -> set
Need counts? -> dict item -> frequency

Next, we'll move into Graph Basics, where dictionaries and sets often help represent connections without slowing down lookups.