获得k-wise独立散列函数 [英] Obtaining a k-wise independent hash function

问题描述

我需要使用属于k-wise独立散列函数族的散列函数。 C，C ++或python中的任何库或工具包上的任何指针，它们都可以生成一组k-wise独立散列函数，我可以从中选择一个函数。

背景：我试图在这里实现这个算法： http://researcher.watson.ibm.com/researcher/files/us-dpwoodru/knw10b.pdf 了解不同元素问题。

我已经看过这个主题：生成k个成对独立散列函数，其中提到使用Murmur散列来生成成对独立散列函数。我想知道是否有任何类似的k-独立散列函数。如果没有可用的，是否有可能构建这样一组k-wise独立散列函数。

预先感谢。

解决方案

这是许多解决方案之一，但您可以使用以下开源哈希算法：
http://code.google.com/p/xxhash/

考虑到主函数声明：
unsigned int XXH32（const void *所以如果你需要k个不同的哈希值，只需用k次不同的种子重复使用相同的算法k次。

p>

I need to use a hash function which belongs to a family of k-wise independent hash functions. Any pointers on any library or toolkit in C, C++ or python which can generate a set of k-wise independent hash functions from which I can pick a function.

Background: I am trying to implement this algorithm here: http://researcher.watson.ibm.com/researcher/files/us-dpwoodru/knw10b.pdf for the Distinct Elements problem.

I have looked at this thread: Generating k pairwise independent hash functions which mentions using Murmur hash to generate a pairwise independent hash function. I was wondering if there is anything similar for k-wise independent hash functions. If there is none available, would it be possible for me to construct such a set of k-wise independent hash functions.

Thanks in advance.

解决方案

This is one of many solutions, but you could use for example the following open-source hash algorithm : http://code.google.com/p/xxhash/

Then, to generate different hashes, you just have to provide different seeds.

Considering the main function declaration : unsigned int XXH32 (const void* input, int len, unsigned int seed);

So if you need k different hash, just re-use the same algorithm k times, with k different seeds.

这篇关于获得k-wise独立散列函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！