Множества и словари Python: hash и общие механизмы

Пятнадцать уроков разделяли две структуры: множество хранит уникальные элементы из урока 1, словарь — пары «ключ: значение» из курса про словари. Но под обеими лежит один и тот же механизм, и это не совпадение: множество — почти словарь без значений. Понимание общего механизма отвечает сразу на три вопроса, которые накопились за курс: почему проверка in мгновенна, почему dict.fromkeys из урока 16 сохраняет порядок, а set нет, и почему список нельзя положить ни в множество, ни в ключ словаря.

hash: общий фундамент

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

print(hash('Анна') == hash('Анна'))
print(hash((1, 2)) == hash((1, 2)))
print(hash((1, 2)) == hash((2, 1)))
print(type(hash('Анна')).__name__)

True
True
False
int

Последняя строка напоминает, что хеш — обычное целое число: type его имени возвращает int. Главное в выводе другое. Равные значения дают равные хеши — иначе ни словарь, ни множество не смогли бы находить элементы. А перестановка в кортеже изменила хеш: хеш чувствителен к составу и порядку, и потому кортежи (1, 2) и (2, 1) — разные ключи.

Ключи словаря — это множество

Ключи словаря и элементы множества подчиняются одним правилам: уникальность, мгновенный in, отсутствие порядка у структуры хранения. Неудивительно, что ключи превращаются в множество одним вызовом:

prices = {'хлеб': 40, 'молоко': 90, 'сыр': 700}

print(len(prices.keys()))
print(sorted(set(prices)))
print('сыр' in prices)
print(set(prices) == {'хлеб', 'молоко', 'сыр'})

3
['молоко', 'сыр', 'хлеб']
True
True

set(prices) собрал множество из ключей — значений в нём не оказалось. Проверка in для словаря ищет среди ключей — тем же механизмом, что и in для множества. Печать через sorted — наше старое правило: множество печатаем только отсортированным.

Операции множеств над ключами двух словарей

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

mon = {'хлеб': 40, 'молоко': 90, 'сыр': 700}
tue = {'молоко': 95, 'сыр': 650, 'сок': 120}

common = set(mon) & set(tue)
only_mon = set(mon) - set(tue)

changed = []
for name in common:
    if mon[name] != tue[name]:
        changed.append(name)

print('в обоих магазинах:', sorted(common))
print('только в первом:', sorted(only_mon))
print('цена изменилась:', sorted(changed))

в обоих магазинах: ['молоко', 'сыр']
только в первом: ['хлеб']
цена изменилась: ['молоко', 'сыр']

Пересечение нашло общие товары, разность — уникальные первого. А изменившиеся цены — это пересечение, прогнанное через сравнение значений: сами множества о ценах не знают, за значениями возвращаемся в словарь по ключу. Схема «множество отвечает за состав, словарь — за значения» повторяется в половине задач на сравнение данных.

views: операции множеств без set()

Оборачивать словарь в set не обязательно: представление keys() само поддерживает операции множеств — и это самый короткий синтаксис сравнения двух словарей:

mon = {'хлеб': 40, 'молоко': 90}
tue = {'молоко': 95, 'сыр': 650}

print(sorted(mon.keys() & tue.keys()))
print(sorted(mon.keys() | tue.keys()))
print(sorted(mon.keys() - tue.keys()))

['молоко']
['молоко', 'сыр', 'хлеб']
['хлеб']

Три строки сравнили два словаря: общие ключи, все ключи, ключи только первого. Никаких промежуточных множеств создавать не пришлось — представление словаря играет роль множества само. То же работает для values() и items(), но с оговоркой: values() — мультимножество, повторяющиеся значения в нём живут по отдельности.

Экзамен на хешируемость общий

Элемент множества и ключ словаря сдают один и тот же экзамен: хеш обязан существовать и не должен меняться после вставки. Отказ у обоих одинаковый и честно называет причину:

data = [1, 2]

try:
    s = {data}
except TypeError as e:
    print('в множество:', e)

try:
    d = {data: 'пара'}
except TypeError as e:
    print('в ключ словаря:', e)

в множество: unhashable type: 'list'
в ключ словаря: unhashable type: 'list'

Одна причина — один текст ошибки в обе двери: у списка нет хеша, потому что его содержимое меняется, и полка, выбранная по старому хешу, стала бы врать. Кандидаты на роль элемента множества и ключа словаря — одни и те же: строки, числа, кортежи из неизменяемых значений и frozenset.

frozenset и кортежи в роли ключей

Неизменяемые сборки из уроков 10 и 11 проходят экзамен и открывают составные ключи. frozenset хешируется независимо от порядка вставки элементов, кортеж — с учётом порядка:

roads = {
    frozenset({'Анна', 'Борис'}): 12,
    frozenset({'Борис', 'Вера'}): 7,
}
point_prices = {(0, 0): 100, (1, 5): 250}

print(roads[frozenset({'Борис', 'Анна'})])
print(point_prices[(1, 5)])

12
250

Дорога между Анной и Борисом нашлась, даже когда города назвали в обратном порядке: frozenset не различает порядок элементов. Цены по координатам, наоборот, зависят от порядка: (1, 5) и (5, 1) были бы двумя разными ключами. Выбор между ними — вопрос о том, важен ли порядок частей в вашем ключе.

d = {}
d[1] = 'целое'
d[1.0] = 'дробное'
d[True] = 'истина'

print(len(d))
print(d[1])

1
истина

Три присваивания, одна пара, и значение — от последней записи: True затерло и целое, и дробное. Словарь не предупреждает: для него это один и тот же ключ, просто названный тремя способами. Если ключи приходят из разных источников — из JSON строками, из счётчика числами — приведите их к одному типу сразу.

a = {'x': 1, 'y': 2}
b = {'y': 2, 'z': 3}

try:
    a.values() & b.values()
except TypeError:
    print('values() операций множеств не поддерживает')
print(sorted(a.items() & b.items()))

values() операций множеств не поддерживает
[('y', 2)]

Что дальше

Общий механизм объяснил три загадки курса: мгновенный in из урока 5 — поиск по полке, а не перебор; ограничение на элементы множеств — тот же экзамен, что у ключей; хешируемость namedtuple из урока 15 — он кортеж. Дальше практика: задачи на множества — уникальные гости и общие друзья, задачи на кортежи — координаты и записи.

Множество — словарь без значений, словарь — множество с значениями. Устроив одни механизм в голове, вы перестаёте запоминать два набора правил и начинаете предсказывать поведение обеих структур по одному общему принципу.