Python快速哈希可变对象

Question

我有一个bytearray,我需要用作字典的键.理想情况下,我不想做像bytearray大小的内存副本.反正有没有这样做？基本上,

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

有没有更快的方法来做到这一点？字节(b)是O(len(字节阵列))操作,这是不希望的.

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没有改变,它这次在字典中创建了一个新的键值对？

每次我通过一把钥匙d,那把钥匙都等于'abcd'.但是因为第一个键的值在添加到字典后发生了变化,所以Python无法判断新键的值是否与添加时的旧键相同.现在,字典中有两个键值对,当时应该只有一个键值对.

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

而对于好奇:肯定,buffer缓存第一个哈希,但这根本没有帮助.只有两个键值,因此这应该只生成两个dict条目:

>>> 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}