От чего зависит появления коллизии?

Коллизии в хеш-таблицах: причины и зависимости

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

Основные факторы появления коллизий

1. Функция хеширования

Качество хеш-функции — первый и самый важный фактор:

• Плохая хеш-функция: порождает коллизии часто (например, хеш от целого числа как само число)
• Хорошая хеш-функция: распределяет значения равномерно (SHA-256, CRC, MurmurHash)

# Плохая хеш-функция
def bad_hash(key: int, table_size: int) -> int:
    return key % table_size  # Проблема: чётные числа получат чётные индексы

# Лучшая хеш-функция в Python
def good_hash(key: str, table_size: int) -> int:
    return hash(key) % table_size  # Встроенная функция распределяет хорошо

2. Коэффициент заполнения (Load Factor)

Коэффициент α = количество элементов / размер таблицы

Это САМЫЙ КРИТИЧНЫЙ фактор:

• α < 0.5: мало коллизий, много памяти
• α ≈ 0.75: оптимальное соотношение
• α > 1.0: много коллизий, деградация производительности

class HashTable:
    def __init__(self, initial_size=16):
        self.table = [None] * initial_size
        self.size = 0
        self.capacity = initial_size
    
    def should_resize(self) -> bool:
        load_factor = self.size / self.capacity
        return load_factor > 0.75
    
    def insert(self, key, value):
        if self.should_resize():
            self.resize(self.capacity * 2)
        
        index = hash(key) % self.capacity
        # Вставка...

3. Размер хеш-таблицы

• Маленький размер → больше коллизий (α возрастает быстро)
• Большой размер → меньше коллизий, но больше памяти
• Простые размеры: часто выбирают степени 2 (16, 32, 64) или простые числа

# В Python dict использует степени 2
print({}.__sizeof__())  # Начинает с 240 байт (~8 слотов)

4. Распределение входных данных

Кластеризация входных значений:

• Если ключи не случайны, а сгруппированы (например, ID последовательные), коллизии вероятнее
• Например, ключи 1, 2, 3, 4 будут хешироваться в близкие индексы

# Плохо: последовательные числа могут кластеризоваться
for i in range(1000):
    table[i] = i  # Зависит от хеш-функции

# Хорошо: хеш-функция должна декоррелировать входные данные

Вероятность коллизий

Парадокс дней рождения: в группе из 23 человек 50% шанс совпадения дней рождения. Аналогично с хешами:

import math

def collision_probability(n: int, m: int) -> float:
    """n — количество элементов, m — размер таблицы"""
    if n > m:
        return 1.0
    # Приблизительная формула
    return 1 - math.exp(-(n * (n - 1)) / (2 * m))

print(collision_probability(10, 100))    # ~0.45
print(collision_probability(10, 1000))   # ~0.045

Стратегии разрешения коллизий

Коллизии неизбежны, поэтому используют:

1. Цепочки (chaining)

class HashTableChaining:
    def __init__(self, size=16):
        self.table = [[] for _ in range(size)]
        self.size = 0
    
    def insert(self, key, value):
        index = hash(key) % len(self.table)
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                self.table[index][i] = (key, value)
                return
        self.table[index].append((key, value))
        self.size += 1

2. Открытая адресация (linear/quadratic probing)

class HashTableOpenAddressing:
    def insert(self, key, value):
        index = hash(key) % len(self.table)
        i = 0
        while self.table[(index + i) % len(self.table)] is not None:
            i += 1  # Линейный probing
        self.table[(index + i) % len(self.table)] = (key, value)

Вывод

Коллизии зависят от:

1. Качества хеш-функции (35%)
2. Коэффициента заполнения (50%) — самый важный
3. Размера таблицы (10%)
4. Распределения входных данных (5%)

В Python dict и set автоматически масштабируют таблицу, чтобы поддерживать α ≈ 0.66, избегая коллизий.