Что такое коллизия в контексте программирования и баз данных?

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

Примеры:

• Хеш-таблица: Два разных ключа имеют одинаковый хеш.

# Пример коллизии в хеш-таблице (упрощенный)
class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]

    def _hash(self, key):
        return hash(key) % self.size # Хеш-функция

    def insert(self, key, value):
        index = self._hash(key)
        # Коллизия, если список по этому индексу уже содержит элементы
        self.table[index].append((key, value))

ht = HashTable(10)
ht.insert("apple", 1)
ht.insert("banana", 2)
# Предположим, hash("apple") % 10 == hash("orange") % 10
ht.insert("orange", 3) # Возможно коллизия

• Хеш-индекс в БД:

-- Пример создания хеш-индекса в PostgreSQL
CREATE INDEX idx_hashed_column ON my_table USING hash (hashed_column);
-- Если два значения в hashed_column имеют одинаковый хеш, возникает коллизия

Методы разрешения коллизий:

• Метод цепочек (Chaining): Каждая запись в хеш-таблице или индексе хранит список (связанный список или массив) элементов с одинаковым хешем.
• Метод открытой адресации (Open Addressing): При коллизии ищется следующее свободное место в таблице (линейное, квадратичное пробирование или двойное хеширование).