Is there any data structure that has no duplicates but can have elements added to it while being iterated over?

Question

I know a set has no duplicates but the issue is that I can't add elements to it while iterating over it using an iterator or for each loop. Is there any other way? Thank you.

Answer 1

The ConcurrentHashMap class can be used for this. For example:

Set<T> set = Collections.newSetFromMap(new ConcurrentHashMap<T, Boolean>());

^{(You can replace <T, Boolean> with <> and let the compiler infer the types. I wrote it as above for illustrative purposes.)}

The Collections::newSetFromMap javadoc says:

Returns a set backed by the specified map. The resulting set displays the same ordering, concurrency, and performance characteristics as the backing map. In essence, this factory method provides a Set implementation corresponding to any Map implementation.

Since ConcurrentHashMap allows simultaneous iteration and updates, so does the Set produced as above. The catch is that an iteration may not see the effect of additions or removals made while iterating.

The concurrency properties of iteration can be inferred from the javadoc for ConcurrentHashMap.

---

Is there any other way.

It depends on your requirements, but there are potentially ways to avoid the problem. For example, you could:

1. copy the set before iterating it, OR
2. add the new element to another new set and add the existing elements to the new set to the new set after ... or while ... iterating.

However, these these are unlikely to work without a concurrency bottleneck (e.g. 1.) or a differences in behavior (e.g. 2.)

Answer 2

Not sure whether below approach fixes your problem but you can try it:

    HashSet<Integer> original = new HashSet<>();
    HashSet<Integer> elementsToAdd = new HashSet<>();
    elementsToAdd.add(element); //while iterating original
    original.addAll(elementsToAdd); //Once done with iterating, just add all.