Hashing and Hash Tables

Why hashing matters

Now that we've covered Arrays and Strings, Sorting and Searching, Graphs, and Recursion and Backtracking, you're ready for one of the most common interview tools: hash tables.

Hash tables power Python's dict and set. They let you answer questions like:

• Have I seen this value before?
• How many times did this item appear?
• Is there a matching partner for this number?
• Can I group records by an ID?

In finance-style problems, think: trade IDs, ticker symbols, account IDs, and timestamps. You often need fast lookup more than sorted order.

The core promise: trade a bit of memory for very fast access.

From key to location

A hash table stores values using a key.

A hash function converts the key into a number, and that number helps choose where the item lives internally.

key: "AAPL"
   ↓ hash function
hash number: 728391...
   ↓ mapped to table slot
bucket location

You usually do not write the hash function yourself in Python interviews. Python handles it inside dict and set.

Your job is to recognize when a problem needs:

• quick membership checks
• key → value lookup
• counting
• grouping
• remembering previous work

This builds directly on the Time and Space Complexity Analysis lesson: hash tables are popular because average lookup, insert, and delete are usually O(1).

Python's hash table tools

In Python, the two main hash-based structures are:

• dict: maps key → value
• set: stores unique values and supports fast membership checks

Use a dict when you need associated information. Use a set when you only care whether something exists.

Run this small example:

```python
# dict: key -> value
positions = {
    "AAPL": 50,
    "MSFT": 20
}

positions["AAPL"] += 10
positions["GOOG"] = 5

print("AAPL position:", positions["AAPL"])
print("All positions:", positions)

# set: membership only
seen_trade_ids = set()
seen_trade_ids.add("T100")
seen_trade_ids.add("T101")

print("Have we seen T100?", "T100" in seen_trade_ids)
print("Have we seen T999?", "T999" in seen_trade_ids)
```

You are given a list of trade IDs and need to quickly detect whether an ID appears more than once.

Which structure is the best first choice?

When keys land together

A hash function maps many possible keys into a limited internal table. Sometimes two different keys map to the same place. This is called a collision.

"AAPL" ─┐
        ├──> same bucket
"MSFT" ─┘

Python handles collisions for you, so you usually do not implement collision logic in interviews.

But you should know the performance story:

• Average case lookup/insert/delete: O(1)
• Worst case, with many bad collisions: O(n)
• In practical Python interview use: assume average O(1) unless the interviewer asks deeper

Also remember the tradeoff: hash tables use extra space to get speed.

Fill in the blank:

In a well-behaved hash table, average key lookup is ___ time.

Fill in the blank: _____________

Frequency maps

A very common interview pattern is: count how often each thing appears.

This is called a frequency map.

You can use it for:

• most common ticker
• first repeated value
• valid anagram checks
• character counts
• duplicate detection with counts

Example: count trades per ticker.

```python
trades = ["AAPL", "MSFT", "AAPL", "GOOG", "MSFT", "AAPL"]

counts = {}

for ticker in trades:
    if ticker not in counts:
        counts[ticker] = 0
    counts[ticker] += 1

print(counts)
print("AAPL trades:", counts["AAPL"])

# A shorter Python version:
counts2 = {}
for ticker in trades:
    counts2[ticker] = counts2.get(ticker, 0) + 1

print(counts2)
```

True or false:

Using a hash table often improves lookup speed by using extra memory.

Remember what you need

Another classic hash table pattern is: while scanning, store what would help you later.

For example, in a two-sum style problem:

Given numbers and a target, find two numbers that add to the target.

Instead of trying every pair, keep a dictionary of numbers you've already seen.

For each number x, ask:

needed = target - x
Have I seen needed before?

This avoids the nested-loop approach from earlier array practice.

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

    for i, x in enumerate(nums):
        needed = target - x

        if needed in seen:
            return [seen[needed], i]

        seen[x] = i

    return []

print(two_sum([8, 3, 11, 2], 10))  # 8 + 2
print(two_sum([4, 7, 1, 9], 8))   # 7 + 1
```

Interview checklist

When you see a problem, ask:

1. Do I need fast lookup?

   • Use set for existence.
   • Use dict for key → value.

2. Am I counting things?

   • Use a frequency map.

3. Am I matching pairs or complements?

   • Store what you've seen so far.

4. Am I grouping by a shared property?

   • Use a dictionary where each key points to a list.

5. What is the complexity?

   • Usually O(n) time for one pass.
   • Usually O(n) extra space.

Hash tables are one of the biggest upgrades in your interview toolkit. Next, we'll look at a different style of decision-making with Greedy Algorithms.