python - 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这一次它是如何在字典中创建了一个新的键值对的？

每次我将一个键传递给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}

Answer 2

如果您关心时间，并且您使用的键始终是同一个object，您可以使用它id（内存中的位置）作为字典中的键：

b = some byte array
d[id(b)] = x

如果你关心内存，你可以在你的字节数组上使用一个好的加密哈希函数，你可能永远不会发生冲突（例如，git 使用 sha1，互联网上有一些 关于如何可能是无意中发生 sha1 碰撞）。如果您可以接受这种极小的风险，您可以：

b = some byte array
d[hashlib.sha1(b).hexdigest()] = x

这将是您的字节数组大小的 O(n)时间（每次计算散列时），但是您可以稍后读取不同的字节数组，但表示相同的序列字节，这将散列到相同的字典键。

@senderle 是绝对正确的；您不想使用实际上是可变的对象，当按值使用它时（而不是它的不可变函数，例如id()）作为字典的键。用作字典键的对象的哈希值不得更改；它违反了字典对象对哈希函数的期望值的不变量。

Answer 3

我认为这可能接近你想要的。它相对较快并且不会复制字节数组大小的内存，但是它是O(len(bytearray)) - 因为我想不出任何方法来避免这种情况并且总是产生唯一值。

def byte(ba):
    """ decode a bytearray as though it were a base 256 number """
    return reduce(lambda a,d: a*256 + d, ba, 0)

ba = bytearray('this is a bytearray')
d = {}
d[byte(ba)] = 42
ba[8] = 'X'  # now 'this is X bytearray'
d[byte(ba)] = 17  # accesses a separate entry in dict
print d