Modifying a set while iterating (Java)

Question

I have a problem with Sets/Iterators in Java. I'm executing code that iterates over elements in a hash set, removing them after they have been used but also removing elements that have been deemed unnecessary to iterate over within the loop. I'm also adding elements to the loop. Here's a code sample:

Set<Integer> thisSet = new HashSet<Integer>();
// add elements into set
while (!thisSet.isEmpty()) {
   int value = thisSet.iterator().next();
   thisSet.remove(value);
   // more remove and add operations
}

I chose hash sets because I thought that the remove operations during the loop would be a lot faster than when using a list. The problem is that statistics show me that if the set gets large, polling a value from the set actually takes up a lot of time (I assume due to creating an iterator every time?). Does anyone have suggestions on how to improve this?

Thanks!

Not an answer, but shouldn't the item be removed by the iterator? — Hovercraft Full Of Eels, Aug 03 '13 at 11:46
I agree with @HovercraftFullOfEels. Why not use iterator to remove elements? — Ankur Shanbhag, Aug 03 '13 at 11:50
Why remove them at all? You can just clear or discard the set after the loop. — Peter Lawrey, Aug 03 '13 at 11:51
He is modifying set (adding/removing elements) in loop. Using iterator allow only item removing in a safe way — Luca Basso Ricci, Aug 03 '13 at 11:53

andreih · Answer 1 · 2013-08-03T13:22:59.213

0

You can find an articles about collections performance measurements: http://www.artima.com/weblogs/viewpost.jsp?thread=122295 (The Final Performance Testing Example by Bruce Eckel)

or http://java.dzone.com/articles/java-collection-performance (Java Collection Performance)

Maybe it will help you to choose the right collection for your implementation.

edited Aug 03 '13 at 13:22

answered Aug 03 '13 at 13:09

andreih

31
3

score 0 · Answer 2 · answered Aug 03 '13 at 16:54

Don't have enough reputation to add a comment to Hovercraft Full Of Eels, but he's absolutely right. Removing an item from a set without using an iterator will eventually lead to a ConcurrentModificationException one way or another. +1

If we're looking at this from perspectives of datastructures, you need a datastructure backed up by a Linked List to make insertion/deletion faster. See Linked lists vs. dynamic arrays @ https://en.wikipedia.org/wiki/Linked_list for insertion/deletion O() bounds.

Ultimately, my suggestion is to backup your Set by a LinkedHashSet object and use a profiler to examine execution times for the sample inputs you're going to use.

Modifying a set while iterating (Java)

2 Answers2