Java LRU (الأقل استخدامًا مؤخرًا) شرح مفصل
LRU هو اختصار أقل استخدامًا مؤخرًا. يتم ترجمته على أنه "أحدث استخدام". يتم تنفيذ ذاكرة التخزين المؤقت LRU باستخدام هذا المبدأ. ببساطة ، هو لتخزين كمية معينة من البيانات. عندما يتم تجاوز عتبة المجموعة ، سيتم حذف بعض البيانات منتهية الصلاحية. على سبيل المثال ، نقوم بتخزين 10،000 قطعة من البيانات. عندما تكون البيانات أقل من 10000 ، يمكنك إضافتها حسب الرغبة. عندما يتجاوز 10000 ، تحتاج إلى إضافة بيانات جديدة. في الوقت نفسه ، تحتاج إلى حذف البيانات المنتهية للتأكد من أنه يمكننا تخزين 10،000 قطعة من البيانات بأقصى حد. كيف تحدد أي بيانات منتهية الصلاحية لحذفها؟ إذا كنت تستخدم خوارزمية LRU لتنفيذها ، فستقوم بحذف أقدم البيانات. دون أن نقول الكثير ، دعنا نتحدث عن إصدار Java من تطبيق LRU Cache.
عادة ما يكون هناك خياران لتنفيذ ذاكرة التخزين المؤقت LRU في Java. أحدهما هو استخدام LinkedHashMap ، والآخر هو تصميم بنية البيانات الخاصة بك واستخدام قائمة مرتبطة + HashMap.
تنفيذ LinkedHashMap من ذاكرة التخزين المؤقت LRU
قامت LinkedHashMap نفسها بتنفيذ تخزين متسلسل. بشكل افتراضي ، يتم تخزينه بترتيب إضافة عناصر. يمكن أيضًا تمكين التخزين بترتيب الوصول ، أي يتم وضع بيانات القراءة مؤخرًا في المقدمة ويتم وضع بيانات القراءة الأولى في النهاية. ثم لديه أيضًا طريقة لتحديد ما إذا كان سيتم حذف أقدم البيانات. الافتراضي هو إرجاع خطأ ، أي ، لا حذف البيانات. تتمثل طريقة استخدام LinkedHashMap لتنفيذ ذاكرة التخزين المؤقت LRU في تنفيذ التوسع البسيط في LinkedHashMap. هناك طريقتان لتمديدهما ، أحدهما هو الميراث والآخر هو التفويض. يتم استخدام الطريقة المحددة للاعتماد على التفضيلات الشخصية.
// مُنشئ من LinkedHashMap. عندما يكون AccessOrder المعلمة صحيحًا ، سيتم فرزه بترتيب الوصول. يتم وضع أحدث وصول أولاً ويتم الوصول إلى أقدم وصول خلف LinkedHashMap العام (int initialcapacity ، float loadfactor ، accessorder boolean) {super (initialCapacity ، loadFactor) ؛ this.AccessOrder = AccessOrder ؛} // يأتي LinkedHashMap مع طريقة لتحديد ما إذا كان سيتم حذف العنصر الأقدم. إنه يعيد خطأ بشكل افتراضي ، أي أنه لا يحذف البيانات القديمة. // ما يتعين علينا القيام به هو إعادة كتابة هذه الطريقة وحذف البيانات القديمة عندما يتم استيفاء شروط معينة محمية Boolean RemoveEldestentry (map.entry <k ، v> senest) {return false ؛} تنفيذ LRU Cache LinkedHashMap (الميراث)
طريقة الميراث بسيطة نسبيا للتنفيذ ، ويتم تنفيذ واجهة الخريطة. عند استخدام بيئة متعددة الخيوط ، يمكنك استخدام طريقة collections.synchronizedMap () لتنفيذ عمليات آمنة مؤشرات الترابط.
package cn.lzrabbit.structure.lru ؛ import java.util.linkedhashmap ؛ import java.util.map ؛/*** تم إنشاؤه بواسطة liuzhao في 14-5-15. */الفئة العامة 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 = cachesize ؛ } Override محمية Boolean RemoveEldestentry (Map.Entry مسن) {return size ()> max_cache_size ؛ } Override Public String ToString () {StringBuilder SB = جديد StringBuilder () ؛ لـ (map.entry <k ، v> intrad: interset ()) {sb.append (string.format ("٪ s: ٪ s" ، intrad.getKey () ، intradvalue ())) ؛ } return sb.toString () ؛ }}هذا هو التنفيذ القياسي نسبيا. لا يزال الأمر مرهقًا بعض الشيء في الكتابة مثل هذا في الاستخدام الفعلي. عند كتابتها مثل هذه الطريقة الأكثر عملية ، فإنه يحفظ مشكلة رؤية الفصل بشكل منفصل.
النهائي int cachesize = 100 ؛ خريطة <string ، string> map = new LinkedHashMap <string ، string> ((int) Math.ceil (cachesize / 0.75f) + 1 ، 0.75f ، true) {override boolean removeeldestentry (map.entry <string> lederly) }} ؛ تنفيذ LRU Cache LinkedHashMap (تفويض)
يعد تطبيق طريقة التفويض أكثر أناقة ، ولكن نظرًا لعدم تطبيق واجهة الخريطة ، يجب أن يتم مزامنة مؤشرات الترابط بنفسك.
package cn.lzrabbit.structure.lru ؛ import java.util.linkedhashmap ؛ استيراد java.util.map ؛ استيراد java.util.set ؛/*** تم إنشاؤه بواسطة liuzhao في 14-5-13. */الفئة العامة lrucache3 <k ، v> {private final int max_cache_size ؛ 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 = new LinkedHashMap (السعة ، default_load_factor ، true) {Override boolean removeeldestentry (map.entry olderly) {return size ()> max_cache_size ؛ }} ؛ } PUD VOID المتزامن العام (مفتاح k ، v value) {map.put (المفتاح ، القيمة) ؛ } synchronized v get (k key) {return map.get (key) ؛ } إزالة الفراغ المزامنة العامة (مفتاح k) {map.remove (مفتاح) ؛ } مجموعة متزامنة عامة <map.entry <k ، v >> getAll () {return map.entryset () ؛ } size size int () {return map.size () ؛ } void المتزامن العام clear () {map.clear () ؛ } Override Public String ToString () {StringBuilder SB = جديد StringBuilder () ؛ لـ (map.entry entry: map.entryset ()) {sb.append (string.format ("٪ s: ٪ s" ، intrad.getKey () ، intradvalue ())) ؛ } return sb.toString () ؛ }} قائمة LRU Cache المرتبطة + تطبيق HashMap
ملاحظة: هذا التنفيذ غير متخلف. إذا تم استخدامها في بيئة متعددة الخيوط ، فأنت بحاجة إلى إضافة متزامنة إلى الطرق ذات الصلة لتحقيق عمليات آمنة مؤشرات الترابط.
Package Cn.LzRabbit.structure.lru ؛ import java.util.hashmap ؛/*** تم إنشاؤه بواسطة Liuzhao في 14-5-12. */الفئة العامة lrucache1 <k ، v> {private final int max_cache_size ؛ الدخول الخاص أولاً ؛ الدخول الخاص الماضي ؛ hashmap الخاص <k ، الدخول <k ، v >> hashmap ؛ public lrucache1 (int cachesize) {max_cache_size = cachesize ؛ hashmap = new hashmap <k ، entry <k ، v >> () ؛ } public void put (k key ، v value) {entrate intplan = getentry (key) ؛ if (entry == null) {if (hashmap.size ()> = max_cache_size) {hashmap.remove (last.key) ؛ إزالة () ؛ } الإدخال = إدخال جديد () ؛ enter.Key = Key ؛ } entry.value = value ؛ movetofirst (الدخول) ؛ hashmap.put (المفتاح ، الدخول) ؛ } public v get (k key) {entry <k ، v> entry = getentry (key) ؛ إذا (الدخول == فارغ) إرجاع فارغ ؛ movetofirst (الدخول) ؛ إرجاع الإدخال. القيمة ؛ } public void remove (k key) {intpl entry = getentry (key) ؛ if (entry! = null) {if (entrate.pre! = null) entry.pre.next = entrate.next ؛ if (enter.next! = null) intpl.next.pre = intrad.pre ؛ إذا (الإدخال == أولاً) أولاً = inter.next ؛ if (entry == last) last = enter.pre ؛ } hashmap.remove (مفتاح) ؛ } private void movetofirst (إدخال الإدخال) {if (entrate == first) return ؛ if (enter.pre! = null) intpl.pre.next = intrad.next ؛ if (enter.next! = null) intpl.next.pre = intrad.pre ؛ إذا (الدخول == الأخير) الماضي = last.pre ؛ if (first == null || last == null) {first = last = intrade ؛ يعود؛ } enter.next = first ؛ first.pre = الدخول ؛ أولا = الدخول ؛ أولا = الدخول ؛ enter.pre = null ؛ } private void lexovelast () {if (last! = null) {last = last.pre ؛ if (last == null) first = null ؛ آخر last.next = null ؛ }} الإدخال الخاص <k ، v> getentry (k key) {return hashmap.get (key) ؛ } Override Public String ToString () {StringBuilder SB = جديد StringBuilder () ؛ إدخال الدخول = أولا ؛ بينما (إدخال! = null) {sb.append (string.format ("٪ s: ٪ s" ، intrad.key ، intrad.value)) ؛ الدخول = enter.next ؛ } return sb.toString () ؛ } إدخال الفئة <k ، v> {الإدخال العام pre ؛ الدخول العام المقبل ؛ مفتاح K العام ؛ قيمة V العامة ؛ }} تطبيق FIFO من LinkedHashMap
FIFO هو اختصار الإدخال الأول الإدخال الأول ، والذي يسمى غالبًا أولاً ، أولاً. بشكل افتراضي ، يتم حفظ LinkedHashMap بترتيب الإضافة. نحتاج فقط إلى إعادة كتابة طريقة removeeldestentry لتنفيذ ذاكرة التخزين المؤقت FIFO بسهولة. النسخة المبسطة من رمز التنفيذ هي كما يلي.
int النهائي cachesize = 5 ؛ linkedHashMap <integer ، string> lru = new LinkedHashMap <Integer ، string> () {Override محمية boolean removeEldestentry (map.entry <integer ، string> elderly) {size ()> cachesize ؛ }} ؛ استدعاء مثال
package cn.lzrabbit.structure.lru ؛ import cn.lzrabbit.itest ؛ import java.util.linkedhashmap ؛ import java.util.map ؛/*** تم إنشاؤه بواسطة liuzhao في 14-5-15. */الفئة العامة 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 ("================================================================") ؛ 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 (devation) 实现 ============================") ؛ 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 محمية boolean removeeldestentry (map.entry <integer ، string> aldest) {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) (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 / (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 (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 ملفات (x86) /java/jdk1.6.0_10/jre/ext/localedata.jar ؛c:/program files (x86) /java/jdk1.6.0_10/jre/leb/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 (x86)/jetbrains/intellij فكرة 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 ========================================== LinkedHashmap التنفيذ ====================================================== {1 = 11 ، 2 = 11 ، 3 = 11 ، 4 = 11 ، 5 = 11} {3 = 11 ، 4 = 11 ، 6 = 66 ، 7 = 77}.شكرا لك على القراءة ، آمل أن تساعدك. شكرا لك على دعمك لهذا الموقع!