Какая сложность доступа элемента словаря по ключу в Python?

Какая сложность доступа элемента словаря по ключу в Python?

Сложность доступа к элементу словаря по ключу

Доступ к элементу словаря (dict) по ключу в Python имеет среднюю сложность O(1) — константное время.

Технический механизм: Хеш-таблица

Python реализует словари как хеш-таблицы с использованием внутреннего хеш-массива:

1. hash(key) → вычисление хеша → O(1)
2. index = hash % table_size → преобразование в индекс → O(1)
3. Прямой доступ по индексу в массиве → O(1)

Итого: O(1)

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

Почему O(1)?

Хеш-таблица использует прямую индексацию. Время доступа не зависит от размера словаря:

import time

for size in [100, 1000, 10000, 100000, 1000000]:
    d = {i: i*2 for i in range(size)}
    
    start = time.perf_counter()
    for _ in range(100000):
        x = d[size // 2]
    elapsed = time.perf_counter() - start
    
    print(f"size={size:7d}: {elapsed*1000:.4f} ms")

Результат: время примерно одинаковое, не зависит от размера!

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

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

Сравнение: dict vs list

import time

# Поиск в list — O(n)
lst = list(range(1000000))
start = time.perf_counter()
for _ in range(100000):
    index = lst.index(500000)
elapsed_list = time.perf_counter() - start

# Доступ к dict — O(1)
d = {i: i for i in range(1000000)}
start = time.perf_counter()
for _ in range(100000):
    value = d[500000]
elapsed_dict = time.perf_counter() - start

print(f"List: {elapsed_list:.4f} s")  # ~2 сек
print(f"Dict: {elapsed_dict:.4f} s")  # ~0.01 сек

Dict в 200 раз быстрее!

Практические примеры для Data Science

Быстро: кэш с dict

user_cache = {user_id: user_data for user_id, user_data in users}

for request in requests:
    user = user_cache[request.user_id]  # O(1)

Медленно: поиск в list

for request in requests:
    user = next(u for u in users if u["id"] == request.user_id)  # O(n)

Реальное использование

# Способ 1: Медленный (O(n) для каждого поиска)
def find_employee_slow(emp_id):
    for emp in employees:
        if emp["id"] == emp_id:
            return emp

# Способ 2: Быстрый (O(1) доступ)
employee_dict = {emp["id"]: emp for emp in employees}
def find_employee_fast(emp_id):
    return employee_dict.get(emp_id)

# На 1 млн поисков:
# Способ 1: ~10-20 сек
# Способ 2: ~0.01 сек

Внутренние детали Python 3.6+

Python 3.6+ сохраняет порядок вставки в словарях и имеет оптимизированное хранилище, но это не влияет на сложность O(1) доступа.

Итого

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