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: https://github.com/Cyan4973/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 values, just re-use the same algorithm k times, with k different seeds.