News for hackers. Stuff that matters.
Re:Google's “Director of Engineering” Hiring Test by dekhn on Thursday October 13, 2016 @01:00PM (#12702209)
The goal of a fingerprint hash is to convert an input space of "large" values to an output space where the output space values are much shorter- typically fixed size and two similar input values have effectively random outputs (without spending the CPU cycles to implement a cryptographic hash). This permits a wide range of optimizations (a document can be fingerprinted, and looked up by its fingerprint, to see if it's a cache, has associated data, etc).

A non-fingerprinting hash function - well, one example of one- is something that for similar inputs, produces the same output (similarity being defined by some distance metric). See, for example: https://en.wikipedia.org/wiki/Locality-sensitive_hashing and https://en.wikipedia.org/wiki/MinHash

Confusingingly, many functions that are used for similarity detection are called Fingerprints, (https://en.wikipedia.org/wiki/Acoustic_fingerprint), but I consider that a distinct use of the term.

Re:Google's “Director of Engineering” Hiring Test by bogomipz on Thursday October 13, 2016 @04:07PM (#12703627)
"The goal of a fingerprint hash is to convert an input space of "large" values to an output space where the output space values are much shorter- typically fixed size and two similar input values have effectively random outputs"

But this is also the goal of non-crypto hash function like those used in a data structure no? Basically mapping a large space of inputs to a smaller space of outputs.

I would say the cryptographic hash is one the that has "desirable" security properties, things like not being able to recover the original input message using the hash, a tiny change in the input causes a substantial change in the output, or that its very unlikely that two inputs will produce a collision.

Re:Google's “Director of Engineering” Hiring Test by dekhn on Thursday October 13, 2016 @04:47PM (#12703902)
both types of hash convert an input space to an output space where (typically) the input space is much larger.

What matters is whether similar inputs get mapped to the same output. For the case where you want to minimize the probability that two inputs which are highly similar land in the same bucket, you want a crypto hash, although those are expensive so you want a cheaper approximation, which is exactly what fingerprint hashes do. The problem is that as the input values counts approach sqrt(output value size), you're going to start getting collisions, and ideally, you want those collisions to be evenly spaced.

In the case of a similarity hash function, you want the opposite, the closer things are in some metric space, the more likely they end in up in the same bucket.

Re:Google's “Director of Engineering” Hiring Test by bogomipz on Thursday October 13, 2016 @07:15PM (#12704979)
"For the case where you want to minimize the probability that two inputs which are highly similar land in the same bucket, you want a crypto hash"

That's what I was trying to say:

"a tiny change in the input causes a substantial change in the output."

But I probably didn't articulate that very well. I think we are saying the same thing.

You mentioned:

"The problem is that as the input values counts approach sqrt(output value size), you're going to start getting collisions"

Can you elaborate on the significant a square root here? Does this relate to the load factor?

Re:Google's “Director of Engineering” Hiring Test by dekhn on Thursday October 13, 2016 @07:32PM (#12705069)
https://en.wikipedia.org/wiki/Birthday_problem Basically, you get 50% chance of collision around sqrt(size of table).
Re:Google's “Director of Engineering” Hiring Test by bogomipz on Friday October 14, 2016 @03:02PM (#12710335)
Ah right, a probability theory classic. Thanks, cheers.
Re:Google's “Director of Engineering” Hiring Test by lucb1e on Thursday October 13, 2016 @02:55PM (#12703128)
Thanks for the elaborate answer! I knew about things like acoustic fingerprints but not that people use the term "hash function" to describe something that indicates similarity.

Could something like Hamming distance be called a hash function too? It's not mentioned on its Wikipedia page.

Re:Google's “Director of Engineering” Hiring Test by rockdoe on Thursday October 13, 2016 @03:18PM (#12703301)
No because that works between pairs. It's a comparison method, not a mapping.
Re:Google's “Director of Engineering” Hiring Test by lucb1e on Thursday October 13, 2016 @07:43PM (#12705123)
Ah I see. Thanks!
Re:Google's “Director of Engineering” Hiring Test by dekhn on Thursday October 13, 2016 @03:51PM (#12703504)
it's worth reading and understanding the ideas behind LSH and hamming distance. there are some... fundamental mathematical relationshps there that are still being ... hashed out.