Java HashMap.get(Object) infinite loop

Question

A few answers on SO mention that the get method in a HashMap can fall into an infinite loop (e.g. this one or this one) if not synchronized properly (and usually the bottom line is "don't use a HashMap in a multi-threaded environment, use a ConcurrentHashMap").

While I can easily see why concurrent calls to the HashMap.put(Object) method can cause an infinite loop, I can't quite see why the get(Object) method can get stuck when it tries to read a HashMap that is being resized at that very moment. I had a look at the implementation in openjdk and it contains a cycle, but the exit condition e != null should be fulfilled sooner or later. How can it loop forever? A piece of code that is mentioned explicitly to be vulnerable to this issue is:

public class MyCache {     private Map<String,Object> map = new HashMap<String,Object>();      public synchronized void put(String key, Object value){         map.put(key,value);     }      public Object get(String key){         // can cause in an infinite loop in some JDKs!!         return map.get(key);     } } 

Can someone explain how a thread putting an object into the HashMap and another reading from it can interleave in such a way that an infinite loop is generated? Is it the case that it has to do with some cache coherency issue or CPU instruction reordering (so the problem can only happen on a multi-processor machine)?

Answer 1

You link is for the HashMap in Java 6. It was rewritten in Java 8. Prior to this rewrite an infinite loop on get(Object) was possible if there were two writing threads. I am not aware of a way the infinite loop on get can occur with a single writer.

Specifically, the infinite loop occurs when there are two simultaneous calls to resize(int) which calls transfer:

 void transfer(Entry[] newTable, boolean rehash) {     int newCapacity = newTable.length;     for (Entry<K,V> e : table) {          while(null != e) {              Entry<K,V> next = e.next;              if (rehash) {                  e.hash = null == e.key ? 0 : hash(e.key);              }              int i = indexFor(e.hash, newCapacity);              e.next = newTable[i];              newTable[i] = e;              e = next;          }      }  } 

This logic reverses the ordering of the nodes in the hash bucket. Two simultaneous reversals can make a loop.

Look at:

             e.next = newTable[i];              newTable[i] = e; 

If two threads are processing the same node e, then first thread executes normally but the second thread sets e.next = e, because newTable[i] has already been set to e by the first thread. The node e now points to itself, and when get(Object) is called it enters an infinite loop.

In Java 8, the resize maintains the node ordering so a loop cannot occur in this fashion. You can lose data though.

The Iterators for LinkedHashMap class can get stuck in an infinite loop when there are multiple readers and no writers when access ordering is being maintained. With multiple readers and access order every read removes and then inserts the accessed node from a double linked list of nodes. Multiple readers can lead to the same node being reinserted more than once into the list, causing a loop. Again the class has been rewritten for Java 8 and I do not know if this issue still exists or not.