Что хотят услышать интервьюеры:

При совпадении хеша возникает коллизия: два разных ключа попадают в одно и то же место таблицы. Важно понимать, что хеш-таблица не полагается только на хеш — она дополнительно сравнивает сами ключи. Хороший ответ должен показать знание способов обработки коллизий и их влияния на производительность.

Определение:

Коллизия в хеш-таблице — это ситуация, когда разные значения дают одинаковый хеш или попадают в один и тот же индекс массива. Это нормальный и ожидаемый случай, а не ошибка. Для корректной работы таблица должна уметь хранить несколько элементов в одном бакете и отличать их по исходным ключам.

В Python при доступе к элементу сначала вычисляется хеш ключа, затем по найденному месту сравнивается сам ключ на равенство. Если там уже лежит другой объект с таким же хешем, используется механизм разрешения коллизий, чтобы найти нужную ячейку или добавить новый элемент.

Пример использования:

class BadHash:
    def __init__(self, value):
        self.value = value

    def __hash__(self):
        return 42  # намеренно одинаковый хеш для всех объектов

    def __eq__(self, other):
        return isinstance(other, BadHash) and self.value == other.value


d = {
    BadHash("a"): 1,
    BadHash("b"): 2
}

print(d[BadHash("a")])  # 1
print(d[BadHash("b")])  # 2

Пояснение кода:

Здесь два разных объекта BadHash("a") и BadHash("b") возвращают одинаковый хеш 42. Это создаёт коллизию при вставке в словарь.
Когда Python ищет BadHash("a"), он сначала попадает в общий диапазон, где могут лежать объекты с таким же хешем, а затем вызывает __eq__, чтобы найти именно тот ключ, у которого value == "a".
То же самое происходит для BadHash("b"): одинаковый хеш не мешает словарю различать ключи, потому что используется ещё и сравнение на равенство.

Ключевые моменты:

Коллизия — это нормальная ситуация, а не поломка хеш-таблицы.
Одинаковый хеш не означает, что ключи одинаковые: всегда есть проверка ==.
Коллизии могут снижать производительность, потому что поиск становится менее близким к O(1).
Хеш-таблицы используют механизм разрешения коллизий: например, цепочки или открытое адресование.
В Python корректная работа словаря зависит от согласованности __hash__ и __eq__.
Если два объекта равны по ==, их хеши должны быть одинаковыми.

Объясните, что происходит, когда два различных входных значения получают одинаковый хеш в хеш-таблице.