title: how to use a synchronized linked hash map correctly
body: <p>trying to make an lru map by subclassing linked hash map.</p>
  
  <p>the map is run through collections.synchronized.</p>
  
  <p>all usages of the map are surrounded by a synchronized block. the unit test also fails if they are all removed. one would think they are not necessary since the map was run through collections.synchronized.</p>
  
  <p>one thread puts sequential numbers (0,1,2,3 ...) into the map. removals are handled by removed eldest entry. no one else removes entries from the map.</p>
  
  <p>the other thread gets the data from the map.</p>
  
  <p>the following unit test fails usually at "oops". this is when a non zero number shows up in the first position (it should be zero until the map gets full). other strange things can happen like null values in the entry set.</p>
  
  <p>any pointers will be appreciated.</p>
  
  <p>thanks</p>
  
  <pre><code>import static org.junit.Assert.*;
  
  import java.util.Collections;
  import java.util.LinkedHashMap;
  import java.util.Map;
  import java.util.Set;
  
  import org.junit.After;
  import org.junit.Before;
  import org.junit.Test;
  class LruMap&lt;K,V&gt; extends LinkedHashMap&lt;K,V&gt; {
      public LruMap() {
          super(defaultMaxSize+1,.75f,true);
          maxSize=defaultMaxSize;
      }
      public LruMap(int arg0) {
          super(arg0+1,.75f,true);
          maxSize=arg0;
      }
      public LruMap(int arg0,float arg1) {
          super(arg0+1,arg1,true);
          maxSize=arg0;
      }
      public LruMap(int arg0,float arg1,boolean arg2) {
          super(arg0+1,arg1,arg2);
          if(!arg2)
              throw new RuntimeException("you did not construct an lru map!");
          maxSize=arg0;
      }
      public LruMap(Map&lt;K,V&gt; arg0) {
          super(arg0);
          throw new RuntimeException("you did not construct an lru map!");
      }
      public boolean removeEldestEntry(Map.Entry&lt;K,V&gt; eldest) {
          return size()&gt;maxSize;
      }
      public final int maxSize;
      public static final int defaultMaxSize=2048;
      static final long serialVersionUID=0;
  }
  class Server implements Runnable {
      public Server(final int pieces,final int period) {
          this.pieces=pieces;
          this.period=period;
          lruMap=Collections.synchronizedMap(new LruMap&lt;Long,Long&gt;(3*pieces/2));
      }
      @Override public void run() {
          t0=System.currentTimeMillis();
          while(piece&lt;stopAtPiece) {
              final long dt=System.currentTimeMillis()-t0;
              final long target=piece(dt);
              System.out.println("adding "+(target-piece+1)+" items");
              for(;piece&lt;=target;piece++) {
                  synchronized(lruMap) {
                      lruMap.put(piece,piece);
                  }
              }
              checkMap(piece,true);
              try {
                  Thread.sleep(100);
              } catch(InterruptedException e) {
                  e.printStackTrace();
                  break;
              }
          }
      }
      Map.Entry&lt;Long,Long&gt;[] checkMap(final long n,boolean print) {
          synchronized(lruMap) {
              Map.Entry&lt;Long,Long&gt;[] entries=null;
              if(lruMap.size()&gt;0) {
                  final Set&lt;Map.Entry&lt;Long,Long&gt;&gt; entrySet=lruMap.entrySet();
                  entries=new Map.Entry[entrySet.size()];
                  entrySet.toArray(entries);
                  long first=entries[0].getKey();
                  long last=entries[entries.length-1].getKey();
                  if(print)
                      for(Map.Entry&lt;Long,Long&gt; entry:entries)
                          System.out.print(entry.getKey()+" ");
                  System.out.println();
                  if(n&lt;pieces&amp;&amp;first!=0) {
                      System.out.println("lru: first!=0! "+first);
                      if(throwWhenfirstIsNotZero) { throw new RuntimeException("oops"); }
                  }
                  for(int i=0;i&lt;entries.length-1;i++) {
                      long p0=entries[i].getKey();
                      long p1=entries[i+1].getKey();
                      if(p0&gt;p1)
                          System.out.println("out of order! "+p0+" "+p1);
                      else if(p0==p1)
                          System.out.println("dupicate "+p0+" "+p1);
                      else if(p0+1==p1)
                          ; // ok
                      else if(p0+1&lt;p1)
                          System.out.println("skipped "+p0+" "+p1);
                      else System.out.println("some case i mssed!");
                  }
              }
              return entries;
          }
      }
      public long piece(final long dt) {
          return dt/period*pieces+dt%period*pieces/period;
      }
      public boolean throwWhenfirstIsNotZero=true;
      protected long piece;
      public long t0;
      protected long stopAtPiece=Long.MAX_VALUE;
      public final int period;
      public final int pieces;
      public final Map&lt;Long,Long&gt; lruMap;
  }
  public class ServerTestCase {
      @Before public void setUp() throws Exception {}
      @After public void tearDown() throws Exception {}
      @Test public void testRun() {
          server.stopAtPiece=server.pieces;
          server.throwWhenfirstIsNotZero=true;
          Thread thread=new Thread(server);
          thread.setName("server");
          thread.start();
          while(thread.isAlive()) {
              for(long i=0;i&lt;server.piece;i++)
                  synchronized(server.lruMap) {
                      server.lruMap.get(i);
                  }
          }
      }
      final int period=2*1000;
      final int serverPieces=100;
      Server server=new Server(serverPieces,period);
  }
  </code></pre>