HashMaps & HashSets

This lesson on HashMaps & HashSets is hands-on and example-driven. You will master the internal mechanics of hash tables, including key-to-index translation, collision resolution via chaining, and runtime trade-offs. You will be able to justify when hash table operations run in O(1) average time versus O(N) worst-case time in technical interviews.

What You'll Be Able To Do

• Trace the three-step key translation pipeline from raw key to array index.
• Identify the two primary theoretical causes of hash collisions.
• Implement collision resolution using linked list chaining inside array buckets.
• Execute end-to-end put and get operations while handling key updates and collisions.
• Evaluate runtime performance differences between average-case O(1) and worst-case O(N) scenarios.

Detailed Concept Walkthrough

1. Internal Structure and Index Mapping

A hash table uses a fixed-size underlying array paired with a deterministic translation pipeline to map arbitrary keys to valid array slots. It bridges infinite potential input keys to a finite set of memory addresses.

• Translation Pipeline: The process converts an input key into an integer hash code using a hash function, which is then mapped into a valid array index via modulo arithmetic (index = hash_code % array_size). This ensures every key targets a valid bucket.
• Under the Hood: Fixed-size arrays provide true O(1) direct memory access when given an index. The hash code itself is an intermediate representation, not the final index, because the hash code range is far larger than the allocated array buffer.
• Nuance: The underlying array size must remain constrained for memory efficiency. Consequently, remapping large hash codes down to a smaller index range inevitably causes different hash codes to compete for the same physical index.

def get_bucket_index(key: str, array_size: int) -> int:
    # Step 1: Generate integer hash code from raw key
    hash_code = hash(key)
    # Step 2: Remap hash code into the fixed array index bounds
    index = hash_code % array_size
    return index

# Example usage with array of size 10
idx = get_bucket_index("user_123", 10)
print(f"Bucket index: {idx}")

Key Takeaway: The hash code is an intermediate integer that must be compressed into a valid array boundary via index mapping.

2. Collision Mechanics and Chaining

Collisions occur when two distinct keys map to the exact same array index. Chaining resolves this by storing a linked list (or dynamic bucket) of key-value pairs at each array index.

• Collision Origins: Collisions arise from two separate sources: two distinct keys producing the exact same hash code, or two different hash codes yielding the same remainder during modulo array indexing.
• Chaining Mechanism: Each array bucket holds a linked list containing (key, value) pairs. When a collision occurs, the new pair is appended to the linked list residing at that computed index.
• Under the Hood: Storing the key alongside the value in each node is mandatory. Because multiple distinct keys share the same bucket, the lookup process must compare the target key against each stored key to identify the correct entry.

class HashNode:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None

class SimpleHashTable:
    def __init__(self, size=10):
        # Underlying array initialized with empty bucket heads
        self.buckets = [None] * size
        self.size = size

Key Takeaway: Buckets must store both keys and values so chained elements can be differentiated during traversal.

3. Operational Flow for Put and Get

Inserting and retrieving data requires traversing the hash-index pipeline and searching the target bucket's linked list to match keys exactly.

• Put Execution Flow: Compute the target index, access the bucket, and traverse its linked list. If the key already exists, overwrite its value in place; if the key is not found, append a new node to the chain.
• Get Execution Flow: Compute the index using the key's hash code, navigate to the bucket, and linearly scan the linked list comparing node keys. Return the matching value, or return null/error if the list ends without a match.
• Best Practice: Always check for an existing key match before appending a new node to avoid creating duplicate key entries within the same chain.

def put(self, key, value):
    index = hash(key) % self.size
    head = self.buckets[index]
    curr = head
    while curr:
        if curr.key == key:  # Key exists; update value in place
            curr.value = value
            return
        curr = curr.next
    # Key not found; insert new node at head of chain
    new_node = HashNode(key, value)
    new_node.next = self.buckets[index]
    self.buckets[index] = new_node

