← Назад к вопросам
Может ли хеш функция возвращать одинаковое значение для разных входных?
1.0 Junior🔥 121 комментариев
#Другое
Комментарии (1)
🐱
claude-haiku-4.5PrepBro AI22 мар. 2026 г.(ред.)
Ответ сгенерирован нейросетью и может содержать ошибки
Коллизии хешей (Hash Collisions)
Да, хеш функция может возвращать одинаковое значение для разных входных. Это называется коллизией (collision) и является неизбежным свойством всех хеш функций.
Принцип Дирихле (Pigeonhole Principle)
Математически, если у нас есть:
- N возможных входных значений (бесконечно много)
- M возможных выходных значений (конечное число, например 2^64 для hash())
То обязательно существуют различные входы X и Y такие, что hash(X) == hash(Y).
# В Python на 64-bit системе hash возвращает значение от -2^63 до 2^63-1
# Это примерно 18 миллионов миллиардов различных значений
# Но строк в Интернете бесконечно много
# Поэтому коллизии обязательны
x = "string1"
y = "string2"
if hash(x) == hash(y):
print("Коллизия!")
else:
print("Разные хеши (обычно)")
Коллизии в Python dictionary
Dictionary в Python обрабатывает коллизии, поэтому они не являются проблемой:
# Допустим, hash("key1") == hash("key2") (коллизия)
d = {}
d["key1"] = "value1"
d["key2"] = "value2"
# Python всё равно хранит оба значения правильно
print(d["key1"]) # "value1"
print(d["key2"]) # "value2"
print(d) # {'key1': 'value1', 'key2': 'value2'}
# Как это работает?
# 1. hash("key1") и hash("key2") одинаковые
# 2. Python проверяет равенство: "key1" == "key2"?
# 3. Нет, они разные
# 4. Python использует разрешение коллизий (chaining или open addressing)
Как Python разрешает коллизии
Python использует открытую адресацию (open addressing) с "double hashing":
# Упрощённый пример
class SimpleDict:
def __init__(self, size=16):
self.size = size
self.slots = [None] * size
self.keys = [None] * size
def _find_slot(self, key):
h = hash(key) % self.size
# Если коллизия - пробуем следующий слот
while self.slots[h] is not None:
if self.keys[h] == key:
return h
h = (h + 1) % self.size
return h
def __setitem__(self, key, value):
h = self._find_slot(key)
self.slots[h] = value
self.keys[h] = key
def __getitem__(self, key):
h = self._find_slot(key)
return self.slots[h]
# Работает даже с коллизиями
d = SimpleDict()
d["a"] = 1
d["b"] = 2
print(d["a"]) # 1
print(d["b"]) # 2
Вероятность коллизии (Birthday Paradox)
Коллизии становятся вероятнее при увеличении количества элементов:
import math
# Вероятность хотя бы одной коллизии
# P(collision) ≈ 1 - e^(-n^2 / 2m)
# Где n = количество элементов, m = размер пространства хешей
def collision_probability(n, m):
"""n элементов, m возможных хешей"""
if n > m:
return 1.0
return 1 - math.exp(-(n * n) / (2 * m))
# На 64-bit системе: m = 2^64 = 18 квинтиллионов
m = 2**64
# При 1000 элементов
print(f"Коллизия при 1000 элементах: {collision_probability(1000, m):.2%}") # ~0.00%
# При 1 миллиарде элементов
print(f"Коллизия при 1M элементах: {collision_probability(1_000_000, m):.2%}") # ~0.00%
# Нужно примерно sqrt(m) ≈ 4 миллиарда элементов чтобы вероятность была 50%
print(f"Коллизия при 2^32 элементах: {collision_probability(2**32, m):.2%}") # ~39%
Примеры коллизий
# Попробуем найти коллизию (может занять долго)
import hashlib
# SHA-256 имеет размер 256 бит
# Вероятность коллизии намного выше, чем случайные совпадения
# Известная коллизия в MD5 (криптографическая хеш функция)
# Это примеры, которые специально подобраны для MD5:
hash1_input = b'\xd1\x31\xdd\x02\xc5\xe6\xee\xc4\x69\x3d\x13\xa8\x02\x00\x20\x03'
hash2_input = b'\xd1\x31\xdd\x02\xc5\xe6\xee\xc4\x69\x3d\x13\xa8\x02\x00\x28\x03'
# У них одинаковый MD5 хеш!
# Но это не значит, что MD5 плохой для dictionary - только для криптографии
Почему это не проблема для Python dict
# Даже если два ключа имеют коллизию, dict работает правильно
# Потому что использует двойную проверку:
# 1. Проверка хеша (быстро)
# 2. Проверка равенства (медленнее, но точно)
class BadHash:
"""Плохой класс - всегда возвращает один хеш"""
def __init__(self, value):
self.value = value
def __hash__(self):
return 42 # Всё имеет одинаковый хеш!
def __eq__(self, other):
return self.value == other.value
def __repr__(self):
return f"BadHash({self.value})"
d = {}
d[BadHash(1)] = "one"
d[BadHash(2)] = "two"
d[BadHash(3)] = "three"
print(d[BadHash(1)]) # "one" - работает!
print(d[BadHash(2)]) # "two" - работает!
print(len(d)) # 3 - все элементы хранятся правильно
# Но это медленнее, т.к. Python проверяет все элементы с одинаковым хешем
Криптографические vs обычные хеш функции
# Обычный хеш (hash() в Python)
# - Быстрый
# - Не криптографический (не защищен от атак)
# - Может быть предсказуем (для защиты от DOS используется salt)
print(hash("test")) # Разное значение при каждом запуске Python 3.3+
# Криптографический хеш (SHA-256, MD5, и т.д.)
# - Медленнее
# - Защищён от коллизий (основной требование)
# - Предназначен для безопасности, а не для dict
import hashlib
m = hashlib.sha256()
m.update(b"test")
print(m.hexdigest()) # Одно и то же значение всегда
# MD5 имеет известные коллизии (криптографически скомпрометирован)
# SHA-256 считается безопасным
# SHA-3 ещё безопаснее
Практические последствия
1. Performance
# ❌ Плохо - может быть много коллизий
class User:
def __init__(self, name):
self.name = name
def __hash__(self):
return 1 # Все пользователи имеют один хеш!
# Если использовать в dict - будет O(n) вместо O(1)
users = {}
for i in range(1000000):
users[User(f"User{i}")] = i
# Поиск будет медленный (проверит тысячи элементов с одинаковым хешем)
# ✅ Хорошо - хеш распределён равномерно
class GoodUser:
def __init__(self, name):
self.name = name
def __hash__(self):
return hash(self.name) # Зависит от имени
2. Безопасность
# Используй криптографические хеши для:
# - Проверки целостности файлов
# - Хранения паролей (с солью)
# - Цифровых подписей
import hashlib
# ❌ Плохо - просто hash()
password_hash = hash("password123")
# ✅ Хорошо - криптографический хеш с солью
import secrets
salt = secrets.token_bytes(32)
password_hash = hashlib.pbkdf2_hmac('sha256', b'password123', salt, 100000)
Итого
- Да, хеш функции могут возвращать одинаковое значение для разных входов
- Это нормально - это называется коллизия и неизбежно
- Python dict обрабатывает коллизии автоматически, так что не проблема
- Для криптографии нужны специальные функции (SHA-256, не hash())
- Для обычного программирования коллизии не заметны благодаря двойной проверке (хеш + равенство)