Hash Maps (Dictionaries)

DSA · Hashing

Theory

A hash map stores key-value pairs and finds the value for a key in average O(1) time. It works by passing the key through a hash function that converts it to an index in an internal array of buckets. To insert, Python hashes the key and stores the pair in that bucket; to look up, it hashes the key again and goes straight to the bucket, instead of scanning every element. Python's dict is a highly optimised hash map that also keeps insertion order. Keys must be hashable (immutable types like str, int, tuple). Hash maps are the single most useful structure in coding interviews: counting frequencies, grouping items, caching results and the famous Two Sum problem all rely on them.

Why we use it

They turn many O(n^2) "search inside a loop" solutions into O(n) by remembering what you have already seen. Lookups, inserts and deletes are all O(1) on average.

When to use it

Use a hash map when you need to look something up by a key, count occurrences, group related items or memoise results. Use a sorted structure instead when you need keys in order or range queries.

How it works

  1. For each item
  2. Key already in map? Yes: Update value (e.g. count + 1). No: Insert key with initial value.
  3. Continue with next item
  4. Use map for O(1) lookups, counts and grouping

Syntax

d[key] = value          insert/update  O(1) avg
d.get(key, default)     lookup         O(1) avg
key in d                membership     O(1) avg
del d[key]              delete         O(1) avg
Worst case (many collisions)          O(n)

Example

from collections import Counter, defaultdict

# 1. Frequency count
words = "to be or not to be".split()
freq = {}
for w in words:
    freq[w] = freq.get(w, 0) + 1
print("Counts:", freq)
print("Counter:", Counter(words).most_common(2))

# 2. Grouping
employees = [("Asha", "Eng"), ("Ravi", "Sales"), ("Meera", "Eng")]
by_dept = defaultdict(list)
for name, dept in employees:
    by_dept[dept].append(name)
print("Grouped:", dict(by_dept))

# 3. Two Sum in O(n)
def two_sum(nums, target):
    seen = {}
    for i, n in enumerate(nums):
        if target - n in seen:
            return [seen[target - n], i]
        seen[n] = i

print("Two Sum:", two_sum([2, 7, 11, 15], 9))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic