One-Way Function

http://en.wikipedia.org/wiki/One-way_functions

The existence of such one-way functions is still an open conjecture. In fact, their existence would prove that the complexity classes P and NP are not equal, thus resolving the foremost unsolved question of theoretical computer science.

Wait! How come hash fucking tables work and the shits like md5?

(I don't know if you got the memo, but md5 doesn't work.)

It's a sort of stupid way of saying that one-way functions must have average case inversions in NP, but not in P. So they can only exist if P!=NP.

The article almost implies the function is expected to be 1:1, but I think it's really trying to say that you must not be able to compute collisions efficiently. Hash tables don't need these properties, although resistance to collision-prediction is desirable for security (i.e. when untrusted input is being hashed) in other scenarios reducing collisions for similar inputs is more important.