title: the best way to implement LRU cache
body: <p>I want to create an efficient implementation of LRU cache. I've found that the most convenient way is to use <code>LinkedHashMap</code> but unfortunately it's quite slow if many threads are using a cache. My implementation is here:</p>
  
  <pre><code>/**
   * Class provides API for FixedSizeCache.
   * Its inheritors represent classes         
   * with concrete strategies     
   * for choosing elements to delete
   * in case of cache overflow. All inheritors
   * must implement {@link #getSize(K, V)}. 
   */
  public abstract class FixedSizeCache &lt;K, V&gt; implements ICache &lt;K, V&gt; {
      /**
       * Current cache size.
       */
      private int currentSize;
  
  
      /**
       *  Maximum allowable cache size.
       */
      private int maxSize;
  
  
      /**
       * Number of {@link #get(K)} queries for which appropriate {@code value} was found.
       */
      private int keysFound;
  
  
      /**
       * Number of {@link #get(K)} queries for which appropriate {@code value} was not found.
       */
      private int keysMissed;
  
  
      /** 
       * Number {@code key-value} associations that were deleted from cache
       * because of cash overflow.
       */
      private int erasedCount; 
  
  
      /**
       * Basic data structure LinkedHashMap provides
       * convenient way for designing both types of cache:
       * LRU and FIFO. Depending on its constructor parameters
       * it can represent either of FIFO or LRU HashMap.
       */
      private LinkedHashMap &lt;K, V&gt; entries;
  
  
      /** 
       * If {@code type} variable equals {@code true}
       * then LinkedHashMap will represent LRU HashMap.
       * And it will represent FIFO HashMap otherwise.
       */ 
      public FixedSizeCache(int maxSize, boolean type) {
  
          if (maxSize &lt;= 0) {
              throw new IllegalArgumentException("int maxSize parameter must be greater than 0");
          }
  
          this.maxSize = maxSize;
          this.entries = new LinkedHashMap&lt;K, V&gt; (0, 0.75f, type);
      }
  
  
      /** 
       * Method deletes {@code key-value} associations 
       * until current cache size {@link #currentSize} will become 
       * less than or equal to maximum allowable
       * cache size {@link #maxSize}
       */
      private void relaxSize()  {
  
          while (currentSize &gt; maxSize) {
  
               // The strategy for choosing entry with the lowest precedence
               // depends on {@code type} variable that was used to create  {@link #entries} variable. 
               // If it was created with constructor LinkedHashMap(int size,double loadfactor, boolean type)
               // with {@code type} equaled to {@code true} then variable {@link #entries} represents
               // LRU LinkedHashMap and iterator of its entrySet will return elements in order
               // from least recently used to the most recently used.
               // Otherwise, if {@code type} equaled to {@code false} then {@link #entries} represents
               // FIFO LinkedHashMap and iterator will return its entrySet elements in FIFO order -
               // from oldest in the cache to the most recently added.
  
              Map.Entry &lt;K, V&gt; entryToDelete = entries.entrySet().iterator().next();
  
              if (entryToDelete == null) {
                  throw new IllegalStateException(" Implemented method int getSize(K key, V value) " +
                          " returns different results for the same arguments.");  
              }
  
              entries.remove(entryToDelete.getKey());
              currentSize -= getAssociationSize(entryToDelete.getKey(), entryToDelete.getValue());
              erasedCount++;
          }
  
          if (currentSize &lt; 0) {
              throw new IllegalStateException(" Implemented method int getSize(K key, V value) " +
                      " returns different results for the same arguments.");
          }
      }
  
  
      /** 
       * All inheritors must implement this method
       * which evaluates the weight of key-value association.
       * Sum of weights of all key-value association in the cache
       * equals to {@link #currentSize}.  
       * But developer must ensure that
       * implementation will satisfy two conditions:
       * &lt;br&gt;1) method always returns non negative integers;
       * &lt;br&gt;2) for every two pairs {@code key-value} and {@code key_1-value_1}
       * if {@code key.equals(key_1)} and {@code value.equals(value_1)} then 
       * {@code getSize(key, value)==getSize(key_1, value_1)};
       * &lt;br&gt; Otherwise cache can work incorrectly.
       */
      protected abstract int getSize(K key, V value);
  
  
      /** 
       * Helps to detect if the implementation of {@link #getSize(K, V)} method
       * can return negative values. 
       */
      private int getAssociationSize(K key, V value)  {
  
          int entrySize = getSize(key, value);
  
          if (entrySize &lt; 0 ) {
              throw new IllegalStateException("int getSize(K key, V value) method implementation is invalid. It returned negative value.");
          }
  
          return entrySize;
      }
  
  
     /**
      * Returns the {@code value} corresponding to {@code key} or
      * {@code null} if  {@code key} is not present in the cache. 
      * Increases {@link #keysFound} if finds a corresponding {@code value}
      * or increases {@link #keysMissed} otherwise. 
      */
      public synchronized final V get(K key)  {
  
          if (key == null) {
              throw new NullPointerException("K key is null");
          }
  
          V value = entries.get(key);
          if (value != null) {
              keysFound++;
              return value;
          }
  
          keysMissed++;
          return value;
      }
  
  
      /** 
       * Removes the {@code key-value} association, if any, with the
      *  given {@code key}; returns the {@code value} with which it
      *  was associated, or {@code null}.
      */
      public synchronized final V remove(K key)  {
  
          if (key == null) {
              throw new NullPointerException("K key is null");
          }
  
          V value = entries.remove(key);
  
          // if appropriate value was present in the cache than decrease
          // current size of cache
  
          if (value != null) {
              currentSize -= getAssociationSize(key, value);
          }
  
          return value;
      }
  
  
     /**
      * Adds or replaces a {@code key-value} association.
      * Returns the old {@code value} if the
      * {@code key} was present; otherwise returns {@code null}.
      * If after insertion of a {@code key-value} association 
      * to cache its size becomes greater than
      * maximum allowable cache size then it calls {@link #relaxSize()} method which
      * releases needed free space. 
      */
      public synchronized final V put(K key, V value)  {
  
          if (key == null || value == null) {
              throw new NullPointerException("K key is null or V value is null");
          }
  
          currentSize += getAssociationSize(key, value);      
          value = entries.put(key, value);
  
          // if key was not present then decrease cache size
  
          if (value != null) {
              currentSize -= getAssociationSize(key, value);
          }
  
          // if cache size with new entry is greater
          // than maximum allowable cache size
          // then get some free space
  
          if (currentSize &gt; maxSize) {
              relaxSize();
          }
  
          return value;
      }
  
  
      /**
       * Returns current size of cache. 
       */
      public synchronized int currentSize() {
          return currentSize;
      }
  
  
      /** 
       * Returns maximum allowable cache size. 
       */ 
      public synchronized int maxSize() {
          return maxSize;
      }
  
  
      /** 
       * Returns number of {@code key-value} associations that were deleted
       * because of cache overflow.   
       */
      public synchronized int erasedCount() {
          return erasedCount;
      }
  
  
      /** 
       * Number of {@link #get(K)} queries for which appropriate {@code value} was found.
       */
      public synchronized int keysFoundCount() {
          return keysFound;
      }
  
  
      /** 
       * Number of {@link #get(K)} queries for which appropriate {@code value} was not found.
       */
      public synchronized int keysMissedCount() {
          return keysMissed;
      }
  
  
      /**
       * Removes all {@code key-value} associations
       * from the cache. And turns {@link #currentSize},
       * {@link #keysFound}, {@link #keysMissed} to {@code zero}.  
       */
      public synchronized void clear() {
          entries.clear();
          currentSize = 0;
          keysMissed = 0;
          keysFound = 0;
          erasedCount = 0;
      }
  
  
      /**
       * Returns a copy of {@link #entries}
       * that has the same content.
       */
      public synchronized LinkedHashMap&lt;K, V&gt; getCopy() {
          return new LinkedHashMap&lt;K, V&gt; (entries);
      }
  }
  </code></pre>
  
  <p>This implementation is quite slow (because of synchronization) if we have many threads are trying to call lets say <code>get()</code> method. Is there a better way? </p>