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

Сложность доступа по ключу в словаре (Dictionary)

Это фундаментальный вопрос о структурах данных. Ответ: O(1) — константная сложность в среднем, O(n) в худшем случае.

Как работает словарь?

Словарь (Dictionary) реализован как хеш-таблица (hash table). Основная идея:

# Python словарь
person = {
    "name": "Alice",
    "age": 30,
    "email": "alice@example.com"
}

# Доступ по ключу — O(1) в среднем
age = person["age"]  # Очень быстро!

# Также O(1):
person["city"] = "Moscow"  # Добавление
del person["email"]  # Удаление
"name" in person  # Проверка наличия

Что происходит под капотом?

1. Hash function — преобразует ключ в индекс массива:

# Упрощённое объяснение
def hash_function(key):
    # Преобразует строку/число в целое число
    hash_value = hash(key)
    # Находит индекс в массиве размера m
    index = hash_value % m
    return index

# Пример
key = "age"
index = hash_function(key)  # Например, 7
array[7] = 30

1. Direct access — идём сразу к индексу:

# Вместо того, чтобы искать по всем элементам
# for i in range(len(dict)):
#     if dict[i]["key"] == "age":
#         return dict[i]["value"]

# Делаем прямой доступ за O(1):
index = hash("age") % len(dict)
return dict[index]

Почему O(1) в среднем?

Главное преимущество хеш-таблицы — прямой доступ по индексу, без поиска:

# Array access — всегда O(1)
array[5] = value
x = array[5]

# Linked list search — O(n)
current = head
while current:
    if current.key == "age":
        return current.value
    current = current.next

Что такое hash collision?

Иногда разные ключи дают одинаковый индекс:

# Коллизия хешей
hash("age") % 8 == 3
hash("city") % 8 == 3  # Одинаковый индекс!

Решение: chaining или open addressing

Chaining (цепочки)

Если индекс занят, добавляем элемент в linked list:

# Визуально:
# Index 0: None
# Index 1: None
# Index 2: None
# Index 3: ("age", 30) -> ("city", "Moscow") -> None
# Index 4: None

Доступ при коллизии:

# Ищем по цепочке
index = hash("city") % 8  # 3
current = table[3]
while current:
    if current.key == "city":
        return current.value  # Нашли!
    current = current.next

Сложность: O(1 + α), где α = n/m (load factor):

• n — количество элементов
• m — размер массива
• Если n ≈ m, то O(1)
• Если n >> m, то α большой, ищем дольше — приближается к O(n)

Сравнение структур данных

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

# O(1) операции со словарём
d = {}

# Вставка — O(1)
d["key"] = "value"

# Доступ — O(1)
val = d["key"]

# Удаление — O(1)
del d["key"]

# Проверка наличия — O(1)
if "key" in d:
    pass

# Все эти операции — ОЧЕНЬ быстро, даже на 1 миллионе элементов!

# Правильно:
print(d["target"])  # Сразу O(1), без цикла!

Выводы

• Средний случай: O(1) — основная причина использования словарей
• Худший случай: O(n) — редко в нормальной практике
• Load factor критичен для производительности
• Python автоматически увеличивает размер словаря при заполнении (rehashing)
• Словари оптимальны для: быстрого поиска по ключу, кешей, счётчиков и группировки данных, графов

В Data Science словари часто используются в Pandas (индексирование), поэтому понимание их сложности критично для оптимизации!