LFU cache

Реализован кэш с политикой вытеснения Last Frequently Used (LFU).

Особенности

• Все операции работают за O(1)
• Поддержка дженериков (Go 1.18+)
• Итерация по элементам с помощью iter.Seq2
• Понятная структура кода с комментариями

Методы

• New[K comparable, V any](capacity ...int) *CacheImpl[K, V]
  Создает новый LFU кэш с указанной емкостью. Если емкость не указана, используется DefaultCapacity (5)
• Get(key K) (V, error)
  Возвращает значение по ключу или ErrKeyNotFound, если ключ отсутствует.
• Put(key K, value V)
  Добавляет или обновляет значение по ключу. При достижении емкости вытесняет наименее часто используемый элемент.
• All() iter.Seq2[K, V]
  Возвращает итератор по всем элементам в порядке убывания частоты использования.
• Size() int
  Возвращает текущее количество элементов в кэше.
• Capacity() int
  Возвращает максимальную емкость кэша.
• GetKeyFrequency(key K) (int, error)
  Возвращает частоту использования ключа или ErrKeyNotFound, если ключ отсутствует.

Принцип работы

• Двусвязный список для хранения всех элементов.
• Элементы упорядоченны по уровням частоты использования.
• Хэш-таблица для быстрого доступа к элементам по ключу.
• Хэш-таблица для быстрого доступа к первым элементам каждого уровня частоты.