Python快速哈希可变对象

Question

我有一个字节数组，我需要用作字典的关键字。理想情况下，我想这样做，而不是做一个字节数组大小的内存副本。无论如何要做到这一点？ 基本上，

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

有没有更快的方法来做到这一点？字节（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：

查看如何即使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} 

Answer 2

如果你很在意时间，关键是你正在使用是永远不变的对象，你可以（在内存中的位置）使用其id在你的字典中的关键：

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

如果你关心内存，你可以在你的字节数组上使用一个很好的加密散列函数，并且你可能永远不会发生冲突（例如，git使用sha1，并且在internet上存在somediscussions关于它有多大可能性得到一个无意的sha1碰撞）。如果您同意与无穷小的风险，你可以：

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

这将是为O（n）在你的字节数组的大小时间（每次计算散列时间），但你'd能够在稍后读入不同的字节数组，但表示相同的字节序列，这将散列到相同的字典密钥。

而@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