哈希 np.array -> int 的确定性方法

Question

我正在创建一个在 pyarrow.plasma 中存储大型 numpy 数组的系统。我想给每个数组一个唯一的，确定性的 plasma.ObjectID，np.array 可悲的是不可散列我当前的（损坏的）方法是：

import numpy as np
from pyarrow import plasma
def int_to_bytes(x: int) -> bytes:
    return x.to_bytes(
        (x.bit_length() + 7) // 8, "big"
    )  # 
def get_object_id(arr):
    arr_id = int(arr.sum() / (arr.shape[0]))
    oid: bytes = int_to_bytes(arr_id).zfill(20)  # fill from left with zeroes, must be of length 20
    return plasma.ObjectID(oid)

但这很容易失败，例如：

arr = np.arange(12)
a1 = arr.reshape(3, 4)
a2 = arr.reshape(3,2,2)
assert get_object_id(a1) != get_object_id(a2), 'Hash collision'
# another good test case
assert get_object_id(np.ones(12)) != get_object_id(np.ones(12).reshape(4,3))
assert get_object_id(np.ones(12)) != get_object_id(np.zeros(12))

它还涉及对数组求和，这对于大型数组来说可能非常慢。随意假设 arr 的 dtype 将是 np.uint 或 np.int.

我知道永远不会发生哈希冲突是不可能的（我只有 20 个字节的 ID 并且有超过 2^20 个）可能的输入，所以我只是在寻找要么 a）计算成本更低 b) 在实践中不太可能失败

或者，理想情况下，两者！

Answer 1

hashlib 模块有一些例程用于从字节字符串（通常用于 CRC）计算哈希值。您可以使用 ndarray.tobytes 将 ndarray 转换为字节字符串，但是您的示例仍然会失败，因为这些数组具有相同的字节但形状不同。所以你也可以散列形状。

def hasharr(arr):
  hash = hashlib.blake2b(arr.tobytes(), digest_size=20)
  for dim in arr.shape:
    hash.update(dim.to_bytes(4, byteorder='big'))
  return hash.digest()

示例：

>>> hasharr(a1)
b'\x9f\xd7<\x16\xb6u\xfdM\x14\xc2\xe49.\xf0P\xaa[\xe9\x0bZ'
>>> hasharr(a2)
b"Z\x18+'`\x83\xd6\xc8\x04\xd4%\xdc\x16V)\xb3\x97\x95\xf7v"

我不是 blake2b 方面的专家，因此您必须自己进行研究才能确定发生碰撞的可能性。

我不确定你为什么标记 pyarrow 但如果你想在 pyarrow 数组上做同样的事情而不转换为 numpy 那么你可以使用 arr.buffers() 获取数组的缓冲区并将这些缓冲区（会有多个，有些可能 None）转换为 buf.to_pybytes() 的字节串。只需散列所有缓冲区。不需要担心这里的形状，因为 pyarrow 数组总是一维的。

哈希 np.array -> int 的确定性方法

Deterministic method to hash np.array -> int

python

hash

numpy

pyarrow