flat assembler
Message board for the users of flat assembler.
Index
> Main > fnv hashing theory  can you share? 
Author 

cod3b453
I don't know the algorithm but I think the values 16777619 and 2166136261 are prime so any multiple in the field h (2^32) will not collide. This is similar to the linear congruence method used for PRNG functions, where you choose "good" (usually prime) values. When mixing the key stream into the calculation, XOR is a good choice because, unlike addition or multiplication, values such as 0,1,2^n () cannot skew the accumulation in h towards a collision so easily. It's also important that p is smaller (2^8 ) than h so that the upper 24bits are not affected by the current round and carry over to the next iteration.
Given that h is 2^32, there will certainly be a collision after 2^32 different inputs; there is also a fair chance that if you tried 2^32 different keys you'd find one or more collisions. Hope that helps. 

06 Oct 2011, 18:22 

Tomasz Grysztar
idle wrote: Fasm uses the algo too & fasm limits symbols length to 2xx chars: is it proved no collisions appear ever. 

06 Oct 2011, 19:00 

idle
Code: aaigb: arsga: compiles 

06 Oct 2011, 19:55 

Goplat
fasm has a linked list for each used hash value, so you're allowed to have multiple labels with the same hash value, it'll just be slow if there's a whole lot of them. Unless you're making collisions on purpose it won't be a problem.


06 Oct 2011, 21:13 

< Last Thread  Next Thread > 
Forum Rules:

Copyright © 19992020, Tomasz Grysztar.
Powered by rwasa.