How does Python handle hash collisions in dictionaries?

Python Data Structures - Interview Questions and Answers

How Python Handles Hash Collisions in Dictionaries

Python dictionaries use a hash table internally, where keys are stored based on their hash values. A hash collision occurs when two different keys generate the same hash value. To handle this, Python uses open addressing with probing.

1. Dictionary Structure

A Python dictionary consists of:

A dynamic array (hash table): Stores key-value pairs.
A hash function: Computes a hash for the key.
Collision resolution strategy: Handles cases where two keys have the same hash.

2. Collision Resolution: Open Addressing

Python uses open addressing with probing to resolve collisions. This means:

If a hash collision occurs, Python searches for the next available empty slot.
The search follows a probing sequence (e.g., linear probing or quadratic probing).

Example of Hash Collision

d = {}
d[1] = "One"
d[2] = "Two"

# Assume hash(1) and hash(2) collide
# Python finds an empty slot for the second key

Even if two keys collide, they still get stored separately due to probing.

3. Steps Python Follows When Inserting a Key

Compute hash(key) % table_size → Finds the initial slot.
If the slot is empty, store (key, value).
If the slot is occupied (collision occurs):
- Check if the key already exists (update value).
- If not, find the next available slot using probing.
If too many collisions occur, Python resizes the dictionary.

4. Example: How Python Handles Collisions

class SimpleDict:
    def __init__(self, size=5):
        self.size = size
        self.table = [None] * size  # Simulated hash table

    def _hash(self, key):
        return hash(key) % self.size  # Simulate Python's hash function

    def insert(self, key, value):
        index = self._hash(key)
        while self.table[index] is not None:
            if self.table[index][0] == key:  # Update value if key exists
                self.table[index] = (key, value)
                return
            index = (index + 1) % self.size  # Linear probing
        self.table[index] = (key, value)

    def display(self):
        print(self.table)

# Example usage
d = SimpleDict()
d.insert(1, "One")
d.insert(6, "Six")  # Hash collision if size=5 (1 and 6 share index)
d.display()

* Uses linear probing to handle collisions.

5. Dictionary Resizing to Reduce Collisions

When the dictionary gets too full, Python doubles its size.
All keys are rehashed and redistributed.

6. Summary

Concept	Python Dictionary Handling
Hashing	`hash(key) % table_size`
Collisions	Open Addressing (Probing)
Probing Strategy	Linear or Quadratic Probing
Resizing	Doubles size to reduce collisions