Element Uniqueness

Element Uniqueness

I was reading on the topics reductions and lower bounds (Combinatorial Algorithms) when met the problem again.

Definition: Given a list of n numbers x_1,x_2,...,x_n, whether any two of them are equal.



An obvious and simple solution is to sort the numbers, and then scanf for ajacent duplicates. The complexity is O(nlogn)

I have another idea using hashing, but choosing hashing functions is not that easy. We could probably use double hashing. The complexity is O(n) as long as the collision in hash table is well controlled.

Is there any efficient algorithms?