What collision resolution methods are you familiar with in hash tables?

In hash tables for collision handling (when two keys hash to the same cell), the following methods are usually used:

1. Chaining method — each cell of the table stores a linked list (or another container) of elements that have fallen into this cell. When a collision occurs, the new element is added to the list.

2. Open addressing — upon collision, the next free cell is searched according to a certain rule (linear probing, quadratic probing, double hashing).

3. Double hashing — used in open addressing, but the step to find the next cell is determined by a second hash function, which reduces clustering.

4. Rehashing — when a certain load factor of the table is reached, a new larger table is created, and all elements are rehashed.

Example of chaining method in Python:

class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]

    def _hash(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        idx = self._hash(key)
        for i, (k, v) in enumerate(self.table[idx]):
            if k == key:
                self.table[idx][i] = (key, value)
                return
        self.table[idx].append((key, value))

    def get(self, key):
        idx = self._hash(key)
        for k, v in self.table[idx]:
            if k == key:
                return v
        return None

This example shows how, in case of a collision, elements are stored in a list (chain) within a single cell.