News for hackers. Stuff that matters.
Re:Which hashing algorithm is best for uniqueness and speed? by ultimoo on Monday October 14, 2013 @12:25PM (#6548134)
>>FNV-1a collisions

>>altarage collides with zinke

>>altarages collides with zinkes

I found this most interesting. I have no idea how FNV-1a is constructed but I'm sure this is an interesting (mathematical?) quirk in an otherwise great algorithm since it had only 4 collisions for more than a couple of hundred thousand inputs.

Re:Which hashing algorithm is best for uniqueness and speed? by netdog on Monday October 14, 2013 @02:14PM (#6548715)
It's not surprising, and it is not peculiar to FNV-1a. Most of these hashes will exhibit this same behavior.

Since the hash iterates over the characters in the string, once you find two colliding strings S and T, if you append any other string to both S and T, the hashes of S' and T' will also be identical. Try it yourself:

    #include <stdio.h>
    #include "hash_32a.c"
    int main(int argc, char* argv[])
    {
        const char* s[] = {
            "altarage",
            "zinke",
            "altarage_foo",
            "zinke_foo",
            "altarage_xyzzy",
            "zinke_xyzzy"
        };
        int i;
        for (i = 0; i < sizeof s / sizeof (char*); ++i)
        {
            Fnv32_t x = fnv_32a_str(s[i], FNV1_32A_INIT);
            printf("%s: %08x\n", s[i], x);
        }
    }


    $ ./test_fnv1a
    altarage:       e460d8b6
    zinke:          e460d8b6
    altarage_foo:   3d8619c5
    zinke_foo:      3d8619c5
    altarage_xyzzy: 2a6373cf
    zinke_xyzzy:    2a6373cf
Re:Which hashing algorithm is best for uniqueness and speed? by Brandon0 on Monday October 14, 2013 @12:57PM (#6548336)
I saw that too. DJB2a also has

>>playwright collides with snush

>>playwrighting collides with snushing

Re:Which hashing algorithm is best for uniqueness and speed? by joshdick on Monday October 14, 2013 @03:02PM (#6548973)
Yeah, that seems to violate the goal of the avalanche effect.

http://en.wikipedia.org/wiki/Avalanche_effect

Re:Which hashing algorithm is best for uniqueness and speed? by dreish on Monday October 14, 2013 @03:07PM (#6549002)
That's a design goal for cryptographic hash functions, which these are not.
Re:Which hashing algorithm is best for uniqueness and speed? by dllthomas on Monday October 14, 2013 @04:03PM (#6549289)
For something like English words, where you will have a lot of common prefixes and suffixes, it seems a legitimate design goal as well (though it may not be a tradeoff worth making, to be sure).