Hash Tables

DSA · Hashing

Theory

A hash table stores key-value pairs. A hash function converts each key into an index in an internal array, so insert, lookup and delete take O(1) on average. Different keys can map to the same index (a collision); implementations resolve this with chaining or probing, and resize the array when it gets too full. Python dict is a highly optimised hash table.

Why we use it

Hash tables give near-constant-time lookups, which turns many O(n²) solutions into O(n).

When to use it

Use them for counting, caching, indexing records by ID, grouping, de-duplication and the classic two-sum pattern.

How it works

  1. key
  2. hash(key) -> integer
  3. index = hash % table_size
  4. Bucket already has other keys? Yes: Collision: chain or probe. No: Store (key, value).
  5. Lookup repeats the same hash: O(1) average

Syntax

d = {}
d[key] = value        insert   O(1) avg
d.get(key, default)   lookup   O(1) avg
del d[key]            delete   O(1) avg
key in d              membership O(1) avg
Worst case (all collisions): O(n)

Example

words = "to be or not to be that is the question".split()
counts = {}
for w in words:
    counts[w] = counts.get(w, 0) + 1
print("Word counts:", counts)

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
    return None

print("Two sum indexes:", 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