Comment voulez-vous mettre en œuvre un cache LRU en Java?

Ou de l'utiliser Apache Commons structure de données:

https://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/map/LRUMap.html

LinkedHashMap est O(1), mais requiert une synchronisation. Pas besoin de réinventer la roue il.

2 options pour l'augmentation de la concurrence:

1.
Créer plusieurs LinkedHashMap, et de hachage en eux:
exemple: LinkedHashMap[4], index 0, 1, 2, 3. Sur la clé ne key%4 (ou binary OR sur [key, 3]) de choisir la carte pour faire un put/get/supprimer.

2.
Vous pourriez faire un "presque" LRU en étendant ConcurrentHashMap, et ayant un lien de hachage de la carte comme la structure dans chacune des régions à l'intérieur d'elle. Le verrouillage se ferait plus granulaire que LinkedHashMap qui est synchronisé. Sur un put ou putIfAbsent seulement un verrou sur la tête et la queue de la liste, est nécessaire (par région). Sur un supprimer ou obtenir l'ensemble de la région doit être verrouillé. Je suis curieux de savoir si Atomique listes liées, de la sorte, peut aider à ici -- probablement à la tête de la liste. Peut-être pour plus d'.

La structure ne serait pas garder le total de la commande, mais seulement de l'ordre par région. Tant que le nombre d'entrées est beaucoup plus grande que le nombre de régions, ce est assez bon pour la plupart des caches. Chaque région devra avoir sa propre entrée comte, ce serait utilisée plutôt que le compte global pour l'expulsion de déclenchement.
La valeur par défaut du nombre de régions dans un ConcurrentHashMap est de 16, ce qui est beaucoup pour la plupart des serveurs aujourd'hui.

1. serait plus facile à écrire et plus rapide, en vertu de modéré la simultanéité.

2. serait plus difficile à écrire, mais l'échelle de mieux à une très forte concurrence. Il serait plus lent pour l'accès normal (tout comme ConcurrentHashMap est plus lent que HashMap où il n'y a pas de simultanéité)

Je voudrais envisager d'utiliser java.util.de façon concomitante.PriorityBlockingQueue, avec une priorité déterminée par une "numberOfUses" compteur dans chaque élément. Je serais très, très prudent pour obtenir tous mes synchronisation correcte, comme le "numberOfUses" compteur implique que l'élément ne peut pas être immuable.

L'élément object serait un wrapper pour les objets dans le cache:

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

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

    ... etc.
}

LRU Cache peut être mis en œuvre à l'aide d'un ConcurrentLinkedQueue et un ConcurrentHashMap qui peut être utilisé dans le multithreading scénario. La tête de la file d'attente est cet élément qui a été mis sur la file d'attente la plus longue de temps. La queue de la file d'attente est cet élément qui a été mis sur la file d'attente la plus courte de temps. Lorsqu'un élément de la Carte, on peut l'enlever de la LinkedQueue et l'insérer à la queue.

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;

public class LRUCache<K,V> {
  private ConcurrentHashMap<K,V> map;
  private ConcurrentLinkedQueue<K> queue;
  private final int size; 

  public LRUCache(int size) {
    this.size = size;
    map = new ConcurrentHashMap<K,V>(size);
    queue = new ConcurrentLinkedQueue<K>();
  }

  public V get(K key) {
    //Recently accessed, hence move it to the tail
    queue.remove(key);
    queue.add(key);
    return map.get(key);
  }

  public void put(K key, V value) {
    //ConcurrentHashMap doesn't allow null key or values
    if(key == null || value == null) throw new NullPointerException();
    if(map.containsKey(key) {
      queue.remove(key);
    }
    if(queue.size() >= size) {
      K lruKey = queue.poll();
      if(lruKey != null) {
        map.remove(lruKey);
      }
    }
    queue.add(key);
    map.put(key,value);
  }

}

Voici mon testés meilleure exécution simultanée de cache LRU mise en œuvre sans synchronisé bloc:

public class ConcurrentLRUCache<Key, Value> {
private final int maxSize;
private ConcurrentHashMap<Key, Value> map;
private ConcurrentLinkedQueue<Key> queue;
public ConcurrentLRUCache(final int maxSize) {
this.maxSize = maxSize;
map = new ConcurrentHashMap<Key, Value>(maxSize);
queue = new ConcurrentLinkedQueue<Key>();
}
/**
* @param key - may not be null!
* @param value - may not be null!
*/
public void put(final Key key, final Value value) {
if (map.containsKey(key)) {
queue.remove(key); //remove the key from the FIFO queue
}
while (queue.size() >= maxSize) {
Key oldestKey = queue.poll();
if (null != oldestKey) {
map.remove(oldestKey);
}
}
queue.add(key);
map.put(key, value);
}
/**
* @param key - may not be null!
* @return the value associated to the given key or null
*/
public Value get(final Key key) {
return map.get(key);
}

}

Bien pour un cache, vous serez généralement en regardant un morceau de données via un serveur proxy de l'objet, (une URL, String....) si l'interface de sage, vous allez vouloir une carte. mais pour le coup les choses que vous voulez une file d'attente comme structure. En interne, je voudrais maintenir deux structures de données, une Priorité de la File d'attente et une HashMap. heres une mise en œuvre qui devrait être capable de tout faire en O(1) fois.

Voici une classe que je fouettée assez rapide:

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;
}       
}
}

