使用LinkedHashMap實現LRU緩存

可能很多人已經知道了這個技術，但是對于我來說，雖然使用Java十余年了，最近才了解到LinkedHashMap這個類。使用這個類可以方便的實現一個本地的LRU Cache類。

之所以沒有關注到這個類，是因為在面對本地緩存的case時，我經常會考慮guava這個框架。

最早可以搜到的一篇關于LinkedHashMap實現本地緩存的文章之一是這篇: How to set up a simple LRU cache using LinkedHashMap ，發表于2005年。文末有附了幾篇關于LinkedHashMap類的介紹。

這個類實現了Hash和雙向鏈表兩種數據結構的混合。 所以通過get方法可以很快的得到相應的元素，而鏈表結構又可以根據access或者insert進行排序。但是這種

方式也會有性能的損耗，因為對數據的插入需要同時更新這兩個數據結構，對數據的訪問在accessOrder情況下也會涉及數據的移動。 我們知道數據量大的情況下對鏈表的更改是很耗時的，所以使用的時候要仔細考量。

import java.util.LinkedHashMap;

import java.util.Map;

public LRUCache<K, V> extends LinkedHashMap<K, V> {

private int cacheSize;

public LRUCache ( int cacheSize) {

super ( 16 , 0.75 , true );

this .cacheSize = cacheSize;

}

protected boolean removeEldestEntry (Map.Entry<K, V> eldest) {

return size() >= cacheSize;

}

}