This is kind of related to Which hashing algorithm is best for uniqueness and speed?. In that question, the excellently written top answer notes,
The other subjective measure is how randomly distributed the hashes are. Mapping the resulting HashTables shows how evenly the data is distributed.
(here, "random" is not being used to mean "deterministic" — all of the functions under consideration are deterministic.)
Based on that question's excellent answer, I implemented FNV-1A. However, the results I'm getting do not seem particularly "random"ly distributed:
In : for x in xrange(10): ....: h = Fnv1A(); h.update(b'testing' + str(x)); print hex(h.value) ....: 0x3e249fc5d899c731L 0x3e249ec5d899c57eL 0x3e249dc5d899c3cbL 0x3e249cc5d899c218L 0x3e24a3c5d899cdfdL 0x3e24a2c5d899cc4aL 0x3e24a1c5d899ca97L 0x3e24a0c5d899c8e4L 0x3e2497c5d899b999L 0x3e2496c5d899b7e6L
Notice that the vast majority of the bits in the output here are the same.
Is FNV-1A supposed to be an extremely discontinuous function? i.e., the output changes drastically for small changes in the input; it exhibits the Avalanche effect.
Note that this is orthogonal to being uniformly distributed, which I also want.
I'm attempting to use FNV-1A to simply randomly distribute users into one of n weighted buckets. None of the inputs are user-controlled, so security is not of much concern, but the inputs are highly not random (they're auto-incrementing integers…); I do, however, need the output two be random (but deterministic): for a given user ID, it should be random which bucket they end up in.
I actually asked another similar question a while ago; I understand that hash outputs don't necessarily need to be random (for hashtables, all you really care about is that they don't collide). For my particular application, I unfortunately need randomness.
(In case you're curious about the correctness of my implementation,
In : h = experiment.Fnv1A(); h.update(b'foobar'); h.value Out: 9625390261332436968L
…as this is for work, I'm trying to share as little code as needed. This question is more about FNV-1A itself, rather than my particular implementation.)