仅包含最近条目的HashMap

Question

最近我进行了一次面试，面试官让我创建一个最多有7个键/值对的HashMap。如果添加了第8个键/值对，则应该删除第一个键/值对，插入第八个键/值对来替换它，等等。

解决这个问题的好策略是什么？

Answer 1

使用LinkedHashMap创建数据结构并覆盖removeEldestEntry，即如下所示：

import java.util.LinkedHashMap;

class CustomHashMap extends LinkedHashMap<Integer, Integer> {
    private int capacity;

    public CustomHashMap(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity; 
    }
}

或者，如果不允许使用标准库，或者使用的语言没有像Java/Python那样的有序字典结构，则可以使用Hashtable +和DoubleEndedLinkedList，这样您就可以定义自己并实现相同的功能，或者使用Deque：

• 时间复杂性： O(1)，用于put和get。
• 空间复杂性： O(capacity).

尽管你必须编写更多的代码。

泛型版本按@Holger的request

import java.util.LinkedHashMap;
import java.util.Map;

class CustomHashMap<K, V> extends LinkedHashMap<K, V> {
    private int capacity;

    public CustomHashMap(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

示例用法：

class Main {
    public static void main(String[] args) {
        CustomHashMap map = new CustomHashMap(3);
        map.put(1, null);
        map.put(2, null);
        map.put(3, null);
        map.put(4, null);
        System.out.println(map.keySet());
    }
}

输出：

[2, 3, 4]

Answer 2

Java标准库包含一个名为LinkedHashMap的类型，它或多或少地完成了您在这里希望做的事情。它就像一个普通的HashMap，只是它跟踪元素插入的顺序。如果您定义了一个子类并覆盖了removeEldestEntry受保护的方法，那么LinkedHashMap将自动地删除旧元素，并按照您想要的时间表用新元素替换它们。

另一方面，如果您想自己构建这样的东西，您可能会寻找类似哈希表的东西，该哈希表具有一个在元素中线程化的双链接列表。每当插入元素时，都将其追加到链接列表中，然后，如果元素太多，则删除第一个元素。我将把如何做删除等细节留给您。

尽管如此，上述策略最适合于相当大的映射(例如，100个键/值对或更多)。如果您只需要存储七个键/值对，那么只将所有内容都抛到一个未排序的数组中，并遍历元素，只需检查每个元素就可以更快地找到要查找的元素。:-)

最后，有趣的事实是:您正在设计的东西有时被称为LRU cache。这些技术在硬件和软件中得到了广泛的应用。