Python快速散列可变对象

Question

我有一个字节数组，我需要将其用作字典的键。理想情况下，我想在不复制字节数组大小的内存的情况下执行此操作。有没有办法做到这一点？ 基本上，

b = some bytearray
d[byte(b)] = x

有没有更快的方法来做到这一点？ byte(b) 是一个 O(len(bytearray)) 操作，这是不受欢迎的。

Answer 1

任何实际正确完成其工作的哈希算法都将使用 O(len(b)) 时间。所以“有没有更快的方法来做到这一点”的答案是否定的。

如果您真正关心的是内存 使用，那么原则上您可以将__hash__ 方法添加到bytearray 的子类。但这是一个非常糟糕的主意。看看会发生什么:

>>> class HashableBytearray(bytearray):
...     def __hash__(self):
...         return hash(str(self))
... 
>>> h = HashableBytearray('abcd')
>>> hash(h)
-2835746963027601024
>>> h[2] = 'z'
>>> hash(h)
-2835746963002600949

所以同一个对象可能散列到字典中的两个不同位置，这是不应该发生的。情况变得更糟:

>>> d = dict()
>>> hb1 = HashableBytearray('abcd')
>>> hb2 = HashableBytearray('abcd')
>>> d[hb1] = 0
>>> d[hb2] = 1
>>> d
{bytearray(b'abcd'): 1}

好的，到目前为止，还不错。值相等，因此字典中应该只有一项。一切都按预期工作。现在让我们看看当我们更改 hb1 时会发生什么:

>>> hb1[2] = 'z'
>>> d[hb2] = 2
>>> d
{bytearray(b'abzd'): 1, bytearray(b'abcd'): 2}

看看虽然 hb2 一点都没变，但这次它在字典中创建了一个新的键值对？

每次我将 key 传递给 d 时，该 key 等于 'abcd'。但是因为第一个键的值在添加到字典后发生了变化，Python 无法判断新键的值是否与添加时旧键的值相同。现在字典中有两个键值对，而应该只有一个。

这只是使用可变值作为键可能导致不可预测和非常错误的行为的众多方式之一。只需将 bytearray 转换为不可变类型，或者首先使用不可变类型。

---

对于好奇者:当然，buffer 缓存了第一个散列，但这根本没有帮助。只有两个键值，所以这应该只生成两个字典条目:

>>> a, b, c = bytearray('abcd'), bytearray('abcd'), bytearray('abzd')
>>> a_buf, b_buf, c_buf = buffer(a), buffer(b), buffer(c)
>>> d = {b_buf:1, c_buf:2}
>>> b[2] = 'z'
>>> d[a_buf] = 0

但它生成三个:

>>> d
{<read-only buffer for 0x1004a2300, size -1, offset 0 at 0x100499cb0>: 1, 
 <read-only buffer for 0x1004a2420, size -1, offset 0 at 0x100499cf0>: 0, 
 <read-only buffer for 0x1004a22d0, size -1, offset 0 at 0x100499c70>: 2}