Skip to main content

Hash Tables

Premium

A hash table (also called a hash map or dictionary) stores key–value pairs for fast retrieval. A hash function converts each key into a fixed-size array index, where its value is stored in a bucket. This enables average O(1) lookups, insertions, and deletions.

hash table

Hash tables are interview staples because they:

  • Offer fast lookups by key (average O(1))
  • Reduce algorithm complexity from O(n²) to O(n) in many problems
  • Support flexible keys (strings, numbers, tuples, etc. depending on language)
  • Exist in all major languages:
    • Python: dict
    • Java: HashMap
    • JavaScript: Map
    • C++: unordered_map

Common hash table operations

1. Insert & remove a key

# Create a hash table (dict) table = {} # Insert a key table["apple"] = 5 # Update safely (no KeyError if apple doesn’t exist) table["apple"] = table.get("apple", 0) + 1 # Remove key del table["apple"] # Safe removal (no error) table.pop("apple", None)

2. Access a value by key

value = table.get("apple") # Returns None if missing value = table.get("apple", 0) # Returns 0 if missing

3. Check if a key exists

if "apple" in table: print("found")

4. Loop over entries

for key, value in table.items(): print(key, value)

Hash Tables TC

Calculating memory usage

Dictionaries, sets, and objects in various coding languages are all built on hash tables. For example:

  • Python: Dictionaries, Sets
  • Javascript: Object, Set
  • Java: HashMap, Set

The memory usage of a hash table is complex and varies based on language and implementation. Typically, a hash table requires an array of a fixed size, plus linked lists to store the entries.

Common edge cases & pitfalls

  1. Updating before initializing: Forgetting to check if a key exists before incrementing or modifying it.

  2. Memory leaks from unbounded growth: Not removing outdated or unused keys, leading to unnecessary memory use (e.g., stale cache entries).

  3. Assuming key order: In most languages, hash table key order is not guaranteed (unless using an ordered map). Relying on iteration order can cause nondeterministic bugs.

  4. Using mutable keys: In Python, lists can’t be dict keys; in Java, keys need stable hashCode() and equals().

  5. Shallow copy pitfalls: Copying a hash table incorrectly can lead to references to the same nested objects — causing accidental mutations elsewhere.

Quiz

  1. What’s the average-time complexity of hash table lookup?

a) O(log n)

b) O(n)

c) O(1)

d) O(n²)

  1. What’s wrong with this frequency counter?
Python
counts = {}
for x in items:
    counts[x] += 1

a) It’s O(n²)

b) It overwrites previous counts

c) It may raise a KeyError for new keys

d) It sorts the keys automatically

Practice problems

Next Lesson