Use which hash functions for count-min sketch?

Question

I am trying to implement count-min sketch with JavaScript. As I need some hash functions, I can not figure out which ones I can/should/must use. Any suggestions?

If this question is stupid, I'd appreciate a hint. Thanks

Answer 1

I think the solution is universal hashing, where you chose random hashfunctions out of a family of hashfunctions. When

• m = universe, e.g. 32 bit which is 2^32-1 possibilities
• p = next prime above m, e.g. 4294967311
• a,b = randomly chosen with 0 < a < p and 0 <= b < p

Then

• h_a,b(x)=((ax+b)mod p)mod m)

is universal.

There is plenty of information online, starting with Wikipedia (https://en.wikipedia.org/wiki/Universal_hashing).