Как Вы реализовали бы кэш LRU в Java?

Взгляните на ConcurrentSkipListMap. Это должно дать Вам журнал (n) время для тестирования и удаления элемента, если это уже содержится в кэше, и постоянное время для передобавления его.

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

Хорошо для кэша Вы будете обычно искать некоторую часть данных через объект прокси, (URL, Строка....) настолько интерфейсно-мудрый, Вы собираетесь хотеть карту. но ударить вещи Вы хотите очередь как структура. Внутренне я поддержал бы две структуры данных, Приоритетная Очередь и HashMap. здесь являются реализацией, которая должна быть в состоянии сделать все в O (1) время.

Вот класс, который я сделал на скорую руку довольно быстрый:

import java.util.HashMap;
import java.util.Map;
public class LRUCache<K, V>
{
    int maxSize;
    int currentSize = 0;

    Map<K, ValueHolder<K, V>> map;
    LinkedList<K> queue;

    public LRUCache(int maxSize)
    {
        this.maxSize = maxSize;
        map = new HashMap<K, ValueHolder<K, V>>();
        queue = new LinkedList<K>();
    }

    private void freeSpace()
    {
        K k = queue.remove();
        map.remove(k);
        currentSize--;
    }

    public void put(K key, V val)
    {
        while(currentSize >= maxSize)
        {
            freeSpace();
        }
        if(map.containsKey(key))
        {//just heat up that item
            get(key);
            return;
        }
        ListNode<K> ln = queue.add(key);
        ValueHolder<K, V> rv = new ValueHolder<K, V>(val, ln);
        map.put(key, rv);       
        currentSize++;
    }

    public V get(K key)
    {
        ValueHolder<K, V> rv = map.get(key);
        if(rv == null) return null;
        queue.remove(rv.queueLocation);
        rv.queueLocation = queue.add(key);//this ensures that each item has only one copy of the key in the queue
        return rv.value;
    }
}

class ListNode<K>
{
    ListNode<K> prev;
    ListNode<K> next;
    K value;
    public ListNode(K v)
    {
        value = v;
        prev = null;
        next = null;
    }
}

class ValueHolder<K,V>
{
    V value;
    ListNode<K> queueLocation;
    public ValueHolder(V value, ListNode<K> ql)
    {
        this.value = value;
        this.queueLocation = ql;
    }
}

class LinkedList<K>
{
    ListNode<K> head = null;
    ListNode<K> tail = null;

    public ListNode<K> add(K v)
    {
        if(head == null)
        {
            assert(tail == null);
            head = tail = new ListNode<K>(v);
        }
        else
        {
            tail.next = new ListNode<K>(v);
            tail.next.prev = tail;
            tail = tail.next;
            if(tail.prev == null)
            {
                tail.prev = head;
                head.next = tail;
            }
        }
        return tail;
    }

    public K remove()
    {
        if(head == null)
            return null;
        K val = head.value;
        if(head.next == null)
        {
            head = null;
            tail = null;
        }
        else
        {
            head = head.next;
            head.prev = null;
        }
        return val;
    }

    public void remove(ListNode<K> ln)
    {
        ListNode<K> prev = ln.prev;
        ListNode<K> next = ln.next;
        if(prev == null)
        {
            head = next;
        }
        else
        {
            prev.next = next;
        }
        if(next == null)
        {
            tail = prev;
        }
        else
        {
            next.prev = prev;
        }       
    }
}

Вот то, как это работает. Ключи хранятся в связанном списке с самыми старыми ключами перед списком (новые ключи переходят к спине), поэтому, когда необходимо 'извлечь' что-то, что Вы просто выталкиваете его от передней стороны очереди и затем используете ключ для удаления значения из карты. Когда на объект ссылаются, Вы захватываете ValueHolder из карты и затем используете queuelocation переменную, чтобы удалить ключ из его текущего местоположения в очереди и затем поместить его позади очереди (его теперь последний раз используемый). Добавление вещей является в значительной степени тем же.

я уверен, что существует тонна ошибок здесь, и я не реализовал синхронизации. но этот класс обеспечит O (1) добавление к кэшу, O (1) удаление старых объектов и O (1) извлечение объектов кэша. Даже тривиальная синхронизация (просто синхронизируют каждый открытый метод) все еще имела бы мало конкуренции за блокировку из-за времени выполнения. Если бы у кого-либо есть какие-либо умные приемы синхронизации, мне очень было бы интересно. Кроме того, я уверен, что существует некоторая дополнительная оптимизация, что Вы могли реализовать использование maxsize переменной относительно карты.

