Что считается хорошей хеш-функцией, а что нет?

Хорошие и плохие хеш-функции

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

Свойства ХОРОШЕЙ хеш-функции

1. Детерминированность

import hashlib

# Хорошо: одинаковый вход → одинаковый выход
value = "hello"
hash1 = hashlib.sha256(value.encode()).hexdigest()
hash2 = hashlib.sha256(value.encode()).hexdigest()

assert hash1 == hash2  # Истина
print(f"Hash: {hash1}")
# 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824

2. Равномерное распределение (Uniform Distribution)

import hashlib

def hash_distribution_test(inputs, buckets=100):
    """Проверяем равномерность распределения"""
    distribution = [0] * buckets
    
    for item in inputs:
        hash_val = int(hashlib.md5(str(item).encode()).hexdigest(), 16)
        bucket = hash_val % buckets
        distribution[bucket] += 1
    
    # Хорошее распределение: каждый bucket ~1/100 от всех хешей
    avg = len(inputs) / buckets
    variance = sum((x - avg)**2 for x in distribution) / buckets
    
    return distribution, variance

inputs = list(range(10000))
dist, var = hash_distribution_test(inputs, buckets=100)

print(f"Variance: {var:.2f}")
# Хорошо: variance низкая (равномерное распределение)
# Плохо: variance высокая (кластеризация)

3. Лавинный эффект (Avalanche Effect)

import hashlib

# Хорошо: малое изменение входа → большое изменение выхода
value1 = "password"
value2 = "passwore"  # одна буква изменена

hash1 = hashlib.sha256(value1.encode()).hexdigest()
hash2 = hashlib.sha256(value2.encode()).hexdigest()

print(f"Hash1: {hash1}")
print(f"Hash2: {hash2}")
# Хеши совершенно разные, хотя входы отличаются на 1 букву

# Плохо: похожие входы → похожие выходы
# (видно, что функция линейна или имеет закономерность)

4. Быстрое вычисление

import time
import hashlib

# Хорошо: быстрое вычисление
data = "x" * 1000000  # 1MB

start = time.time()
for _ in range(1000):
    hash_val = hashlib.sha256(data.encode()).hexdigest()
end = time.time()

print(f"Time: {end - start:.4f}s")  # ~0.3-0.5s на 1000 операций

# Плохо: медленное вычисление
# (например, криптографическая функция на маленьких данных — оверкилл)

5. Невозможность обратного преобразования (One-way)

import hashlib

# Хорошо: невозможно восстановить исходное значение
original = "secret"
hash_val = hashlib.sha256(original.encode()).hexdigest()

print(f"Original: {original}")
print(f"Hash: {hash_val}")
# Нет способа из hash_val получить "secret"

# Плохо:
def bad_hash(x):
    return x * 7 % 1000

hash_val = bad_hash(123)  # 861
# Можно попытаться подобрать исходное значение (brute force)

6. Устойчивость к коллизиям (Collision Resistance)

import hashlib

# Хорошо: найти два разных входа с одинаковым хешем сложно
# SHA-256: требуется ~2^128 попыток (практически невозможно)

# Плохо: коллизии найдены
# MD5: есть известные коллизии, не безопасен
# CRC32: много коллизий (используется для проверки, не безопасности)

def simple_hash(x):
    return x % 100

# Легко найти коллизии:
assert simple_hash(5) == simple_hash(105)  # True
assert simple_hash(10) == simple_hash(110)  # True

Примеры хороших функций

# SHA-256 (криптографическая)
import hashlib
hash_val = hashlib.sha256(b"data").hexdigest()

# MD5 (быстрая, но уже небезопасная)
hash_val = hashlib.md5(b"data").hexdigest()

# Python's hash() (для словарей)
hash_val = hash("key")  # встроенная, оптимизирована

# MurmurHash (быстрая, равномерная)
# pip install mmh3
import mmh3
hash_val = mmh3.hash("data")

Примеры плохих функций

# 1. Просто модуль
def bad_hash_1(x):
    return x % 1000
# Проблема: много коллизий (x, x+1000, x+2000 → одинаковый хеш)

# 2. Просто сумма цифр
def bad_hash_2(x):
    return sum(int(d) for d in str(x))
# Проблема: 123 и 321 имеют одинаковый хеш

# 3. Первые N символов
def bad_hash_3(s):
    return s[:5]
# Проблема: "hello_world" и "hello_universe" имеют одинаковый хеш

# 4. CRC32 для безопасности
import zlib
hash_val = zlib.crc32(b"data")
# Проблема: уязвим, есть коллизии, не криптографический

В контексте ML и Big Data

# PySpark: хеширование для partition-ирования
from pyspark.sql import SparkSession

spark = SparkSession.builder.appName("Example").getOrCreate()

df = spark.createDataFrame([
    (1, "Alice"), (2, "Bob"), (3, "Charlie")
], ["id", "name"])

# Рейнер должен распределить данные равномерно
df_hashed = df.repartition(4, "id")  # использует хеширование

# Если хеш-функция плохо распределяет:
# → data skew (некоторые партиции переполнены)
# → медленная обработка

Таблица сравнения

Резюме

Хорошая хеш-функция:

• Детерминирована
• Равномерно распределяет значения
• Имеет лавинный эффект (small change → big change)
• Быстрая
• Устойчива к коллизиям
• Невозможно обратить (если критично)

Плохая:

• Неравномерное распределение (clustering)
• Легко найти коллизии
• Медленная
• Предсказуемая (похожие входы → похожие выходы)