Из недавнего вопроса SO (см. Создайте словарь в python, который индексируется списками) Я понял, что, вероятно, ошибочно понял смысл хешируемых и неизменяемых объектов в python.
Хеширование - это процесс преобразования некоторого большого количества данных в гораздо меньшую сумму (как правило, одно целое) повторяемым образом, так что его можно искать в таблице в постоянном времени (O(1)), что важно для высокопроизводительных алгоритмов и структур данных.
Неизменность - это идея о том, что объект не изменится каким-то важным образом после его создания, особенно любым способом, который может изменить хэш-значение этого объекта.
Эти две идеи связаны с тем, что объекты, которые используются как хэш-ключи, обычно должны быть неизменными, поэтому их хеш-значение не изменяется. Если бы было разрешено изменить, то местоположение этого объекта в структуре данных, такое как хэш-таблица, изменилось бы, и тогда вся цель хэширования для эффективности будет побеждена.
Чтобы действительно понять идею, вы должны попытаться реализовать свою собственную хэш-таблицу на языке C/С++ или прочитать реализацию Java класса HashMap.
Технически хеширование означает, что класс определяет __hash __(). Согласно документам:
__ hash __() должен возвращать целое число. Единственное требуемое свойство состоит в том, что объекты, которые сравнивают одинаковые, имеют одно и то же значение хэш-функции; рекомендуется каким-то образом смешивать (например, с использованием эксклюзивных или) хеш-значений для компонентов объекта, которые также играют роль в сравнении объектов.
Я думаю, что для типов встроенных python все хешируемые типы также неизменяемы. Было бы трудно, но, возможно, не невозможно иметь изменяемый объект, который, тем не менее, определял __hash __().
Из Python Glossary:
Объект hashable, если он имеет значение хэша, которое никогда не изменяется в течение его жизненного цикла (ему нужен метод
__hash__()), и его можно сравнить с другими объектами (ему нужен метод__eq__()или__cmp__()). Объекты Hashable, которые сравниваются равными, должны иметь одно и то же значение хэш-функции.Hashability позволяет использовать объект как ключ словаря и член набора, поскольку эти структуры данных используют внутреннее значение хэша.
Все неиспользуемые встроенные объекты Pythons являются хешируемыми, в то время как нет изменяемых контейнеров (таких как списки или словари). Объекты, являющиеся экземплярами пользовательских классов, по умолчанию хешируются; все они сравниваются неравномерно, а их хэш-значение - их id().
Дикты и наборы должны использовать хэш для эффективного поиска в хэш-таблице; значения хэша должны быть неизменными, так как изменение хэша испортит структуры данных и приведет к сбою dict или set. Самый простой способ сделать значение хеша неизменным - сделать весь объект неизменным, поэтому два часто упоминаются вместе.
Хотя ни один из встроенных изменяемых объектов не является хешируемым, можно создать изменяемый объект с хеш-значением, которое не изменено. Общеизвестно, что только часть объекта представляет свою личность, а остальная часть объекта содержит свойства, которые могут быть изменены. Пока значение хеш-функции и функции сравнения основаны на идентификаторе, но не изменяемых свойствах, а личность никогда не изменяется, вы выполнили требования.
Существует неявный, даже если нет явной связи, вынужденной между неизменяемыми и хешируемыми из-за взаимодействия между
Здесь нет проблем, если вы не переопределите __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.
На самом деле это означает при создании хеша (b) == hash (c), несмотря на то, что никогда не сравниваются равные. Я изо всех сил стараюсь найти полезное определение __hash__() для изменяемого объекта, который определяет сравнение по значению.
Примечание: __lt__, __le__, __gt__ и __ge__ не влияют, поэтому вы все же можете определить упорядочение хешируемых объектов, изменяемых или иным образом на основе их значения.
просто потому, что это лучший хит 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.
Неизменяемый означает, что объект не будет меняться каким-либо значительным образом в течение его срока службы. Это неопределенная, но общая идея в языках программирования.
Хешируемость немного отличается и относится к сравнению.
hashable Объект hashable, если он имеет значение хэша, которое никогда изменений в течение его жизненного цикла (ему нужен метод
__hash__()) и может быть по сравнению с другими объектами (ему нужен метод__eq__()или__cmp__()). Объекты Hashable, которые сравниваются равными, должны иметь одно и то же значение хэш-функции.
Все пользовательские классы имеют __hash__ метод, который по умолчанию возвращает идентификатор объекта. Таким образом, объект, который удовлетворяет критериям хешируемости, не обязательно является неизменным.
Объекты любого нового класса, который вы объявляете, могут использоваться в качестве словарного ключа, если только вы не предотвращаете его, например, бросая из __hash__
Можно сказать, что все неизменяемые объекты хешируются, потому что, если хэш изменяется во время жизни объекта, это означает, что объект мутировался.
Но не совсем. Рассмотрим кортеж, который имеет список (изменяемый). Некоторые говорят, что кортеж неизменен, но в то же время он несколько не хешируется (бросает).
d = dict()
d[ (0,0) ] = 1 #perfectly fine
d[ (0,[0]) ] = 1 #throws
Хешируемость и неизменность относятся к объекту instancess, а не к типу. Например, объект типа кортежа может быть хешируемым или нет.
В Python кортеж является неизменным, но он хешируется, только если все его элементы хешируются.
>>> tt = (1, 2, (30, 40))
>>> hash(tt)
8027212646858338501
>>> tl = (1, 2, [30, 40])
>>> hash(tl)
TypeError: unhashable type: 'list'
Типы Hashable
В Python они в основном взаимозаменяемы; поскольку хеш должен представлять контент, поэтому он так же изменен, как и объект, и имеет изменение объекта, значение хэша сделает его непригодным для использования в качестве ключа dict.
В других языках хеш-значение больше связано с идентификацией объектов, а не (обязательно) значением. Таким образом, для изменяемого объекта указатель можно использовать для запуска хэширования. Предполагая, конечно, что объект не перемещается в памяти (как это делает некоторый GC). Например, это подход, используемый в Lua. Это делает изменяемый объект применимым в качестве ключевого слова таблицы; но создает несколько (неприятных) сюрпризов для новичков.
В конце концов, наличие неизменяемого типа последовательности (кортежи) делает его более приятным для "многозначных ключей".
Hashable означает, что значение переменной может быть представлено (или, скорее, закодировано) константой - строкой, числом и т.д. Теперь то, что может быть изменено (изменено), не может быть представлено чем-то, что не является. Поэтому любая переменная, которая является изменяемой, не может быть хешируемой и, тем самым, могут быть хешируемыми только неизменяемые переменные.
Надеюсь, что это поможет...