search

tjwebb / fnv-plus

Javascript FNV-1a Hash Algorithm (up to 1024 bit) implementation. Based on:
http://tools.ietf.org/html/draft-eastlake-fnv-06
85 stars 13 forks source link

52 bit fnv not working properly? #7

Open yhahn opened 9 years ago

yhahn commented 9 years ago

I picked up this module to make use of the 52-bit fnv1a hashes. After some use, however, I noticed that it was generating a lot of collisions -- many more than the 32-bit fnv1a hash that we'd been using before.

To demonstrate I've put a gist together -- it hashes 1 million random text strings -- 32 and 64 bit fnv1a behave about as expected but the 52 bit hash is :flushed:

32 bits, collisions: 0.009% (92/1000000)
52 bits, collisions: 85.581% (855814/1000000)
64 bits, collisions: 0.000% (0/1000000)

A quick glance at the code makes me a little curious about this comment https://github.com/tjwebb/fnv-plus/blob/master/index.js#L124-L128 -- afaik bitwise operators only work with 32-bit integers in JS. Is this not true?

tjwebb commented 8 years ago

I'll take look, sorry I noticed this issue just now.

Kirill89 commented 8 years ago

I have a same issue. Please fix this as soon as possible.

P.S.: нere is my example if you need.

limoragni commented 7 years ago

I've been using this module for a while now. At first I was using it with very different strings so I didn't noticed this bug. With similar strings is giving the same output! Since 52 bits is the default you get lots of collisions. Any plans on fixing this? Otherwise it should be on the docs.

connorjburton commented 7 years ago

Any updates on this @tjwebb ?

desudesutalk commented 7 years ago

Yep, bitwise operators only work with 32-bit integers in JS. So this function will not work if implemented in that way. I fixed 52bit hash in #9 so it returns 52bit JS integer and computes hash according to FNV specs.

But it is important to remember what any bitwise operation will convert this hash to 32bit. So this version must be used when number is needed as is.

Another interesting fact - 52bit version is fastest one.

maxammann commented 5 years ago

I just stumbled upon this while fixing a bug :D Can you publish the fixed version on npm? :)