Понимание хэширования и равенства в Python с помощью __hash__ и __eq__

питон

Понимание хэширования и равенства в Python с помощью __hash__ и __eq__

Узнайте о том, как они работают, как вы должны их использовать, и что вы категорически не должны делать.

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

Оператор равенства «__eq__» и «is»

Оператор __eq__ в Python — это метод перегрузки оператора == по умолчанию, т. е. для определения того, являются ли два объекта равными. Добавляется так:

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

Очевидно, что a и b имеют одинаковые значения, и, в свою очередь, логично, что они должны быть равны, верно? Но это не всегда верно, и я вернусь к этому через секунду. Во-первых, давайте поговорим о другом операторе под названием is. Если вы проверите, что два объекта «являются» друг другом, то есть a is b, то это будет верно только в том случае, если они являются одним и тем же объектом. Например:

Теперь улов. Если вы создадите собственный класс и не добавите метод __eq__, использование is и == будет одним и тем же. То есть оператор равенства только проверяет, одинаковы ли объекты, его не волнуют атрибуты класса. Таким образом, если вы хотите сравнить свои пользовательские классы по значению, вам нужно определить оператор самостоятельно.

Однако для встроенных объектов, как было показано в предыдущем фрагменте, существуют четко определенные определения равенства, которые имеют смысл в зависимости от значения. Исключение составляют числа с плавающей запятой, в которых может существовать ошибка с плавающей запятой.

Давайте посмотрим на пример, чтобы закрепить то, что вы только что прочитали:

Хорошо, а как насчет __hash__?

Оператор __hash__

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

Хранение и сравнение паролей

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

Как хеш-функции это исправляют? Вместо того, чтобы хранить пароли напрямую, пароль преобразуется в хеш-значение, а затем сохраняется. Затем, в следующий раз, когда пользователь захочет войти в систему и ввести пароль, пароль будет хэширован, а затем сравнен с ранее хэшированным значением.

Таким образом, пароль не сохраняется. Теперь, если кто-то найдет хешированный пароль, он не сможет его использовать. Причина в том, что хэш-функции, используемые для хеширования паролей, являются односторонними функциями, т. е. найти входные данные по выходному хешу практически невозможно. Таким образом, все ранее заявленные проблемы эффективно предотвращаются. Здесь очень важно, чтобы так называемые хеш-коллизии,т.е. когда два разных входа возвращают один и тот же хэш, крайне редко (практически невозможно). В противном случае вы можете войти в систему как пользователь с другим паролем.

Это одно из приложений криптографии, в котором широко используются хэш-функции. Другим приложением может быть криптовалюта.

Хэш-карта/хеш-таблица

Хеш-карта – это структура данных, используемая для хранения значений для быстрого доступа. Он имеет отношение "ключ-значение", при котором данные группируются в сегменты на основе хэш-значения каждого ключа. Идея, лежащая в основе этого процесса, заключается в том, что если сначала быстро найти ведро, часто содержащее несколько элементов (или всего 1), количество сравнений на равенство значительно сокращается. Например, представьте, что у вас есть миллион элементов в списке, и вы хотели бы увидеть, существует ли в нем элемент. Затем, если бы список не был отсортирован, нам пришлось бы перебирать элементы один за другим и сравнивать каждый на равенство. Вместо этого, если бы у нас была хеш-таблица, скажем, с 500 000 сегментов, нам нужно было бы только хэшировать ключ, найти сегмент, а затем выполнить в среднем 2 сравнения на равенство. Разница в скорости колоссальная.

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

Итак, словарь в Python представляет собой хэш-карту, простую и понятную. set или frozenset также реализуется с использованием хэш-карты. Вариант использования __hash__ в Python — это просто хеш-функция для хеширования ключа в хеш-таблицах, то есть в наборах и словарях. Таким образом, как описано ранее, это не должна быть медленная хеш-функция, используемая в криптографии, допускаются коллизии.

Как и __eq__, __hash__ — это метод, который можно добавить к классам. Значение метода можно вернуть с помощью hash(object):

Вот несколько правил в отношении __hash__:

• Возвращаемое фиксированное представление __hash__ должно быть целым числом. Если вы этого не сделаете, будет выброшена ошибка.
• The__hash__ объекта должен быть неизменяемым, то есть он не должен меняться в течение своей жизни. Причина этого в том, что если вы поместите объект, например, в набор, а затем измените хэш, в следующий раз, когда вы будете искать его, вы не найдете его, потому что хэш другой.
• Если два объекта «равны», т. е. __eq__ возвращает равенство, они должны иметь одинаковое значение__hash__ (но обратное не обязательно верно, т. е. во время коллизий).
• Если вы определите __eq__ без определения __hash__, объект станет недоступным для хеширования, и при попытке его хэширования будет выдана ошибка. Причина этого в том, что если вы определяете __eq__, единственной допустимой причиной должно быть то, что is по умолчанию больше не подходит, следовательно, хеш по умолчанию также больше не будет подходящим (поскольку по умолчанию он имеет свойства, предназначенные для использования с «есть»-равенством).
• Если метод __eq__ использует изменяемые/изменяемые атрибуты, то вам также не следует определять функцию __hash__. Это следует из того, что хэш должен быть неизменяемым и два одинаковых объекта должны иметь одинаковый хэш. Если вы измените объект, то __eq__ с другими объектами должно измениться, и, в свою очередь, __hash__ должно измениться, и, следовательно, он больше не является неизменным. Исключением будет константа __hash__, но она бесполезна.

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

Давайте посмотрим на некоторые примеры.

Нецелочисленный возвращаемый тип приводит к ошибке:

Причина сохранения неизменяемых хеш-значений:

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

Если они равны, они должны иметь одинаковое хеш-значение

Добавление __eq__ без __hash__ делает объект недоступным для хеширования

Как насчет постоянного хэша?

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

Теперь с уникальным хешем:

Тот, у кого был уникальный хеш, был примерно в 1742 раза быстрее, и он будет только расти по мере добавления новых элементов в словарь/хеш-таблицу. При постоянном хэше элементы в одном сегменте циклически перебираются и их равенство сравнивается до тех пор, пока не будет найдено совпадение, что фактически устраняет все преимущества хеш-таблиц. Кроме того, вставка также будет медленнее.

Последний вопрос

Прежде чем закончить статью, я задам вам последний вопрос: что вернет следующий фрагмент кода?

Я помещу ответ в разделе комментариев. Если вас интересуют дополнительные статьи о словарях и наборах в Python, я написал по одной о каждом:

Если вам понравилась эта статья и вы хотели бы прочитать мою будущую работу, вы можете подписаться на меня здесь, на Medium. Если вы заинтересованы в получении членства в Medium, вы можете использовать мою реферальную ссылку, если хотите. Хорошего дня.