Java Lru (ใช้อย่างน้อยเมื่อเร็ว ๆ นี้) คำอธิบายโดยละเอียด
LRU เป็นตัวย่อที่ใช้อย่างน้อยเมื่อเร็ว ๆ นี้ มันแปลว่า "การใช้งานล่าสุด" แคช LRU ถูกนำมาใช้โดยใช้หลักการนี้ พูดง่ายๆคือการแคชข้อมูลจำนวนหนึ่ง เมื่อเกินเกณฑ์ชุดข้อมูลที่หมดอายุจะถูกลบ ตัวอย่างเช่นเราแคชข้อมูล 10,000 ชิ้น เมื่อข้อมูลน้อยกว่า 10,000 คุณสามารถเพิ่มได้ตามต้องการ เมื่อเกิน 10,000 คุณต้องเพิ่มข้อมูลใหม่ ในเวลาเดียวกันคุณต้องลบข้อมูลที่หมดอายุเพื่อให้แน่ใจว่าเราสามารถแคชข้อมูล 10,000 ชิ้นได้สูงสุด จะกำหนดข้อมูลที่หมดอายุได้อย่างไร หากคุณใช้อัลกอริทึม LRU เพื่อใช้งานคุณจะลบข้อมูลที่เก่าแก่ที่สุด โดยไม่พูดอะไรมากเรามาพูดถึงการใช้งาน LRU Cache เวอร์ชัน Java
โดยปกติจะมีสองตัวเลือกสำหรับการใช้แคช LRU ใน Java หนึ่งคือการใช้ LinkedHashMap และอื่น ๆ คือการออกแบบโครงสร้างข้อมูลของคุณเองและใช้รายการที่เชื่อมโยง + HashMap
การใช้งาน LinkedHashMap ของ LRU Cache
LinkedHashMap เองได้ใช้ที่เก็บข้อมูลตามลำดับ โดยค่าเริ่มต้นจะถูกเก็บไว้ในลำดับของการเพิ่มองค์ประกอบ นอกจากนี้ยังสามารถเปิดใช้งานการจัดเก็บตามลำดับการเข้าถึงนั่นคือข้อมูลที่อ่านเมื่อเร็ว ๆ นี้จะถูกวางไว้ที่ด้านหน้าและข้อมูลการอ่านที่เร็วที่สุดจะถูกวางไว้ในตอนท้าย จากนั้นก็มีวิธีการตรวจสอบว่าจะลบข้อมูลที่เก่าแก่ที่สุดหรือไม่ ค่าเริ่มต้นคือการส่งคืน FALSE นั่นคือไม่ใช่ลบข้อมูล วิธีการใช้ LinkedHashMap เพื่อใช้ Cache LRU คือการใช้การขยายตัวของ LinkedHashMap อย่างง่าย มีสองวิธีในการขยายหนึ่งคือมรดกและอีกวิธีหนึ่งคือการมอบหมาย วิธีการเฉพาะนั้นใช้เพื่อขึ้นอยู่กับการตั้งค่าส่วนบุคคล
// ตัวสร้างของ LinkedHashMap เมื่อพารามิเตอร์ accessorder เป็นจริงมันจะถูกจัดเรียงตามลำดับของการเข้าถึง การเข้าถึงล่าสุดถูกวางไว้ก่อนและการเข้าถึงที่เร็วที่สุดจะอยู่ด้านหลัง Public LinkedHashMap (int initialcapacity, float loadfactor, boolean accessorder) {super (initialcapacity, loadfactor); this.accessOrder = AccessOrder;} // LinkedHashMap มาพร้อมกับวิธีการตรวจสอบว่าจะลบองค์ประกอบที่เก่าแก่ที่สุดหรือไม่ มันส่งคืนเท็จโดยค่าเริ่มต้นนั่นคือมันไม่ได้ลบข้อมูลเก่า // สิ่งที่เราต้องทำคือเขียนวิธีนี้ใหม่และลบข้อมูลเก่าเมื่อเงื่อนไขบางอย่างได้รับการป้องกันบูลีน removeldestentry (map.entry <k, v> eldest) {return false;} LRU Cache LinkedHashMap (การสืบทอด) การใช้งาน
วิธีการสืบทอดนั้นค่อนข้างง่ายต่อการใช้งานและใช้อินเทอร์เฟซ MAP เมื่อใช้สภาพแวดล้อมแบบมัลติเธรดคุณสามารถใช้วิธีการรวบรวม SynchronizedMap () เพื่อใช้งานการทำงานของเธรดที่ปลอดภัย
แพ็คเกจ cn.lzrabbit.structure.lru; นำเข้า java.util.linkedhashmap; นำเข้า java.util.map;/*** สร้างโดย liuzhao เมื่อวันที่ 14-5-15 */คลาสสาธารณะ lrucache2 <k, v> ขยาย linkedhashmap <k, v> {ส่วนตัวสุดท้าย int max_cache_size; สาธารณะ lrucache2 (int cachesize) {super ((int) math.ceil (cachesize / 0.75) + 1, 0.75f, true); max_cache_size = cachesize; } @Override boolean ที่ได้รับการป้องกัน removeEldestentry (map.entry ผู้สูงอายุ) {return size ()> max_cache_size; } @Override สตริงสาธารณะ toString () {StringBuilder sb = new StringBuilder (); สำหรับ (map.entry <k, v> รายการ: entryset ()) {sb.append (string.format ("%s:%s", entry.getKey (), entry.getValue ())); } return sb.toString (); -นี่คือการใช้งานที่ค่อนข้างมาตรฐาน มันยังค่อนข้างยุ่งยากในการเขียนแบบนี้ในการใช้งานจริง เมื่อเขียนแบบนี้เป็นวิธีที่ใช้งานได้จริงมันจะช่วยประหยัดปัญหาในการดูชั้นเรียนแยกต่างหาก
int int สุดท้าย cachesize = 100; แผนที่ <สตริง, สตริง> แผนที่ = ใหม่ linkedHashMap <สตริง, สตริง> ((int) math.ceil (cachesize / 0.75f) + 1, 0.75f, true) {@Override protected boolean removeeldestentry (map.entry <string, string - LRU Cache LinkedHashMap (การมอบหมาย) การใช้งาน
การใช้วิธีการมอบหมายนั้นมีความสง่างามมากขึ้น แต่เนื่องจากอินเทอร์เฟซ MAP ไม่ได้ถูกนำมาใช้การซิงโครไนซ์เธรดจึงจำเป็นต้องทำด้วยตัวเอง
แพ็คเกจ cn.lzrabbit.structure.lru; นำเข้า java.util.linkedhashmap; นำเข้า java.util.map; นำเข้า java.util.set;/*** สร้างโดย liuzhao เมื่อวันที่ 14-5-13 */คลาสสาธารณะ lrucache3 <k, v> {ส่วนตัวสุดท้าย int max_cache_size; Private Final Float default_load_factor = 0.75f; LinkedHashMap <K, V> MAP; public lrucache3 (int cachesize) {max_cache_size = cachesize; // คำนวณ capactiy ของ hashmap ตามปัจจัยแคชและการโหลด +1 ตรวจสอบให้แน่ใจว่าการขยาย HashMap จะไม่ถูกเรียกใช้เมื่อถึงขีด จำกัด สูงสุดของแคช ความจุ int = (int) math.ceil (max_cache_size / default_load_factor) + 1; MAP = ใหม่ linkedHashMap (ความจุ, default_load_factor, true) {@Override boolean protected removeEldestentry (map.entry ผู้สูงอายุ) {return size ()> max_cache_size; - } โมฆะที่ซิงโครไนซ์สาธารณะ put (k คีย์, v ค่า V) {map.put (คีย์, ค่า); } public synchronized v get (k key) {return map.get (key); } โมฆะที่ซิงโครไนซ์สาธารณะลบ (k key) {map.remove (คีย์); } ชุดที่ซิงโครไนซ์สาธารณะ <map.entry <k, v >> getall () {return map.entryset (); } ขนาด int ที่ซิงโครไนซ์สาธารณะ () {return map.size (); } โมฆะที่ซิงโครไนซ์สาธารณะ Clear () {map.clear (); } @Override สตริงสาธารณะ toString () {StringBuilder sb = new StringBuilder (); สำหรับ (map.entry entry: map.entryset ()) {sb.append (string.format ("%s:%s", entry.getKey (), entry.getValue ())); } return sb.toString (); - การใช้งานรายการที่เชื่อมโยง + HashMap ของ LRU Cache
หมายเหตุ: การใช้งานนี้ไม่ใช่เธรด หากใช้ในสภาพแวดล้อมแบบมัลติเธรดคุณจะต้องเพิ่มวิธีการซิงโครไนซ์กับวิธีการที่เกี่ยวข้องเพื่อให้ได้การดำเนินการที่ปลอดภัยจากเธรด
แพ็คเกจ cn.lzrabbit.structure.lru; นำเข้า java.util.hashmap;/*** สร้างโดย liuzhao เมื่อวันที่ 14-5-12 */คลาสสาธารณะ lrucache1 <k, v> {ส่วนตัวสุดท้าย int max_cache_size; รายการส่วนตัวก่อน; รายการส่วนตัวสุดท้าย; hashmap ส่วนตัว <k, entry <k, v >> hashmap; สาธารณะ lrucache1 (int cachesize) {max_cache_size = cachesize; hashmap = new hashmap <k, entry <k, v >> (); } โมฆะสาธารณะใส่ (k คีย์, ค่า V) {รายการรายการ = getEntry (คีย์); if (entry == null) {if (hashmap.size ()> = max_cache_size) {hashmap.remove (last.key); Removelast (); } รายการ = รายการใหม่ (); entry.key = key; } entry.value = value; Movetofirst (รายการ); hashmap.put (คีย์, รายการ); } สาธารณะ v get (k key) {entry <k, v> entry = getEntry (คีย์); if (entry == null) return null; Movetofirst (รายการ); return entry.value; } โมฆะสาธารณะลบ (ปุ่ม k) {รายการรายการ = getEntry (คีย์); if (entry! = null) {ถ้า (entry.pre! = null) entry.pre.next = entry.next; if (entry.next! = null) entry.next.pre = entry.pre; if (entry == ก่อน) first = entry.next; if (entry == สุดท้าย) สุดท้าย = entry.pre; } hashmap.remove (คีย์); } โมฆะส่วนตัว movetofirst (รายการรายการ) {if (entry == ก่อน) return; if (entry.pre! = null) entry.pre.next = entry.next; if (entry.next! = null) entry.next.pre = entry.pre; if (entry == สุดท้าย) last = last.pre; if (first == null || last == null) {first = last = entry; กลับ; } entry.next = ก่อน; First.pre = รายการ; ครั้งแรก = รายการ; ครั้งแรก = รายการ; entry.pre = null; } โมฆะส่วนตัว removelast () {ถ้า (สุดท้าย! = null) {last = last.pre; if (last == null) first = null; else last.next = null; }} รายการส่วนตัว <k, v> getEntry (k key) {return hashmap.get (คีย์); } @Override สตริงสาธารณะ toString () {StringBuilder sb = new StringBuilder (); รายการรายการ = ก่อน; ในขณะที่ (รายการ! = null) {sb.append (string.format ("%s:%s", entry.key, entry.value)); รายการ = entry.next; } return sb.toString (); } รายการคลาส <k, v> {รายการสาธารณะก่อน; รายการสาธารณะถัดไป; กุญแจ K สาธารณะ; มูลค่า V สาธารณะ; - การใช้งาน FIFO ของ LinkedHashMap
FIFO เป็นตัวย่อของอินพุตแรกเอาต์พุตแรกซึ่งมักเรียกว่าครั้งแรกในอันดับแรก โดยค่าเริ่มต้น LinkedHashMap จะถูกบันทึกไว้ในลำดับของการเพิ่ม เราเพียงแค่ต้องเขียนวิธี removeeldestentry ใหม่เพื่อใช้แคช FIFO ได้อย่างง่ายดาย รหัสการใช้งานเวอร์ชันที่ง่ายขึ้นมีดังนี้
int int สุดท้าย cachesize = 5; linkedHashMap <จำนวนเต็ม, สตริง> lru = ใหม่ linkedHashMap <จำนวนเต็ม, สตริง> () {@Override boolean ป้องกัน remvereldestentry (map.entry <จำนวนเต็ม, สตริง> ผู้สูงอายุ) {ขนาดคืน ()> cachesize; - ตัวอย่างการโทร
แพ็คเกจ cn.lzrabbit.structure.lru; นำเข้า cn.lzrabbit.itest; นำเข้า java.util.linkedhashmap; นำเข้า java.util.map;/*** สร้างโดย liuzhao เมื่อวันที่ 14-5-15 */คลาสสาธารณะ LRUCACHETEST {โมฆะสาธารณะคงที่หลัก (สตริง [] args) โยนข้อยกเว้น {System.out.println ("เริ่ม ... "); lrucache1 (); lrucache2 (); lrucache3 (); lrucache4 (); System.out.println ("Over ... "); } โมฆะคงที่ lrucache1 () {system.out.println (); System.out.println ("============================= lru 链表实现 ============================"); lrucache1 <จำนวนเต็ม, สตริง> lru = ใหม่ 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 <จำนวนเต็ม, สตริง> lru = ใหม่ 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 (); } โมฆะคงที่ lrucache3 () {system.out.println (); System.out.println ("============================= lru linkedhashmap (คณะผู้แทน) 实现 =============================="); lrucache3 <จำนวนเต็ม, สตริง> lru = ใหม่ 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 (); } โมฆะคงที่ lrucache4 () {system.out.println (); System.out.println ("============================ FIFO LinkedHashMap 默认实现 ============================"); int cachesize สุดท้าย = 5; LinkedHashMap <จำนวนเต็ม, สตริง> lru = ใหม่ linkedHashMap <จำนวนเต็ม, สตริง> () {@Override boolean protected removeldestentry (map.entry <จำนวนเต็ม, สตริง> 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:/ไฟล์โปรแกรม (x86) /java/jdk1.6.0_10/bin/java" -didea.launcher.port = 7535 "-didea.launcher.bin.path = c:/โปรแกรมโปรแกรม (x86)/jetbrains/intellij (x86) /java/jdk1.6.0_10/jre/lib/charsets.jar; (x86) /java/jdk1.6.0_10/jre/lib/javaws.jar; (x86) /java/jdk1.6.0_10/jre/lib/jce.jar; (x86) /java/jdk1.6.0_10/jre/lib/plugin.jar; (x86) /java/jdk1.6.0_10/jre/lib/rt.jar; (x86) /java/jdk1.6.0_10/jre/ext/localedata.jar; (x86) /java/jdk1.6.0_10/jre/lib/ext/sunmscapi.jar; (x86) /java/jdk1.6.0_10/jre/lib/ext/sunpkcs11.jar; (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 =================================== Fifo LinkedHashMap การใช้งาน ===================================================== {1 = 11, 2 = 11, 3 = 11, 4 = 11, 5 = 11} {3 = 11, 4 = 11, 5 = 11ขอบคุณสำหรับการอ่านฉันหวังว่ามันจะช่วยคุณได้ ขอบคุณสำหรับการสนับสนุนเว็บไซต์นี้!