java - 时间过期数据结构

Question

在最近的编码面试中，我被要求实现一个键值存储数据结构。实现

size() :列表中元素的数量。

find(key) : 返回key处的值，否则抛出nosuchelement异常。

insert(key, timestamp) :使用这个键添加或更新元素。如果列表已满，则不要执行任何操作。

• 列表有它可以容纳的最大元素数
• 每个元素都作为键和值插入，超过该元素不应被视为在列表中的持续时间，以及输入时间的时间戳。
• 如果列表已满，则忽略试图添加的元素，除非它是重复键。
• 如果具有相同key的元素已经存在，则更新已有的value和已有的时间戳
• 一旦时间超过元素的时间戳+持续时间，则不再将其视为结构的一部分。这意味着如果列表以前是满的，它不再是满的。

我很难找到一种有效的方法来跟踪仍在列表中的元素，因为如果元素的时间用完了，它们可能会从列表中弹出。

Answer 1

我认为您正在寻找的是索引优先级队列。基本上，您构建一个最小优先级队列，其键是时间戳。然后您创建一个索引(按键)来跟踪优先级队列中的项目位置。

在每个操作中，您都可以使用类似以下内容从队列中删除过期的项目:

while (pq.peek().timestamp < current_time) {
    pq.remove();
}

复杂度为 O(k log n)，其中 k 是您移除的项目数，n 是队列中的项目总数。

在 http://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html 有一个索引优先级队列实现。 .我听说过关于它的好消息，但我自己从未使用过它。