HashMap, HashSet and infinite loop
hi,
our code ended up in an infinite loop while parsing the entries of a HashMap with this code:
Iterator it = myHashMap.entrySet().iterator();
while (it.hasNext()){
field = (Map.Entry) it.next();
// code that access content of "field"
}
as the loop creates some kind of objects, the JVM terminated with a out-of-memory. luckily we got a heap-dump file and that shows:
- the hash-map has 325 entries
- the loop was iterated more than 3 million times
- the iterator "it" has a current and a next field pointing at the same element of the HashMap
a snapshot of the heap-analysis of the iterator can be seen at
http://www.sbox.tugraz.at/home/a/archmage/hashset/EntryIterator.html
maybe the HashMap was accessed concurrently, but then there should be a ConcurrentModificationException.
we are using
> java -version
java version"1.4.2_12"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.2_12-b03)
Java HotSpot(TM) Client VM (build 1.4.2_12-b03, mixed mode)
for me, this looks like a JVM bug, but i cannot really believe that (and i could not find a bug stating this behaviour).
is there anything i did not notice during using hashmaps/hashsets/iterators?
regards, werner
[1463 byte] By [
archmagea] at [2007-11-27 1:58:32]
# 1
one thing i forgot to mention: we could not reproduce the infinite loop. until now, we ran into the problem only once.
# 2
> maybe the HashMap was accessed concurrently, but then
> there should be a ConcurrentModificationException.
Not necessarily. The iterators cannot always detect ConcurrentModificationException.
Far more likely though, is that the HashMap internal fields are corrupted by unsynchronized access.
Say thread 1 calls map.put(X,100), and thread 2 calls map.put(Y,200).
If X and Y happen to map to the same bucket in the HashMap,
and you didn't use a lock, then they would corrupt that bucket's internal pointers,
possibly leading to a cycle in the bucket (hence an infinite loop).
This sounds like a classic race condition (hence it is not easily reproducible)
If you have a massive test suite that periodically triggers this bug,
then you can try changing the HashMap to a SynchronizedMap (just for debugging purpose)
and see if the infinite loop goes away. If it does, then you can be 99% certain
that unsynchronized access was at fault.
# 3
>> there should be a ConcurrentModificationException.
> Not necessarily. The iterators cannot always detect ConcurrentModificationException.
api-docs of HashMap say:
...
A structural modification is any operation that adds or deletes one or more mappings
...
if the map is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException.
...
for me, that means, the iterator should detect any "add" or "delete" operation like map.put(...). am i wrong? or are the docs wrong here?
# 4
> >> there should be a
> ConcurrentModificationException.
>
> > Not necessarily. The iterators cannot always detect
> ConcurrentModificationException.
>
> api-docs of HashMap say:
> ...
> A structural modification is any operation that adds
> or deletes one or more mappings
> ...
> if the map is structurally modified at any time after
> the iterator is created, in any way except through
> the iterator's own remove or add methods, the
> iterator will throw a
> ConcurrentModificationException.
> ...
>
> for me, that means, the iterator should detect any
> "add" or "delete" operation like map.put(...). am i
> wrong? or are the docs wrong here?
Immediately AFTER the paragraph you quoted, it says
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.
http://java.sun.com/j2se/1.5.0/docs/api/java/util/HashMap.html
Furthermore, did you READ what I said after that?
It's FAR MORE LIKELY to be a result of data corruption, rather than multiple simultaneous iterators.
# 5
> Immediately AFTER the paragraph you quoted
my mistake, i did not read the api-docs to the end, where the earlier statements are weakend again. and as i cannot guarantee no concurrent modification happens, we will look deeper in this direction.
> Furthermore, did you READ what I said after that?
i read your reply multiple times before i answered. my quote of api-docs was because of your answer. just again my mistake, that i did not read it to the end, sorry.
thanks for all the help,
regards,
werner
# 6
Sorry I was impatient with you earlier. I apologize. Good luck on your project.
