the best way to implement LRU cache

I want to create an efficient implementation of LRU cache. I've found that the most convenient way is to use `LinkedHashMap` but unfortunately it's quite slow if many threads are using a cache. My implementation is here: ``` /** * 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 <K, V> implements ICache <K, V> { /** * 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 <K, V> 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 <= 0) { throw new IllegalArgumentException("int maxSize parameter must be greater than 0"); } this.maxSize = maxSize; this.entries = new LinkedHashMap<K, V> (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 > 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 <K, V> 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 < 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: * <br>1) method always returns non negative integers; * <br>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)}; * <br> 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 < 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 > 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<K, V> getCopy() { return new LinkedHashMap<K, V> (entries); } } ``` This implementation is quite slow (because of synchronization) if we have many threads are trying to call lets say `get()` method. Is there a better way?