Что такое хеширование и почему оно используется в Python
Привет! Сегодня я попытаюсь в меру своих возможностей синтезировать, что такое хэширование и для чего оно используется в Python.
Что такое хеширование (в Python)?
Процесс хеширования в основном означает, что некоторые данные (скажем, объект Python, поскольку почти все в Python является объектом) передаются числовому алгоритму и получают значение хеш-функции, которое в Python является >целочисленное значение, сопоставленное с этими данными.
Где это используется?
Хеширование используется в приложениях со структурой данных определенного типа, которая обеспечивает прямой и быстрый доступ к данным, особенно в ситуациях, когда задействован большой объем данных. Эта сложная, но эффективная структура данных называется хеш-таблицей.
Что такое хеш-таблица?
Python прекрасно использует хэш-таблицы, когда речь идет о создании словарей и наборов и работе с ними. Если вы еще не знаете, что такое хеш-таблица, то пока достаточно знать, что словарь Python — это реализация хеш-таблицы. Короче говоря, хеш-таблицы хранят пары ключ-значение, где значением является элемент данных, а ключ получается из хеш-функции, которая возвращает хэш-значение, о котором мы упоминали. ранее.
Хэшируемые объекты в Python
Глядя на словарь Python (вы можете прочитать о них подробнее здесь), основываясь на том, что мы только что узнали, мы можем сделать вывод, что ключи должны быть хешируемыми для правильной работы словаря. То же самое касается элементов набора, они тоже должны быть хешируемыми, чтобы принадлежать набору.
Объекты можно хэшировать — и, следовательно, сделать действительными ключи в словаре — если:
- у них есть хеш-значение — не все объекты в Python могут иметь хеш-значение, как мы скоро узнаем;
- указанное хеш-значение никогда не изменится в течение всего времени существования указанного объекта.
Эти два условия могут быть упрощенно переведены в требование, чтобы объект реализовывал оба метода __hash__() и метода __eq__(). Метод __hash__() предоставляет объекту связанное хэш-значение, а метод __eq__() отвечает за выполнение необходимых операций сравнения.
Очень важно отметить, что метод хеширования должен работать следующим образом: объекты, которые признаны равными, должны также иметь равные хэш-значения. Подробнее о методе __hash__() можно прочитать здесь.
Как правило, в Python неизменяемые встроенные объекты, такие как числа, строки, кортежи, обнаруживаются как хэшируемые, тогда как изменяемые объекты, такие как списки, словари, наборы, не хэшируются. Экземпляры объектов определяемых пользователем классов по умолчанию считаются хэшируемыми.
Рассмотрим несколько примеров хеширования некоторых встроенных объектов Python;
# tuples are hashable
my_tuple = (1, 2, 3)
print(hash(my_tuple))
# numbers are also hashable
my_int = 451
print(hash(my_int))
my_float = 45.1
print(hash(my_float))
my_negative_int = -56
print(hash(my_negative_int))
# lists are not
my_list = [1, 2, 3]
print(hash(my_list))
Output:
529344067295497451
451
230584300921372717
-56
Traceback (most recent call last):
...
print(hash(my_list))
TypeError: unhashable type: 'list'
Мы видим, как для неизменного кортежа Python смог вычислить хеш-значение. При вызове функции hash() произошло то, что Python вызвал метод __hash__() этого экземпляра кортежа. Возвращаемое значение — это большое целое число, которое мы получили в первой строке вывода. То же самое при хешировании чисел. Заметили, что хэш целого числа равен самому числу?
Список не был настолько успешным в получении хеш-значения, учитывая его изменяемое свойство, и поэтому нам было выдано исключение (точнее, исключение TypeError).
Я упомянул, что если мы определяем наш собственный класс, его экземпляры по умолчанию хэшируются. Давайте расширим это:
# build a custom class
class MyClass():
def __init__(self, number):
self.number = number
# instantiate the class
my_instance = MyClass(1)
print(my_instance.__hash__)
print(hash(my_instance))
# instantiate it again
my_other_instance = MyClass(1)
print(my_instance.__hash__)
print(hash(my_other_instance))
# instances are not equal
print(my_instance.__eq__(my_other_instance))
print(id(my_instance))
print(id(my_other_instance))
print(my_instance == my_other_instance)
Output:
<method-wrapper '__hash__' of MyClass object at 0x7fd0c8277fd0>
8783417997309
<method-wrapper '__hash__' of MyClass object at 0x7fd0c8277fd0>
8783417997294
NotImplemented
140534687956944
140534687956704
False
Как мы видим, экземпляры этого класса по умолчанию являются хешируемыми, и они сравниваются как False, за исключением случаев, когда они сравниваются сами с собой, и вот почему: хотя экземпляры являются экземплярами одного и того же класса и имеют одинаковое значение атрибута (self.number = 1), сами экземпляры оцениваются как неравные. Это потому, что метод __eq__() не реализован. Как прямое следствие этого, Python в конце концов приступает к проверке, являются ли они одним и тем же объектом или нет, используя оператор is. Поскольку это не так (их результаты id() различаются), оператор == возвращает False.
Что касается хеш-значений, то функция __hash__() в данном случае по умолчанию получается из id() самого объекта. Вот почему мы получили разные значения хеш-функции.
Давайте немного поинтереснее и приступим к реализации метода __eq__():
# build a custom class
class MyClass():
def __init__(self, number):
self.number = number
# implement / override the __eq__ method
def __eq__(self, other_instance):
return (isinstance(other_instance, MyClass) and
self.number == other_instance.number)
# instantiate the class
my_instance = MyClass(1)
print(my_instance.__hash__)
print(hash(my_instance))
Output:
None
Traceback (most recent call last):
...
print(hash(my_instance))
TypeError: unhashable type: 'MyClass'
В тот момент, когда наш пользовательский класс начал реализовывать метод __eq__(), по умолчанию для атрибута __hash__ было установлено значение None, и поэтому метод __hash__() начал выдавать нам исключение.
Чтобы все исправить, теперь нам нужно также реализовать метод __hash__():
# build a custom class
class MyClass():
def __init__(self, number):
self.number = number
# implement / override the __eq__ method
def __eq__(self, other_instance):
return (isinstance(other_instance, MyClass) and
self.number == other_instance.number)
# implement / override the __hash__ method
def __hash__(self):
return hash(self.number)
# instantiate the class
my_instance = MyClass(1)
print(my_instance.__hash__)
print(hash(my_instance))
Output:
<bound method MyClass.__hash__ of <__main__.MyClass object at 0x7ff0fe5fffd0>>
1
Итак, как мы видели, теперь экземпляр стал хэшируемым. Ключевой вывод: если мы реализуем/переопределяем метод __eq__(), если мы хотим, чтобы экземпляр можно было хэшировать, мы также должны реализовать метод __hash__().
В Интернете есть много документации об этом, убедитесь, что вы также углубитесь в нее и расширите свои знания.
Завернув очередной, благодарю вас, желаю вам здоровья и благополучия и, конечно же, удачного кодинга! До следующего!
Дак — инженер-программист, наставник, писатель и иногда даже учитель. Обладая более чем 12-летним опытом разработки программного обеспечения, он теперь является настоящим сторонником языка программирования Python, а его страстью является помощь людям в оттачивании их навыков Python и программирования в целом. Вы можете связаться с колодой в Linkedin, Facebook, Twitter и Discord: Deck451#6188, а также следить за его публикациями здесь, на Medium.
Дополнительные материалы на PlainEnglish.io. Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter, LinkedIn, YouTube и Discord . Заинтересованы в хакинге роста? Ознакомьтесь с разделом Схема.
