mercredi 27 septembre 2017

Fastest way to generate hash function from k wise independent hash family for small k(<=5)

I need a hash function h[n]:[t] from k wise independent hash family when k is small(<=5). Or I need n hash values from [1-t] coming from a hash function which comes from k wise independent hash family. I am trying to implement some randomized algorithms where I needed this. I was generating n random number from range [1-t] using scipy.stats.randint(0,self._t).rvs(self._n)
but this seems to be too slow for my application. Since I don't need full randomness but only 4 wise independence I was wondering if I could speed this up. I know I can use polynomial hash family to get k wise independence but is this the best? If yes are there any fast implementation of this which I can plug in? If no what are the alternative ways(libraries possibly in python)?
I have looked at this thread Obtaining a k-wise independent hash function but I am not sure what the accepted answer mean by this "if you need k different hash, just re-use the same algorithm k times, with k different seeds"
Any suggestions are greatly appreciated. Thanks




Aucun commentaire:

Enregistrer un commentaire