LRU キャッシュの効率的な実装を作成したいと考えています。最も便利な方法は を使用することですLinkedHashMapが、残念ながら多くのスレッドがキャッシュを使用している場合は非常に遅くなります。私の実装はここにあります：
/**
* 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);
}
}
多くのスレッドがメソッドを呼び出そうとしている場合、この実装は非常に遅くなります (同期のため) get()。より良い方法はありますか？