CODEWITHSUNDEEP
javahashsetsublistlinkedhashset
Bob
Bob

Reputation: 1211

Get a sublist last 5 elements of LinkedHashSet?

Is there a one liner to get the last 5 elements of a LinkedHashSet in a new LinkedHashSet?

This is what I currently have, but it's not very efficient:

new LinkedHashSet<String>(new LinkedList<String>(set)
.subList(Math.max(0, set.size() - 5), set.size());

Or should I use for this case a TreeSet, SortedSet, HashSet ?

Upvotes: 1

Views: 1500

Answers (5)

M. Justin
M. Justin

Reputation: 21315

This can be efficiently achieved using the reversed() method added to LinkedHashSet in Java 21 as part of the SequencedSet interface.

LinkedHashSet<String> lastFive = new LinkedHashSet<>(set.reversed().stream()
        .limit(5).toCollection(LinkedHashSet::new).reversed());

This can be simplified to use the reversed Set directly if the returned set doesn't need to be a LinkedHashSet, but just a mutable Set with a well-defined iteration order and near-identical characteristics of a LinkedHashSet:

SequencedSet<String> lastFive = set.reversed().stream()
        .limit(5).toCollection(LinkedHashSet::new).reversed();

Upvotes: 0

Bob
Bob

Reputation: 1211

I ended up using this:

com.google.common.collect.EvictingQueue<E>

with this you get to keep only the last x elements.

EvictingQueue<String> queue = EvictingQueue.create(5);

Upvotes: 0

Stephen C
Stephen C

Reputation: 719376

Here's the problem. The iterators for a LinkedHashSet are unidirectional; i.e. you can't iterate backwards, even though the underlying data structure has a doubly-linked list. That means to get the last N you need to iterate to the end of the list. That is O(N).

In your algorithm, the LinkedList constructor is copying the set into a new data structure using (probably) the iterator.

By contrast, the TreeSet API has an descendingIterator() method that returns an Iterator that iterates backwards through the list. If you use that correctly, you can get the last 5 elements of the set in O(1). The downside is that adding elements to the set will be O(logN) instead of O(1) for a hash-based set.

Upvotes: 0

muzahidbechara
muzahidbechara

Reputation: 253

Using ArrayList you could get a better performance:

long s1 = System.nanoTime();
LinkedHashSet<String> last5 = new LinkedHashSet<String>(new LinkedList<String>(set)
        .subList(Math.max(0, set.size() - 5), set.size()));
System.out.println(System.nanoTime() - s1);

s1 = System.nanoTime();
LinkedHashSet<String> usingArrayList = new LinkedHashSet<String>(new ArrayList<String>(set)
        .subList(Math.max(0, set.size() - 5), set.size()));
System.out.println(System.nanoTime() - s1);

Upvotes: 0

grebesche
grebesche

Reputation: 511

If you use Java 8 and you are ok to get back a HashSet (instead of a LinkedHashSet), you can use the Stream API:

Set<String> newSet = set.stream()
                        .skip(set.size() - 5)
                        .collect(Collectors.<String>toSet());

Upvotes: 0

Related Questions