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