如何限制Java哈希表中条目的数量？

Question

有没有一种技术可以指定一个数字n，这样当插入第(n + 1)个条目时，最旧的条目会被首先删除，以确保哈希表的大小始终限制为n？

- Obediah Stane

---

这类似于https://dev59.com/d3VC5IYBdhLWcg3whBWj。该问题提供了一个解决方案。 - Rob Hruska

@robhruska - 你认为这算是重复吗？我还没有决定。 - Paul Tomblin

我不确定。角度有些不同，因为这个问题问的是“大小限制”，而另一个问题则针对“不经常使用的”条目。如果这样做只是为了从这个问题的角度更容易搜索，那么我并不反对让它保持开放状态。 - Rob Hruska

http://letmegooglethatforyou.com/?q=data+structures - yfeldblum

Answer 1

LinkedHashMap 正好可以做到这一点，详见removeEldestEntry 方法的 Java 文档。

像下面这样做就可以了，这将删除最早插入的条目：

Map map = new LinkedHashMap() {
    @Override
    protected boolean removeEldestEntry(Entry eldest) {
        return size() > N;
    }
};

您也可以在构造函数中指定要删除的最早访问条目：

    Map map = new LinkedHashMap(16, 0.75f, true) {
        @Override
        protected boolean removeEldestEntry(Entry eldest) {
            return size() > N;
        }
    };

- Kristian

Answer 2

也许你正在寻找一个LRU缓存？这里有一篇关于基于LinkedHashMap的博客文章。

- sblundy

---

我来这里提一下LinkedHashMap，我最近用它实现了一个LRU缓存。 - Paul Tomblin

Answer 3

你可能想考虑使用 Apache Collections。它们有一堆 LRU 的实现。否则，你可以轻松地为标准库集合编写类似的包装器；我认为没有一个可以直接使用的。

- Uri

Answer 4

你可以使用双端队列或Deque，并在达到最大计数时仅删除第一个项目。

- Eric H

Answer 5

如果您有并发需求，请不要试图自己解决这个问题。Guava的CacheBuilder有一个.maximumSize()方法，允许您限制映射的大小，尽管我理解在实际达到限制之前可能会清除旧条目。

关于数据结构设计，有一个有趣的页面，它应该让读者印象深刻，说明要比Google的实现做得更好是多么困难。 :)

- Rag

Answer 6

如果您正在进行缓存，您可以使用WeakHashMap或WeakReference，这样就不必担心缓存的大小了。

- Steve Kuo

---

只是为了澄清以避免传播一个常见的误解：WeakHashMap本身不适合LRU缓存；它使用弱引用作为键，而不是值。它非常适合保留关于不属于您的对象的元数据；但不适合假设条目将在内存耗尽时被丢弃。 - Cowan