什麼是類似散列表的數據結構類型，但不常用的鍵會被刪除？

我正在尋找一個類似於散列表的操作的數據結構，但表中有一個大小限制。當哈希中的項目數量達到大小限制時，應調用一個剔除函數來擺脫表中最少檢索的鍵/值對。什麼是類似散列表的數據結構類型，但不常用的鍵會被刪除？

這裏是我工作的一些僞代碼：

class MyClass { 
    private Map<Integer, Integer> cache = new HashMap<Integer, Integer>(); 
    public int myFunc(int n) { 
    if(cache.containsKey(n)) 
     return cache.get(n); 
    int next = . . . ; //some complicated math. guaranteed next != n. 
    int ret = 1 + myFunc(next); 
    cache.put(n, ret); 
    return ret; 
    } 
}

什麼情況是，也有n一些值，這myFunc()將被稱爲很多次，但n許多其他值這將只計算一次。因此，緩存可能會填充數百萬個不再需要的值。我想有一種方法讓緩存自動刪除不經常檢索的元素。

這感覺就像一個必須解決的問題，但我不確定數據結構是什麼，我會用它來有效地做到這一點。任何人都可以將我指向正確的方向嗎？

更新我知道這必須是一個已經解決的問題。它被稱爲LRU緩存，並且通過擴展LinkedHashMap類很容易實現。這裏是一個融合解決方案的代碼：

class MyClass { 
    private final static int SIZE_LIMIT = 1000; 
    private Map<Integer, Integer> cache = 
    new LinkedHashMap<Integer, Integer>(16, 0.75f, true) { 
     protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) 
     { 
     return size() > SIZE_LIMIT; 
     } 
    }; 
    public int myFunc(int n) { 
    if(cache.containsKey(n)) 
     return cache.get(n); 
    int next = . . . ; //some complicated math. guaranteed next != n. 
    int ret = 1 + myFunc(next); 
    cache.put(n, ret); 
    return ret; 
    } 
}

來源

2008-11-07 Kip

另請參閱http://stackoverflow.com/questions/224868/easy-simple-to-use-lru-cache-in-java。 – 2008-11-07 17:05:49