Check whether all elements are different 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.
This sounds like an assignment, so I'll just give you a few things to think about:


Using a hash table/hash map allows you to access elements in near $O(1)$ time. The only reason it's not exactly $O(1)$ is because of the collisions, $m$.
Given two elements $a_i$ and $a_j$, if $h(a_i) = h(a_j)$, the two elements may or may not be equal. The hash table has to handle this collision in some way; you may then have to go back and check for actual duplicates.
On the other hand, if $h(a_i) \neq h(a_j)$, it's necessarily true that the elements are NOT equal. $a_i$ and $a_j$ are stored in separate locations in the hash table.
Think about the worst case test case; what would happen as you build up the hash table?