Какая скорость вставки в Dictionary?

# Скорость вставки в Dictionary Python

Вставка в словарь (dictionary) в Python имеет среднюю временную сложность O(1) — это константное время, независимо от количества элементов в словаре. Это одна из главных причин, почему dict так широко используется в Python.

Как это работает под капотом

Dictionary в Python реализован с помощью hash table — таблицы хеширования. Процесс вставки состоит из нескольких этапов:

1. Вычисление хеша ключа

key = "username"
hash_value = hash(key)  # hash("username") → -5978932812500765308

Пайтон вычисляет хеш-значение ключа с помощью встроенной функции hash(). Хеш — это целое число, которое служит "отпечатком пальца" объекта.

2. Расчёт индекса в таблице

# Смещение вычисляется как: index = hash_value % table_size
table_size = 256  # (обычно степень двойки)
index = hash_value % table_size

По хеш-значению вычисляется индекс в массиве таблицы хеширования.

3. Поиск свободной ячейки (при коллизии)

Если ячейка занята другим ключом (коллизия хеша), используется linear probing или другой метод разрешения коллизий:

# Примерная логика разрешения коллизий
def find_slot(hash_value, key, table):
    index = hash_value % len(table)
    step = 1
    
    while True:
        if table[index] is None:  # Свободная ячейка
            return index
        elif table[index].key == key:  # Ячейка с тем же ключом
            return index
        else:  # Коллизия, пробуем следующую ячейку
            index = (index + step) % len(table)
            step += 1

4. Вставка значения

# Финальная вставка O(1)
dictionary[index] = (key, value)

Теоретическая сложность

O(1) в среднем случае при условии:

• Равномерное распределение хеш-значений
• Коэффициент заполнения (load factor) остаётся в приемлемом диапазоне (обычно 0.66)

O(n) в худшем случае (очень редко):

• Все ключи имеют одинаковый хеш (плохо подобранная функция хеша)
• Таблица почти полностью заполнена

Однако на практике это практически не встречается благодаря качественной хеш-функции Python.

Реальные тесты производительности

import timeit
from typing import Dict

# Тест вставки элементов
def test_insertion_speed():
    d: Dict[int, str] = {}
    
    # Вставка 100,000 элементов
    start = timeit.default_timer()
    for i in range(100_000):
        d[i] = f"value_{i}"
    end = timeit.default_timer()
    
    print(f"Вставка 100k элементов: {(end - start) * 1000:.2f} ms")
    print(f"Среднее время на одну вставку: {(end - start) / 100_000 * 1_000_000:.3f} µs")
    # Результат: ~0.0-0.1 µs на одну вставку (зависит от CPU)

# Сравнение с List
def compare_insertion_methods():
    # Dictionary - O(1)
    time_dict = timeit.timeit(lambda: {i: i**2 for i in range(10_000)}, number=1000)
    
    # List - O(1) amortized, но требует копирования при расширении
    def build_list():
        lst = []
        for i in range(10_000):
            lst.append(i)
        return lst
    
    time_list = timeit.timeit(build_list, number=1000)
    
    print(f"Dictionary создание: {time_dict:.3f}s")
    print(f"List создание: {time_list:.3f}s")
    print(f"Dict быстрее в {time_list / time_dict:.1f}x раз")

test_insertion_speed()
compare_insertion_methods()

Оптимизация вставки

1. Предварительное выделение памяти (Python обычно делает это автоматически)

# Dict автоматически увеличивает размер при необходимости
d = {}
for i in range(1_000_000):
    d[i] = i  # Python сам управляет расширением таблицы

2. Выбор типов ключей

# Хорошо: Небольшие целые числа и строки
dict_int = {i: i for i in range(100_000)}  # Быстро
dict_str = {f"key_{i}": i for i in range(100_000)}  # Быстро

# Медленнее: Кортежи больших размеров
dict_tuple = {(i, i, i, i, i): i for i in range(100_000)}  # Медленнее

# Проблема: Пользовательские объекты без хорошей __hash__
class BadHash:
    def __hash__(self):
        return 42  # Все объекты имеют одинаковый хеш!

bad_dict = {BadHash(): i for i in range(100)}  # Деградация к O(n)

3. Использование defaultdict для частых вставок

from collections import defaultdict

# Вместо проверки существования ключа
def slow_append():
    d = {}
    for item in items:
        if item not in d:
            d[item] = []
        d[item].append(value)

# Быстрее: defaultdict обрабатывает создание автоматически
def fast_append():
    d = defaultdict(list)
    for item in items:
        d[item].append(value)  # Вставка за O(1) гарантирована

Почему O(1) важна для приложений

# Кеширование результатов функции
cache: Dict[str, any] = {}

def expensive_function(key: str) -> any:
    if key in cache:  # O(1) поиск
        return cache[key]
    
    result = compute_expensive(key)
    cache[key] = result  # O(1) вставка
    return result

# Подсчёт частоты элементов
from collections import Counter

word_freq = Counter()
for word in huge_text.split():
    word_freq[word] += 1  # O(1) вставка/обновление

# Проверка уникальности
seen = set()  # Set также использует хеш-таблицу
for element in data:
    if element in seen:  # O(1) проверка
        print("Дублирован")
    seen.add(element)  # O(1) вставка

Заключение

• Скорость вставки: O(1) в среднем случае — константное время
• На практике: вставка одного элемента занимает микросекунды
• Масштабируемость: вставка 1 млн элементов занимает столько же времени на элемент, что и 1000 элементов
• Идеальна для: кеширования, подсчёта частот, проверки уникальности, индексирования

Это делает Dictionary идеальной структурой данных для большинства задач, требующих быстрого поиска и вставки.