What is a hash collision and what methods exist to resolve it?

A hash collision occurs when two different input values produce the same hash function value. This is inevitable because the set of possible inputs is usually larger than the set of possible hash values.

Methods for resolving collisions:

1. Open addressing — when a collision occurs, the next free cell is searched according to a certain sequence (linear, quadratic probing, double hashing).
2. Chaining — each cell in the hash table stores a linked list of all elements with the same hash value.
3. Rehashing — a different hash function is used when a collision occurs.

Example with chaining in Python:

hash_table = [[] for _ in range(10)]

def insert(key, value):
    index = hash(key) % 10
    hash_table[index].append((key, value))

insert('apple', 1)
insert('papel', 2)  # collision possible