Python快速哈希可变对象

Question

Python快速哈希可变对象

5

我有一个bytearray，需要将其用作字典的键。理想情况下，我希望能够在不复制bytearray大小的内存的情况下实现此操作。有没有办法做到这一点？基本上，

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

有没有更快的方法来做这件事？byte(b)是一个O(len(bytearray))的操作，这是不可取的。

- RyanCheu

你会如何处理哈希冲突？ - Cameron

问题不在于碰撞，而在于如果您突变密钥会发生什么。 - FogleBird

1

你使用的是哪个版本的Python？ - jedwards

1

你是否关注内存或处理时间，因为2（O(len(b))) [转换为bytes，然后哈希] 仍然是O(len(b))。 - jedwards

3个回答

4

如果您担心时间问题，并且您使用的关键字始终是相同的对象，则可以使用其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()这样的它的不可变函数），您不希望使用实际上是可变的对象。用作字典键的对象的哈希值不能更改; 这违反了字典对象对哈希函数的预期不变量。

- Matt Anderson

1

请注意，如果您使用id值，则需要确保您获取id的对象的生命周期比id更长。即不要使用此技术来映射可能在字典之前被垃圾回收的对象。否则，任何分配在与旧对象相同的内存地址上的对象（这不是不太可能的情况，因为释放将为随后的分配打开一个方便的内存空洞）将似乎已经在字典中。 - Ben

我非常喜欢在嵌入式系统、密钥异常大的情况下使用密码哈希建议，因为这些情况下存在真正的内存耗尽风险。 - senderle

1

我认为这可能接近你想要的。它相对快速，不会复制bytearray大小的内存，但是它确实是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

- martineau

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- senderle · Accepted Answer

任何正确执行其工作的哈希算法都需要O(len(b))时间。因此，“有没有更快的方法来做到这一点”的答案是“没有”。

如果您实际关心的是内存使用情况，那么原则上可以向bytearray的子类添加__hash__方法。但这是一个相当糟糕的想法。看看会发生什么：

>>> 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会缓存第一个哈希值，但这完全没有帮助。只有两个键值，因此这应该仅生成两个字典条目：

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