This is still an open and interesting problem. The best deterministic algorithm that I know of takes $O(n \log n)$ time and $O(\log n)$ words of space by Munro, Fich and Poblete in [Permuting in place][1]. This paper doesn't explicitly mention the problem of detecting if there is a duplicate but the method they develop for permuting in place is directly applicable. It is still possible that there is a true linear time and $O(1)$ words of space solution (either randomised or deterministic).

If you simply increase the alphabet size from $n$ the situation changes drastically. Even if you change it to $2n$ the complexity of finding if there is a duplicate is unknown and in particular no near linear time solution is known for small space. The most obvious randomised approach is to hash the elements down to the range $[1,\dots,n]$.  You are then left with the problem of trying to distinguish real duplicates from ones created by hash collisions.  With full independence it seems you can most likely do this in something like $O(n^{3/2})$ time  but I am not sure if this has ever been formally analyzed in published work. However, we can't actually use a hash function with full independence without also using linear space so the problem as before is to show that a hash function family whose members can be represented in small space and which has the desired properties actually exists.

For even larger alphabets of size $n^2$ there is an existing lower bound for small space algorithms given in [Time-space trade-off lower bounds for randomized computation of decision problems][2].  With space $O(\log n)$ bits (or $O(1)$ words) it simplifies to approximately $\Omega(n \sqrt{\log n})$. This means that no linear time solution is possible in this case.

COMMENT: This should be a comment to David Eppstein's answer but I don't have the points for that.  The function $h(x) = 2^x \bmod p$ with $p$ a prime with $O(\log n)$ bits is very interesting. Although it is clear that it takes $\Theta(\log n)$ time to evaluate the hash function once (by repeated squaring, assuming constant time operations on words),  is it obvious that it can't be done faster on average when evaluating at $n$ points by some clever method? Consider, for example, an array with the elements in increasing order. In this case it takes only $O(n)$ time to compute all the hash values.

  [1]: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.2256
  [2]: http://www.cs.washington.edu/homes/beame/papers/randomts.ps