我正在寻找一种数据结构，它类似于哈希表但具有大小限制。当哈希表中的项目数量达到大小限制时，应该调用清除函数来清除表中最少检索的键/值对。
这是我所工作内容的一些伪代码：
这感觉像是一个已经解决的问题，但我不确定要使用哪种数据结构才能高效地解决它。是否有人可以指点我正确的方向？
更新：我知道这一定是一个已经解决的问题了。它被称为LRU缓存（最近最少使用缓存），可以通过扩展LinkedHashMap类轻松创建。以下是包含解决方案的代码：
这是我所工作内容的一些伪代码：
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;
}
}