HashSet: add() during iteration?

[Bruce Feist]

What happens when I add a new item to a HashSet during iteration? Will
the new item added eventually be included in the iteration, will it not
show up, or is it unpredictable?

I *want* it to be included, so if it isn't I'm going to have to use more
complicated logic, where each time through an iteration I build the next
HashSet to be iterated over, and I use a loop to iterate through each of
the HashSets until I get to an empty one. Much nastier, but I suspect
I'll have to -- please tell me that I'm wrong!

Thanks,
Bruce Feist

 

[Lasse Reichstein Nielsen]

What happens when I add a new item to a HashSet during iteration?

You get a ConcurrentModificationException the next time you use the
iterator.

Will the new item added eventually be included in the iteration, will
it not show up, or is it unpredictable?

It's completely predictable. From the JavaDoc of HashSet:

 

[Eric Sosman]

Bruce Feist wrote On 10/24/06 12:50,:

What happens when I add a new item to a HashSet during iteration? Will
the new item added eventually be included in the iteration, will it not
show up, or is it unpredictable?

The new item is added (if it wasn't already in the Set).
This modifies the Set and thus invalidates the Iterator:

"The iterators returned by this class' iterator method
are fail-fast: if the set is modified at any time after
the iterator is created, in any way except through the
iterator's own remove method, the iterator throws a
ConcurrentModificationException."

I *want* it to be included, so if it isn't I'm going to have to use more
complicated logic, where each time through an iteration I build the next
HashSet to be iterated over, and I use a loop to iterate through each of
the HashSets until I get to an empty one. Much nastier, but I suspect
I'll have to -- please tell me that I'm wrong!

You're doing some kind of a "completion" operation, maybe?
You apply a rule to each element of the Set to create zero or
more "direct descendants," add them to the Set and compute
their descendants in turn, and so on until nothing more can be
added? Sort of like the LR(k) parser generator algorithm?

If that's what you're doing, you'll need some fancier logic
anyhow. There's no ordering in a HashSet, so if you insert a
new item you don't know whether it landed "before" or "after"
the current position of the Iterator -- in other words, even if
the Iterator could somehow keep going, you couldn't be sure it
would visit the newly-inserted item.

Two simple approaches occur to me:

- Use a single Set, iterate over its elements, and add
their descendants. Whenever an element produces one
or more descendants that actually get added (weren't
already there), discard the now-invalid Iterator and
create a fresh one, thus restarting the traversal at
the beginning.

- Use a Set to hold "all elements" and something like
a Stack to hold "elements whose descendants have not
yet been found." While the Stack is non-empty, pop
an element, compute its descendants, add them to the
Set, and if set.add() returned true also push them
onto the Stack (they are new descendants, and need
to be explored).

I'd prefer the second, since you won't waste a lot of
effort computing and re-computing and re-re-computing the
descendants of already-visited elements. But if you really
want to use just one Collection, the first approach works.

 

[Mark Jeffcoat]

What happens when I add a new item to a HashSet during iteration?
Will the new item added eventually be included in the iteration, will
it not show up, or is it unpredictable?

I *want* it to be included, so if it isn't I'm going to have to use
more complicated logic, where each time through an iteration I build
the next HashSet to be iterated over, and I use a loop to iterate
through each of the HashSets until I get to an empty one. Much
nastier, but I suspect I'll have to -- please tell me that I'm wrong!

I suspect you'd get a ConcurrentModificationException most
of the time, though the behavior isn't entirely well defined
in the javadocs that I can see.

You can do something like

Set working = new HashSet(original);
for (Object o : original) {
if (condition(o)) {
working.add(o);
}
}

original = working;


Alternately, you could shove your Set into a temporary
List and ask for a ListIterator, which does have a well-defined
add() method, and verify yourself that the elements you're
adding don't violate Set's contract.

 

[Lex]

I'm not sure if this will help, but I required similar functionality
when dealing with a List. Instead of calling myList.iterator(), I
called myList.listIterator().

With the ListIterator, you can add elements directly to the
ListIterator and you won't get the ConcurrentModificationException. It
just adds your element to the end of the iterator and continues on.

 

[Bruce Feist]

What happens when I add a new item to a HashSet during iteration?

Thanks for your responses, all. Lasse and Eric pointed out (very
politely) that if I'd read the javadocs more closely I'd have gotten my
answer. Eric, Mark, and Lex suggested solutions involving lists; I'm
going to avoid those, because most of the operations against my
collection will be tests for membership which I want to be as fast as
possible. Mark also suggested iterating between HashSets, creating a
new one while iterating through the old and then switching to the new.
This is quite close to my back-up plan, and is what I am now implementing.

The application is a maze generator, which divides cells into those
which are already on paths through the maze, and those which are not
("free" cells). It works by iterating through the points on the maze
and generating paths through previously free cells from each one, until
no more are possible.

Thanks again, everyone!

 

[Mark Jeffcoat]

You get a ConcurrentModificationException the next time you use the
iterator.


It's completely predictable. From the JavaDoc of HashSet:

Yeah.... but you've got to read the next paragraph, too:

(from the 1.5.0 HashSet Javadoc)


Note that the fail-fast behavior of an iterator cannot be
guaranteed as it is, generally speaking, impossible to make
any hard guarantees in the presence of unsynchronized concurrent
modification. Fail-fast iterators throw ConcurrentModificationException
on a best-effort basis. Therefore, it would be wrong to write a
program that depended on this exception for its correctness:
the fail-fast behavior of iterators should be used only to detect bugs.


(Pedantry aside, I suspect that the ConcurrentModificationException
is quite dependable if everything is happening in the same thread,
but why court trouble?)