Key Takeaway: Both insertion and lookup depend on exact key equality checks while scanning the bucket chain.

4. Runtime Complexity and Degradation

Hash tables offer O(1) average-case time complexity, but degrade to O(N) worst-case time complexity when collisions cluster entries into long chains.

• Average Case O(1): Under a uniform hash distribution, keys spread evenly across all buckets, resulting in short, constant-length chains (O(1) search time).
• Worst Case O(N): If a flawed hash function maps all keys to the exact same index, the table degrades into a single linked list, requiring linear O(N) traversals for lookups, insertions, and deletions.
• Interview Context: State O(1) as the standard operational expectation for hash lookups, but explicitly qualify that this assumption relies on a good hash function with minimal clustering.

# Average Case: Uniform distribution across buckets (O(1) lookup)
# [Bucket 0] -> ('a', 1)
# [Bucket 1] -> ('b', 2)
# [Bucket 2] -> ('c', 3)

# Worst Case: Pathological collision / bad hash function (O(N) lookup)
# [Bucket 0] -> ('a', 1) -> ('b', 2) -> ('c', 3) -> ('d', 4)
# [Bucket 1] -> None
# [Bucket 2] -> None

Key Takeaway: O(1) lookup performance is conditional on uniform distribution; excessive collisions degrade performance to O(N).

Topics Covered in HashMaps & HashSets

1. Hash Table Definition and Utility (0:00 - 1:08) — Explains why hash tables are fundamental for fast key-value lookups in algorithmic problem solving.
2. Internal Structure and Index Mapping (1:08 - 1:51) — Covers the key-to-hash-code generation and modulo array index remapping pipeline.
3. Collision Mechanics and Limits (1:51 - 2:11) — Identifies why collisions are mathematically inevitable due to finite address spaces.
4. Collision Resolution using Chaining (2:11 - 3:06) — Demonstrates using linked lists at bucket indices to store multiple key-value pairs.
5. Put and Get Operational Flow (3:06 - 3:43) — Walks through key lookup, node traversal, and in-place value updating during insertions.
6. Runtime Complexity Analysis (3:43 - 4:52) — Contrasts standard O(1) average time with O(N) worst-case degradation under severe collisions.

DSA for Interviews Cheat Sheet

• hash(key) — Generates integer hash code from key

  code = hash("user_id_42")
  

• hash_code % array_size — Maps hash code to array index

  idx = hash("user_id_42") % 16
  

• dict[key] = value — Inserts or updates key-value pair

  lookup_table["alpha"] = 100
  

• dict.get(key, default) — Retrieves value safely with fallback

  val = lookup_table.get("alpha", None)
  

• key in dict — Checks if key exists in table

  if "alpha" in lookup_table: pass
  

• del dict[key] — Removes key and associated value

  del lookup_table["alpha"]
  

Comparison Table

Common Pitfalls

• Mistake: Assuming the raw hash code is the final array index. Avoid: Remapping the hash code via modulo array size to fit memory bounds.
• Mistake: Storing only the value in a chained collision bucket. Avoid: Storing both key and value to disambiguate collisions during list traversal.
• Mistake: Quoting O(1) lookup time without stating distribution assumptions. Avoid: Explicitly stating that O(1) relies on a uniform hash function to prevent O(N) degradation.

FAQs

• Why are collisions theoretically inevitable? The domain of potential keys is infinite, whereas the set of integer hash codes and array indices is strictly finite.
• Why must the key be stored inside the linked list node alongside the value? Because multiple distinct keys can map to the same bucket, the lookup algorithm must inspect the key of each node to find the exact match.
• What causes an entire hash table to degrade to O(N) performance? A poor hash function or high collision rate that clusters all keys into a single bucket linked list causes linear degradation.
• What happens during a put operation when an existing key is inserted again? The table traverses the chain at the mapped index, matches the existing key, and updates its value in place without adding a new node.