Java LRU (наименьшее недавно) подробное объяснение
LRU - это аббревиатура наименее недавно используемых. Это переводится как «последнее использование». Кэш LRU реализуется с использованием этого принципа. Проще говоря, это для кэширования определенного количества данных. При превышении установленного порога, некоторые истекшие данные будут удалены. Например, мы кэшируем 10 000 фрагментов данных. Когда данные составляют менее 10000, вы можете добавить их по желанию. Когда он превышает 10000, вам необходимо добавить новые данные. В то же время вам необходимо удалить истекшие данные, чтобы убедиться, что мы можем кэшировать 10 000 кусков данных с максимумом. Как определить, какие срок действия данных для удаления? Если вы используете алгоритм LRU для его реализации, вы удалите самые старые данные. Не говоря уже много, давайте поговорим о Java версии реализации LRU Cache.
Обычно есть два варианта реализации кэша LRU в Java. Одним из них является использование LinkedHashmap, а другой - разработать вашу собственную структуру данных и использовать связанный список + Hashmap.
Реализация LinkedHashmap Cache LRU
Сам LinkedHashmap реализовал последовательное хранилище. По умолчанию он хранится в порядке добавления элементов. Он также может включить хранилище в порядке доступа, то есть недавние данные считывания размещаются спереди, а самые ранние данные чтения размещаются в конце. Затем он также имеет метод, чтобы определить, следует ли удалить самые старые данные. По умолчанию является возвращение false, то есть не удалять данные. Метод использования LinkedHashmap для реализации кэша LRU заключается в реализации простого расширения LinkedHashmap. Есть два способа расширения, один из них наследуется, а другой - делегирование. Конкретный метод используется для зависимости от личных предпочтений.
// конструктор LinkedHashmap. Когда параметр Доступ верна, он будет отсортирован в порядке доступа. Самый последний доступ помещен в первую очередь, и самый ранний доступ находится за публичным LinkedHashmap (int initialCapacity, Float LoadFactor, Boolean Accesrord) {Super (initialCapacity, LoadFactor); this.accessorder = accessord;} // LinkedHashmap поставляется с методом, чтобы определить, удалить ли самый старый элемент. По умолчанию он возвращает false, то есть не удаляет старые данные. // Что нам нужно сделать, так это переписать этот метод и удалить старые данные, когда выполнены определенные условия защищенные Реализация LRU Cache LinkedHashmap (наследование)
Метод наследования относительно прост в реализации, а интерфейс карты реализован. При использовании многопоточной среды вы можете использовать метод collections.synchronizedmap () для реализации безопасных потоков операций.
Пакет cn.lzrabbit.structure.lru; import java.util.linkedhashmap; импорт java.util.map;/***, созданный Liuzhao на 14-5-15. */public class lrucache2 <k, v> extends linkedhashmap <k, v> {private final int max_cache_size; public lrucache2 (int cachesize) {super ((int) math.ceil (cachesize / 0,75) + 1, 0,75f, true); Max_cache_size = cachesize; } @Override Protected Boolean removeEldestentry (map.Entry пожилой) {return size ()> max_cache_size; } @Override public String toString () {stringBuilder sb = new StringBuilder (); for (map.Entry <K, v> inpit: intrySet ()) {sb.Append (string.format ("%s:%s", entry.getKey (), intry.getValue ())); } вернуть sb.toString (); }}Это относительно стандартная реализация. Это все еще немного громоздко писать так в реальном использовании. При написании этого более практического метода он спасает неприятности увидеть класс отдельно.
final int cachesize = 100; map <string, string> map = new LinkedHashmap <String, String> ((int) math.ceil (cachesize / 0,75f) + 1, 0,75f, true) {@Override защищенное boolean removeEldestentry (map.Entry <String, String> Olderle) {return ()>> cachesize; }}; Реализация LRU Cache LinkedHashmap (делегирование)
Реализация метода делегирования является более элегантной, но, поскольку интерфейс карты не реализован, синхронизация потоков должна быть выполнена самостоятельно.
Пакет cn.lzrabbit.structure.lru; import java.util.linkedhashmap; import java.util.map; import java.util.set;/*** Создан Люжао на 14-5-13. */public class lrucache3 <k, v> {private final int max_cache_size; private final float default_load_factor = 0,75F; LinkedHashmap <K, V> Map; public lrucache3 (int cachesize) {max_cache_size = cachesize; // Рассчитайте капциплин HashMap на основе коэффициентов кэширования и загрузки. +1 Убедитесь, что расширение HashMAP не будет вызвано при достижении верхнего предела кэширования. int емкость = (int) math.ceil (max_cache_size / default_load_factor) + 1; map = new LinkedHashmap (емкость, default_load_factor, true) {@Override Protected Boolean RemodEldEStentry (map.Entry Olderly) {return size ()> max_cache_size; }}; } public Synchronized void put (k -ключ, v value) {map.put (key, value); } public synchronized v get (k key) {return map.get (key); } public Synchronized void remove (k key) {map.remove (key); } public Synchronized Set <Map.Entry <K, v >> getAll () {return map.enterSet (); } public synchronized int size () {return map.size (); } public synchronized void clear () {map.clear (); } @Override public String toString () {stringBuilder sb = new StringBuilder (); for (map.Entry intry: map.EntrySet ()) {sb.Append (string.format ("%s:%s", entry.getKey (), intry.getValue ())); } вернуть sb.toString (); }} Связанный список LRU Cache + реализация HashMap
Примечание: эта реализация не читается. При использовании в многопоточной среде вам необходимо добавить синхронизированные к соответствующим методам для достижения безопасных потоков операций.
Пакет cn.lzrabbit.structure.lru; import java.util.hashmap;/*** Создан Люжао на 14-5-12. */public class lrucache1 <k, v> {private final int max_cache_size; частная запись в первую очередь; частная запись в последнюю очередь; Частный Hashmap <K, intry <K, v >> HashMap; public lrucache1 (int cachesize) {max_cache_size = cachesize; hashmap = new hashmap <K, intry <K, v >> (); } public void put (k key, v value) {intpring = getEntry (key); if (inpit == null) {if (hashmap.size ()> = max_cache_size) {hashmap.remove (last.key); removeLast (); } entry = new entry (); intry.key = key; } inpit.value = value; MovetoFirst (intport); hashmap.put (ключ, запись); } public v get (k key) {intry <k, v> entry = getEntry (key); if (inpit == null) return null; MovetoFirst (intport); return entry.value; } public void remove (k key) {inpit intry = getEntry (key); if (inpit! = null) {if (entry.pre! = null) entry.pre.next = intry.next; if (entry.next! = null) entry.next.pre = entry.pre; if (inpit == First) First = intry.Next; if (inpit == последний) last = intry.pre; } hashmap.remove (key); } private void movetoFirst (запись в записи) {if (entry == First) return; if (entry.pre! = null) entry.pre.next = entry.next; if (entry.next! = null) entry.next.pre = entry.pre; if (inpit == последний) последний = last.pre; if (first == null || last == null) {first = last = intry; возвращаться; } entry.next = First; first.pre = intry; First = intry; First = intry; intry.pre = null; } private void removelast () {if (last! = null) {last = last.pre; if (last == null) First = null; еще последний. next = null; }} частная запись <K, v> getEntry (k key) {return hashmap.get (key); } @Override public String toString () {stringBuilder sb = new StringBuilder (); Запись в записи = первое; while (intry! = null) {sb.append (string.format ("%s:%s", entry.key, intry.value)); intry = entry.next; } вернуть sb.toString (); } запись в классе <K, V> {public inpit pre; Публичная запись Далее; Public K Key; Общественное V ценность; }} Реализация FIFO LinkedHashmap
FIFO-это аббревиатура первого входа первого вывода, который часто называют первым в первом. По умолчанию LinkedHashmap сохраняется в порядке сложения. Нам просто нужно переписать метод RemoveLdestEntestEntry, чтобы легко реализовать кэш FIFO. Упрощенная версия кода реализации заключается в следующем.
final int cachesize = 5; LinkedHashmap <Integer, String> lru = new LinkedHashmap <Integer, String> () {@Override защищенная логическая lementEldestentry (map.entry <integer, string> пожилые люди) {return size ()> cachesize; }}; Пример вызови
пакет cn.lzrabbit.structure.lru; import cn.lzrabbit.itest; импорт java.util.linkedhashmap; импорт java.util.map;/*** Создан Люжао на 14-5-15. */public class lrucachetest {public static void main (string [] args) бросает exection {System.out.println ("start ..."); lrucache1 (); lrucache2 (); lrucache3 (); lrucache4 (); System.out.println ("Over ..."); } static void lrucache1 () {System.out.println (); System.out.println ("======================================================================= Lrucache1 <integer, string> lru = new lrucache1 (5); lru.put (1, "11"); lru.put (2, "11"); lru.put (3, "11"); lru.put (4, "11"); lru.put (5, "11"); System.out.println (lru.toString ()); lru.put (6, "66"); lru.get (2); lru.put (7, "77"); lru.get (4); System.out.println (lru.toString ()); System.out.println (); } static <t> void lrucache2 () {System.out.println (); System.out.println ("========================================================================== ======================================================================================== LinkedHashmap (наследование) 实现 =============================================================== Lrucache2 <integer, string> lru = new lrucache2 (5); lru.put (1, "11"); lru.put (2, "11"); lru.put (3, "11"); lru.put (4, "11"); lru.put (5, "11"); System.out.println (lru.toString ()); lru.put (6, "66"); lru.get (2); lru.put (7, "77"); lru.get (4); System.out.println (lru.toString ()); System.out.println (); } static void lrucache3 () {System.out.println (); System.out.println ("================================================================================== Lrucache3 <integer, string> lru = new lrucache3 (5); lru.put (1, "11"); lru.put (2, "11"); lru.put (3, "11"); lru.put (4, "11"); lru.put (5, "11"); System.out.println (lru.toString ()); lru.put (6, "66"); lru.get (2); lru.put (7, "77"); lru.get (4); System.out.println (lru.toString ()); System.out.println (); } static void lrucache4 () {System.out.println (); System.out.println ("============================================================================================= окончательный int cachesize = 5; LinkedHashmap <Integer, String> lru = new LinkedHashmap <Integer, String> () {@Override Protected Boolean RemodelEldestentry (map.Entry <Integer, String> Eldest) {return size ()> cachesize; }}; lru.put (1, "11"); lru.put (2, "11"); lru.put (3, "11"); lru.put (4, "11"); lru.put (5, "11"); System.out.println (lru.toString ()); lru.put (6, "66"); lru.get (2); lru.put (7, "77"); lru.get (4); System.out.println (lru.toString ()); System.out.println (); }}Результаты бега
"C:/Program Files (x86) /java/jdk1.6.0_10/bin/java" -didea.launcher.port = 7535 "-didea.launcher.bin.path = c:/программа файлов (x86)/jetbrains/intellij Idea 13.0.2/bin". "C:/Program Files (x86) /java/jdk1.6.0_10/jre/lib/charsets.jar;c://program files (x86) /java/jdk1.6.0_10/jre/lib/deploy.jar ;c:/program files (x86) /java/jdk1.6.0_10/jre/lib/javaws.jar;c://program files (x86) /java/jdk1.6.0_10/jre/lib/jce.jar;c://program files (x86) /java/jdk1.6.0_10/jre/lib/jce.jar;c://program files (x86) /java/jdk1.6.0_10/jre/lib/management-agent.jar;c://program files (x86) /java/jdk1.6.0_10/jre/lib/plugin.jar;c://program files (x86) /java/jdk1.6.0_10/jre/lib/resources.jar;c://program files (x86) /java/jdk1.6.0_10/jre/lib/rt.jar;c://program files (x86) /java/jdk1.6.0_10/jre/ext/dnsns.jar;c://program files (x86) /java/jdk1.6.0_10/jre/ext/localedata.jar;c://program files (x86) /java/jdk1.6.0_10/jre/lib/ext/sunjce_provider.jar;c://program files (x86) /java/jdk1.6.0_10/jre/lib/ext/sunmscapi.jar;c://program files (x86) /java/jdk1.6.0_10/jre/lib/ext/sunpkcs11.jar;d:/svn/projects/java/java.algorithm/target/test-class ;d:/svn/projects/java/java.algorits;d:/svn/projects/java/java.algorses; (x86)/jetbrains/intellij Idea 13.0.2/lib/idea_rt.jar "com.intellij.rt.execution.application.appmain Mainstart ... ====================================================================================================== ============================================================================================================= ======================================================================================================== ============================================================================================================= LinkedHashmap (наследование) Реализация ================================================================== ============================================================================ =========================================================================== ============================================================================ 1:11 2:11 3:11 4:11 5:11 5:11 6:66 2:11 7:77 4:11 ================================================ Реализация ==================================================================================================================
Спасибо за чтение, я надеюсь, что это поможет вам. Спасибо за поддержку этого сайта!