java - 仅包含最新条目的 HashMap

Question

我最近接受了一次面试，面试官要求我创建一个最多有 7 个键/值对的 HashMap。如果添加了第 8 个键/值对，则应删除第一个键/值对并插入第 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 的通用版本的要求:

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]