What is a collision in hash tables? How does Python resolve collisions?

A collision in hash tables occurs when two different keys produce the same hash index. This leads to a conflict when trying to store both values in the same cell.

Python's dictionary implementation uses open addressing with double hashing to resolve collisions. When a collision occurs, Python searches for the next free cell using a specific formula to place the element.

An example of a simplified idea:

# Suppose the hash for key1 and key2 coincides
index = hash(key1) % size
if table[index] is occupied:
    # find the next index using the formula
    index = (index + step) % size
# insert the element

This approach allows for efficient storage and quick retrieval of elements, minimizing collisions and ensuring good performance.