NumPy - 最快的非加密抗碰撞哈希

Question

我正在为NumPy寻找最好的64-bit（或至少是32-bit）具有下一个属性的哈希函数：

1. 它针对 numpy 进行了矢量化，这意味着它应该具有散列任何 ND numpy 数组的所有元素的函数。
2. 它可以应用于任何可散列的 numpy 的dtype. 为此，这种散列能够仅处理原始字节块就足够了。
3. 它非常非常快，就像xxhash一样。特别是对于许多小输入，例如 32、64 位数字或短 np.str_ 的巨大数组，它应该很快，但也应该处理其他 dtype。
4. 它应该是抗碰撞的。我可能只使用部分位，所以散列中的任意数量的位也应该是抗碰撞的。
5. 它可能是（也可能不是）非加密的，这意味着如果它有时可以反转就可以了，比如xxhash.
6. 它应该产生64-bit整数或更大的输出，但如果是，32-bit那么仍然可以，尽管不是那么可取。如果可能的话，最好选择生成 32、64、128 位大小的散列。
7. 它本身应该在内部将 numpy 数组转换为字节以使散列速度更快，或者至少可能在 numpy 中已经有这样的转换函数，可以将任何流行的 dtype 的整个 ND 数组转换为可变的字节序列，如果有人会告诉我这个很好.

xxhash如果它有numpy数组矢量化，我会使用上面链接提到的。但是现在它只是单个对象，它的绑定函数每次调用只接受一个字节块，产生一个整数输出。并且 xxhash 每次调用小（4、8 个字节）输入时只使用几个 CPU 周期，因此可能在大数组上执行纯 Python 循环来为每个数字调用 xxhash 效率非常低。

我需要它用于不同的事情，一个是概率存在过滤器（或集合），即我需要设计这样的结构（集合），N如果请求的元素可能在集合中或不是。为此，我想使用较低的散列位将输入分布到K存储桶中，并且每个存储桶还存储一些（可调整的）较高位的数量，以增加正确答案的概率。另一个应用是布隆过滤器。我需要这个集合在添加和请求时非常快，并且在内存中尽可能紧凑，并处理非常多的元素。

如果没有现有的好的解决方案，那么也许我还可以改进xxhash库并向作者的存储库创建拉取请求。

Answer 1

我会这样做：

from xxhash import xxh3_64

def hash_numpy(array):
    return xxh3_64(array.tobytes()).digest()

我不认为你能变得更好。我蹩脚的基准测试表明，在我蹩脚的笔记本电脑（旧的 i3 CPU）上，每秒哈希 2 亿个浮点数。