Assume we have $n$ double elements $a_1 \dots a_n$. We want to find out if two of the elements of the array are identical. And we have a hash function $h(x)$ which assigns each double value an integer between $1$ and $n$ and which can be calculate in $O(1)$ time. Let $m := \{(i,j) : a_j \neq a_i \text{ and } h(a_j) = h(a_i)\}.$
How can i check if all $n$ elements are different in $O(n+ |m|)$ time and $O(n)$ memory?
1) The naive approach would be to check all $n$ elements if there is another element with the same value, which requires $O(n^2)$ time.
2) A better way would be if i sort the elements, which needs $O(n \cdot \log(n))$ time and then check each adjacent pair of elements. In total it would be $O(n \cdot \log(n))$.
But i don't know how i can solve this problem quicker. I think neither approach 1) nor 2) can be further improved. Apparently I have to use the hash function somehow, but I don't see how.