CODEWITHSUNDEEP
javaperformancelinkedhashset
Fred
Fred

Reputation: 175

Is it worth it to check LinkedHashSet.contains(...) before adding?

I'm using a LinkedHashSet to implement a set ordered by entry. If a duplicate element is added, it should go at the end and the entry already in the set should be removed.

I'm debating whether it's worth it to check set.contains(entry) before I call set.remove(entry)? Essentially does checking contains() each time offer any time/space benefit over just blindly calling remove() each time?

Set<Integer> set = new LinkedHashSet<>();

// The below
set.remove(entry);
set.add(entry);

// Versus the below
if (set.contains(entry)) {
  set.remove(entry);
}
set.add(entry);

Upvotes: 4

Views: 717

Answers (3)

M. Justin
M. Justin

Reputation: 21315

Java 21 added the addLast method to LinkedHashSet, which will move the element to the end of the set if it is not already present.

Adds an element as the last element of this collection (optional operation). After this operation completes normally, the given element will be a member of this collection, and it will be the last element in encounter order.

Using this method instead of add solves the stated requirement without having to also call remove.

Set<Integer> set = new LinkedHashSet<>();

set.addLast(entry);

Upvotes: 0

Nitin Dandriyal
Nitin Dandriyal

Reputation: 1607

LinkedHashSet uses HashMap behind the scenes remove(Object) will remove the Object only if it contains the Object hence its unnecessary and will increase time complexity in case Object exists in set.

Upvotes: 1

augray
augray

Reputation: 3171

I would recommend against calling both contains and remove. Both calls have to search through the chains to find the element, and contains does this no faster than remove. So you are potentially doubling your required time for a call each time.

You can browse through the code for contains and remove yourself.

You'll find that both end up possibly iterating through the hash chains at some point (remove in HashMap's removeNode and contains in HashMap's getNode), which could be a performance hit if your set is under heavy load.

If your set isn't under heavy load, then it still probably isn't worth it, but doesn't matter so much since in a sparse hash chains set the expected lookup/remove is O(1) (i.e. will be just as fast regardless of whether you have 5 elements or 5000 in it).

Upvotes: 1

Related Questions