Как реализовать самый недавно используемый кэш

Какой был бы лучший способ реализовать самый недавно использованный кеш объектов?

Вот требования и ограничения...

Объекты хранятся как пары ключ/значение Object/Object, поэтому интерфейс будет немного похож на Hashtable get/put
Призыв к 'get' будет отмечать этот объект как последний раз.
В любой момент, последний использованный объект может быть удален из кеша.
Поиск и очистка должны быть быстрыми (как в Hashtable быстро)
Количество объектов может быть большим, поэтому просмотры списков недостаточно хороши.
Реализация должна выполняться с использованием JavaME, поэтому возможностей для использования сторонних кодов или опрятных классов библиотеки из стандартных библиотек Java не существует. По этой причине я больше ищу алгоритмические ответы а не рекомендации решений без привязки.

Ответ 1

Коллекции Java предоставляют LinkedHashMap из коробки, которая хорошо подходит для создания кэшей. Вероятно, у вас этого нет в Java ME, но вы можете взять здесь исходный код:

http://kickjava.com/src/java/util/LinkedHashMap.java.htm

Если вы не можете просто скопировать его, посмотрите, чтобы вы начали внедрять его для своего мобильного приложения. Основная идея состоит в том, чтобы включить связанный список через элементы карты. Если вы постоянно обновляете его, когда кто-либо помещает или получает, вы можете эффективно отслеживать порядок доступа и использовать порядок.

Документы содержат инструкции по созданию кэша MRU путем переопределения метода removeEldestEntry(Map.Entry). Все, что вам действительно нужно сделать, это сделать класс, расширяющий LinkedHashMap и переопределить метод следующим образом:

private static final int MAX_ENTRIES = 100;

protected boolean removeEldestEntry(Map.Entry eldest) {
   return size() > MAX_ENTRIES;
}

Также существует конструктор который позволяет указать, хотите ли вы, чтобы класс хранил вещи по порядку путем вставки или использования, так что вы получили небольшую гибкость для вашей политики выселения тоже:

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder)

Pass true для порядка использования и false для порядка вставки.

Ответ 2

A ConcurrentLinkedHashMap сложно построить из-за требований блокировки. LinkedHashMap с замком прост, но не всегда исполнен. Одновременная версия будет пытаться уменьшить количество блокировки, либо путем блокировки блокировки, либо в идеале сделать операции CAS сделать блокировку очень дешевой. Если операции CAS когда-либо становятся дорогими, то аналогичным образом может быть полезно разделение ковша. Поскольку LRU требует записи для каждой операции доступа и использует двусвязный список, это очень сложно реализовать с чистыми операциями CAS. Я попытался это сделать, но мне нужно продолжить созвать свой алгоритм. Если вы ищете ConcurrentLinkedHashMap, вы увидите мою страницу проекта...

Если Java ME не поддерживает операции CAS, которые я ожидал бы быть правдой, тогда базовая синхронизация - это все, что вы можете сделать. Вероятно, это достаточно хорошо с LHM, учитывая, что я видел проблемы с производительностью при высоком количестве потоков на стороне сервера. Итак, +1 к ответам выше.

Ответ 3

Зачем внедрять что-то уже реализованное? Используйте Ehcache.

Однако, если сторонние библиотеки полностью не могут быть и речи, я думаю, вы хотите внедрить структуру данных, которая выглядит примерно так:

В принципе, это HashMap (расширяет HashMap<Object, Object>, если вы это сделаете)
Каждое значение в карте указывает на объект в отсортированном списке, на основе которого наиболее часто используется.
Недавно добавленные объекты добавляются в список списка - O(1)
Очистка наименее недавнего использования означает усечение конца списка - O(1)
Все еще дает вам поиск по карте, но все же сохраняет недавно используемые элементы...

Ответ 4

Другой подход может состоять в том, чтобы взглянуть на раздел 5.6 в Java Concurrency на практике Брайан Гетц: "Создание эффективного масштабируемого кэша результатов". Взгляните на Memoizer, хотя вам, возможно, придется настроить его для своих целей.

В стороне, я не могу понять, почему Java не имеет ConcurrentLinkedHashMap из коробки. Эта структура данных будет очень полезна для создания кеша.