Можно ли всегда гарантировать уникальность хеша?

Можно ли всегда гарантировать уникальность хеша

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

Принцип Дирихле (Pigeonhole Principle)

Если функция хеша выводит N бит (2^N возможных значений), а входных данных больше чем 2^N, то по крайней мере два разных входа будут иметь одинаковый хеш.

# Пример с малым пространством хешей
def simple_hash(obj: str) -> int:
    """Хеш в диапазоне 0-9 (только 10 возможных значений)"""
    return sum(ord(c) for c in obj) % 10

print(simple_hash("abc"))  # Например: 3
print(simple_hash("bac"))  # Может быть тоже 3

# С бесконечным количеством строк и только 10 хешами гарантирована коллизия

Python хеши (64-бит на 64-бит системе)

Пython использует 64-битные хеши. Это означает всего 2^64 возможных значений хешей.

import sys

print(sys.hash_info)  # Информация о хеш-функции

# Максимальный хеш
print(hash("test"))  # Случайное число до 2^63

# Но объектов в памяти может быть намного больше 2^64
# (если рассматривать все возможные объекты, когда-либо существовавшие)

Математическое доказательство неизбежности коллизий

# Birthday Paradox — парадокс дня рождения
# Если у нас есть хеши из 2^N возможных значений,
# то вероятность коллизии превышает 50% уже при sqrt(2^N) объектов

import math

def probability_collision(num_hashes: int, space_size: int) -> float:
    """Вероятность коллизии при num_hashes хешах из space_size возможных"""
    # Приближение: P = 1 - e^(-n^2 / 2m)
    n = num_hashes
    m = space_size
    return 1 - math.exp(-n * n / (2 * m))

# Для 64-битного хеша (2^64 возможных значений)
space = 2**64

# При 2^32 объектах (4 миллиарда)
print(probability_collision(2**32, space))  # ~0.5 (50% вероятность)

# При 1 миллионе объектов
print(probability_collision(1_000_000, space))  # Очень мало

# При 10 миллиардов объектов
print(probability_collision(10_000_000_000, space))  # Близко к 100%

Практические примеры коллизий

Пример 1: Целочисленные хеши

# Встроенные целые числа хешируются по себе
print(hash(42))   # 42
print(hash(42.0)) # 42 (то же самое!)
print(hash(True)) # 1
print(hash(1))    # 1 (то же самое!)

# Коллизии:
print(42 == 42.0)  # True
print(1 == True)   # True

# В словаре это проблема?
d = {}
d[1] = "int"
d[True] = "bool"
print(d)  # {1: 'bool'} — True перезаписал 1, так как 1 == True

Пример 2: Строки

# Python использует SipHash для строк (случайный seed)
# Каждый запуск может дать разные хеши для одной строки

# Но внутри одного запуска, хеши одной строки консистентны
print(hash("python"))  # Фиксированное значение для этого запуска
print(hash("python"))  # То же значение

# Но найти коллизию можно
for i in range(1000000):
    if hash(f"string_{i}") == hash("python"):
        print(f"Коллизия найдена: string_{i}")
        break

Как Python справляется с коллизиями в dict

Python использует открытую адресацию в словарях для разрешения коллизий.

class SimpleDict:
    def __init__(self, size=10):
        self.table = [None] * size
        self.size = size
    
    def __setitem__(self, key, value):
        # Вычисляем индекс по хешу
        index = hash(key) % self.size
        
        # Если место занято, ищем следующее свободное место
        while self.table[index] is not None:
            existing_key, _ = self.table[index]
            if existing_key == key:
                # Перезаписываем
                self.table[index] = (key, value)
                return
            # Перемещаемся дальше (linear probing)
            index = (index + 1) % self.size
        
        # Вставляем в свободное место
        self.table[index] = (key, value)
    
    def __getitem__(self, key):
        index = hash(key) % self.size
        
        while self.table[index] is not None:
            existing_key, value = self.table[index]
            if existing_key == key:
                return value
            index = (index + 1) % self.size
        
        raise KeyError(key)

# Использование
d = SimpleDict()
d["alice"] = 25
d["bob"] = 30
print(d["alice"])  # 25

Почему это важно: безопасность хешей

Проблема 1: Уязвимость DoS (Denial of Service)

# В старых версиях Python можно было создать данные,
# которые специально вызывают коллизии
# Это замедляет операции со словарями до O(n)

# Решение: Python 3.3+ использует random seed
import sys
print(hash("test"))  # Каждый запуск может быть разным
print(os.environ.get('PYTHONHASHSEED', 'not set'))

Проблема 2: Криптографические хеши не гарантируют уникальность

import hashlib

# MD5 (broken)
hash_md5_1 = hashlib.md5(b"data1").hexdigest()
hash_md5_2 = hashlib.md5(b"data2").hexdigest()
print(len(hash_md5_1))  # 32 символа (128 бит)

# SHA-256
hash_sha_1 = hashlib.sha256(b"data1").hexdigest()
print(len(hash_sha_1))  # 64 символа (256 бит)

# Но существуют коллизии даже для SHA-256 (теоретически)
# и уже найдены для MD5 и SHA-1

Практические подходы к гарантированию уникальности

1. Использовать UUID вместо хеша

import uuid

# UUID гарантирует (практически) уникальность
id1 = uuid.uuid4()
id2 = uuid.uuid4()

print(id1 == id2)  # False (вероятность коллизии 1 на 10^36)

# Для словаря
d = {id1: "data1", id2: "data2"}

2. Комбинировать хеш с сравнением значений

class SafeDict:
    def __init__(self):
        self.data = {}  # hash -> list of (key, value)
    
    def __setitem__(self, key, value):
        h = hash(key)
        if h not in self.data:
            self.data[h] = []
        
        # Ищем существующий ключ
        for i, (k, v) in enumerate(self.data[h]):
            if k == key:
                self.data[h][i] = (key, value)
                return
        
        # Добавляем новую пару
        self.data[h].append((key, value))
    
    def __getitem__(self, key):
        h = hash(key)
        if h in self.data:
            for k, v in self.data[h]:
                if k == key:
                    return v
        raise KeyError(key)

# Python dict уже делает это внутренне

3. Для критичных приложений использовать криптографические хеши

import hashlib

def secure_hash(data: str) -> str:
    """Криптографический хеш для хранения паролей"""
    return hashlib.sha256(data.encode()).hexdigest()

# Или использовать bcrypt для паролей
import bcrypt

salt = bcrypt.gensalt()
hashed = bcrypt.hashpw(b"password", salt)
print(bcrypt.checkpw(b"password", hashed))  # True

Выводы

1. Коллизии неизбежны — это математический факт
2. Python это знает — dict обрабатывает коллизии через открытую адресацию
3. Проверять == важно — хеш только первый фильтр, окончательное сравнение через ==
4. Для критичной уникальности — используй UUID, не хеши
5. Для безопасности — используй bcrypt/argon2, не простые хеши
6. Birthday Paradox — коллизии при sqrt(2^n) объектов, не 2^n