Как бы вы реализовали LRU-кеш в Java? - PullRequest
Новая
       130

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

161 голосов
/ 21 октября 2008

Пожалуйста, не говорите EHCache или OSCache и т. Д. Предположим, что для целей этого вопроса я хочу реализовать свой собственный, используя только SDK (обучение на практике). Учитывая, что кеш будет использоваться в многопоточной среде, какие структуры данных вы бы использовали? Я уже реализовал один, используя LinkedHashMap и Collections # synchronizedMap , но мне любопытно, будут ли какие-либо из новых параллельных коллекций более подходящими кандидатами.

ОБНОВЛЕНИЕ: я только что прочитал последние Yegge, когда я нашел этот самородок:

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

Прежде чем перейти к реализации LinkedHashMap + Collections#synchronizedMap, о которой я упоминал выше, я думал почти об одном и том же. Приятно осознавать, что я что-то не заметил.

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

Ответы [ 21 ]

0 голосов
/ 25 апреля 2013

Еще одна мысль и даже простая реализация, использующая коллекцию Java LinkedHashMap.

LinkedHashMap предоставляет метод removeEldestEntry, который можно переопределить способом, упомянутым в примере. По умолчанию реализация этой структуры коллекции ложна. Если его истинное значение и размер этой структуры выходят за пределы начальной емкости, то старые или более старые элементы будут удалены.

У нас может быть pageno и содержимое страницы, в моем случае pageno является целым числом и содержанием страницы. Я сохранил строку значений номера страницы. 

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 ");

     }

}

Результат выполнения вышеуказанного кода выглядит следующим образом: 

 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
Страница:
...