Недавно я наткнулся на один из вопросов интервью Java:
«Реализовать кэш списка недавно использованных (LRU) классов Java?»
Если вы уже работали над подобной проблемой, то это действительно легко для вас. В противном случае вы начинаете думать о лучшем классе коллекции для реализации кеша LRU. Большинство людей не понимают, что LinkedHashMap обеспечивает поддержку и может использоваться самостоятельно с минимальным кодом.
Что такое наименьший недавно использованный (LRU) кэш
Если вы знаете эту концепцию, перейдите к разделу реализации. Существуют разные алгоритмы, используемые в кешировании элементов. Самым популярным является наименее недавно использованный. Кэш всегда имеет ограниченную память и может содержать только ограниченное количество элементов. Он использует алгоритм для обнаружения и выселения предметов, которые не заслуживают хранения. Исследования показывают, что новые предметы, скорее всего, будут доступны в ближайшее время по сравнению со старыми предметами. LRU основан на этом наблюдении. Алгоритм отслеживает время последнего обращения к элементам. Он выселяет предметы, которые имеют самую старую временную метку доступа.
Реализация LRU Cache
LinkedHashMap действительно полезен, если вы хотите реализовать LRU Cache. Даже Sun Java Framework использует этот класс для реализации com.sun.tdk.signaturetest.util.LRUCache и sun.security.ssl.X509KeyManagerImpl.SizedMap .
Для реализации метод removeEldestEntry() должен быть переопределен. Этот метод putAll() после put() и putAll() . На основе его возвращаемого значения Map удаляет старую запись. Если этот метод возвращает true , тогда старая запись удаляется. В противном случае он может остаться на Map . Реализация по умолчанию этого метода возвращает false . В этом случае старые записи остаются на карте и никогда не удаляются; Он просто действует как общий класс коллекции Map .
В большинстве реализаций этот метод возвращает значение true , если количество записей на карте превышает начальную емкость.
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
package code4reference.test;import java.util.LinkedHashMap;import java.util.Map;public class LRUCacheImpl extends LinkedHashMap<Integer, String> { private static final long serialVersionUID = 1L; private int capacity; public LRUCacheImpl(int capacity, float loadFactor){ super(capacity, loadFactor, true); this.capacity = capacity; } /** * removeEldestEntry() should be overridden by the user, otherwise it will not * remove the oldest object from the Map. */ @Override protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest){ return size() > this.capacity; } public static void main(String arg[]){ LRUCacheImpl lruCache = new LRUCacheImpl(4, 0.75f); lruCache.put(1, "Object1"); lruCache.put(2, "Object2"); lruCache.put(3, "Object3"); lruCache.get(1); lruCache.put(4, "Object4"); System.out.println(lruCache); lruCache.put(5, "Object5"); lruCache.get(3); lruCache.put(6, "Object6"); System.out.println(lruCache); lruCache.get(4); lruCache.put(7, "Object7"); lruCache.put(8, "Object8"); System.out.println(lruCache); }} |
Метод println() печатает объекты в порядке их устаревания. Как вы можете видеть в приведенном выше коде, Object1, Object2 и Object3 вставляются и к object1 обращаются непосредственно перед вставкой Object4, и, следовательно, Object1 печатается перед object4 в первой строке вывода. Когда Object5 вставлен, Object2 удаляется из списка, потому что этот объект является самым старым в списке. Когда к object3 обращаются, он продвигается выше, чем object5, и когда object6 вставляется, Object1 выселяется. Остальные результаты говорят сами за себя, надеюсь, вы не найдете трудностей в понимании результатов.
|
1
2
3
|
{2=Object2, 3=Object3, 1=Object1, 4=Object4}{4=Object4, 5=Object5, 3=Object3, 6=Object6}{6=Object6, 4=Object4, 7=Object7, 8=Object8} |
| Ссылка: | Недавно использованная реализация Code4ReferenceList (LRU) с использованием LinkedHashMap от нашего партнера по JCG Ракеша Кусата в блоге Code4Reference . |