Java LRU（最近使用されていない）詳細な説明
LRUは、最近使用されていないことの略語です。 「最新の使用」と翻訳されています。 LRUキャッシュは、この原則を使用して実装されます。簡単に言えば、一定量のデータをキャッシュすることです。設定されたしきい値を超えると、いくつかの期限切れのデータが削除されます。たとえば、10,000個のデータをキャッシュします。データが10,000未満の場合、それを自由に追加できます。 10,000を超える場合は、新しいデータを追加する必要があります。同時に、最大10,000個のデータをキャッシュできるように、期限切れのデータを削除する必要があります。削除する期限切れのデータを決定する方法は？ LRUアルゴリズムを使用して実装すると、最古のデータが削除されます。あまり言わずに、LRUキャッシュの実装のJavaバージョンについて話しましょう。
通常、JavaにLRUキャッシュを実装するための2つのオプションがあります。 1つはLinkedHashmapを使用することであり、もう1つは独自のデータ構造を設計し、Linked List + Hashmapを使用することです。
LRUキャッシュのLinkedHashmap実装
LinkedHashmap自体は、シーケンシャルストレージを実装しています。デフォルトでは、要素を追加する順に保存されます。また、アクセスの順序でストレージを可能にすることもできます。つまり、最近読み取られたデータは前面に配置され、最終的な読み取りデータが最後に配置されます。また、最古のデータを削除するかどうかを判断する方法もあります。デフォルトは、false、つまりデータを削除するのではなく、falseを返すことです。 LinkedHashmapを使用してLRUキャッシュを実装する方法は、LinkedHashmapの簡単な拡張を実装することです。拡張するには2つの方法があります。1つは継承であり、もう1つは代表団です。特定の方法は、個人の好みに依存するために使用されます。
// linkedhashmapのコンストラクター。パラメーターAccessOrderがtrueの場合、アクセスの順にソートされます。最新のアクセスが最初に配置され、最も早いアクセスはパブリックLinkedhashmap（int initialcapacity、float loadfactor、boolean accessorder）{super（initialcapacity、loadfactor）; this.accessorder = AccessOrder;} // linkedhashmapには、最古の要素を削除するかどうかを決定する方法が付属しています。デフォルトでfalseを返します。つまり、古いデータを削除しません。 //私たちがしなければならないのは、この方法を書き換えて、特定の条件が満たされているときに古いデータを削除することです。 LRUキャッシュLinkedHashmap（相続）実装
継承方法は比較的簡単に実装でき、マップインターフェイスが実装されています。マルチスレッド環境を使用する場合、collections.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 = cachesize; } @Override Protected Boolean RemoveElDestentry（Map.Entry Elderly）{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"、entry.getKey（）、entry.getValue（））; } return sb.toString（）; }}これは比較的標準的な実装です。実際に使用してこのように書くのはまだ少し面倒です。このより実用的な方法のようにそれを書くとき、それはクラスを個別に見るというトラブルを救います。
final int cachesize = 100; map <string、string> map = new linkedhashmap <string>（（int）math.ceil（cachesize / 0.75f） + 1、0.75f、true）{@override保護されたブーリアンremoveeldesterry（map.entry <string、string> lerd ersize（）cachesize; }}; LRUキャッシュLinkedHashmap（委任）実装
委任方法の実装はよりエレガントですが、マップインターフェイスは実装されていないため、スレッドの同期を自分で行う必要があります。
パッケージcn.lzrabbit.structure.lru; import java.util.linkedhashmap; import java.util.map; import java.util.set;/*** Liuzhaoが14-5-13に作成しました。 */public class lrucache3 <k、v> {private final int max_cache_size;プライベートファイナルフロートdefault_load_factor = 0.75f; linkedhashmap <k、v> map; public lrucache3（int cachesize）{max_cache_size = cachesize; //キャッシュ化係数に基づいてハッシュマップのキャパクトを計算します。 +1カチェザイズの上限に達したときに、ハッシュマップの拡張がトリガーされないようにします。 int容量=（int）math.ceil（max_cache_size / default_load_factor） + 1; Map = new LinkedHashMap（容量、default_load_factor、true）{@OverRide Protected Boolean RemoveElDestentry（Map.Entry Elderly）{return size（）> max_cache_size; }}; } public Synchronized void put（k key、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.entryset（）; } public synchronized int size（）{return map.size（）; } public synchronized void clear（）{map.clear（）; } @Override public String toString（）{StringBuilder sb = new StringBuilder（）; for（map.entry entry：map.entryset（））{sb.append（string.format（ "％s：％s"、entry.getKey（）、entry.getValue（））; } return sb.toString（）; }} LRU Cacheのリンクリスト + Hashmap実装
注：この実装は非読み取りです。マルチスレッド環境で使用される場合は、スレッドセーフ操作を実現するために、関連する方法に同期して追加する必要があります。
パッケージcn.lzrabbit.structure.lru; import java.util.hashmap;/*** 14-5-12にLiuzhaoによって作成されました。 */public class lrucache1 <k、v> {private final int max_cache_size;最初にプライベートエントリ。最後にプライベートエントリ; private hashmap <k、entry <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）{entry entry = getEntry（key）; if（entry == null）{if（hashmap.size（）> = max_cache_size）{hashmap.remove（last.key）; removelast（）; } entry = new entry（）; entry.key = key; } entry.value = value; Movetofirst（エントリ）; Hashmap.put（key、entry）; } public v get（k key）{entry <k、v> entry = getEntry（key）; if（entry == null）nullを返します。 Movetofirst（エントリ）; return entry.value; } public void remove（k key）{entry entry = getEntry（key）; if（entry！= null）{if（entry.pre！= null）entry.pre.next = entry.next; if（entry.next！= null）entry.next.pre = entry.pre; if（entry == first）first = entry.next; if（entry == last）last = entry.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（entry == last）last = last.pre; if（first == null || last == null）{first = last = entry;戻る; } entry.next = first; first.pre = entry; first = entry; first = entry; entry.pre = null; } private void removelast（）{if（last！= null）{last = last.pre; if（last == null）first = null; else last.next = null; }} private entry <k、v> getEntry（k key）{return hashmap.get（key）; } @Override public String toString（）{StringBuilder sb = new StringBuilder（）;エントリエントリ= first; while（entry！= null）{sb.append（string.format（ "％s：％s"、entry.key、entry.value））; entry = entry.next; } return sb.toString（）; } class entry <k、v> {public entry pre;次にパブリックエントリ;パブリックKキー;パブリックV値; }} LinkedHashmapのFIFO実装
FIFOは、First入力ファースト出力の略語であり、これはしばしばファーストイン、ファーストアウトと呼ばれます。デフォルトでは、LinkedHashmapは追加の順に保存されます。 FIFOキャッシュを簡単に実装するには、RemoveElDestentryメソッドを書き換えるだけです。実装コードの簡素化されたバージョンは次のとおりです。
final int cachesize = 5; linkedhashmap <integer、string> lru = new linkedhashmap <integer、string>（）{@override protected boolean removeeldestentry（map.entry <integer、string> lergly）{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）throws exception {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（ "======================================================================================================= final int cachesize = 5; linkedhashmap <integer、string> lru = new linkedhashmap <integer、string>（）{@override protected boolean removeeldestentry（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：/プログラムファイル（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; c：/program files（x86）/java/jdk1.6.0_10/jre/lib/deploy.jar ;c：/programファイル（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/java （x86）/java/jdk1.6.0_10/jre/lib/management-agent.jar; c：/grogam 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ファイル（x86）/java/jdk1.6.0_10/jre/lib/rt.jar ;c：/programファイル（x86）/java/javaファイル（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：/gromenファイル（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/test-classes;d：/svn/projects/java/java.al.algorithm/gsprassmsmgrathmsmstargetsmava/ （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デフォルト実装========================================================================= 11、5 = 11、5 = 11} {3 = 11、4 = 11、5 = 11、6 = 66、7 = 77 = 77>読んでくれてありがとう、私はそれがあなたを助けることができることを願っています。このサイトへのご支援ありがとうございます！