python 可哈希、不可变[重复]

ltqd579y  于 2023-03-16  发布在  Python
关注(0)|答案(9)|浏览(155)

此问题在此处已有答案

(18个答案)
What does "hashable" mean in Python?(10个答案)
十小时前关门了。
从最近的一个SO问题(参见Create a dictionary in python which is indexed by lists)中,我意识到我可能对python中hashable和immutable对象的含义有一个错误的概念。

  • hashable在实践中意味着什么?
  • 哈希和不可变之间的关系是什么?
  • 是否存在可哈希的可变对象或不可哈希的不可变对象?
zaqlnxep

zaqlnxep1#

X1 E0 F1 X是以可重复的方式将某个大数据量转换成小得多的数据量(通常是单个整数)的过程,以便可以在恒定时间(X1 M0 N1 X)内在表中查找它,这对于高性能算法和数据结构是重要的。
Immutability是这样的思想,即对象在被创建之后将不会以某些重要方式改变,尤其是以可能改变该对象的散列值的任何方式。
这两个概念是相关的,因为用作哈希键的对象必须是不可变的,这样它们的哈希值就不会改变。如果允许它改变,那么该对象在数据结构(如哈希表)中的位置就会改变,然后哈希提高效率的整个目的就落空了。
要真正理解这个概念,您应该尝试用C/C++之类的语言实现自己的哈希表,或者阅读HashMap类的Java实现。

avkwfej4

avkwfej42#

  • 是否存在可哈希的可变对象或不可哈希的不可变对象?

在Python中,tuple是不可变的,但是只有当它的所有元素都是可哈希的时候,它才是可哈希的。

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

可哈希类型

  • 原子不可变类型都是可散列的,如str、bytes、numeric类型
  • 冻结集始终是可散列的(其元素必须根据定义是可散列的)
  • 仅当元组的所有元素都可哈希时,元组才可哈希
  • 默认情况下,用户定义类型是可哈希的,因为它们的哈希值是它们的id()
e0uiprwp

e0uiprwp3#

Python Glossary
如果一个对象的哈希值在其生存期内从未改变(它需要__hash__()方法),并且可以与其他对象进行比较(它需要__eq__()__cmp__()方法),则该对象是可哈希的。比较相等的可哈希对象必须具有相同的哈希值。
哈希性使对象可以用作字典键和集成员,因为这些数据结构在内部使用哈希值。
所有Python的不可变内置对象都是可散列的,而没有可变容器(如列表或字典)是可散列的。默认情况下,用户定义类的示例对象是可散列的;它们比较起来都不相等,并且它们的散列值是它们的id()。
字典和集合必须使用哈希值,以便在哈希表中进行高效查找;散列值必须是不可变的,因为改变散列值会打乱数据结构,并导致dict或set失败。2使散列值不可变的最简单的方法是使整个对象不可变,这就是为什么这两者经常被一起提到的原因。
虽然没有一个内置的可变对象是可散列的,但是有可能使一个可变对象的散列值是 * 不可 * 可变的。通常只有对象的一部分代表它的身份,而对象的其余部分包含可以自由更改的属性。只要散列值和比较函数基于身份而不是可变属性,身份也不会改变,你就符合要求了

a5g8bdjr

a5g8bdjr4#

从技术上讲,hashable意味着类定义了__hash__()
__hash__()应该返回一个整数。唯一需要的属性是比较相等的对象具有相同的哈希值;建议以某种方式将对象的组件的散列值混合在一起(例如,使用异或),所述散列值也在对象的比较中起作用。
我认为对于Python内置类型,所有的hashable类型也是不可变的。
虽然有一个可变对象定义了__hash__(),但这是很困难的,但也许不是不可能的。

abithluo

abithluo5#

即使没有显式的关系,也存在一种隐式的关系,强制在不可变和可散列之间,这是由于
1.比较结果相等的可哈希对象必须具有相同的哈希值
1.如果一个对象的哈希值在其生存期内从未改变,则该对象是可哈希的。
这里没有问题,除非您重新定义__eq__,以便objects类定义值的等价性。
一旦你这样做了,你需要找到一个稳定的散列函数,它总是返回相同的值的对象表示相同的值(例如,其中__eq__)返回真,并永远不会改变在一个对象的生命周期。
很难找到这样的应用程序,考虑一个满足这些要求的类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__比较不受影响,因此您仍然可以定义可散列对象、可变对象或基于其值的其他对象的排序。

wnavrhmk

wnavrhmk6#

不可变意味着对象在其生命周期内不会发生任何重大变化,这是编程语言中一个模糊但常见的概念。
哈希性略有不同,指的是比较。

可散列如果对象的散列值在其生存期内从未更改(需要__hash__()方法),并且可以与其他对象进行比较(需要__eq__()__cmp__()方法),则该对象是可散列的。比较结果相等的可散列对象必须具有相同的散列值。

所有用户定义的类都有__hash__方法,默认情况下只返回对象ID。因此,满足可散列性标准的对象不一定是不可变的。
您声明的任何新类的对象都可以用作字典键,除非您通过例如从__hash__抛出来阻止它
我们可以说所有不可变的对象都是可散列的,因为如果散列值在对象的生命周期内发生了变化,那么就意味着对象发生了变异。
但不完全是这样。考虑一个有列表的元组(可变的)。有人说元组是不可变的,但同时它也是不可散列的(抛出)。

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

可散列性和不变性指的是对象示例,而不是类型。例如,元组类型的对象可以是可散列的,也可以不是。

2ekbmq32

2ekbmq327#

正因为这是Google的热门主题,这里有一个简单的方法可以使一个可变对象成为hashable:

>>> 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键。

bxfogqkk

bxfogqkk8#

在Python中,它们基本上是可以互换的;因为散列值应该表示内容,所以它和对象一样是可变的,如果对象更改了散列值,它将无法用作dict键。
在其他语言中,散列值更多地与对象的“身份”相关,而不是(必须)与值相关。因此,对于可变对象,指针可以用来启动散列。当然,假设对象不在内存中移动(如一些GC所做的)。例如,这是Lua中使用的方法。这使得可变对象可以用作表键;但是给新手带来了一些(不愉快的)惊喜。
最后,拥有一个不可变的序列类型(元组)使它更适合于“多值键”。

hm2xizp9

hm2xizp99#

Hashable意味着变量的值可以用常量来表示(或者更确切地说,可以用常量来编码)--字符串、数字等等。现在,一些易变的东西(可变的)不能用一些不变的东西来表示。因此,任何可变的变量都不能是hashable,同样,只有不可变的变量才是hashable。
希望这能帮上忙...

相关问题