Что такое Коллизия?

Что такое Коллизия?

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

1. Коллизия в хеш-функциях

Определение: Коллизия — когда hash(x) == hash(y), но x != y

Математически:

hash_func = lambda x: x % 10

# Примеры данных
key1 = "apple"  → hash("apple") = 5
key2 = "grape"  → hash("grape") = 5

# Коллизия! Оба ключа имеют одинаковый хеш

Реальный пример в Python:

# Python использует встроенную хеш-функцию для строк
print(hash("hello"))      # Зависит от версии Python
print(hash("world"))      # Другой хеш

# Но при работе с словарями могут быть коллизии
my_dict = {}
my_dict["key1"] = "value1"
my_dict["key2"] = "value2"

# Внутри Python использует хеш для поиска ключа
# Если два разных ключа имеют одинаковый хеш — коллизия!

2. Как словари/хеш-таблицы справляются с коллизиями

Метод 1: Chaining (Цепочка)

Хранить все значения с одинаковым хешем в списке:

# Внутреннее представление
hash_table = [
    [None],                           # hash = 0
    [("apple", 5), ("grape", 2)],    # hash = 1 (коллизия!)
    [("banana", 3)],                 # hash = 2
    # ...
]

# При поиске "apple":
# 1. Вычислить хеш("apple") = 1
# 2. Найти bucket на позиции 1
# 3. Найти ("apple", value) в цепочке

Плюсы: Простое удаление, работает при высокой нагрузке
Минусы: Если много коллизий — деградация до O(n)

Метод 2: Open Addressing (Открытая адресация)

Найти другой свободный слот в таблице:

# Если hash_table[1] занят, пробуем hash_table[2], затем [3] и т.д.
# Процесс поиска свободного места:
hash_table = [
    None,
    ("apple", 5),      # hash("apple") = 1
    ("grape", 2),      # hash("grape") = 1, но [1] занят, поэтому [2]
    ("banana", 3),
    # ...
]

Плюсы: Лучше локальность памяти, не нужны доп. структуры
Минусы: Удаление сложнее, нужна перехеширование

3. Коллизии в реальном коде Python

# Создание словаря
my_dict = {}
my_dict["name"] = "John"
my_dict["age"] = 30
my_dict["email"] = "john@example.com"

# Внутри Python:
# 1. hash("name") вычисляется
# 2. Индекс = hash("name") % table_size
# 3. Если позиция занята — обработка коллизии

# Можно проверить хеш
print(hash("name"))
print(hash("age"))
print(hash("email"))

# При доступе:
value = my_dict["name"]  # Быстро, потому что O(1) в среднем

4. Коллизии в криптографии

В криптографических хеш-функциях коллизии критичны:

import hashlib

# SHA-256 (криптографическая функция)
hash1 = hashlib.sha256(b"password1").hexdigest()
hash2 = hashlib.sha256(b"password2").hexdigest()

print(hash1)  # a7c7f...something
print(hash2)  # 8f9d2...different

# Если бы существовала коллизия (что очень редко в SHA-256):
# hash("password1") == hash("password2")
# Это позволило бы использовать password2 вместо password1
# КРАЙНЕ ОПАСНО для безопасности!

Хорошие криптографические функции:

• SHA-256, SHA-3: очень сложно найти коллизии
• MD5: УЯЗВИМА к коллизиям (не используй!)
• SHA-1: УЯЗВИМА к коллизиям (не используй!)

5. Вероятность коллизий (Birthday Paradox)

Сюрпризно, коллизии возникают чаще, чем кажется:

import random

# Парадокс дней рождения
# В группе из 23 человек есть 50% вероятность совпадения дня рождения
# Это применимо и к хешам!

# Если хеш-таблица на 100 слотов, вероятность коллизии:
# P(коллизия) ≈ sqrt(n) / sqrt(size)
# P(коллизия) ≈ sqrt(100) / sqrt(size)

# Поэтому нужен хороший load factor (заполненность < 75%)
load_factor = elements / table_size
if load_factor > 0.75:
    # Перехешировать — увеличить размер таблицы
    pass

6. Обработка коллизий в коде

class SimpleHashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]  # Chaining
    
    def _hash(self, key):
        return hash(key) % self.size
    
    def insert(self, key, value):
        index = self._hash(key)
        # Проверяем, есть ли уже такой ключ
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                self.table[index][i] = (key, value)  # Update
                return
        # Новая пара — добавляем
        self.table[index].append((key, value))
    
    def get(self, key):
        index = self._hash(key)
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

# Использование
ht = SimpleHashTable()
ht.insert("name", "John")
ht.insert("age", 30)
print(ht.get("name"))  # "John"

7. Когда коллизии проблематичны

❌ Критично:

• Криптография (SHA-1, MD5 уязвимы)
• Проверка целостности данных
• Подписи документов

✅ Приемлемо:

• Словари (хеш-таблицы справляются)
• Кеши (можно перезаписать)
• Индексирование БД

Выводы

1. Коллизия — когда два разных значения дают одинаковый хеш
2. Обработка: chaining (списки) или open addressing (другие слоты)
3. Вероятность: растет с sqrt(n), поэтому нужен правильный load factor
4. В Python: встроенные dict очень оптимизированы, вам это не видно
5. В криптографии: коллизии опасны, нужны криптостойкие функции