什么是数据结构类似哈希表,但不常使用的键被删除？

Question

我正在寻找一个类似于哈希表的数据结构,但表中有一个大小限制.当散列中的项数达到大小限制时,应调用剔除函数以消除表中检索次数最少的键/值对.

这是我正在研究的一些伪代码:

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 Cache,通过扩展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;
  }
}

Answer 1

你正在寻找LRUList/ Map.退房LinkedHashMap:

removeEldestEntry(Map.Entry)可以重写该方法,以便在将新映射添加到映射时自动删除过时映射的策略.