Какво е хеш колизия и какви методи за нейното разрешаване съществуват?

Колизия на хеширане възниква, когато две различни входни стойности дават еднаква стойност на хеш функцията. Това е неизбежно, тъй като множеството възможни входове обикновено е по-голямо от множеството възможни хеш стойности.

Методи за решаване на колизии:

1. Отворена адресация — при колизия се търси следващата свободна клетка по определена последователност (линейно, квадратично, двойно хеширане).
2. Връзки (chaining) — във всяка клетка на хеш таблицата се съхранява свързан списък с всички елементи с еднаква хеш стойност.
3. Рехеширане — при колизия се прилага друга хеш функция.

Пример с връзки в Python:

хеш таблица = [[] for _ in range(10)]

def вмъкни(ключ, стойност):
    индекс = hash(ключ) % 10
    хеш таблица[индекс].append((ключ, стойност))

вмъкни('ябълка', 1)
вмъкни('пам', 2)  # възможна колизия