The 30 second answer
It uses equals and hashCode. On ordered streams the first occurrence is kept; on unordered streams any may be kept. It is a stateful intermediate operation and gets expensive when you keep ordering in parallel, so unordered can help. Under the hood the sequential path is basically a HashSet of seen elements.
Uses Object.equals (and therefore hashCode). For ordered streams the first occurrence is kept (stable); for unordered streams any may be kept. It is a stateful intermediate op; in parallel with ordering it is expensive — unordered() relaxes that.
[Impl] From OpenJDK DistinctOps (jdk-21+35): the sequential path keeps a HashSet of seen elements (with special null handling via a flag). If the upstream is already DISTINCT it is a no-op; if SORTED it only compares with the previous element. Parallel ordered uses a LinkedHashSet reduction; parallel unordered uses a ConcurrentHashMap. Expected O(n) time, O(n) space.
Sources: