TL;DR

Не переопределяйте __hash__ и __eq__ для принудительного хеширования объектов. Вместо этого используйте неизменяемые объекты.

Обзор

Словари и наборы - одни из наиболее распространенных структур данных, которые интенсивно используются для O(1) времени поиска. Этот O(1) вид обеспечивается хэш-функциями, которые имеют следующие свойства:

  • Если a == b, то hash(a) == hash(b)
  • Если hash(a) == hash(b), то a может равняться b
  • Если hash(a) != hash(b), то a != b

Словари и наборы, независимо от языка, используют эти предположения для обеспечения быстрого O(1) поиска. Этот пост будет посвящен Python, но уроки применимы независимо от языка.

Краткий обзор словарей

Словари Python довольно продвинуты и оптимизированы - подробности см. В этом отличном выступлении Раймонда Хеттингера, но чтобы понять, почему эти свойства важны, мы рассмотрим, как они работают на высоком уровне.

Хранение объекта:

  1. Вызов __hash__ на ключе, чтобы вычислить хэш ключа. Если ключ не хэшируемый, поднимите TypeError
  2. Хранить (hash_value, ключ, значение) в массиве по адресу hash_value % len(array).
  3. Если массив требует изменения размера, повторно используйте ранее вычисленные hash_value, чтобы повторно вставить все ранее сохраненные значения.

Получение объекта по ключу

  1. Вызов __hash__ на ключе, чтобы вычислить хэш ключа. Если ключ не хэшируемый, поднимите TypeError
  2. Найдите в hash(key) % len(array) запись с совпадающим hash_value. Если есть - проверьте на равенство сначала по идентичности, затем по телефону __eq__.

Из этого следует несколько вещей, чтобы иметь функционально правильные словари:

  1. __eq__ и __hash__ должны согласиться - одинаковые объекты должны иметь одинаковые хэши.
  2. __hash__ не должен изменяться. После вставки хэш объекта никогда не пересчитывается.
  3. Объекты, которые реализуют логическое равенство (например, реализуют __eq__), должны быть неизменными, чтобы их можно было хэшировать. Если объект имеет логическое равенство, обновление этого объекта изменит его хэш, нарушив правило 2. dict, list, set все по своей сути изменчивы и, следовательно, нехешируемы. str, bytes, frozenset и tuple неизменяемы и, следовательно, хешируемы.

Погружение в детали

Давайте сначала рассмотрим, как работают объекты, если мы не реализуем __hash__ и __eq__.

По умолчанию равенство и хэши основаны на идентичности объекта. Текущая реализация - id >> 4 (мы никогда не должны полагаться на эту деталь реализации).

Hash of x: 8729258887714
id of x: 139668142203424
id of x >> 4: 8729258887714
Is x equal to itself? True

Словари и наборы предполагают, что если объект имеет идентичность, эквивалентную объекту в set или dict, объекты равны (например, мы предполагаем, что объект всегда равен самому себе). Это важная оптимизация, поскольку __eq__ функции могут быть дорогими.

Is never_equal in a set of itself? True

__hash__ вызывается только один раз, когда объект вставляется в dict или set. Обратите внимание, что мы никогда не видим повторного вызова хеша для a или b, хотя мы принудительно изменили размер набора, вставив еще 10 000 элементов и получив логически идентичный объект.

Calling hash for a: 42
Calling hash for b: 37
Calling hash for c: 42
True

Вот почему абсолютно важно, чтобы __hash__ объект никогда не изменялся за время его существования. Это работает вне пределов идентификации объекта (если id(a) == id(b) мы знаем a == b).

Если __hash__ изменится, мы можем попасть в ситуацию, когда словари и наборы больше не работают и будут иметь чрезвычайно трудно обнаруживаемые ошибки.

Object is in list: True
Object is in set: True
Logically equivalent object is in list: True
Logically equivalent object is in set: True

Все идет нормально. Мы перехитрили Python и заставили тот словарь, который он не хотел хешировать, быть хешируемым! Но что произойдет, если мы изменим d - основной словарь

