python - 使用可变对象的副本作为字典键

Question

据我所知，python 要求对象是不可变的才能用作字典键。例如，我们不能使用 list 作为字典键，我们必须先将它们转换为 tuple。那么制作可变对象的副本并使用副本作为键有什么问题呢？这样，对对象的更改不会影响 key 。是因为这种方法空间效率低还是其他原因？

Answer 1

dict 不通过在内部制作深拷贝来接受可变对象有几个原因，每个原因都足够了。这些原因包括:

1) 这会使插入的开销任意高。

2) 这会使插入的开销不可预测。

3) 它会破坏 O(1) 查找。

O(1) 查找是通过对键进行散列并将该散列值用作表中的索引来实现的。这假定 key 可以存在永久哈希。

考虑一下，在您假设的 Python 版本中，这个程序:

d = { [1,2,3]:"hello" }
for k in d:
    k.append(4)

我们正在修改字典的复制键对象。显然必须重新计算哈希，同样显然必须重新计算 d 的哈希表。但当？或者，拟人化一下，d 怎么知道 k 修改了自己？答案:实际上，它不能。

不，如果我们想要 O(1) 查找，我们需要一个哈希表。如果我们想要一个哈希表，我们需要键的永久哈希值。如果我们想要键的永久哈希值，我们需要不可变对象(immutable对象)。

相反，如果我们想要可变键，我们可以实现 O(logN) 查找。但是由于 Python 需要 O(1) 查找，我们有不可变的键。