What is the input of a given hash?
The problem can be verified in polynomial time (using a hash that executed in polynomial time), and I suspect that it may be possible to prove that there is no algorithm that can solve it in polynomial time.
Take a binary string $X$ of length $n$.
The number of possible values for $X$ is $2^n$.
Solving the problem by using a hash table still involves initially calculating the hashes for all $2^n$ variations, so I'm not sure if it can be counted. But if hash tables are permitted, and generation of the hash table is not included in the cost, then time complexity goes down to $O(n)$, (binary search on the elements of the (sorted) hash table gives a time complexity of $O(\log(2^n)) = O(n)$.
I feel if we permit hash tables to reduce the asymptotic complexity, then we should permit similar methods to reduce the asymptotic complexity of problems. Hash table generation is $O(2^n)$ and I feel this should be accounted for.