algorithm - LFU 缓存，如何在 O(1) 中获取和设置？

Question

准备面试时，我遇到了一些事情，这让我质疑我对大 O 常数时间算法的理解。

LeetCode 上的一个问题要求创建 LFU 缓存问题的解决方案。

有3种实现方法:

构造器 - 输入:int 容量

得到 - 输入:整数键 - 输出:整数

设置 - 输入:int key, int value

容量表示一次可以保存的缓存键/值对的最大数量。当容量被破坏时，您必须弹出访问频率最低的对。

很明显，您必须跟踪每个项目被访问的次数。

在问题的底部，它询问您是否可以在 O(1) 时间内获取和设置。

我正在查看多个建议的实现方案，一长串的人都同意它们是恒定时间实现的示例，但对我来说它们看起来像 O(N)。

有关完整示例，请参见此处: https://leetcode.com/problems/lfu-cache/discuss/94515/Java-O(1)-Accept-Solution-Using-HashMap-DoubleLinkedList-and-LinkedHashSet?page=1

但是这个例子中的相关方法在下面的代码块中。注意valueHash和nodeHash都是java哈希表。

public int get(int key) {
    if (valueHash.containsKey(key)) {
        increaseCount(key);
        return valueHash.get(key);
    }
    return -1;
}

    public void set(int key, int value) {
    if ( cap == 0 ) return;
    if (valueHash.containsKey(key)) {
        valueHash.put(key, value);
    } else {
        if (valueHash.size() < cap) {
            valueHash.put(key, value);
        } else {
            removeOld();
            valueHash.put(key, value);
        }
        addToHead(key);
    }
    increaseCount(key);
}

方法调用Hashtable.containsKey和Hashtable.get，实现线性搜索。那么最坏情况下的时间复杂度是 O(N) 对吗？我错过了什么？

Answer 1

无论您使用什么数据结构，它都有一些悲观的搜索时间 T(n)，取决于存储的项目数 n。如果您设置了一些最大容量 Nmax，并在程序执行期间将其保持常量，如问题陈述中的具体要求，那么处理任何请求的最长时间为 T(Nmax)，这是常数。

感谢@Zabuza 强调 Nmax 的恒定性质。