Object is in list: True
Object is in set: False
Logically equivalent object is in list: True
Logically equivalent object is in set: False

Что? Я думал, что объект всегда равен самому себе? Почему x находится в списке, но не в наборе, который содержит точно такие же объекты? То же самое для логически эквивалентного объекта?

Напомним - все оптимизации, которые позволяют словарям и наборам работать очень быстро с O(1) поиском требовать, чтобы хэши никогда не менялись. Борясь с языком, мы представили возможность для действительно тонких, сбивающих с толку ошибок.

Хорошо, я понял, что мне делать вместо этого?

Я рада, что вы спросили !! Если мы действительно хотим, чтобы эти объекты были хешируемыми, мы можем добиться этого с помощью неизменяемости!

Мы можем использовать несколько встроенных модулей, а именно tuple и frozenset, и некоторые сторонние библиотеки, которые мы можем использовать - immutables и attrs. Хотя обе эти библиотеки являются сторонними библиотеками, обе имеют сильные аналоги в стандартной библиотеке Python (неизменяемые объекты могут быть частью стандартной библиотеки в 3.9, поскольку они используются как часть asyncio contextvars, а attrs в основном дублированы в стандартной библиотеке с помощью dataclass).

Встроенные

Если у нас есть list, который мы хотим хэшировать, мы можем преобразовать его в tuple, чтобы гарантировать его неизменность:

Exception when trying to hash a list! unhashable type: 'list'
hash(tuple(x)): 2528502973977326415

Если у нас есть set, который мы хотим хэшировать, мы можем преобразовать его в frozenset, чтобы гарантировать его неизменность, сохраняя при этом поиск O (1):

Exception when trying to hash a set! unhashable type: 'set'
hash(frozenset(x)): -272375401224217160

Классы и словари

Мы собираемся использовать две высококачественные сторонние библиотеки: attrs и immutables.

attrs поддерживает frozen объекты, которые можно рассматривать как неизменяемые и, следовательно, хешируемые. В качестве бонуса он избавляет от тонны стандартного кода!

Created an ImmutableThing: ImmutableThing(x=42, y='hello world', computed_field=('hello', 'world'))
Caught an error trying to assign to ImmutableThing! <class 'attr.exceptions.FrozenInstanceError'>
hash(thing): -7021629421173658791
ImmutableThing respects logical equality: True
ImmutableThing as a dictionary key: {'thing': 'thing is a key'}

Для dict мы будем использовать immutables.Map. immutables.Map - неизменяемая карта и, следовательно, Hashable. Любые мутации создают новую карту вместе, но оставляют базовую карту без изменений. Его производительность значительно выше, чем у deepcopy.

Exception when trying to hash a dict! unhashable type: 'dict'
hash(m): -4868096002692125985
Map as a dictionary key: {'m': 'map is a key!'}
'immutables._map.Map' object does not support item assignment
m after assignment: <immutables.Map({'c': 3, 'b': 2, 'a': 1}) at 0x7f0705d0d1b0>
m_prime after assignment: <immutables.Map({'c': 3, 'b': 2, 'a': 42}) at 0x7f0705d0d5e8>

Заключение

Борьба с языком, чтобы заставить объекты быть хешируемыми, является одновременно медленным и небезопасным - тратой денег, сокращением времени отклика и снижением надежности. Мы рассмотрели некоторые инструменты, которые вы можете использовать здесь, чтобы сделать объекты хешируемыми, когда это необходимо, с сохранением правильности и производительности. В качестве примера мы использовали Python, эти проблемы и контракты не ограничиваются Python - они имеют фундаментальное значение для работы таких структур данных, как хеш-карты или хеш-наборы. Это сообщение в блоге также доступно в виде записной книжки Jupyter, которую вы можете скачать и самостоятельно поиграть с примерами!

Если вы обнаружите, что боретесь с языком, остановитесь и подумайте, действительно ли это правильно.

Если вы хотите присоединиться к команде Lyft, мы ищем! Не стесняйтесь заходить на нашу страницу вакансий для получения дополнительной информации.