Что будет, если у двух элементов будет одинаковый хеш?

1️⃣ Как кратко ответить

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

2️⃣ Подробное объяснение темы

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

Зачем это нужно

Хеширование позволяет быстро находить, добавлять и удалять элементы в структурах данных. Хеш-таблицы, например, обеспечивают среднее время доступа O(1), что делает их очень эффективными для многих приложений, таких как базы данных и кэширование.

Где применяется

Хеширование используется в:

• Хеш-таблицах для быстрого поиска данных.
• Криптографии для обеспечения безопасности данных.
• Контрольных суммах для проверки целостности данных.
• Уникальных идентификаторах, таких как UUID.

Как работает

Пример хеш-таблицы

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

class HashTable:
    def __init__(self, size):
        # Инициализация хеш-таблицы с заданным размером
        self.size = size
        self.table = [[] for _ in range(size)]
​
    def hash_function(self, key):
        # Простая хеш-функция, которая возвращает остаток от деления длины ключа на размер таблицы
        return len(key) % self.size
​
    def insert(self, key, value):
        # Вставка элемента в хеш-таблицу
        index = self.hash_function(key)
        # Добавление пары ключ-значение в список по индексу
        self.table[index].append((key, value))
​
    def search(self, key):
        # Поиск элемента в хеш-таблице
        index = self.hash_function(key)
        # Проход по списку в ячейке таблицы для поиска ключа
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

• __init__: Инициализирует хеш-таблицу с заданным размером. Каждая ячейка таблицы содержит пустой список для хранения элементов с одинаковым хешем.
• hash_function: Простая хеш-функция, которая вычисляет индекс на основе длины ключа. Это упрощенный пример, в реальных приложениях используются более сложные функции.
• insert: Вставляет элемент в таблицу. Вычисляет индекс с помощью хеш-функции и добавляет пару ключ-значение в соответствующий список.
• search: Ищет элемент в таблице. Вычисляет индекс и проходит по списку в этой ячейке, чтобы найти нужный ключ.

Как решаются коллизии

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