dict как абстрактный тип

В прошлых уроках мы разобрались с хеш-функцией. Теперь поднимемся на уровень выше — посмотрим на dict как на абстрактный тип данных (ADT). ADT — это контракт: какие операции есть и за какое время они выполняются, без обязательств описывать, как именно это реализовано внутри.

Внутренности Python dict — отдельная история (модуль 9). А контракт прост и сводится к четырём операциям, каждая из которых работает за O(1) в среднем.

Четыре главные операции

set: вставить или обновить

d = {}
d["alice"] = 30        # вставка
d["bob"] = 25          # вставка
d["alice"] = 31        # обновление — alice уже есть
print(d)               # {'alice': 31, 'bob': 25}

Контракт: O(1) average. Внутри dict хеширует ключ, выбирает слот по хешу, и либо вставляет, либо заменяет существующее значение.

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

import time
d = {}
n = 1_000_000

start = time.perf_counter()
for i in range(n):
    d[i] = i
elapsed = time.perf_counter() - start

print(f"{n} inserts: {elapsed:.2f}s, {elapsed*1e9/n:.0f} ns each")
# 1000000 inserts: 0.08s, 80 ns each

80 наносекунд на вставку — это включая ~6-7 resize’ов за миллион вставок. Без resize было бы ~50 ns. Amortization прячет цену resize в среднем.

get: получить значение

Два способа получить значение:

d = {"alice": 30, "bob": 25}

# через [] — выбрасывает KeyError, если нет
print(d["alice"])      # 30
# d["unknown"]         # KeyError: 'unknown'

# через .get() — возвращает None или дефолт
print(d.get("alice"))               # 30
print(d.get("unknown"))             # None
print(d.get("unknown", "default"))  # "default"

Что выбрать? Зависит от смысла:

• d[k] — «ключ обязан быть, иначе это баг — упади красиво».
• d.get(k) — «ключа может не быть — это нормально».

В DE второй вариант чаще, потому что данные часто неполные.

del: удалить

d = {"alice": 30, "bob": 25}
del d["alice"]
print(d)               # {'bob': 25}

# del у несуществующего ключа — KeyError
# del d["alice"]       # KeyError

# безопасный pop с дефолтом
v = d.pop("alice", None)
print(v)               # None

del у Python dict делает tombstone — специальную метку «удалено», чтобы probing мог продолжать через этот слот. Слот не освобождается, пока не произойдёт resize. Это внутренняя деталь, но влияет на поведение: dict, в котором много раз вставляли и удаляли, занимает больше памяти, чем ожидалось.

contains: проверка ключа

d = {"alice": 30}

print("alice" in d)    # True
print("bob" in d)      # False

Это самая частая операция в DE. Если нужно проверить «есть ли user_id в нашем множестве», dict (или set, что то же самое без values) — единственный правильный выбор. list с x in xs даёт O(n), dict — O(1). На миллионе элементов разница — секунды vs миллисекунды.

Гарантия сложности

Что значит «O(1) average» для dict? Это слабее, чем «всегда O(1)», но сильнее, чем «иногда O(1)».

В реальной работе average case — это то, что вы видите всегда. Worst case случается, только если вы намеренно подобрали ключи с одинаковым хешем или написали __hash__ как return 0. Поэтому в практической оценке производительности dict — это O(1), без оговорок.

Что внутри (без deep dive)

Полный разбор внутренностей в модуле 9. Тут — общая картина в три строки:

1. dict хранит данные в массиве слотов — каждый слот это пара (hash, key, value).
2. hash(k) % capacity выбирает начальный слот для ключа. Если слот занят другим ключом — пробуем следующий по специальной формуле (probing).
3. Когда заполнено больше 2/3 — массив resize’ится в 2-4 раза, все ключи перехешируются.

dict vs list — когда использовать что

Самая частая ошибка junior data engineer’а — использовать list там, где нужен dict. Вот сравнение:

# плохо: проверка наличия в list
ids_list = [1, 5, 7, 12, 99, ...]   # 100K элементов
if 99 in ids_list:                  # O(n) — линейный поиск
    do_something()

# хорошо: то же через set (или dict)
ids_set = {1, 5, 7, 12, 99, ...}    # 100K элементов
if 99 in ids_set:                   # O(1) — мгновенно
    do_something()

На 100К in для list — это в среднем 50К сравнений, ~100 микросекунд. Для set — одна операция, ~50 наносекунд. Разница в 2000 раз.

