Что такое хеш-функция?

Что такое хеш-функция

Хеш-функция — это одна из фундаментальных концепций в информатике, которая лежит в основе многих важных структур данных и алгоритмов. Объясню от простого к сложному.

Простое объяснение: как работает хеш-функция

Представь, что у тебя есть огромная библиотека с миллионом книг. Вместо того, чтобы искать книгу в каталоге по названию (O(n) или O(log n)), ты используешь специальную систему:

1. Берёшь название книги
2. Пропускаешь через специальную машину (хеш-функцию)
3. Машина выдаёт номер полки (хеш)
4. Ты идёшь прямо на эту полку (O(1))

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

# Пример: обычная хеш-функция в Python
name = "Alice"
hash_value = hash(name)
print(hash_value)  # Большое число, зависит от содержимого

# Если запустишь дважды:
name2 = "Alice"
print(hash(name2))  # ВСЕГДА одно и то же число!

# Но если изменится хотя бы один символ:
name3 = "Bob"
print(hash(name3))  # Совершенно другое число

Ключевые свойства хеш-функции

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

Одинаковый вход всегда даёт одинаковый выход:

# Одна и та же строка — одинаковый хеш
print(hash("hello") == hash("hello"))  # True
print(hash("hello") == hash("Hello"))  # False! (строки разные)

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

Хеш вычисляется за O(1) (константное время):

import time

# Хеш от маленькой строки — микросекунда
start = time.time()
for _ in range(1000000):
    hash("a")
print(f"Small: {time.time() - start:.4f}s")  # ~0.05s

# Хеш от большой строки — немного дольше, но всё равно O(1)
start = time.time()
for _ in range(1000000):
    hash("a" * 1000)
print(f"Large: {time.time() - start:.4f}s")  # ~0.1s

3. Распределение

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

# Проверяем распределение хешей
hashes = {}
for i in range(1000):
    h = hash(i) % 10  # Берём остаток от деления на 10
    hashes[h] = hashes.get(h, 0) + 1

print(hashes)
# Приблизительно: {0: 100, 1: 100, 2: 100, ...}
# Распределение примерно равномерно

4. Коллизии

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

# Коллизии существуют
# Но Python использует разные техники разрешения:
# - Chaining (список элементов с одинаковым хешом)
# - Open addressing (поиск другого свободного места)

# На практике коллизии редкие благодаря хорошей хеш-функции

Практическое применение: Set и Dict

Это самое важное применение хеш-функции в Python:

# Set использует хеш для быстрого поиска
my_set = {1, 2, 3, 4, 5}
print(2 in my_set)  # O(1) — очень быстро!

# Как это работает внутри:
# 1. Вычислить hash(2)
# 2. Найти индекс в таблице: index = hash(2) % table_size
# 3. Проверить элемент в этой позиции

# Dict использует хеш для ключей
my_dict = {'name': 'Alice', 'age': 30}
print(my_dict['name'])  # O(1) — очень быстро!

# Как это работает:
# 1. Вычислить hash('name')
# 2. Найти индекс: index = hash('name') % table_size
# 3. Вернуть значение в этой позиции

Важно: элементы в Set и ключи в Dict должны быть hashable:

# Hashable (можно использовать в Set/Dict)
my_set = {1, "hello", (1, 2), 3.14}  # int, str, tuple - OK

# Не hashable (нельзя использовать в Set/Dict)
my_set = {1, [2, 3]}  # TypeError! List не hashable
my_set = {1, {'key': 'value'}}  # TypeError! Dict не hashable

# Но frozenset (неизменяемый set) — hashable
my_set = {1, frozenset([2, 3])}  # OK!

Как реализовать свою хеш-функцию

# Простая хеш-функция (не для использования в продакшене!)
def simple_hash(s: str, table_size: int = 100) -> int:
    """Вычислить хеш строки"""
    hash_value = 0
    for char in s:
        # Прибавить ASCII значение каждого символа
        hash_value = (hash_value * 31 + ord(char)) % table_size
    return hash_value

