Hash function that maps similar inputs to similar outputs?

Question

Is there a hash function where small changes in the input result in small changes in the output? For example, something like:

hash("Foo") => 9e107d9d372bb6826bd81d3542a419d6
hash("Foo!") => 9e107d9d372bb6826bd81d3542a419d7 <- note small difference

Answer 1

A trivial solution would be be to XOR all bytes module N. E.g. for a 64 bits hash, you'd XOR (input[0] ^ input[8] ^ input[16]) + 256*(input[1] ^ input[9] ^ input[17]) etc. So, "Foo" hashes to "Foo\0\0\0\0\0" and "Foo!" hashes to "Foo!\0\0\0\0".

Answer 2

I wouldn't call this a hash because the point of a hash is exactly the opposite. However, with your stated goal of small changes in input producing small changes in output, I would look at using either a soundex function or the Ratcliff algorithm.

Answer 3

I would recommend the simhash, algorithm by Mark Manasse.