0

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

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
AndreasInfo
  • 1,062
  • 11
  • 26

1 Answers1

0

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).

AndreasInfo
  • 1,062
  • 11
  • 26