Правило: если вы делаете больше одной проверки in на коллекции, переведите её в set/dict. Стоимость конверсии амортизируется за пару lookup’ов.

Типичные DE-паттерны через dict

Lookup-таблица

# имеем продукты с ценами, заказы со ссылкой на продукт
products = [
    {"id": 101, "price": 250.0},
    {"id": 102, "price": 180.0},
]
orders = [
    {"product_id": 101, "qty": 2},
    {"product_id": 102, "qty": 1},
]

# наивно: O(N*M)
for o in orders:
    for p in products:
        if p["id"] == o["product_id"]:
            o["total"] = p["price"] * o["qty"]

# через lookup-dict: O(N + M)
price_by_id = {p["id"]: p["price"] for p in products}
for o in orders:
    o["total"] = price_by_id[o["product_id"]] * o["qty"]

На 10К заказов и 10К продуктов — 100M сравнений vs 20K lookup’ов. В 5000 раз быстрее.

Группировка по ключу

events = [
    {"user_id": 1, "event": "click"},
    {"user_id": 2, "event": "view"},
    {"user_id": 1, "event": "purchase"},
]

# через setdefault
by_user = {}
for e in events:
    by_user.setdefault(e["user_id"], []).append(e["event"])

# или через defaultdict (см. ниже)
from collections import defaultdict
by_user = defaultdict(list)
for e in events:
    by_user[e["user_id"]].append(e["event"])

print(dict(by_user))
# {1: ['click', 'purchase'], 2: ['view']}

Дедупликация

# дубли по составному ключу
events = [{"user_id": 1, "event": "click"}, ...]
seen = set()
unique = []
for e in events:
    key = (e["user_id"], e["event"])
    if key not in seen:
        seen.add(key)
        unique.append(e)

Заметьте: ключ — tuple (hashable, immutable), а не объединение строк. Это и быстрее, и читаемее.

Counter — частоты

from collections import Counter

words = ["click", "view", "click", "purchase", "click"]
counter = Counter(words)
print(counter)               # Counter({'click': 3, 'view': 1, 'purchase': 1})
print(counter.most_common(2))   # [('click', 3), ('view', 1)]

Counter — это специализированный dict[str, int] для подсчёта. В DE используется для frequency analysis, top-K, дистрибуции значений.

Порядок ключей

Маленькая, но важная деталь. С Python 3.7 dict сохраняет порядок вставки:

d = {"first": 1, "second": 2, "third": 3}
print(list(d))   # ['first', 'second', 'third']

d["fourth"] = 4
print(list(d))   # ['first', 'second', 'third', 'fourth']

Это гарантия языка, не имплементационная деталь. Можно полагаться. До 3.7 порядок был неопределённым (зависел от хешей).

Попробуй сам

# 1. Сравните скорость in для list vs set
import time

n = 100_000
lst = list(range(n))
st = set(lst)

# 1000 lookup'ов случайных значений
import random
queries = [random.randint(0, n) for _ in range(1000)]

start = time.perf_counter()
for q in queries:
    q in lst
t_lst = time.perf_counter() - start

start = time.perf_counter()
for q in queries:
    q in st
t_st = time.perf_counter() - start

print(f"list: {t_lst*1000:.0f} ms")
print(f"set:  {t_st*1000:.0f} ms")
print(f"ratio: {t_lst/t_st:.0f}x")

# 2. Измерьте время вставки 1M ключей в dict
n = 1_000_000
d = {}
start = time.perf_counter()
for i in range(n):
    d[i] = i
print(f"1M inserts: {(time.perf_counter()-start)*1000:.0f} ms")
print(f"per insert: {(time.perf_counter()-start)*1e9/n:.0f} ns")

# 3. Что произойдёт со скоростью при ключах str вместо int?
d = {}
start = time.perf_counter()
for i in range(n):
    d[str(i)] = i
print(f"1M str inserts: {(time.perf_counter()-start)*1000:.0f} ms")

Ожидаемые результаты:

• list lookup в 1000-2000 раз медленнее set lookup.
• 1M вставок int-ключей: ~80-100 ms.
• 1M вставок str-ключей: ~150-200 ms (дороже из-за более тяжёлого хеша).

В следующем уроке разберём две стратегии разрешения коллизий — chaining и open addressing. Поймём, почему Python выбрал open addressing, а Java HashMap — chaining.