Hash Functions and Collisions

DSA · Hashing

Theory

A hash function maps a key to an integer; the table uses hash % capacity as the bucket index. A good hash function is fast and spreads keys evenly. When two keys land in the same bucket, chaining stores both in a small list in that bucket, while open addressing probes for the next free slot. The load factor (items ÷ buckets) is kept low by resizing, which keeps operations O(1) on average.

Why we use it

Understanding collisions explains why hash tables are fast on average but can degrade, and how to design your own hashing.

When to use it

This matters when implementing a hash map, choosing keys, explaining worst-case behaviour in interviews, and designing consistent hashing in distributed systems.

How it works

  1. key
  2. Compute hash(key)
  3. Two keys share an index? Yes: Resolve: chaining (list) or open addressing (next slot). No: Store directly.
  4. Load factor too high? Yes: Resize and rehash. No: Continue.
  5. Done

Syntax

index = hash(key) % capacity
Chaining:        buckets[index] = [(k1, v1), (k2, v2)]
Open addressing: try index, index+1, index+2 ...
Resize when load factor > ~0.7

Example

class HashMap:
    def __init__(self, size=4):
        self.buckets = [[] for _ in range(size)]
    def _index(self, key):
        total = 0
        for ch in str(key):
            total = total * 31 + ord(ch)
        return total % len(self.buckets)
    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value
                return
        bucket.append([key, value])
    def get(self, key):
        for k, v in self.buckets[self._index(key)]:
            if k == key:
                return v
        return None

m = HashMap()
for city, pin in [("Pune", 411001), ("Delhi", 110001), ("Goa", 403001), ("Agra", 282001), ("Ooty", 643001)]:
    m.put(city, pin)
print("Delhi PIN:", m.get("Delhi"))
for i, b in enumerate(m.buckets):
    print("Bucket", i, ":", b)

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