NumPy -最快的非加密抗冲突哈希

kq4fsx7k  于 2023-03-30  发布在  其他
关注(0)|答案(1)|浏览(129)

我正在寻找最好的64-bit(或至少32-bithash functionNumPy具有以下属性:
1.它针对numpy进行了向量化,这意味着它应该具有散列任何N-D numpy数组的所有元素的函数。
1.它可以应用于任何可散列的numpy的dtype。为此,这种散列能够处理原始字节块就足够了。
1.它非常非常快,就像xxhash一样。特别是对于很多小的输入,比如32,64位数字的大数组或短np.str_,它应该很快,但也应该处理其他数据类型。
1.它应该是collision-resistant。我可能只使用了一部分位,所以哈希中的任何数量的位都应该是抗冲突的。
1.它可能是(也可能不是)非排版的,这意味着如果它有时可以被反转,就像xxhash一样。
1.它应该产生64-bit整数或更大的输出,但如果它是32-bit,那么仍然是可以的,尽管不是最好的。如果可能的话,选择产生大小为32,64,128位的哈希值会更好。
1.它本身应该在内部将numpy数组转换为字节,以便快速散列,或者至少可能在numpy中已经有这样的转换函数,可以将任何流行的dtype的整个N-D数组转换为可变的字节序列,如果有人会告诉我这一点,那就好了。
我会使用上面链接中提到的xxhash,如果它有numpy数组向量化。但现在它只是单对象,它的绑定函数每次调用只接受一个字节块,产生一个整数输出。而xxhash在小(4,8字节)输入,所以可能在大型数组上执行纯Python循环来为每个数字调用xxhash将非常低效。
我需要它做不同的事情,一个是概率存在过滤器(或集合),即我需要设计这样的结构(集合)应按给定概率回答的(对于给定数量的N个元素)如果一个请求的元素可能在集合中或没有。为此,我想使用较低的哈希位来将输入分散在K个桶中,每个桶额外存储一些(可调整)高位数,以增加正确答案的概率。另一个应用是bloom filter。我需要这个集合在添加和请求时非常快,并且在内存中尽可能紧凑,并处理非常大量的元素。
如果没有现成的好的解决方案,那么也许我还可以改进xxhash库,并创建一个pull request到作者的存储库。

rur96b6h

rur96b6h1#

我会选这个

from xxhash import xxh3_64

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

我不认为你能做得更好。我的蹩脚基准测试显示,在我的蹩脚笔记本电脑(旧的i3 CPU)上,这个程序每秒散列2亿个浮点数。

相关问题