Карта фиксированной памяти Java - PullRequest
Новая
       10

Карта фиксированной памяти Java

13 голосов
/ 31 мая 2010

Существует ли простая, эффективная Map реализация, позволяющая ограничить использование памяти картой.

Мой вариант использования заключается в том, что я хочу динамически распределять большую часть памяти, доступной на момент ее создания, но я не хочу OutOFMemoryError в будущем По сути, я хочу использовать эту карту в качестве кеша, но я хочу избежать тяжелых реализаций кеша, таких как EHCache. Моя потребность проста (максимум алгоритм LRU)

Я должен пояснить, что объекты в моем кэше char[] или аналогичные примитивы, которые не будут содержать ссылки на другие объекты.

Я могу установить максимальный размер для каждой записи.

Ответы [ 5 ]

9 голосов
/ 31 мая 2010

Вы можете использовать LinkedHashMap, чтобы ограничить количество записей в Map:

removeEldestEntry(Map.Entry<K,V> eldest): Возвращает true, если эта карта должна удалить свою самую старую запись. Этот метод вызывается put и putAll после вставки новой записи в карту. Это дает разработчику возможность удалять самую старую запись каждый раз, когда добавляется новая. Это полезно, если карта представляет собой кэш: она позволяет карте уменьшить потребление памяти, удаляя устаревшие записи.

Пример использования: это переопределение позволит карте увеличиваться до 100 записей, а затем удалять самую старую запись при каждом добавлении новой записи, поддерживая устойчивое состояние 100 записей. 

private static final int MAX_ENTRIES = 100;

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

Похожие вопросы

6 голосов
/ 31 мая 2010

Для кэшей SoftHashMap гораздо более уместен, чем WeakHashMap. WeakhashMap обычно используется, когда вы хотите сохранить связь с объектом до тех пор, пока этот объект жив, но не препятствуя его восстановлению.

Напротив, SoftReference более тесно связан с распределением памяти. См. Нет SoftHashMap? для получения подробной информации о различиях.

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

В коллекциях Commons есть ReferenceMap, где вы можете указать, какие типы ссылок вы хотите использовать для ключей и значений. Для кеша, чувствительного к памяти, вы, вероятно, будете использовать жесткие ссылки для ключей и программные ссылки для значений.

Чтобы получить семантику LRU для заданного числа ссылок N, ведите список последних N записей, извлеченных из кэша - при получении записи из кэша она добавляется в начало списка (и хвост список удален.) Чтобы убедиться, что это не удерживает слишком много памяти, вы можете создать мягкую ссылку и использовать ее в качестве триггера для удаления процента записей из конца списка. (И создайте новую мягкую ссылку для следующего триггера.)

3 голосов
/ 31 мая 2010

Решения для платформы Java

Если все, что вам нужно, это Карта, ключи которой можно очистить, чтобы избежать OutOfMemoryErrors, вы можете посмотреть WeakHashMap . Он использует WeakReferences , чтобы позволить сборщику мусора пожинать записи карты. Тем не менее, он не будет применять какую-либо семантику LRU, кроме тех, которые присутствуют в сборке мусора поколений.

Также есть LinkedHashMap , что есть в документации:

Специальный конструктор предоставляется создать связанную хэш-карту, порядок которой итерации - это порядок, в котором ее записи, к которым последний раз обращались, из наименее недавно доступ к совсем недавно (доступ-порядок). это вид карты хорошо подходит для строительства LRU кеширует. Вызов пут или получить метод приводит к доступу к соответствующая запись (при условии, что это существует после вызова завершается). Метод putAll генерирует одну запись доступа для каждого отображение на указанной карте, в заказать, что сопоставления ключ-значение обеспечивается указанным элементом карты установить итератор. Других методов нет генерировать входы. В в частности, операции на представления коллекции не влияют на порядок итерации карты поддержки.

Так что, если вы используете этот конструктор для создания карты, чей Iterator повторяется в LRU, становится довольно легко обрезать карту. Единственное (довольно большое ) предостережение в том, что LinkedHashMap не синхронизируется вообще , так что вы по отдельности для одновременности. Вы можете просто обернуть его в синхронизированную оболочку, но это может иметь проблемы с пропускной способностью.

Раскатайте свое собственное решение

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

1 голос
/ 31 мая 2010

WeakHashMap не обязательно достигнет вашей цели, поскольку, если ваше приложение удержит достаточно сильную ссылку на клавиши, вы увидите OOME.

В качестве альтернативы вы можете посмотреть на SoftReference, который обнулит содержимое, как только куча станет недостаточной. Тем не менее, большинство комментариев, которые я видел, показывают, что он не будет обнулять ссылку, пока куча действительно не станет очень низкой, и многие GC начнут работать с серьезным ударом по производительности (поэтому я не рекомендую использовать его для своих целей) ,

Я рекомендую использовать простую карту LRU, например http://commons.apache.org/collections/apidocs/org/apache/commons/collections/LRUMap.html

0 голосов
/ 03 июня 2010

спасибо за ответы, ребята!

Как указал jasonmp85, LinkedHashMap имеет конструктор, который разрешает порядок доступа. Я пропустил этот бит, когда посмотрел на API документы. Реализация также выглядит довольно эффективно (см. Ниже). В сочетании с максимальным размером крышки для каждой записи, это должно решить мою проблему.

Я также посмотрю внимательно на SoftReference. Просто отметим, что Google Коллекции, похоже, имеют довольно хороший API для SoftKeys, SoftValues ​​и Карт в целом.

Вот фрагмент из класса Java LikedHashMap, который показывает, как они поддерживают поведение LRU. 

    /**
     * Removes this entry from the linked list.
     */
    private void remove() {
        before.after = after;
        after.before = before;
    }

    /**
     * Inserts this entry before the specified existing entry in the list.
     */
    private void addBefore(Entry<K,V> existingEntry) {
        after  = existingEntry;
        before = existingEntry.before;
        before.after = this;
        after.before = this;
    }

    /**
     * This method is invoked by the superclass whenever the value
     * of a pre-existing entry is read by Map.get or modified by Map.set.
     * If the enclosing Map is access-ordered, it moves the entry
     * to the end of the list; otherwise, it does nothing.
     */
    void recordAccess(HashMap<K,V> m) {
        LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
        if (lm.accessOrder) {
            lm.modCount++;
            remove();
            addBefore(lm.header);
        }
...