Efficiency of collection.stream().skip().findFirst()

Question

Suppose set is a HashSet with n elements and k is some int between 0 (inclusive) and n (exclusive).

Can somebody explain, in simple terms, what actually happens when you do this?

set.stream().skip(k).findFirst();

In particular, what is the time complexity of this? Does the addition of spliterator() to the Collection interface mean that we now have faster access to "random" elements of collections than would have been possible with Java 7?

Answer 1

Current implementation has O(k) complexity and moreless equivalent to the following:

Iterator<?> it = set.iterator();
for(int i=0; i<k && it.hasNext(); i++) it.next();
return it.hasNext() ? Optional.of(it.next()) : Optional.empty();

Current implementation never takes into account ORDERED characteristic for sequential streams. The piece of code cited in @the8472 answer works for parallel streams only. In parallel case the amortized complexity is roughly O(k/n) where n is the number of processors.

Answer 2

As louis mentions skip does not really make sense on unordered streams, in fact it's currently (jdk 1.8) implemented in a way where the following method optimizes the skip away under some circumstances:

        Spliterator<T> unorderedSkipLimitSpliterator(Spliterator<T> s,
                                                     long skip, long limit, long sizeIfKnown) {
            if (skip <= sizeIfKnown) {
                // Use just the limit if the number of elements
                // to skip is <= the known pipeline size
                limit = limit >= 0 ? Math.min(limit, sizeIfKnown - skip) : sizeIfKnown - skip;
                skip = 0;
            }
            return new StreamSpliterators.UnorderedSliceSpliterator.OfRef<>(s, skip, limit);
        }

This is valid because it is equivalent to simply traversing the source collection in a different order.