Java LRU (최근에 사용되지 않은) 상세한 설명
LRU는 최근에 사용 된 최소한의 약어입니다. "최신 용도"로 번역됩니다. LRU 캐시는이 원리를 사용하여 구현됩니다. 간단히 말해서, 일정량의 데이터를 캐시하는 것입니다. 설정 임계 값이 초과되면 일부 만료 된 데이터가 삭제됩니다. 예를 들어, 우리는 10,000 개의 데이터를 캐시합니다. 데이터가 10,000 미만인 경우 마음대로 추가 할 수 있습니다. 10,000을 초과하면 새 데이터를 추가해야합니다. 동시에 만료 된 데이터를 삭제하려면 최대 10,000 개의 데이터를 캐시 할 수 있는지 확인해야합니다. 삭제할 만료 된 데이터를 결정하는 방법은 무엇입니까? LRU 알고리즘을 사용하여 구현하면 가장 오래된 데이터가 삭제됩니다. 말할 것도없이 LRU 캐시 구현의 Java 버전에 대해 이야기 해 봅시다.
Java에는 LRU 캐시를 구현하기위한 두 가지 옵션이 있습니다. 하나는 LinkedHashMap을 사용하고 다른 하나는 자신의 데이터 구조를 설계하고 Linked List + Hashmap을 사용하는 것입니다.
LRU 캐시의 LinkedHashMap 구현
LinkedHashMap 자체는 순차적 스토리지를 구현했습니다. 기본적으로 요소 추가 순서로 저장됩니다. 또한 액세스 순서대로 저장할 수 있습니다. 즉, 최근에 읽은 데이터는 전면에 배치되고 최초의 읽기 데이터는 끝에 배치됩니다. 그런 다음 가장 오래된 데이터를 삭제할지 여부를 결정하는 방법도 있습니다. 기본값은 false, 즉 데이터를 삭제하는 것이 아닙니다. LRU 캐시를 구현하기 위해 LinkedHashMap을 사용하는 방법은 LinkedHashMap의 간단한 확장을 구현하는 것입니다. 확장하는 두 가지 방법이 있습니다. 하나는 상속이며 다른 하나는 대표단입니다. 특정 방법은 개인 선호도에 의존하는 데 사용됩니다.
// LinkedHashmap의 생성자. 매개 변수 accessorder가 true 일 때 액세스 순서대로 정렬됩니다. 가장 최근의 액세스가 먼저 배치되며 최초의 액세스는 공개 LinkedHashMap (Int InitialCapacity, Float Loadfactor, Boolean AccessOrder) {Super (InitialCapacity, Loadfactor); this.accessorder = accessorder;} // linkedhashmap에는 가장 오래된 요소를 삭제할지 여부를 결정하는 메소드가 제공됩니다. 기본적으로 False를 반환합니다. 즉, 이전 데이터를 삭제하지 않습니다. // 우리가해야 할 일은 특정 조건을 보호 할 때이 메소드를 다시 작성하고 이전 데이터를 삭제하는 것입니다. LRU 캐시 LinkedHashmap (상속) 구현
상속 방법은 구현하기가 비교적 간단하며 MAP 인터페이스가 구현됩니다. 다중 스레드 환경을 사용하는 경우 Collection.synchronizedMap () 메소드를 사용하여 스레드 안전 작업을 구현할 수 있습니다.
패키지 cn.lzrabbit.structure.lru; import java.util.linkedhashmap; import java.util.map;/*** liuzhao가 14-5-15에 생성했습니다. */public class lrucache2 <k, v>는 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 = 캐시 크기; } @override protected boolean removeeldestry (map.entry 노인) {return size ()> max_cache_size; } @override public String toString () {StringBuilder sb = new StringBuilder (); for (map.Entry <k, v> entry : entryset ()) {sb.append (string.format ( "%s :%s", entery.getKey (), enther.getValue ())); } return sb.toString (); }}이것은 비교적 표준 구현입니다. 실제로 사용하면 이와 같이 글을 쓰는 것은 여전히 약간 번거 롭습니다. 이보다 실용적인 방법처럼 글을 쓸 때 수업을 따로 보는 데 어려움이 절약됩니다.
최종 int cachesize = 100; map <string, string> map = new LinkedHashmap <string, string> ((int) math.ceil (cachesize / 0.75f) + 1, 0.75f, true) {@override protected boolean removeeldestry (map.entry <string, string> enlderly) {return size ()> cachesize; }}; LRU 캐시 LinkedHashmap (위임) 구현
대표 방법 구현은 더 우아하지만 MAP 인터페이스가 구현되지 않기 때문에 스레드 동기화를 직접 수행해야합니다.
패키지 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; 개인 최종 플로트 DEFAULT_LOAD_FACTOR = 0.75F; LinkedHashMap <k, v> 맵; public lrucache3 (int cachesize) {max_cache_size = cachesize; // 캐시 크기 및 로딩 계수를 기반으로 해시 맵의 capactiy를 계산합니다. +1 캐시 크기 상한에 도달하면 해시 맵 확장이 트리거되지 않도록하십시오. int 용량 = (int) math.ceil (max_cache_size / default_load_factor) + 1; map = new LinkedHashMap (용량, default_load_factor, true) {@override protected boolean removeEldestry (map.entry 노인) {return size ()> max_cache_size; }}; } public synchronized void put (k key, v value) {map.put (키, 값); } public synchronized v get (k key) {return map.get (키); } public synchronized void remove (k key) {map.remove (키); } public synchronized set <map.entry <k, v >> getAll () {return map.entryset (); } public synchronized int size () {return map.size (); } public synchronized void star () {map.clear (); } @override public String toString () {StringBuilder sb = new StringBuilder (); for (map.entry entry : map.entryset ()) {sb.append (string.format ( "%s :%s", entery.getKey (), entery.getValue ())); } return sb.toString (); }} LRU 캐시의 링크 된 목록 + 해시 맵 구현
참고 :이 구현은 스레드되지 않았습니다. 다중 스레드 환경에서 사용되는 경우 스레드 안전 작업을 달성하기 위해 관련 메소드에 동기화 된 방법을 추가해야합니다.
패키지 cn.lzrabbit.structure.lru; import java.util.hashmap;/*** liuzhao가 14-5-12에 만들었습니다. */public class lrucache1 <k, v> {private final int max_cache_size; 개인 항목 먼저; 개인 입국 마지막; 개인 해시 맵 <k, Entry <k, v >> 해시 맵; public lrucache1 (int cachesize) {max_cache_size = cachesize; HASHMAP = New Hashmap <k, Entry <k, v >> (); } public void put (k key, v value) {Entry Entry = getEntry (키); if (entry == null) {if (hashmap.size ()> = max_cache_size) {hashmap.remove (last.key); removelast (); } entry = 새 항목 (); Entrys.key = 키; } entry.value = value; Movetofirst (Entry); hashmap.put (키, 항목); } public v get (k key) {Entry <k, v> entry = getEntry (키); if (Entry == null) return null; Movetofirst (Entry); reture entry.value; } public void remove (k key) {Entry Entry = GetEntry (키); if (Entry! = null) {if (Entry.pre! = null) Entry.pre.next = Entry.next; if (Entry.Next! = NULL) ENTERTE.NEXT.PRE = ENTER.PRE; if (entry == first) first = actor.next; if (entry == last) last = actor.pre; } hashmap.remove (키); } private void movetofirst (Entry Entry) {if (enther == first) return; if (Entry.pre! = null) Entry.pre.next = Entry.Next; if (Entry.Next! = NULL) ENTERTE.NEXT.PRE = ENTER.PRE; if (entry == last) last = last.pre; if (first == null || last == null) {first = last = entry; 반품; } entry.next = 첫 번째; First.pre = Entry; 첫 번째 = 입력; 첫 번째 = 입력; Entry.pre = null; } private void removelast () {if (last! = null) {last = last.pre; if (last == null) first = null; else last.next = null; }} 개인 항목 <k, v> getEntry (k key) {return hashmap.get (키); } @override public String toString () {StringBuilder sb = new StringBuilder (); 입력 항목 = 첫 번째; while (entry! = null) {sb.append (string.format ( "%s :%s", entery.key, entert.value); Entry = Entry.Next; } return sb.toString (); } 클래스 항목 <k, v> {public entry pre; 다음에 공개 항목; 공개 K 키; 공개 v 값; }} FIFO LinkedHashmap의 구현
FIFO는 첫 번째 입력 첫 출력의 약어이며, 종종 첫 번째 출력이라고합니다. 기본적으로 LinkedHashMap은 추가 순서대로 저장됩니다. FIFO 캐시를 쉽게 구현하려면 removeEldestentry 메소드를 다시 작성하면됩니다. 구현 코드의 단순화 된 버전은 다음과 같습니다.
Final int Cachesize = 5; LinkedHashMap <Integer, String> lru = new LinkedHashMap <Integer, String> () {@Override Protected Boolean removeEldestry (map.Entry <Integer, String> Elderly) {return size ()> Cachesize; }}; 전화 예제
패키지 CN.LZRABBIT.STRUCTURE.LRU; import CN.LZRABBIT.ITEST; import java.util.linkedhashmap; import java.util.map;/*** Liuzhao가 14-5-15에 작성했습니다. */public class lrucachetest {public static void main (String [] args)은 예외 {system.out.println ( "start ..."); lrucache1 (); lrucache2 (); lrucache3 (); lrucache4 (); System.out.println ( "Over ..."); } static void lrucache1 () {system.out.println (); System.out.println ( "=========================== LRU 链表实现 ==============================================="); 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 ( "========================= LRU LinkedHashMap (Delegation) 实现 ====================================== 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 ( "========================== FIFO LinkedHashMap 默认实现 =================================== 최종 int 캐시 크기 = 5; linkedhashmap <integer, string> lru = new LinkedHashMap <integer, string> () {@override Protected Boolean removeEldestry (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 :/program files (x86)/jetbrains/Intellij Idea 13.0.2/bin" -eNcoding = utf -8 -Class " (x86) /java/jdk1.6.0_10/jre/lib/charsets.jar; (x86) /java/jdk1.6.0_10/jre/lib/javaws.jar ;c:/program 파일 (x86) /java/jdk1.6.0_10/jre/lib/jce.jar ;c:/program 파일 (x86)/java/jdk1.6.0_10/jre/lib/jce.jar ;c:/program 파일 (x86) /java/jdk1.6.0_10/jre/lib/management-agent.jar ;c:/program 파일 (x86)/java/jdk1.6.0_10/jre/lib/plugin.jar ;c:/program 파일 (x86) /java/jdk1.6.0_10/jre/lib/resources.jar ;c:/program 파일 (x86)/java/jdk1.6.0_10/jre/lib/rt.jar ;c:/program 파일 (x86) /java/jdk1.6.0_10/jre/ext/dnsns.jar ;c:/program 파일 (x86)/java/jdk1.6.0_10/jre/ext/localedata.jar ;c:/program files (x86) /java/jdk1.6.0_10/jre/ext/sunjce_provider.jar;c:/program 파일 (x86) /java/jdk1.6.0_10/jre/lib/ext/sunmscapi.jar ;c:/program 파일 (x86)/java/jdk1.6.0_10/jre/lib/ext/sunpkcs11.jar ;d:/svn/projects/java/java.algorithm/target/testclasses ;d:/svn/projects/java/java.algorithm/targets//targetse (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 5:11 6:66 2:11 7:77 4:11 ============================= FIFO LinkedHashMap 기본값 구현 ======================================================== {1 = 11, 2 = 11, 3 = 11, 4 = 11, 5 = 11} {3 = 11, 4 = 11, 5 = 11, 66, 7 = 7 = 7 = 77}.읽어 주셔서 감사합니다. 도움이되기를 바랍니다. 이 사이트를 지원 해주셔서 감사합니다!