This is kind of related to Which hashing algorithm is best for uniqueness and speed?. In that question, the excellently written top answer notes,RandomnessificationThe 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 randomly distributed:In [19]: for x in xrange(10):   ....:     h = Fnv1A(); h.update(b'testing' + str(x)); print hex(h.value)   ....:0x3e249fc5d899c731L0x3e249ec5d899c57eL0x3e249dc5d899c3cbL0x3e249cc5d899c218L0x3e24a3c5d899cdfdL0x3e24a2c5d899cc4aL0x3e24a1c5d899ca97L0x3e24a0c5d899c8e4L0x3e2497c5d899b999L0x3e2496c5d899b7e6LNotice 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 [22]: h = experiment.Fnv1A(); h.update(b'foobar'); h.valueOut[22]: 9625390261332436968Las 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.)
Should changes to FNV-1A's input exhibit the avalanche effect?
algorithms;random;hashing
From your requirements it rather sounds like you should be using a secure (cryptographic) hash.To your actual question: 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.we can quickly get an answer of No by looking at the FNV test vectors linked from the FNV homepage. Your foobar => 0x85944171f73967e8 test case is here, and also here we find these test cases:input    outputa      0xaf63dc4c8601ec8cb      0xaf63df4c8601f1a5c      0xaf63de4c8601eff2d      0xaf63d94c8601e773e      0xaf63d84c8601e5c0f      0xaf63db4c8601ead9It's clear that this hash is not one to use if you want small changes to avalanche.