Что происходит при коллизии ключей в dictionary?

Что происходит при коллизии ключей в dictionary

Этот вопрос о реализации хеш-таблицы в Python и том, как она разрешает конфликты. Это глубокое погружение в CPython internals.

1. Основной механизм: хеширование

# Когда мы создаём словарь:
d = {"apple": 1, "banana": 2, "cherry": 3}

# Внутри Python создана хеш-таблица (hash table)
# Вычисляется хеш каждого ключа:

print(hash("apple"))   # 6357535495662763244
print(hash("banana"))  # 8768435673826854677
print(hash("cherry"))  # 8765431228949756788

# Хеш преобразуется в индекс массива (bucket):
# index = hash(key) % size_of_table

# Типично size = 8, 16, 32, 64, 128... (степени 2)
table_size = 8
index_apple = hash("apple") % table_size   # Индекс в таблице
index_banana = hash("banana") % table_size
index_cherry = hash("cherry") % table_size

2. Что такое коллизия

Коллизия — когда два разных ключа получают одинаковый индекс:

# Пример коллизии
key1 = "hello"
key2 = "world"  # Может дать тот же индекс

hash1 = hash(key1)
hash2 = hash(key2)

table_size = 4
index1 = hash1 % table_size  # Допустим, 2
index2 = hash2 % table_size  # Тоже 2! Коллизия!

# Оба ключа хотят быть на позиции 2
# Что делать?

3. Метод разрешения: Open Addressing

Python использует Open Addressing (проб), а точнее Quadratic Probing

Оформление хеш-таблицы Python:

Позиция:  0    1    2    3    4    5    6    7
TABLE:  [None][None][None][None][None][None][None][None]

Вставляем ключ "apple" (hash % 8 = 3):
TABLE:  [None][None][None]["apple"=1][None][None][None][None]

Вставляем ключ "banana" (hash % 8 = 3) — КОЛЛИЗИЯ!

Открытое обращение (Open Addressing):
1. Пробуй позицию 3: занято
2. Пробуй следующую: 3 + 1^2 = 4: свободно!

TABLE:  [None][None][None]["apple"=1]["banana"=2][None][None][None]

Вставляем ключ "cherry" (hash % 8 = 3) — ЕЩЁ КОЛЛИЗИЯ!

Проб:
1. Пробуй позицию 3: занято
2. Пробуй 3 + 1^2 = 4: занято
3. Пробуй 3 + 2^2 = 7: свободно!

TABLE:  [None][None][None]["apple"=1]["banana"=2][None][None]["cherry"=3]

Формула quadratic probing:

и = h(k) + c1*i + c2*i^2  (mod m)

В Python примерно:
for i in range(1, table_size):
    new_index = (initial_hash + i^2) % table_size

4. Практический пример на Python

class SimpleHashTable:
    def __init__(self, size=8):
        self.size = size
        self.table = [None] * size
        self.count = 0
    
    def hash_function(self, key):
        return hash(key) % self.size
    
    def insert(self, key, value):
        initial_index = self.hash_function(key)
        index = initial_index
        
        # Quadratic probing
        i = 1
        while self.table[index] is not None:
            # Если ключ уже существует — обновляем
            if self.table[index][0] == key:
                self.table[index] = (key, value)
                return
            
            # Попытаемся другой индекс
            index = (initial_index + i ** 2) % self.size
            i += 1
            
            if i > self.size:
                # Таблица переполнена!
                self._resize()
                return self.insert(key, value)
        
        # Нашли пустой слот
        self.table[index] = (key, value)
        self.count += 1
        
        # Если таблица переполнилась (load factor > 0.66)
        if self.count > self.size * 0.66:
            self._resize()
    
    def search(self, key):
        initial_index = self.hash_function(key)
        index = initial_index
        
        i = 1
        while self.table[index] is not None:
            if self.table[index][0] == key:
                return self.table[index][1]
            
            index = (initial_index + i ** 2) % self.size
            i += 1
            
            if i > self.size:
                return None  # Не найдено
        
        return None
    
    def _resize(self):
        """Увеличиваем таблицу (rehashing)"""
        old_table = self.table
        self.size *= 2
        self.table = [None] * self.size
        self.count = 0
        
        # Перехешируем все элементы
        for item in old_table:
            if item is not None:
                self.insert(item[0], item[1])

# Использование
ht = SimpleHashTable()
ht.insert("apple", 1)
ht.insert("banana", 2)
ht.insert("cherry", 3)

print(ht.search("banana"))  # 2
print(ht.table)  # Внутренняя структура

5. Реальная реализация Python (CPython)

Современный Python (3.6+) использует Compact Hash Tables:

# В CPython 3.6+ словарь хранит:

# 1. Компактный индексный массив (small indices)
# 2. Отдельный array entries для хранения данных

# Это экономит память и улучшает cache locality

import sys

d = {"a": 1, "b": 2, "c": 3}

print(f"Dictionary size: {sys.getsizeof(d)} bytes")
# Output: ~240 bytes для маленького словаря

# Для сравнения, старый способ (Python < 3.6):
# Требовалось ~1400+ bytes для того же словаря

6. Load Factor и Rehashing

# Load Factor = количество элементов / размер таблицы

load_factor = len(dictionary) / size_of_hash_table

