Кэш LFU, как получить и установить в O(1)?

Question

Готовясь к интервью, я столкнулся с чем-то, что заставляет меня усомниться в моем понимании больших алгоритмов с постоянным временем.

Вопрос о LeetCode просит создать решение проблемы кэширования LFU.

Есть 3 способа реализации:

Конструктор - Ввод: int Capacity

get - ввод: int key - вывод: int

set - ввод: ключ int, значение int

Емкость представляет собой максимальное количество кэшированных пар ключ / значение, которое вы можете хранить одновременно. Когда емкость нарушена, вы должны извлечь наименее часто используемую пару.

Очевидно, что вы должны следить за количеством обращений к каждому элементу.

В нижней части вопроса спрашивается, можете ли вы одновременно получить и установить время 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.