Коллекции, хеши и сложность операций

Скрипт, который сверяет два файла по 100 тысяч строк, может работать секунду или полчаса при одном и том же алгоритме. Разница в одной строке: if order_id in seen при seen списке или множестве. Этот урок про то, что у каждой коллекции своя цена операций, и про механизм, который делает словарь и множество быстрыми: хеширование.

Четыре коллекции и их цена

O(1) значит «за постоянное время, не зависящее от размера», O(n) значит «пропорционально числу элементов». Самая важная строка в таблице это x in c. Проверка принадлежности списку перебирает элементы один за другим, в среднем половину списка. Для множества и словаря это вычисление хеша и один-два прыжка в памяти.

Откуда берётся получасовая сверка: для каждой из 100 тысяч строк первого файла проверить, есть ли она в списке из 100 тысяч строк второго, это 100 000 × 50 000 сравнений, пять миллиардов. С множеством это 100 тысяч вычислений хеша.

seen = set()
for row in rows:
    if row["order_id"] in seen:      # O(1)
        duplicates.append(row)
    seen.add(row["order_id"])

list и tuple устроены одинаково: массив ссылок на объекты. Поэтому доступ по индексу O(1), а поиск O(n). Разница в изменяемости: кортеж нельзя дополнить, зато он чуть компактнее, создаётся быстрее и может быть ключом словаря. Кортеж это «запись с фиксированным составом полей» (координата, пара ключей), список это «последовательность одинаковых вещей, которая растёт».

append у списка O(1) амортизированно: список резервирует память с запасом, и переразмещение случается редко. А insert(0, x) и pop(0) сдвигают весь массив, O(n). Если нужна очередь с добавлением в один конец и забором с другого, это collections.deque.

Как словарь находит ключ за O(1)

Словарь это хеш-таблица. У ключа вычисляется hash(key), целое число, и по нему определяется, в какой ячейке таблицы искать. Если ячейка занята другим ключом (коллизия), проверяются соседние по определённому правилу. При удачной функции хеша коллизий мало, и поиск занимает одно-два сравнения независимо от размера таблицы.

Из этого следуют два требования к ключу. Во-первых, у него должен быть хеш. Во-вторых, хеш не должен меняться, пока ключ лежит в словаре: иначе словарь будет искать его не в той ячейке и не найдёт.

d = {}
d[(1, 2)] = "ok"          # кортеж хешируем
d[[1, 2]] = "ok"          # TypeError: unhashable type: 'list'

Список изменяем: после key.append(3) его содержимое, а значит и хеш, другие. Разработчики языка не стали делать хеш по идентичности списка и просто запретили его хешировать. То же со словарём и множеством. Если нужно множество в роли ключа, есть frozenset.

Ключом может быть любой неизменяемый встроенный тип: int, float, str, bytes, bool, None, tuple и frozenset, при условии что внутри кортежа тоже только хешируемые значения. (1, [2]) ключом быть не может.

Хеш согласован с равенством: 1 == 1.0 == True, и hash(1) == hash(1.0) == hash(True), поэтому это один и тот же ключ.

d = {1: "a"}
d[1.0] = "b"
d[True] = "c"
print(d)        # {1: 'c'}

Свой класс как ключ

Экземпляр своего класса хешируем по умолчанию: хеш считается от адреса объекта, а равенство это is.

class Key:
    pass
 
k1 = Key()
k2 = Key()
d = {k1: 1}
print(k2 in d)   # False: другой объект, хотя «такой же»

То есть на вопрос «может ли экземпляр class MyClass: pass быть ключом словаря» ответ: да, может. Но только как уникальный объект, не как значение. Два экземпляра с одинаковыми полями будут двумя разными ключами.

Чтобы ключ сравнивался по содержимому, нужны __eq__ и __hash__ вместе. Как только вы определяете __eq__, Python обнуляет __hash__ (__hash__ = None): объект с равенством по значению и хешем по адресу нарушил бы правило «равные объекты имеют равный хеш». Приходится определять оба:

class CityKey:
    def __init__(self, city, segment):
        self.city = city
        self.segment = segment
 
    def __eq__(self, other):
        return isinstance(other, CityKey) and (self.city, self.segment) == (other.city, other.segment)
 
    def __hash__(self):
        return hash((self.city, self.segment))

Правило контракта: если a == b, то hash(a) == hash(b). Обратное не требуется. Проще всего строить хеш от кортежа тех же полей, по которым проверяется равенство.

На практике руками это пишут редко. @dataclass(frozen=True) генерирует и __eq__, и __hash__ по всем полям, и запрещает их менять, то есть делает ровно то, что нужно ключу. namedtuple тоже хешируем. А чаще всего составной ключ это просто кортеж: counts[(city, segment)] += 1.

Что ещё стоит знать про словарь

Словарь сохраняет порядок вставки, начиная с Python 3.7 это гарантия языка. На это можно опираться: порядок колонок в записи, порядок ключей в отчёте.

d.get(key, default) и d.setdefault(key, default) избавляют от проверки if key in d. Для подсчётов есть collections.Counter, для группировки collections.defaultdict(list).

Поиск по словарю O(1) только при хорошем распределении хешей. Хеш у str и int хороший. У своих классов хеш, который возвращает константу, формально корректен, но превращает словарь в список: все ключи попадут в одну цепочку.

Как отвечать на собеседовании

Как рассчитывается сложность операций у list и tuple? Оба это массив ссылок: доступ по индексу O(1), поиск по значению и проверка in O(n), у списка append амортизированно O(1), вставка в начало O(n). Кортеж неизменяем и может быть ключом словаря, список нет.

Что может быть ключом словаря? Любой хешируемый объект: неизменяемые встроенные типы (int, str, tuple из хешируемых, frozenset), а также экземпляры классов. Изменяемые встроенные (list, dict, set) ключом быть не могут.

Может ли экземпляр class MyClass: pass быть ключом? Да, по умолчанию он хешируется по адресу и сравнивается по идентичности. Чтобы два экземпляра с одинаковыми полями считались одним ключом, нужно определить __eq__ и __hash__ согласованно, например через @dataclass(frozen=True).

Почему нельзя изменяемый объект в ключ? Хеш вычисляется из содержимого, и после изменения объекта словарь искал бы его в другой ячейке. Поэтому у list, dict, set хеша нет вообще, и попытка даёт TypeError: unhashable type.

Практика