可哈希,不可变

Hashing 是以可重复的方式将大量数据转换成更小数据量(通常是单个整数)的过程,以便可以在固定时间内在表中查找数据( O(1) ),这对于高性能算法和数据结构非常重要。

Immutability 一个对象在创建之后不会以某种重要的方式改变,特别是以任何可能改变该对象哈希值的方式。

这两个概念是相关的,因为用作哈希键的对象通常必须是不可变的,这样它们的哈希值就不会改变。如果允许更改,则该对象在数据结构(如哈希表)中的位置将发生更改,然后为提高效率而进行哈希处理的整个目的就失败了。

HashMap 班级。

• 是否存在可散列的可变对象或不可散列的不可变对象?

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

哈希类型

• 冻结集始终是可哈希的(根据定义,其元素必须是可哈希的)
• 只有元组的所有元素都是可哈希的,元组才是可哈希的
• 默认情况下,用户定义的类型是可散列的,因为它们的散列值是它们的id()

从 Python Glossary

如果对象的哈希值在其生存期内从未更改(它需要一个 __hash__() __eq__() 或 __cmp__()

哈希性使对象可用作字典键和集合成员,因为这些数据结构在内部使用哈希值。

所有python不可变的内置对象都是可散列的,而不支持可变容器(如列表或字典)。默认情况下,作为用户定义类实例的对象是可散列的;它们都比较不相等,哈希值是它们的id()。

虽然没有一个内置的可变对象是可散列的,但是可以使用 不

从技术上讲,hashable意味着类定义 __hash__() . 根据文件:

应返回整数。唯一需要的属性是比较相等的对象具有相同的哈希值;建议以某种方式混合(例如,使用异或)对象组件的哈希值,这些组件在对象比较中也起作用。

尽管如此,要定义一个可变的对象是困难的,但也许不是不可能的

即使不可变和可散列之间没有显式关系,由于它们之间的相互作用,也存在隐式关系

1. 比较相等的可哈希对象必须具有相同的哈希值
2. 如果对象的哈希值在其生存期内从未更改,则该对象是可哈希的。

这里没有问题,除非你重新定义 __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.

__散列__ ()用于定义按值比较的可变对象。

注意 __lt__ , __le__ __gt__ 和 __ge__

不可变意味着对象在其生存期内不会发生任何显著的变化。在编程语言中,这是一个模糊但普遍的概念。

hashable 如果一个对象的哈希值 在其生命周期内发生变化(它需要 __hash__() 与其他对象相比(它需要 __eq__() __cmp__() 比较相等的可哈希对象必须具有相同的哈希值。

所有用户定义的类都具有 __hash__ 方法,默认情况下只返回对象ID。因此满足哈希性条件的对象不一定是不可变的。

声明的任何新类的对象都可以用作字典键,除非通过抛出 __散列__

我们可以说所有不可变对象都是可哈希的,因为如果哈希在对象的生存期内发生变化,则意味着对象发生了变化。

但不完全是。考虑一个具有列表(可变)的元组。有人说元组是不可变的,但同时它有点不可散列(throws)。

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

正因为这是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键使用的哈希性。

在Python中,它们基本上是可以互换的;因为散列应该表示内容,所以它和对象一样是可变的,并且让对象更改散列值会使其无法用作dict键。

在其他语言中,哈希值更多地与对象的“标识”相关,而不一定与值相关。因此,对于可变对象,可以使用指针来启动哈希。当然,假设一个对象没有在内存中移动(就像某些GC那样)。例如,这就是Lua中使用的方法。这使得可变对象可用作表键;但是给新手带来了一些(不愉快的)惊喜。

最后,拥有一个不可变的序列类型(tuples)使“多值键”变得更好。

Hashable意味着一个变量的值可以用一个常量来表示(或者,更确切地说,是编码的)——字符串、数字等等。现在,可以改变的东西(可变的)不能用不可变的东西来表示。因此,任何可变的变量都不能是可哈希的,同样地,只有不可变的变量才能是可哈希的。

希望这有帮助。。。