Временная сложность
Лучший: O(1)
Средний: O(1)
Худший: O(n)
Кэш LRU хранит фиксированное количество записей и при заполнении удаляет ту запись, к которой дольше всего не обращались. Основная задача — обеспечить выполнение операций get и put за O(1).
Почему одной структуры недостаточно:
1. Одна хеш-таблица обеспечивает доступ за O(1), но не позволяет определить, какая запись самая старая
2. Один упорядоченный список позволяет определить самую старую запись, но поиск ключа занимает O(n)
3. Поэтому их объединяют: хеш-таблица отвечает на вопрос «где», а список — «когда»
Структура:
Хеш-таблица: key → указатель на узел, O(1)
Двусвязный список: head = самый недавно использованный, tail = следующий на удаление
Два важных нюанса:
Каждый узел хранит собственный ключ. При удалении узел
извлекается из хвоста списка, а его ключ нужен, чтобы
удалить соответствующую запись из хеш-таблицы — иначе
в таблице останется ссылка на несуществующий элемент.
Список должен быть двусвязным. Перемещение узла в начало
требует отсоединить его от текущей позиции, для чего
необходим указатель prev. В односвязном списке эта
операция заняла бы O(n).
Временная сложность:
Лучшая: O(1) для get и put
Средняя: O(1) — поиск в хеш-таблице и постоянное количество операций с указателями
Худшая: O(n), только если все ключи имеют одинаковый хеш
Пространственная сложность: O(capacity)
Применение: кэширование в базах данных и веб-приложениях, вытеснение записей в Redis (приближённый алгоритм на основе выборки), замена данных в кэше процессора, история переходов назад и вперёд в браузере, мемоизация с ограниченным объёмом памяти
Похожие алгоритмы
Частые вопросы
- Что такое Кэш LRU (Least Recently Used)?
- Кэш LRU хранит фиксированное количество записей и при заполнении удаляет ту запись, к которой дольше всего не обращались. Основная задача — обеспечить выполнение операций get и put за O(1).
- Какова сложность Кэш LRU (Least Recently Used)?
- Время (среднее): O(1) — поиск в хеш-таблице и постоянное количество операций с указателями · Память: O(capacity)
- Для кого предназначена визуализация Кэш LRU (Least Recently Used)?
- Визуализация Кэш LRU (Least Recently Used) рассчитана на продвинутый уровень в категории «Структуры данных». Полезна для студентов, подготовки к собеседованиям и практического изучения.
- Какие алгоритмы связаны с Кэш LRU (Least Recently Used)?
- В той же категории (Структуры данных) вы можете изучить: Stack, Queue, Linked List. Каждый из них имеет интерактивную визуализацию.