# Когда load_factor > 2/3 (0.66):
# 1. Коллизии растут
# 2. Поиск становится медленнее
# 3. Python увеличивает таблицу вдвое
# 4. Все элементы перехешируются (дорого!)

# Демонстрация:
d = {}
for i in range(100):
    d[i] = i
    if i in [7, 15, 31, 63]:  # После каждого rehash
        print(f"Элементов: {len(d)}, Size: ?")

# Rehashing происходит при:
# 1 → 8 → 16 → 32 → 64 → 128 → 256 → ...

7. Почему именно quadratic probing

# Альтернативы:

# 1. Linear probing (простой)
index = (h + i) % size  # 3, 4, 5, 6, ...
# Минус: clustering (скопления элементов)

# 2. Quadratic probing (Python использует)
index = (h + i^2) % size  # 3, 4, 6, 11, 19, ...
# Плюсы: лучше распределение, меньше clustering

# 3. Double hashing
index = (h1 + i * h2) % size
# Плюсы: очень хорошее распределение
# Минусы: медленнее (вторая хеш-функция)

# 4. Chaining (другой подход)
# Каждый bucket содержит linked list
# Плюсы: легко удалять
# Минусы: больше памяти, pointer'ы

8. Визуализация коллизии

# Симуляция коллизий

from collections import defaultdict

def simulate_hash_table(keys, size=8):
    table = defaultdict(list)
    collisions = 0
    
    for key in keys:
        index = hash(key) % size
        
        if table[index]:
            collisions += 1
        
        table[index].append(key)
    
    print(f"Table size: {size}")
    print(f"Keys: {len(keys)}")
    print(f"Collisions: {collisions}")
    print(f"Load factor: {len(keys) / size:.2f}")
    print("\nDistribution:")
    
    for i in range(size):
        print(f"  Bucket {i}: {table[i]}")

# Плохое распределение (много коллизий)
keys = ["apple", "apricot", "avocado", "apricot"] * 5
simulate_hash_table(keys, size=4)

# Output:
# Table size: 4
# Keys: 20
# Collisions: 15
# Load factor: 5.00  (очень плохо!)
# Distribution:
#   Bucket 0: много элементов
#   Bucket 1: мало
#   Bucket 2: много
#   Bucket 3: мало

9. Производительность

import timeit

# При низком load factor (мало коллизий)
# O(1) поиск, вставка, удаление

d = {i: i for i in range(1000)}
start = timeit.timeit(lambda: d[999], number=100000)
print(f"Поиск в маленьком словаре: {start:.4f}s")  # ~0.001s

# При высоком load factor (много коллизий)
# Деградирует к O(n) в худшем случае

# Но обычно load factor не превышает 0.66
# Так что O(1) гарантирован

10. Hash-интовских-функций и безопасность

# Python использует SipHash по умолчанию для безопасности
# Это защищает от hash collision attacks

# Атака: создать ключи с одинаковым хешем
# Результат: O(n) вместо O(1)
# Защита: random seed для каждого процесса

hash("test")  # Разный в каждый раз (при PYTHONHASHSEED)

# Можно отключить для воспроизводимости:
# export PYTHONHASHSEED=0
# python script.py

11. Практический пример: отладка коллизий

from collections import Counter

def analyze_dictionary(d):
    """Анализировать коллизии в словаре"""
    
    # CPython не даёт прямой доступ к внутренней структуре,
    # но можно косвенно анализировать
    
    hashes = [hash(key) for key in d.keys()]
    print(f"Unique hashes: {len(set(hashes))}")
    print(f"Total keys: {len(d)}")
    
    # Распределение хешей по модулю 256
    indices = [h % 256 for h in hashes]
    counter = Counter(indices)
    
    print(f"\nDistribution (mod 256):")
    print(f"  Max in bucket: {counter.most_common(1)[0][1]}")
    print(f"  Empty buckets: {256 - len(counter)}")
    print(f"  Load factor: {len(d) / 256:.3f}")

# Пример
d = {f"key_{i}": i for i in range(100)}
analyze_dictionary(d)

Итоговая таблица: что происходит

┌─────────────────────────────────────────────┐
│ 1. Ключ получает хеш                       │
├─────────────────────────────────────────────┤
│ 2. Хеш → индекс в таблице (hash % size)  │
├─────────────────────────────────────────────┤
│ 3. Проверка: есть ли в таблице[индекс]? │
├─────────────────────────────────────────────┤
│ 4. Если пусто → вставить здесь            │
├─────────────────────────────────────────────┤
│ 5. Если занято → quadratic probing        │
│    (пробуем индекс + 1², + 4, + 9, ...)  │
├─────────────────────────────────────────────┤
│ 6. Нашли пустой слот → вставить           │
├─────────────────────────────────────────────┤
│ 7. Если load factor > 2/3 → rehashing     │
│    (увеличиваем таблицу в 2 раза)        │
└─────────────────────────────────────────────┘

Вывод

При коллизии ключей в Python dictionary:

1. Используется Quadratic Probing — пробуем соседние позиции
2. Формула: (initial_hash + i²) % size
3. Rehashing при load factor > 2/3 — таблица удваивается
4. Средняя сложность O(1) — коллизии разрешаются быстро
5. Современный Python использует compact hash tables для экономии памяти

Это один из самых интересных аспектов CPython internals и показывает, почему словари такие мощные в Python!