print(simple_hash("hello", 10))  # 0
print(simple_hash("world", 10))  # 2
print(simple_hash("hello", 10))  # 0 (детерминированно)

Хеш для пользовательских классов

from dataclasses import dataclass

@dataclass(frozen=True)  # frozen=True делает объект hashable
class User:
    id: int
    name: str

# Теперь User можно использовать в Set и Dict
users = {User(1, "Alice"), User(2, "Bob")}
print(User(1, "Alice") in users)  # True

# Кастомная хеш-функция
class Product:
    def __init__(self, sku: str):
        self.sku = sku
    
    def __hash__(self):
        return hash(self.sku)
    
    def __eq__(self, other):
        return isinstance(other, Product) and self.sku == other.sku

# Теперь Product можно использовать в Set
products = {Product("ABC123"), Product("DEF456")}

Криптографические хеш-функции (SHA, MD5)

Это другой класс хеш-функций, используется для безопасности:

import hashlib

# SHA-256 (криптографическая хеш-функция)
password = "mypassword123"
hash_value = hashlib.sha256(password.encode()).hexdigest()
print(hash_value)  # 8d969eef6ecad3c29a3a873fba8a46bde5d727f36e74a14fa34bc2be5fb4a5b

# Свойства криптографического хеша:
# 1. Маленькое изменение входа - большое изменение выхода
password2 = "mypassword124"
hash_value2 = hashlib.sha256(password2.encode()).hexdigest()
print(hash_value2)  # Совершенно другой

# 2. Невозможно восстановить входные данные из хеша
# Если видишь хеш - не сможешь узнать пароль

# 3. Очень медленный (специально!)
import time
start = time.time()
for _ in range(100000):
    hashlib.sha256(b"password").digest()
print(f"Time: {time.time() - start:.4f}s")  # ~0.5s

Отличие обычной хеш-функции от криптографической:

Обычная хеш-функция (для Set/Dict):
- Быстрая (O(1))
- Просто распределяет данные по индексам
- Легко может быть коллизия
- Пример: hash() в Python

Криптографическая хеш-функция:
- Медленная (специально, для безопасности)
- Не восстанавливается входное значение
- Коллизии практически невозможны
- Маленькое изменение входа - большое изменение выхода
- Примеры: SHA-256, MD5 (deprecated), bcrypt

Практическое применение

# 1. Быстрый поиск в Set
visited = set()
for url in urls:
    if url not in visited:  # O(1) благодаря хешу
        process(url)
        visited.add(url)

# 2. Кэширование (memoziation)
from functools import lru_cache

@lru_cache(maxsize=128)  # Использует хеш для быстрого поиска в кэше
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

# 3. Проверка целостности файла
import hashlib

def file_hash(filename):
    sha256_hash = hashlib.sha256()
    with open(filename, "rb") as f:
        for chunk in iter(lambda: f.read(4096), b""):
            sha256_hash.update(chunk)
    return sha256_hash.hexdigest()

# Если файл изменился - хеш другой
hash1 = file_hash("document.pdf")
time.sleep(1)
hash2 = file_hash("document.pdf")
print(hash1 == hash2)  # True (файл не менялся)

# 4. Хранение паролей
def store_password(password):
    # Никогда не хранишь пароль в открытом виде!
    hashed = hashlib.sha256(password.encode()).hexdigest()
    return hashed

# При проверке:
stored_hash = store_password("user_password")
input_hash = hashlib.sha256("user_password".encode()).hexdigest()
print(stored_hash == input_hash)  # True (пароли совпадают)

Выводы

Хеш-функция — это инструмент, который преобразует данные в индекс для быстрого поиска:

1. Обычная хеш-функция — для Set/Dict, быстрая O(1)
2. Криптографическая хеш-функция — для безопасности, медленная и необратимая
3. Детерминированность — один вход = один выход
4. Коллизии нормальны — язык справляется с ними
5. Hashable объекты — только неизменяемые (int, str, tuple, frozenset)

Хеш-функции — основа всех быстрых структур данных в программировании!