Что означает «хэшируемый» в Python?

Я попытался найти в интернете, но не смог найти значение hashable.

Когда они говорят, что объекты hashableили hashable objectsчто это значит?

Из глоссария Python :

Объект является хешируемым, если у него есть хеш-значение, которое никогда не изменяется в течение его времени жизни (ему нужен __hash__()метод), и его можно сравнить с другими объектами (ему нужен метод __eq__()или __cmp__()). Хэшируемые объекты, которые сравниваются равными, должны иметь одинаковое хеш-значение.

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

Все неизменяемые встроенные объекты Python являются хэшируемыми, в то время как нет изменяемых контейнеров (таких как списки или словари). Объекты, которые являются экземплярами пользовательских классов, по умолчанию могут быть хэшируемыми; все они сравниваются неравно, и их хэш-значение является их id().

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

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

Например, если у вас есть 10 000 телефонных номеров, и вы хотите сохранить их в массиве (который представляет собой последовательную структуру данных, которая хранит данные в смежных местах памяти и обеспечивает произвольный доступ), но у вас может не быть необходимого количества непрерывных данных. места памяти.

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

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

Для более подробной информации обратитесь к https://en.wikipedia.org/wiki/Hash_function

Вот еще одна хорошая ссылка: http://interactivepython.org/runestone/static/pythonds/SortSearch/Hashing.html

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

#x = hash(set([1,2])) #set unhashable
x = hash(frozenset([1,2])) #hashable
#x = hash(([1,2], [2,3])) #tuple of mutable objects, unhashable
x = hash((1,2,3)) #tuple of immutable objects, hashable
#x = hash()
#x = hash({1,2}) #list of mutable objects, unhashable
#x = hash([1,2,3]) #list of immutable objects, unhashable

Список неизменяемых типов:

int, float, decimal, complex, bool, string, tuple, range, frozenset, bytes

Список изменяемых типов:

list, dict, set, bytearray, user-defined classes

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

>>> tuple_a = (1,2,3)
>>> tuple_a.__hash__()
2528502973977326415
>>> tuple_b = (2,3,4)
>>> tuple_b.__hash__()
3789705017596477050
>>> tuple_c = (1,2,3)
>>> tuple_c.__hash__()
2528502973977326415
>>> id(a) == id(c)  # a and c same object?
False
>>> a.__hash__() == c.__hash__()  # a and c same value?
True
>>> dict_a = {}
>>> dict_a[tuple_a] = 'hiahia'
>>> dict_a[tuple_c]
'hiahia'

мы можем обнаружить, что хеш-значения tuple_a и tuple_c одинаковы, поскольку они имеют одинаковые члены. Когда мы используем tuple_a в качестве ключа в dict_a, мы можем обнаружить, что значение dict_a [tuple_c] одинаково, что означает, что, когда они используются в качестве ключа в dict, они возвращают одно и то же значение, потому что значения хеша тот же самый. Для тех объектов, которые не являются хэшируемыми, хэш метода определен как None:

>>> type(dict.__hash__) 
<class 'NoneType'>

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

Позвольте мне привести вам рабочий пример для понимания хэшируемых объектов в python. Для этого примера я беру 2 кортежа. Каждое значение в кортеже имеет уникальное значение хеша, которое никогда не меняется в течение жизни. Таким образом, на основании этого имеет значение сравнение двух кортежей. Мы можем получить хеш-значение элемента кортежа, используя Id ().

В python это означает, что объект может быть членом множеств для возврата индекса. То есть они имеют уникальную личность / идентификатор.

например, в питоне 3.3:

Списки структуры данных не являются хэшируемыми, но кортежи структуры данных являются хэшируемыми.

Hashable = может хэшироваться.

Хорошо, что такое хеширование? Хеш-функция - это функция, которая принимает объект, например строку «Python», и возвращает код фиксированного размера. Для простоты предположим, что возвращаемое значение является целым числом.

Когда я запускаю хэш ('Python') в Python 3, я получаю 5952713340227947791 в результате. Различные версии Python могут свободно изменять базовую хеш-функцию, поэтому вы, скорее всего, получите другое значение. Важно то, что, несмотря на то, что сейчас я много раз запускаю хэш ('Python'), я всегда получаю один и тот же результат с одной и той же версией Python.

Но hash ('Java') возвращает 1753925553814008565. Поэтому, если объект, который я хэширую, изменяется, то и результат изменяется. С другой стороны, если объект, который я хэширую, не изменяется, то результат остается прежним.

Почему это важно?

Ну, например, словари Python требуют, чтобы ключи были неизменяемыми. То есть ключи должны быть объектами, которые не меняются. Строки являются неизменяемыми в Python, как и другие основные типы (int, float, bool). Кортежи и заморозки также неизменны. Списки, с другой стороны, не являются неизменяемыми (то есть они изменяемы), потому что вы можете изменить их. Точно так же, слова изменчивы.

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

>>> hash('Python')
1687380313081734297
>>> hash('Java')
1753925553814008565
>>>
>>> hash([1, 2])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>> hash({1, 2})
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'set'
>>> hash({1 : 2})
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'dict'
>>>
>>> hash(frozenset({1, 2}))
-1834016341293975159
>>> hash((1, 2))
3713081631934410656

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

Вот почему Python требует от нас использовать неизменяемые типы данных для ключей в словаре.

Для создания таблицы хэширования с нуля все значения должны быть установлены на «Нет» и изменены после возникновения требования. Хешируемые объекты относятся к изменяемым типам данных (словарь, списки и т. Д.). Наборы, с другой стороны, не могут быть повторно инициализированы после назначения, поэтому наборы не могут быть хешируемыми. Принимая во внимание, что вариант set () - frozenset () - является хэшируемым.