在Python中,为什么元组可以清除而不是列表？

Question

下面当我尝试哈希一个列表时,它给了我一个错误但是使用了一个元组.猜猜它与不变性有关.有人可以详细解释一下吗？

名单

 x = [1,2,3]
 y = {x: 9}
  Traceback (most recent call last):
   File "<stdin>", line 1, in <module>
 TypeError: unhashable type: 'list'

元组

z = (5,6)
y = {z: 89}
print(y)
{(5, 6): 89}

Answer 1

Dicts和其他对象使用哈希来快速存储和检索项目.这一切的机制都发生在"幕后" - 你作为程序员不需要做任何事情,Python在内部处理它.基本思想是,当你创建一个字典时{key: value},Python需要能够散列你用过的任何东西,key这样它就可以快速存储和查找值.

不可变对象或无法更改的对象是可清除的.它们有一个永不改变的唯一值,因此python可以"散列"该值并使用它来有效地查找字典值.属于此类别的对象包括字符串,元组,整数等.您可能会想,"但我可以更改字符串!我只是去mystr = mystr + 'foo',但实际上这是创建一个新的字符串实例并将其分配给它mystr,它不会修改现有实例.不可变对象永远不会改变,所以你可以始终确保在为不可变对象生成哈希时,通过哈希查找对象将始终返回您开始使用的同一对象,而不是修改后的对象.

你可以试试这个自己:hash("mystring"),hash(('foo', 'bar')),hash(1)

可变对象或可以修改的对象不可清除.列表可以就地修改:mylist.append('bar')或mylist.pop(0).您无法安全地对可变对象进行哈希处理,因为您无法保证自上次查看对象后该对象没有更改.你会发现list,set和其他可变类型没有一个__hash__()方法.因此,您不能将可变对象用作字典键.

编辑:Eric Duminil的回答提供了一个很好的例子,说明了使用可变对象作为字典键所产生的意外行为

Answer 2

以下是为什么允许可变类型作为键可能不是一个好主意.在某些情况下,此行为可能很有用,但也可能导致令人惊讶的结果或错误.

蟒蛇

通过__hash__在以下子类上定义,可以使用数字列表作为键list:

class MyList(list):
    def __hash__(self):
        return sum(self)

my_list = MyList([1, 2, 3])

my_dict = {my_list: 'a'}

print my_dict.get(my_list)
# 'a'

my_list[2] = 4  # __hash__() becomes 7
print my_dict.keys()[0]
# [1, 2, 4]
print my_dict.get(my_list)
# None
print my_dict.get(MyList([1,2,3]))
# None

my_list[0] = 0  # __hash_() is 6 again, but for different elements
print my_dict.keys()[0]
# [0, 2, 4]
print my_dict.get(my_list)
# 'a'

红宝石

在Ruby中,允许使用列表作为键.Ruby列表被称为Arraya Hash,而dict是a ,但语法与Python非常相似:

my_list = [1]
my_hash = { my_list => 'a'}
puts my_hash[my_list]
#=> 'a'

但是如果修改了这个列表,那么即使密钥仍在dict中,dict也不会再找到相应的值:

my_list << 2

puts my_list
#=> [1,2]

puts my_hash.keys.first
#=> [1,2]

puts my_hash[my_list]
#=> nil

可以强制dict再次计算键哈希值:

my_hash.rehash
puts my_hash[my_list]
#=> 'a'

Answer 3

哈希集计算对象的哈希，并基于该哈希将对象存储在结构中以进行快速查找。结果，根据约定，一旦将对象添加到字典中，就不允许更改哈希值。大多数好的哈希函数将取决于元素的数量和元素本身。

元组是不可变的，因此在构造之后，值不能更改，因此哈希值也不能更改（或者至少一个好的实现不应让哈希值更改）。

另一方面，列表是可变的：以后可以添加/删除/更改元素。结果，哈希值可能会违反合同而发生变化。

因此，所有不能保证哈希函数在添加对象后保持稳定的对象都违反了合同，因此不是好的候选对象。因为要进行查找，字典将首先计算键的哈希值，然后确定正确的存储桶。如果同时更改了密钥，则可能会导致误报：该对象位于词典中，但是由于哈希值不同，因此无法再检索它，因此将搜索与最初添加对象的桶不同的桶。 。