Suppose I had a hash function which produced a 256-bits output for any given input (such as SHA-3-256). Now suppose i did an exhaustive mapping from every possible 512-bits input to a given 256-bits output, and stored it in a table along with the original 512-bits input.
Now, if I later wanted to find the original 512-bits input based on a 256-bits hash, What is the probability of finding a collision rather than the original input?
It seems that in the case of exhaustive mapping from input to output, the risk of collision get "unacceptable" very fast. Would I be correct to assume that in this case there exists $2^{512}$ inputs, but the hash function is only able to supply $\approx 2^{256}$ (minus unnecessary collisions caused by imperfections in the hash function), so the there must exist $\approx 2^{256}$ collisions?