Hashable, неизменный

Question

Из недавнего вопроса SO (см. Создание словаря на python, который индексируется списками ). Я понял, что, возможно, у меня неправильное представление о значении объектов hashable и неизменяемых в python.

• Что означает хэши на практике?
• Какое отношение между хэшируемым и неизменным?
• Существуют ли изменяемые объекты, которые являются хэшируемыми или неизменяемыми объектами, которые не являются хэшируемыми?

Answer 1

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

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

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

Чтобы действительно понять идею, вы должны попытаться реализовать собственную хеш-таблицу на языке, подобном C / C ++, или прочитать реализацию Java HashMap класса на Java.

Answer 2

• Существуют ли изменяемые объекты, которые являются хэшируемыми, или неизменяемые объекты, которые не являются хэшируемыми?

В Python кортеж неизменен, но его можно хэшировать, только если все его элементы являются хэшируемыми.

>>> tt = (1, 2, (30, 40))
>>> hash(tt)
8027212646858338501
>>> tl = (1, 2, [30, 40])
>>> hash(tl)
TypeError: unhashable type: 'list'

Типы хэшей

• Все атомарные неизменяемые типы могут быть хэшируемыми, например, str, байты, числовые типы
• Замороженный набор всегда может быть хэшируемым (его элементы должны быть хэшируемыми по определению)
• Кортеж может быть хэшируемым, только если все его элементы являются хэшируемыми
• Пользовательские типы по умолчанию могут быть хэшируемыми, потому что их хеш-значением является их id ()

Answer 3

Технически, hashable означает, что класс определяет __hash__().Согласно документам:

__hash__() должен возвращать целое число.Единственным обязательным свойством является то, что объекты, которые сравниваются равными, имеют одинаковое значение хеш-функции;Рекомендуется как-то смешивать (например, используя exclusive или) хеш-значения для компонентов объекта, которые также играют роль в сравнении объектов.все типы hashable также неизменны.

Было бы трудно, но, возможно, не невозможно иметь изменяемый объект, который, тем не менее, определил __hash__().

Answer 4

Из Глоссарий Python :

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

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

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

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

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

Answer 5

Существует неявное, даже если нет явных отношений между неизменяемыми и хешируемыми из-за взаимодействия между

1. Хешируемые объекты, которые сравниваются равными, должны иметь одинаковое значение хеша
2. Объект является хешируемым, если у него есть хеш-значение, которое никогда не изменяется в течение его жизни.

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

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

Трудно увидеть приложение, где это возможно, рассмотрим возможный класс A , который отвечает этим требованиям. Хотя есть очевидный вырожденный случай, когда __hash__ возвращает константу.

Теперь: -

>>> a = A(1)
>>> b = A(1)
>>> c = A(2)
>>> a == b
True
>>> a == c
False
>>> hash(a) == hash(b)
True
>>> a.set_value(c)
>>> a == c
True
>>> assert(hash(a) == hash(c)) # Because a == c => hash(a) == hash(c)
>>> assert(hash(a) == hash(b)) # Because hash(a) and hash(b) have compared equal 
                                 before and the result must stay static over the objects lifetime.

Фактически это означает, что при создании hash (b) == hash (c), несмотря на то, что они никогда не сравниваются равными. Я изо всех сил пытаюсь увидеть в любом случае, чтобы с пользой определить __hash__ () для изменяемого объекта, который определяет сравнение по значению.

Примечание : __lt__, __le__, __gt__ и __ge__ сравнения не затрагиваются, поэтому вы все равно можете определить порядок объектов, которые можно хэшировать, изменяемые или иные, на основе их значения.

Answer 6

Неизменяемость означает, что объект не изменится каким-либо существенным образом в течение его срока службы. Это неопределенная, но распространенная идея в языках программирования.

Hashability немного отличается, и относится к сравнению.

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

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

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

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

Но не совсем. Рассмотрим кортеж, у которого есть список (изменяемый). Некоторые говорят, что кортеж неизменен, но в то же время он не является хэшируемым (бросает).

d = dict()
d[ (0,0) ] = 1    #perfectly fine
d[ (0,[0]) ] = 1  #throws

Хешабильность и неизменность относятся к экземпляру объекта, а не к типу. Например, объект типа кортеж может быть хэшируемым или нет.

Answer 7

только потому, что это лучший хит Google, вот простой способ сделать изменяемый объект хазируемым:

>>> class HashableList(list):
...  instancenumber = 0  # class variable
...  def __init__(self, initial = []):
...   super(HashableList, self).__init__(initial)
...   self.hashvalue = HashableList.instancenumber
...   HashableList.instancenumber += 1
...  def __hash__(self):
...   return self.hashvalue
... 
>>> l = [1,2,3]
>>> m = HashableList(l)
>>> n = HashableList([1,2,3])
>>> m == n
True
>>> a={m:1, n:2}
>>> a[l] = 3
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>> m.hashvalue, n.hashvalue
(0, 1)

Я действительно нашел применение для чего-то подобного, когда создавал класс для преобразования записей SQLAlchemy во что-то изменяемое и более полезное для меня, сохраняя при этом их хеш-свойство для использования в качестве ключей dict.

Answer 8

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

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

В конце концов, наличие неизменяемого типа последовательности (кортежей) делает его более привлекательным для «многозначных ключей».

Answer 9

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

Надеюсь, это поможет ...