Voici comment cela fonctionne. Les clés sont stockées dans une liste liée avec la plus ancienne des touches à l'avant de la liste (nouvelles clés aller à l'arrière) lorsque vous avez besoin de "éjection" quelque chose que vous venez de pop hors de l'avant de la file d'attente, puis utilisez la touche pour supprimer la valeur de la carte. Quand un élément reçoit référencés à vous de prendre la ValueHolder de la carte, puis utilisez la emplacement_file variable pour supprimer la clé à partir de son emplacement actuel dans la file d'attente, puis le mettre à l'arrière de la file d'attente (c'est à présent le plus récemment utilisé). L'ajout de choses est à peu près la même.

Je suis sûr que theres une tonne d'erreurs ici et je n'ai pas mis en place de la synchronisation. mais cette classe fournira O(1) en ajoutant dans le cache, O(1) suppression d'éléments anciens, et O(1) la récupération des éléments du cache. Même une simple synchronisation (juste synchroniser chaque méthode publique) serait encore peu de verrouillage en raison du moment de l'exécution. Si quelqu'un a des intelligent de synchronisation des astuces, je serais très intéressé. Aussi, je suis sûr qu'il ya quelques optimisations supplémentaires que vous pourriez mettre en œuvre à l'aide de la maxsize variable par rapport à la carte.

Voici mon court de mise en place, merci de les critiquer ou de les améliorer!

package util.collection;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;
/**
* Limited size concurrent cache map implementation.<br/>
* LRU: Least Recently Used.<br/>
* If you add a new key-value pair to this cache after the maximum size has been exceeded,
* the oldest key-value pair will be removed before adding.
*/
public class ConcurrentLRUCache<Key, Value> {
private final int maxSize;
private int currentSize = 0;
private ConcurrentHashMap<Key, Value> map;
private ConcurrentLinkedQueue<Key> queue;
public ConcurrentLRUCache(final int maxSize) {
this.maxSize = maxSize;
map = new ConcurrentHashMap<Key, Value>(maxSize);
queue = new ConcurrentLinkedQueue<Key>();
}
private synchronized void freeSpace() {
Key key = queue.poll();
if (null != key) {
map.remove(key);
currentSize = map.size();
}
}
public void put(Key key, Value val) {
if (map.containsKey(key)) {//just heat up that item
put(key, val);
return;
}
while (currentSize >= maxSize) {
freeSpace();
}
synchronized(this) {
queue.add(key);
map.put(key, val);
currentSize++;
}
}
public Value get(Key key) {
return map.get(key);
}
}

Je suis à la recherche d'une meilleure LRU cache à l'aide de code Java. Est-il possible pour vous de partager votre Java LRU cache de code à l'aide de LinkedHashMap et Collections#synchronizedMap? Actuellement, je suis en utilisant LRUMap implements Map et le code fonctionne bien, mais je suis ArrayIndexOutofBoundException sur les tests de charge à l'aide de 500 utilisateurs sur la méthode ci-dessous. La méthode déplace l'objet récent à l'avant de la file d'attente.

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) et put(Object key, Object value) les appels de méthode ci-dessus moveToFront méthode.

Une autre pensée, et même une simple mise en œuvre à l'aide de LinkedHashMap collection de Java.

LinkedHashMap méthode fournie removeEldestEntry et qui peut être remplacée dans la manière citée en exemple. Par défaut, la mise en œuvre de cette structure de collecte est faux. Si c'est vrai et la taille de cette structure va au-delà de la capacité initiale de l'aîné ou plus éléments seront supprimés.

Nous pouvons avoir une pageno et le contenu de la page dans mon cas pageno est entier et au contenu de la page j'ai gardé le numéro de page des valeurs de chaîne.

import java.util.LinkedHashMap;
import java.util.Map;
/**
* @author Deepak Singhvi
*
*/
public class LRUCacheUsingLinkedHashMap {
private static int CACHE_SIZE = 3;
public static void main(String[] args) {
System.out.println(" Pages for consideration : 2, 1, 0, 2, 8, 2, 4,99");
System.out.println("----------------------------------------------\n");
//accessOrder is true, so whenever any page gets changed or accessed,    //its order will change in the map, 
LinkedHashMap<Integer,String> lruCache = new              
LinkedHashMap<Integer,String>(CACHE_SIZE, .75F, true) {
private static final long serialVersionUID = 1L;
protected boolean removeEldestEntry(Map.Entry<Integer,String>                           
eldest) {
return size() > CACHE_SIZE;
}
};
lruCache.put(2, "2");
lruCache.put(1, "1");
lruCache.put(0, "0");
System.out.println(lruCache + "  , After first 3 pages in cache");
lruCache.put(2, "2");
System.out.println(lruCache + "  , Page 2 became the latest page in the cache");
lruCache.put(8, "8");
System.out.println(lruCache + "  , Adding page 8, which removes eldest element 2 ");
lruCache.put(2, "2");
System.out.println(lruCache+ "  , Page 2 became the latest page in the cache");
lruCache.put(4, "4");
System.out.println(lruCache+ "  , Adding page 4, which removes eldest element 1 ");
lruCache.put(99, "99");
System.out.println(lruCache + " , Adding page 99, which removes eldest element 8 ");
}
}

Suite de ci-dessus exécution de code est comme suit:

 Pages for consideration : 2, 1, 0, 2, 8, 2, 4,99
--------------------------------------------------
{2=2, 1=1, 0=0}  , After first 3 pages in cache
{2=2, 1=1, 0=0}  , Page 2 became the latest page in the cache
{1=1, 0=0, 8=8}  , Adding page 8, which removes eldest element 2 
{0=0, 8=8, 2=2}  , Page 2 became the latest page in the cache
{8=8, 2=2, 4=4}  , Adding page 4, which removes eldest element 1 
{2=2, 4=4, 99=99} , Adding page 99, which removes eldest element 8 

Android offre une mise en œuvre d'un Cache LRU. Le code est propre et simple.