3

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.)

4
  • 3
    I think the term you're looking for is discontinuous, or the avalanche effect. Random means unpredictable, which makes it kind of the opposite of deterministic. It's also not the opposite of uniformly distributed, which you do want, because that's how you avoid collisions.
    – Doval
    Feb 20, 2015 at 1:24
  • 1
    @Doval Along those lines, is the statement in the Wikipedia article about the weak diffusion also a potential concern, since we know the numbers are incrementing? It sounds like it may be more a concern for cryptography but less for this problem...
    – J Trana
    Feb 20, 2015 at 2:03
  • @Doval: Ah, I didn't mean to imply that randomness and uniformly distributed were opposites, merely that they're orthogonal. I see how that's confusing. The avalanche effect is definitely a good way of describing what I need. I'll edit these into the question.
    – Thanatos
    Feb 20, 2015 at 6:35
  • Consider SipHash. It's simple, relatively fast and secure. Feb 20, 2015 at 15:36

1 Answer 1

3

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.

1
  • Indeed, the code is now using SHA2.
    – Thanatos
    Feb 20, 2015 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.