Я рассмотрел бы использование java.util.concurrent. PriorityBlockingQueue, с приоритетом, определенным "numberOfUses", противостоит в каждом элементе. Я был бы очень, очень осторожен для получения всей моей корректной синхронизации, поскольку счетчик "numberOfUses" подразумевает, что элемент не может быть неизменным.

объект элемента был бы оберткой для объектов в кэше:

class CacheElement {
    private final Object obj;
    private int numberOfUsers = 0;

    CacheElement(Object obj) {
        this.obj = obj;
    }

    ... etc.
}

LinkedHashMap O (1), но требует синхронизации. Никакая потребность изобрести велосипед там.

2 опции для увеличения параллелизма:

1. Создайте приблизительно LinkedHashMap и хеш в них: пример: LinkedHashMap[4], index 0, 1, 2, 3. На ключе делают key%4 (или binary OR на [key, 3]) для выбора который карта сделать помещение/получение/удаление.

2. Вы могли сделать 'почти' LRU путем расширения ConcurrentHashMap и наличия связанной карты хеша как структура в каждом из регионов в нем. Блокировка произошла бы более детализировано, чем LinkedHashMap, который синхронизируется. На put или putIfAbsent только блокировка на голове и хвосте списка необходима (на регион). На удалении или заставляют целые потребности региона быть заблокированными. Мне любопытно, если Атомарные какие-то связанные списки могли бы помочь здесь - вероятно, так для заголовка списка. Возможно, для больше.

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

1. было бы легче записать и быстрее под умеренным параллелизмом.

2. было бы более трудным записать, но масштабироваться намного лучше в очень высоком параллелизме. Это было бы медленнее для нормального доступа (как ConcurrentHashMap медленнее, чем [1 112], где нет никакого параллелизма)

Мне нравятся многие из этих предложений, но пока я думаю, что я буду придерживаться LinkedHashMap + Collections.synchronizedMap. Если я вернусь к этому в будущем, то, вероятно, буду работать над расширением ConcurrentHashMap таким же образом LinkedHashMap расширяет HashMap.

UPDATE:

По запросу, вот суть моей текущей реализации.

private class LruCache<A, B> extends LinkedHashMap<A, B> {
    private final int maxEntries;

    public LruCache(final int maxEntries) {
        super(maxEntries + 1, 1.0f, true);
        this.maxEntries = maxEntries;
    }

    /**
     * Returns <tt>true</tt> if this <code>LruCache</code> has more entries than the maximum specified when it was
     * created.
     *
     * <p>
     * This method <em>does not</em> modify the underlying <code>Map</code>; it relies on the implementation of
     * <code>LinkedHashMap</code> to do that, but that behavior is documented in the JavaDoc for
     * <code>LinkedHashMap</code>.
     * </p>
     *
     * @param eldest
     *            the <code>Entry</code> in question; this implementation doesn't care what it is, since the
     *            implementation is only dependent on the size of the cache
     * @return <tt>true</tt> if the oldest
     * @see java.util.LinkedHashMap#removeEldestEntry(Map.Entry)
     */
    @Override
    protected boolean removeEldestEntry(final Map.Entry<A, B> eldest) {
        return super.size() > maxEntries;
    }
}

Map<String, String> example = Collections.synchronizedMap(new LruCache<String, String>(CACHE_SIZE));

Существует две реализации с открытым исходным кодом.

Apache Solr имеет ConcurrentLRUCache: https://lucene.apache.org/solr/3_6_1/org/apache/solr/util/ConcurrentLRUCache.html

Есть проект с открытым исходным кодом для ConcurrentLinkedHashMap: http://code.google.com/p/concurrentlinkedhashmap/

Я ищу лучший кеш LRU с использованием кода Java. Можно ли поделиться своим кодом кэша LRU Java с помощью LinkedHashMap и Collections # synchronizedMap ? В настоящее время я использую LRUMap реализует карту , и код работает нормально, но я получаю ArrayIndexOutofBoundException при нагрузочном тестировании с использованием 500 пользователей по указанному ниже методу. Метод перемещает последний объект в начало очереди. Метод

private void moveToFront(int index) {
        if (listHead != index) {
            int thisNext = nextElement[index];
            int thisPrev = prevElement[index];
            nextElement[thisPrev] = thisNext;
            if (thisNext >= 0) {
                prevElement[thisNext] = thisPrev;
            } else {
                listTail = thisPrev;
            }
            //old listHead and new listHead say new is 1 and old was 0 then prev[1]= 1 is the head now so no previ so -1
            // prev[0 old head] = new head right ; next[new head] = old head
            prevElement[index] = -1;
            nextElement[index] = listHead;
            prevElement[listHead] = index;
            listHead = index;
        }
    }

get (Object key) и put (Object key, Object value) вызывает вышеупомянутый метод moveToFront .