title: Strange HashMap exception (HashMap$Node cannot be cast to HashMap$TreeNode)
body: <p>After another question asked on stackoverflow, 
  (<a href="https://stackoverflow.com/questions/29965956/java-why-this-program-not-throwing-concurrent-modification-exception/%20HashMap%20concurrency%20question">Java- Why this program not throwing concurrent Modification exception</a>)
  I started to experiment with the HashMap. Here are a few lines of code which I wrote:</p>
  
  <pre><code>import java.util.HashMap;
  import java.util.Random;
  
  public class Concurrency {
      public static void putEntriesToMap(HashMap&lt;String, String&gt; hashMap) {
          for (int count = 0; count &lt; 10000; count++) {
              hashMap.put(Integer.toString(count), Integer.toString(count));
              Random random = new Random();
              if (random.nextBoolean()) {
                  hashMap.remove(count + "");
              }
          }
      }
  
      public static void main(String[] args) throws InterruptedException {
          final HashMap&lt;String, String&gt; hashMap = new HashMap&lt;String, String&gt;();
          Thread t1 = new Thread(new Runnable() {
              @Override
              public void run() {
                  putEntriesToMap(hashMap);
              }
          });
  
          Thread t2 = new Thread(new Runnable() {
              @Override
              public void run() {
                  putEntriesToMap(hashMap);
              }
          });
          t1.start();
          t2.start();
          t1.join();
          t2.join();
      }
  }
  </code></pre>
  
  <p>Once upon a time (approx 1 in 20 runs), when executing this code, I get</p>
  
  <pre><code>Exception in thread "Thread-0" Exception in thread "Thread-1" java.lang.ClassCastException: java.util.HashMap$Node cannot be cast to java.util.HashMap$TreeNode
      at java.util.HashMap$TreeNode.moveRootToFront(HashMap.java:1819)
      at java.util.HashMap$TreeNode.treeify(HashMap.java:1936)
      at java.util.HashMap.treeifyBin(HashMap.java:771)
      at java.util.HashMap.putVal(HashMap.java:643)
      at java.util.HashMap.put(HashMap.java:611)
      at Concurrency.putEntriesToMap(Concurrency.java:9)
      at Concurrency$1.run(Concurrency.java:27)
      at java.lang.Thread.run(Thread.java:745)
  </code></pre>
  
  <p>This, however, seems strange to me, because it looks like it is an <strong>internal HashMap error</strong>. 
  I know that the concurrency <strong>is not used correctly</strong>, but it is done <strong>on purpose</strong>.</p>
  
  <p>I tried to google the exception, but I found almost no info.</p>
  
  <p>Can you even reproduce the same exception?</p>
  
  <p>I am using <strong>oracle jdk 1.8.0_40</strong></p>
  
  <p>EDIT:</p>
  
  <p>Firstly, thanks for answers, it is now clear for me.
  I just want to point out that I knew how to avoid the program from breaking by using thread safe precautions, but I didn't know why specifically this exception is thrown in given situation. 
  Thomas has explained it very well in the comments below. It is also well explained in the accepted answer. Thanks again :).</p>