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