java - 什么是类似于哈希表的数据结构，但是不常用的键被删除了？

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 缓存，通过扩展 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) 方法可能会被覆盖，以在 map 中添加新映射时自动删除陈旧映射。