Что такое хэш-функция Python
Обновлено: 05.07.2024
Хорошая хэш-функция – это функция, которая приводит к наименьшему количеству конфликтов, то есть никакие два набора данных не должны иметь одинаковые хеш-значения.
Хеш Python()
Python hash() — это встроенный метод, который возвращает хеш-значение объекта, если оно есть. Хэш-значения — это просто целые числа, которые используются для быстрого сравнения ключей словаря во время поиска в словаре. Проще говоря, хэш — это целое число фиксированного размера, которое идентифицирует конкретное значение. Обратите внимание, что приведенное выше определение является самым простым объяснением.
Укажем, что может означать фиксированный хеш? См. следующие пункты.
- Одни и те же данные будут иметь одинаковое хеш-значение.
- Даже незначительное изменение исходных данных может привести к совершенно другому значению хеш-функции.
- Хеш получается из хэш-функции, которая отвечает за преобразование части заданной информации в закодированный хэш.
- Несколько объектов могут иметь гораздо большее число хеш-значений, поэтому два объекта могут хешировать одно и то же значение хеш-функции. Это называется коллизией хэшей. Это означает, что если два объекта имеют одинаковый хеш-код, они не обязательно имеют одинаковое значение.
- Объекты, хешированные с помощью hash(), необратимы, что приводит к потере информации.
- Метод hash() возвращает хешированные значения только для неизменяемых объектов. Следовательно, его можно использовать в качестве индикатора для проверки изменяемых/неизменяемых объектов.
Внутренне метод hash() вызывает метод __hash__() объекта, который установлен по умолчанию для любого объекта. Мы рассмотрим это позже.
Хэш-коды чаще всего используются при сравнении ключей словаря.
Хэш-код ключей словаря сравнивается, когда для конкретного ключа выполняется поиск в словаре. Сравнение хэша происходит намного быстрее, чем сравнение всех значений ключа, поскольку набор целых чисел, который хэш-функция сопоставляет с каждым ключом словаря, намного меньше, чем сам набор объектов.
Синтаксис
См. приведенный ниже синтаксис метода хеширования.
Параметры
Параметр объекта, хэш-значение которого должно быть возвращено (целое число, строка, число с плавающей запятой).
См. приведенный ниже пример кода.
См. вывод ниже.
Кортеж — это неизменяемый объект, то есть мы можем создать хеш-значение из кортежа.
Список — это изменяемый объект. Вот почему он выдает ошибку, как будто мы можем преобразовать список в хеш.
Список является нехешируемым типом.
Возвращаемое значение функции hash()
Функция hash() возвращает хеш-значение объекта, если оно есть. Если у объекта есть собственный метод __hash__(), он усекает возвращаемое значение до размера Py_ssize_t.
Как hash() работает в Python
См. следующий пример хэша в Python.
В приведенном выше коде мы использовали два типа данных.
Теперь хэш целого числа — это само целое число, но хэш числа с плавающей запятой несколько отличается. Например, см. приведенный ниже вывод.
Python hash() Строка
Давайте начнем создавать простые примеры и сценарии, в которых метод hash() может быть полезен.
В этом примере мы получим хеш-значение строки.
См. вывод ниже.
Оба результата одинаковы, потому что мы использовали одну и ту же строку для хеша.
Вот существенная загвоздка: если вы повторно запустите тот же скрипт, хэш изменится, как показано ниже.
Как определить функцию hash() для пользовательских объектов
Функция hash() переопределяет функцию __hash()__.
Стоит заметить, что не каждый объект можно хэшировать (изменяемые коллекции не хэшируются).
Мы также можем определить функцию __hash__() для нашего пользовательского класса. Так вот что мы сейчас сделаем. Но перед этим отметим несколько важных моментов.
См. следующий пример.
- Хешируемая реализация не должна выполняться для изменяемых коллекций, так как ключи коллекций должны быть неизменными для хеширования.
- Нам не нужно определять собственную реализацию функции __eq()__, так как она определена для всех объектов.
См. следующий пример кода.
См. следующий вывод.
Случаи реализации пользовательского хэша для объектов.
Для__hash__() неявно задано значение "Нет"
Вызывает исключение TypeError при попытке получить хэш.
Вызывает исключение TypeError при попытке получить хэш.
Почему изменяемый объект нельзя хэшировать
Как мы уже знаем, хешировать можно только неизменяемый объект. Это ограничение, запрещающее хеширование изменяемого объекта, значительно упрощает хеш-таблицу. Давайте разберемся, как это сделать.
Если разрешено хеширование изменяемого объекта, нам нужно обновлять хеш-таблицу каждый раз, когда значение объекта обновляется. Это означает, что нам придется переместить объект в совершенно другое ведро. Это очень дорогостоящая операция.
В Python у нас есть два объекта, которые используют хеш-таблицы, словари и наборы:
В этом руководстве мы изучим метод Python hash() с помощью примеров.
Метод hash() возвращает хеш-значение объекта, если оно есть. Хэш-значения — это просто целые числа, которые используются для быстрого сравнения ключей словаря во время просмотра словаря.
Пример
Синтаксис хэш()
Синтаксис метода hash():
Параметры hash()
Метод hash() принимает один параметр:
- object – объект, хеш-значение которого должно быть возвращено (целое число, строка, число с плавающей запятой)
Возвращаемое значение hash()
Метод hash() возвращает хеш-значение объекта.
Пример 1. Как функция hash() работает в Python?
Вывод
Пример 2: hash() для неизменяемого объекта кортежа?
Метод hash() работает только для неизменяемых объектов в виде кортежа.
Вывод
Как работает функция hash() для пользовательских объектов?
Как указано выше, метод hash() вызывает внутренний метод __hash__(). Таким образом, любые объекты могут переопределять __hash__() для пользовательских хеш-значений.
Но для правильной реализации хэша __hash__() всегда должна возвращать целое число. И оба метода __eq__() и __hash__() должны быть реализованы.
Ниже приведены случаи правильного переопределения __hash__().
| __eq__() | __hash__() | Описание |
|---|---|---|
| Определено (по умолчанию)< /td> | Определено (по умолчанию) | Если оставить как есть, все объекты сравниваются неравно (кроме самих себя) |
| (Если изменяемое) Определено | Не следует определять | Для реализации хешируемой коллекции требуется, чтобы хеш-значение ключа было неизменным |
| Не определено | Не следует определять | Если __eq__() не определено, __hash__() не должно определяться. |
| Определено | Не определено | Экземпляры класса нельзя использовать в качестве хешируемой коллекции. Неявность __hash__() установлена на None . Вызывает исключение TypeError при попытке получить хэш. |
| Определено | Сохранение от родителя | __hash__ = |
Пример 3: hash() для пользовательских объектов путем переопределения __hash__()
Вывод
Примечание. Вам не нужно реализовывать метод __eq__() для хеша, так как он создается по умолчанию для всех объектов.
Учебное пособие по хэшированию в Python объясняет концепцию хеширования в Python. Мы объясняем хэш-таблицы и хэш-объекты Python.
Хеш-таблица
Хэш-таблицы используются для реализации карт и структур данных множества во многих распространенных языках программирования, таких как C++, Java и Python. Python использует хеш-таблицы для словарей и наборов. A — это неупорядоченный набор пар ключ-значение, где каждый ключ уникален. Хэш-таблицы предлагают комбинацию эффективных операций поиска, вставки и удаления. Это лучшие свойства массивов и связанных списков.
Хеширование
это процесс использования алгоритма для сопоставления данных любого размера с фиксированной длиной. Это называется хэш-значением. Хеширование используется для создания высокопроизводительных структур данных с прямым доступом, в которых необходимо хранить и быстро получать доступ к большим объемам данных. Хэш-значения вычисляются с помощью хеш-функций.
Хэширование Python
Объект является хэшируемым, если его хеш-значение никогда не меняется в течение всего его существования. (Он может иметь разные значения во время нескольких вызовов программ Python.) Для хэшируемого объекта требуется метод __hash__. Для выполнения сравнений хешируемому объекту нужен метод __eq__.
Хешируемость делает объект пригодным для использования в качестве ключа словаря и члена множества, поскольку эти структуры данных используют хэш-значение внутри себя. Неизменяемые встроенные объекты Python можно хэшировать; изменяемые контейнеры (такие как списки или словари) не являются. Объекты, являющиеся экземплярами определяемых пользователем классов, по умолчанию хэшируются. Все они сравниваются неравными (кроме самих себя), а их хэш-значение получается из их идентификатора .
Примечание. Если класс не определяет метод __eq__, он также не должен определять операцию __hash__; если он определяет __eq__, но не __hash__ , его экземпляры нельзя будет использовать в качестве элементов в хешируемых коллекциях.
Функция Python hash()
Хеш-функция возвращает хеш-значение объекта, если оно есть. Хэш-значения являются целыми числами. Они используются для быстрого сравнения ключей словаря во время поиска в словаре. Объекты могут реализовывать метод __hash__.
Неизменяемые встроенные функции Python можно хэшировать
Неизменяемые встроенные функции Python, такие как целые числа, строки или кортежи, можно хэшировать.
В этом примере выводятся значения трех хеш-таблиц: целое число, строка и кортеж.
Пример I пользовательского хеширования Python
Настраиваемые объекты Python по умолчанию хэшируются. Их хеш получается из их идентификатора.
В этом примере у нас есть два экземпляра пользователя .
У нас есть два экземпляра с одинаковыми данными.
Хэш-функция возвращает хеш-значение объекта. Реализация по умолчанию определяется идентификатором объекта.
Несмотря на то, что сведения о пользователе совпадают, сравнение дает разные объекты. Чтобы изменить его, нам нужно реализовать метод __eq__.
Пример II пользовательского хеширования Python
Во втором примере мы реализуем собственный метод __eq__.
Теперь сравнение возвращает нам ожидаемый результат; однако мы не можем вставлять объекты в набор Python; это приведет к TypeError: unhashable type: 'User' . Чтобы изменить это, мы реализуем метод __hash__.
Пример III пользовательского хеширования Python
В третьем примере мы реализуем методы __eq__ и __hash__.
В этом примере сравниваются два объекта с пользовательской реализацией методов __eq__ и __hash__. Объекты могут быть вставлены в набор Python, и при последующем изменении атрибута мы получаем ожидаемый результат.
Реализация функции __hash__ возвращает хеш-значение, вычисленное с помощью хеш-функции, из кортежа атрибутов.
__eq__, он не должен реализовывать __hash__ , так как реализация хэшируемых коллекций требует, чтобы хэш-значение ключа было неизменным.
В примере у нас есть список в качестве атрибута. Список — это изменяемый объект, и это влияет на алгоритм хеширования.
Изменяем элемент списка первого пользователя. Однако это не отражено.
Вывод по-прежнему говорит, что объекты равны.
Декоратор Python @dataclass
Начиная с Python 3.7, у нас есть декоратор класса данных, который автоматически генерирует шаблонный код.
Какой алгоритм хеширования Python используется по умолчанию?
Я знал, что объекты Python могут реализовывать метод __hash__(), но не знал, какой алгоритм хэширования используется по умолчанию, поэтому немного углубился в этот вопрос.
ПРИМЕЧАНИЕ. Если у вас мало времени, ответ — SipHash.
Читайте дальше, чтобы узнать больше о том, для чего Python использует хеширование и почему Python использует именно алгоритм SipHash.
Что такое хеширование?
Вот определение хеш-функции в Википедии:
Хеш-функция — это любая функция, которую можно использовать для преобразования данных произвольного размера в значения фиксированного размера.
Вы можете увидеть, как это работает, зайдя в оболочку Python и вызвав встроенную функцию hash() для объекта:
Обратите внимание на длину хешированной строки. Теперь я собираюсь хешировать очень короткую строку:
В этих примерах встроенная функция hash() сопоставляет произвольно длинные строковые объекты с целыми числами фиксированного размера точно так, как предполагает определение Википедии.
Хорошо, отлично, подумаете вы, но какой смысл в хешировании?
Для чего Python использует хеширование?
Самая важная вещь, для которой Python использует хеширование, — это поиск ключей в словарях, и это то, что документация Python говорит нам о встроенной функции hash():
Хеш-значения […] используются для быстрого сравнения ключей словаря во время поиска в словаре.
Словарь — это своего рода хеш-таблица, структура данных, в которой используется хэш-функция для сопоставления ключей со значениями.
В качестве примера «поиска» представьте себе словарь, ключами которого являются имена людей, а значениями — номера телефонов. На следующем изображении показано, как хеш-функция переводит имя (ключ в словаре) в корзину в базовом массиве, содержащем телефонные номера:
Вопрос о хеш-таблицах, относящийся к этому обсуждению, заключается в том, что происходит, когда два ключа имеют одинаковый хэш? Если хеш-функция генерирует один и тот же хэш для двух ключей, это называется коллизией.
Хэш-таблицы могут обрабатывать коллизии по-разному.Один из подходов заключается в использовании связанных списков для отслеживания пар ключ-значение, которые имеют один и тот же хэш, как показано на следующем рисунке.
В словарях Python используется другой подход, называемый открытой адресацией. Однако, независимо от того, как хэш-таблицы управляют коллизиями, это сказывается на производительности. Это станет важным в тот момент, когда мы рассмотрим конкретный алгоритм хеширования, который использует Python.
Подводя итог, мы увидели, что Python использует хеш-функцию для сопоставления ключа, такого как «Эндрю Брукинс», с номером телефона, например «666-666-6666», хранящимся в словаре. Существует множество алгоритмов, которые Python может использовать для создания таких хэшей, например CityHash, MurmurHash, DJBX33A и многие другие.
Итак, какой алгоритм хеширования использует Python и, что более важно, почему Python использует именно его?
Почему Python использует SipHash
Python перешел на SipHash в версии 3.4. До этого изменения в Python использовался вариант хэш-функции Фаулера-Нолла-Во.
Почему это изменение? Все дело было в безопасности. Помните, я сказал, что коллизии хэшей увеличивают затраты на поиск? Злоумышленники могут использовать это, чтобы превратить, скажем, форму API или HTML в атаку типа «отказ в обслуживании», если им удастся создать коллизии хэшей.
Это называется атакой коллизии. Если злоумышленнику удастся это сделать, он снизит производительность и потенциально может вывести из строя ваш веб-сайт или API.
Python выбрал SipHash, потому что это криптографическая хэш-функция с достойными характеристиками производительности, разработанная проверенными экспертами по безопасности. «Криптографическая» хэш-функция очень затрудняет обнаружение коллизий хэшей и, таким образом, не позволяет злоумышленникам проводить атаки коллизий.
Итак, вот оно: Python использует SipHash, потому что это доверенная криптографическая хеш-функция, которая должна предотвращать атаки столкновений. Во всяком случае, пока кто-нибудь не придумает, как его сломать.
Читайте также: