Какая сложность вставки в словарь?

Сложность вставки в словарь Python

Вставка в словарь Python имеет среднюю сложность O(1) (константное время), но может достичь O(n) в худшем случае. Это напрямую связано с внутренней реализацией словаря как хеш-таблицы.

Теория: как работает словарь

Хеш-таблица с открытой адресацией

Словарь в Python реализован как динамический массив с хешированием:

my_dict = {"name": "Alice", "age": 30}

# Внутри происходит:
# 1. Вычисляется хеш ключа: hash("name")
# 2. По хешу вычисляется индекс: hash("name") % table_size
# 3. По индексу находится слот в массиве
# 4. Если слот пуст → вставляем
# 5. Если занят → ищем следующий свободный слот (с помощью perturbation)

Сложность операций со словарем

Средняя сложность O(1)

Почему это O(1)?

При хорошем распределении хешей:

• Вычисление хеша ключа: O(1)
• Поиск индекса в таблице: O(1) с вероятностью ~99%
• При коллизии (редко) поиск следующего свободного слота: обычно 1-2 попытки

import time

# Демонстрация O(1) вставки
my_dict = {}
for i in range(1000000):
    my_dict[i] = f"value_{i}"  # Почти одинаковое время на каждую вставку

# Каждая вставка занимает микросекунды, независимо от размера словаря

Худший случай O(n)

Когда может быть O(n)?

1. Плохая функция хеша — все ключи хешируются в один индекс
2. Pathological input — специально подобранные ключи для создания коллизий
3. Во время rehashing — при расширении таблицы все элементы перехешируются

# Пример худшего случая (редко в реальной практике)
class BadHash:
    def __init__(self, value):
        self.value = value
    
    def __hash__(self):
        return 0  # Все объекты хешируются в 0 → всегда коллизия!
    
    def __eq__(self, other):
        return self.value == other.value

# Это вызовет O(n) вставки
bad_dict = {}
for i in range(1000):
    bad_dict[BadHash(i)] = i  # Каждая вставка ищет свободный слот

Реаллокация (Rehashing)

Динамическое расширение таблицы

Когда словарь заполняется на ~2/3, Python расширяет внутреннюю таблицу:

import sys

my_dict = {}
print(sys.getsizeof(my_dict))  # Начальный размер

# При добавлении элементов
for i in range(10):
    my_dict[i] = i
    print(f"Size {i}: {sys.getsizeof(my_dict)} bytes")  # Размер растёт скачками

# Во время rehash вставка может быть O(n) для одной операции,
# но амортизированная сложность остаётся O(1)

Амортизированная сложность O(1)

Амортизированный анализ

Хотя отдельная операция при rehash может быть O(n), средняя стоимость остаётся O(1):

# Вставка n элементов в пустой словарь
my_dict = {}
total_time = 0
rehash_count = 0

for i in range(10000):
    if len(my_dict) * 2 >= capacity:  # Условие реаллокации
        rehash_count += 1
        # Rehash: O(current_size)
    my_dict[i] = i

# Среднее время на вставку: total_time / 10000 = O(1)
# Потому что rehash происходит редко (логарифмически: O(log n) раз)

Python 3.6+ оптимизации

Компактный словарь (Python 3.6+)

Модернизация словарей в Python 3.6 значительно улучшила эффективность:

# До Python 3.6: словарь занимал много памяти
# После Python 3.6: структура более компактна

my_dict = {"a": 1, "b": 2, "c": 3}
# Хранится в порядке вставки
# Таблица хешей отделена от массива значений → меньше памяти

Оптимизация для строковых ключей

# Строки часто используются как ключи
my_dict = {"name": "Alice", "age": 30}
# Python оптимизирует вычисление хешей строк для быстродействия

Практические примеры

Пример 1: Быстрый поиск

# O(1) вставка и поиск
users = {}
for user in large_list:
    users[user.id] = user  # O(1) вставка

# Позже: быстрый поиск
user = users[user_id]  # O(1) поиск

Пример 2: Подсчёт частоты

# Используя словарь для O(1) обновления
from collections import Counter

words = ["apple", "banana", "apple", "cherry", "banana", "banana"]
word_count = {}

for word in words:
    if word in word_count:  # O(1) поиск
        word_count[word] += 1  # O(1) обновление
    else:
        word_count[word] = 1  # O(1) вставка

# Намного быстрее, чем искать в списке list.count(word) → O(n)

Пример 3: Кеширование

# LRU кеш использует словарь для O(1) доступа
cache = {}

def get_user(user_id):
    if user_id in cache:  # O(1)
        return cache[user_id]
    
    user = fetch_from_db(user_id)  # Дорогая операция
    cache[user_id] = user  # O(1) вставка
    return user

Сравнение со списком

# ❌ Медленно: O(n) поиск + O(n) вставка
my_list = []
for i in range(1000):
    if i in my_list:  # O(n) поиск
        pass
    my_list.append(i)  # O(1) вставка в конец

# ✅ Быстро: O(1) поиск + O(1) вставка
my_dict = {}
for i in range(1000):
    if i in my_dict:  # O(1) поиск
        pass
    my_dict[i] = i  # O(1) вставка

Правила при работе со словарём

1. Ключи должны быть хешируемыми: строки, числа, кортежи, frozenset
2. Не меняй ключи в процессе использования (нарушит целостность)
3. Для частых поисков используй словарь вместо списка
4. Амортизированная O(1) означает, что в среднем это O(1), но отдельные операции могут быть медленнее

Словарь — одна из самых важных и эффективных структур данных в Python для быстрого поиска и кеширования!