Should changes to FNV-1A's input exhibit the avalanche effect?

Question

This is kind of related to Which hashing algorithm is best for uniqueness and speed?. In that question, the excellently written top answer notes,

Randomnessification

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 [19]: 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 [22]: h = experiment.Fnv1A(); h.update(b'foobar'); h.value
Out[22]: 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.)

Answer 1

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    output
"a"      0xaf63dc4c8601ec8c
"b"      0xaf63df4c8601f1a5
"c"      0xaf63de4c8601eff2
"d"      0xaf63d94c8601e773
"e"      0xaf63d84c8601e5c0
"f"      0xaf63db4c8601ead9

It's clear that this hash is not one to use if you want small changes to avalanche.