Java LRU (paling baru digunakan) Penjelasan terperinci
LRU adalah singkatan dari yang paling baru digunakan. Itu diterjemahkan sebagai "penggunaan terbaru". Cache LRU diimplementasikan menggunakan prinsip ini. Sederhananya, itu untuk menyimpan sejumlah data. Ketika ambang batas yang ditetapkan terlampaui, beberapa data kedaluwarsa akan dihapus. Misalnya, kami menyimpan 10.000 data. Ketika data kurang dari 10.000, Anda dapat menambahkannya sesuka hati. Ketika melebihi 10.000, Anda perlu menambahkan data baru. Pada saat yang sama, Anda perlu menghapus data yang sudah kadaluwarsa untuk memastikan bahwa kami dapat menyimpan 10.000 data secara maksimal. Bagaimana cara menentukan data yang sudah kadaluwarsa mana? Jika Anda menggunakan algoritma LRU untuk mengimplementasikannya, Anda akan menghapus data tertua. Tanpa banyak bicara, mari kita bicara tentang Implementasi Cache LRU versi Java.
Biasanya ada dua opsi untuk menerapkan cache LRU di Java. Salah satunya adalah menggunakan LinkedHashMap, dan yang lainnya adalah merancang struktur data Anda sendiri dan menggunakan daftar tertaut + HashMap.
LinkedHashMap Implementasi LRU Cache
LinkedHashMap sendiri telah menerapkan penyimpanan berurutan. Secara default, disimpan dalam urutan penambahan elemen. Ini juga dapat memungkinkan penyimpanan dalam urutan akses, yaitu, data yang baru dibaca ditempatkan di depan dan data baca paling awal ditempatkan di akhir. Maka ia juga memiliki metode untuk menentukan apakah akan menghapus data tertua. Standarnya adalah mengembalikan false, yaitu, bukan menghapus data. Metode menggunakan LinkedHashMap untuk mengimplementasikan cache LRU adalah mengimplementasikan ekspansi sederhana dari LinkedHashMap. Ada dua cara untuk memperpanjang, satu adalah warisan dan yang lainnya adalah delegasi. Metode spesifik digunakan untuk bergantung pada preferensi pribadi.
// Konstruktor LinkedHashMap. Ketika parameter AccessOrder benar, itu akan diurutkan dalam urutan akses. Akses terbaru ditempatkan terlebih dahulu dan akses paling awal ditempatkan di belakang LinkedHashMap publik (int initialcapacity, float loadfactor, boolean accessOrder) {super (initialcapacity, loadfactor); this.accessOrder = accessOrder;} // LinkedHashMap hadir dengan metode untuk menentukan apakah akan menghapus elemen tertua. Ini mengembalikan false secara default, yaitu, tidak menghapus data lama. // Apa yang perlu kita lakukan adalah menulis ulang metode ini dan menghapus data lama ketika kondisi tertentu dipenuhi boolean yang dilindungi lepas lepas (map.entry <k, v> sulung) {return false;} LRU Cache LinkedHashMap (Warisan) Implementasi
Metode warisan relatif mudah diimplementasikan, dan antarmuka peta diimplementasikan. Saat menggunakan lingkungan multi-threaded, Anda dapat menggunakan metode collections.synchronizedMap () untuk mengimplementasikan operasi yang aman utas.
Paket cn.lzrabbit.struktur.lru; impor java.util.linkedhashmap; import java.util.map;/*** dibuat oleh liuzhao pada 14-5-15. */kelas publik lrucache2 <k, v> memperluas linkedHashMap <k, v> {private final int max_cache_size; publik lrucache2 (int cacachesize) {super ((int) math.ceil (cacheSize / 0,75) + 1, 0,75F, true); Max_cache_size = cacheSize; } @Override Protected Boolean RemestEldestEntry (MAP.ENTRY ELDERLY) {return size ()> max_cache_size; } @Override public string toString () {stringBuilder sb = new stringBuilder (); untuk (map.entry <k, v> entri: entryset ()) {sb.append (string.format ("%s:%s", entri.getKey (), entri.getValue ())); } return sb.toString (); }}Ini adalah implementasi yang relatif standar. Masih agak rumit untuk menulis seperti ini dalam penggunaan aktual. Saat menulisnya seperti metode yang lebih praktis ini, ia menghemat kesulitan melihat kelas secara terpisah.
Final int cacheSize = 100; peta <string, string> peta = new LinkedHashMap <String, String> ((int) math.ceil (cacheSize / 0.75f) + 1, 0.75f, true) {@Override lepas ukuran returnEldestry (map.entry <string, string> elderly) {ukuran return () (MAP.entry <string, string> elderly) {ukuran pengembalian () () (MAP.entry <string, string> elderly) {ukuran pengembalian ()> caches; }}; LRU Cache LinkedHashMap (Delegasi) Implementasi
Implementasi metode delegasi lebih elegan, tetapi karena antarmuka peta tidak diimplementasikan, sinkronisasi utas perlu dilakukan sendiri.
Paket cn.lzrabbit.struktur.lru; impor java.util.linkedhashmap; import java.util.map; import java.util.set;/*** dibuat oleh liuzhao pada 14-5-13. */kelas publik lrucache3 <k, v> {private final int max_cache_size; private final float default_load_factor = 0.75f; LinkedHashMap <K, V> peta; publik lrucache3 (int cacheSize) {max_cache_size = cacheSize; // Hitung kapaktasi hashmap berdasarkan cacheze dan faktor pemuatan. +1 Pastikan bahwa ekspansi hashmap tidak akan dipicu ketika batas atas cacheSize tercapai. Int Capasity = (int) math.ceil (max_cache_size / default_load_factor) + 1; peta = new LinkedHashMap (kapasitas, default_load_factor, true) {@Override Dilindungi boolean lepas lepas ongkos (peta.entry elderly) {return size ()> max_cache_size; }}; } public yang disinkronkan void put (tombol k, nilai v) {MAP.Put (key, value); } public disinkronkan v get (K key) {return map.get (key); } public yang disinkronkan void lepas (K key) {map.remove (key); } set disinkronkan publik <map.entry <k, v >> getAll () {return map.entryset (); } ukuran int sinkronisasi publik () {return map.size (); } public disinkronkan void clear () {map.clear (); } @Override public string toString () {stringBuilder sb = new stringBuilder (); untuk (entri map.entry: map.entryset ()) {sb.append (string.format ("%s:%s", entri.getKey (), entri.getValue ())); } return sb.toString (); }} Daftar Tertaut LRU Cache + Implementasi HashMap
Catatan: Implementasi ini tidak utuh. Jika digunakan dalam lingkungan multi-threaded, Anda perlu menambahkan metode yang disinkronkan ke yang relevan untuk mencapai operasi yang aman.
Paket cn.lzrabbit.struktur.lru; import java.util.hashmap;/*** dibuat oleh liuzhao pada 14-5-12. */kelas publik lrucache1 <k, v> {private final int max_cache_size; entri pribadi terlebih dahulu; entri pribadi terakhir; hashmap pribadi <k, entri <k, v >> hashmap; publik lrucache1 (int cacheSize) {max_cache_size = cacheSize; hashmap = hashmap baru <k, entri <k, v >> (); } public void put (Key k, nilai v) {entri entri = getEntry (key); if (entry == null) {if (hashmap.size ()> = max_cache_size) {hashmap.remove (last.key); removelast (); } entri = entri baru (); entri.key = key; } entri.value = nilai; movetofirst (entri); hashmap.put (kunci, entri); } public v get (K key) {entri <k, v> entri = getEntry (key); if (entri == null) return null; movetofirst (entri); return entry.value; } public void Remove (K key) {entri entri = getEntry (key); if (entri! = null) {if (entry.pre! = null) entri.pre.next = entry.next; if (entry.next! = null) entry.next.pre = entri.pre; if (entri == pertama) pertama = entri.next; if (entri == terakhir) terakhir = entri.pre; } hashmap.remove (key); } private void moveToFirst (entri entri) {if (entri == pertama) kembali; if (entry.pre! = null) entri.pre.next = entri.next; if (entry.next! = null) entry.next.pre = entri.pre; if (entri == terakhir) terakhir = last.pre; if (first == null || last == null) {first = last = entri; kembali; } entry.next = pertama; first.pre = entri; pertama = entri; pertama = entri; entri.pre = null; } private void removeLast () {if (last! = null) {last = last.pre; if (last == null) pertama = null; lain last.next = null; }} entri pribadi <k, v> getEntry (K key) {return hashmap.get (key); } @Override public string toString () {stringBuilder sb = new stringBuilder (); Entri entri = pertama; while (entri! = null) {sb.append (string.format ("%s:%s", entri.key, entri.value)); entri = entri.next; } return sb.toString (); } entri kelas <k, v> {entri publik pre; Entri publik berikutnya; Kunci K Publik; nilai v publik; }} Implementasi FIFO dari LinkedHashMap
FIFO adalah singkatan dari output pertama input pertama, yang sering disebut pertama, pertama. Secara default, LinkedHashMap disimpan dalam urutan penambahan. Kita hanya perlu menulis ulang metode RemestEldestEntry untuk dengan mudah mengimplementasikan cache FIFO. Versi yang disederhanakan dari kode implementasi adalah sebagai berikut.
Final int cacheSize = 5; LinkedHashMap <Integer, String> lru = new LinkedHashMap <Integer, String> () {@Override Dilindungi Boolean RemestEldestEntry (Map.entry <Integer, String> Elderly) {ukuran pengembalian ()> cacheSize; }}; Contoh panggilan
Paket cn.lzrabbit.struktur.lru; import cn.lzrabbit.itest; import java.util.linkedhashmap; import java.util.map;/*** dibuat oleh liuzhao pada 14-5-15. */kelas publik lrucachetest {public static void main (string [] args) melempar pengecualian {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 = lrucache baru (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 (warisan) 实现 ============================ "); 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 (Delegasi) 实现 ============================"); 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 默认实现 ==========================="); Final Int Cachesize = 5; LinkedHashMap <Integer, String> lru = new LinkedHashMap <Integer, String> () {@Override Dilindungi Boolean RemestEldestEntry (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 (); }}Hasil berjalan
"C:/Program Files (x86) /java/jdk1.6.0_10/bin/java" -didea.launcher.port = 7535 "-didea.launcher.bin.path = C:/Program File (x86)/JetBrains/Intellijer Ide 13.0.2/Bin" -Dfile/JetBrains/IntelliJ 13.0.2/Bin "-dfile. "C:/Program Files (x86) /java/jdk1.6.0_10/jre/lib/charsets.jar;c:/programs file (x86) /java/jdk1.6.0_10/jre/lib/deploy.jar;c:/programam (x86) /java/jdk1.6.0_10/jre/lib/javaws.jar;c:/programs file (x86) /java/jdk1.6.0_10/jre/lib/jce.jar;c:/programs File (x86) /java/jdk1.6.0_10/jre/lib/jce.jar;c:/programs file (x86) /java/jdk1.6.0_10/jre/lib/management-agent.jar;c:/programam file (x86) /java/jdk1.6.0_10/jre/lib/plugin.jar;c:/programs file (x86) /java/jdk1.6.0_10/jre/lib/resources.jar;c:/programam file (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;c:/programs file (x86) /java/jdk1.6.0_10/jre/lib/ext/sunpkcs11.jar;d:/svn/projects/java/java.algorithm/target/test-classes;d:/svn/projects/java.java.dasses; (x86)/JetBrains/IntelliJ Idea 13.0.2/lib/Idea_rt.jar "com.intellij.rt.execution.application.appmain MainStart ... ==================================================================================================================================================== =========================================================================================================================================== ============================================================================================================================================= =========================================================================================================================================== LinkedHashMap (warisan) Implementasi ================================================================= ============================================================================ ========================================================================== ============================================================================ 1:11 2:11 3:11 4:11 5:11 5:11 6:66 2:11 7:77 4:11 ======================================= FIFO LINKEDHASHMAP Default LinkedHashMap Implementasi ===================================================== {1 = 11, 2 = 11, 3 = 11, 4 = 11, 5 = 11} {3 = 11, 4 = 11, 5 = 11, 6 = 66, 7 = 7 = 7 =Terima kasih telah membaca, saya harap ini dapat membantu Anda. Terima kasih atas dukungan Anda untuk situs ini!