【アルゴリズム】LRU(Least Recently Used)の実装
要するに、一番使われていないものを捨てて、新しいものと入れ替える方式のこと。
今回は、最大で保持できる要素数は5個までとし、6個目の要素を格納したときに、
一番使われていない要素を捨てて6個目の要素を入れるような処理を目指します。
まず、「最大で保持できる要素が5個まで」という仕組みを作ります。
具体的にはLinkedHashMapのremoveEldestEntryメソッドをオーバーライドし、
return size() > 5;とします。
Java
public static void main(String[] args) {
//↓↓インナークラスここから↓↓
class LRU5 extends LinkedHashMap<String, String> {
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > 5;
}
}
//↑↑インナークラスここまで↑↑
tryLRU(new LRU5());
}
private static void tryLRU(Map map) {
map.put("Amazon", "11111");
map.put("Apple", "22222");
map.put("MicroSoft", "33333");
map.put("TOYOTA", "44444");
map.put("NISSAN", "55555");
System.out.println("5個目：" + map);
map.put("Tesla", "66666");
System.out.println("6個目追加：" + map);
}
実行すると以下の2行が出力されます。
Java
5個目：{Amazon=11111, Apple=22222, MicroSoft=33333, TOYOTA=44444, NISSAN=55555}
6個目追加：{Apple=22222, MicroSoft=33333, TOYOTA=44444, NISSAN=55555, Tesla=66666}
removeEldestEntryはTrueを返すたびに、Mapの先頭の要素を削除します。
前後の出力結果を見比べると6個目のTeslaを追加された代わりに1個目のAmazonが無くなっていることが分かります。
これで「最大で保持できる要素が5個まで」という仕組みは完成です。
次に、「一番使われていない要素」を判定するためにMapをアクセス順に保持する必要があります。
インナークラスのインスタンスを生成する際の引数を以下のようにします。
Java
new LRU5(5, 0.75f, true));
前述の１と２を組み合わせて以下のようなソースにするとLRUとして機能します。
Java
public static void main(String[] args) {
//↓↓インナークラスここから↓↓
class LRU5 extends LinkedHashMap<String, String> {
LRU5(int i, float f, boolean b){
super(i, f, b);
}
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > 5;
}
}
//↑↑インナークラスここまで↑↑
tryLRU(new LRU5(5, 0.75f, true));
}
private static void tryLRU(Map map) {
map.put("Amazon", "11111");
map.put("Apple", "22222");
map.put("MicroSoft", "33333");
map.put("TOYOTA", "44444");
map.put("NISSAN", "55555");
System.out.println("アクセス前：" + map);
map.get("Amazon");
map.put("Tesla", "66666");
System.out.println("アクセス後：" + map);
}
実行すると以下の2行が出力されます。
Java
アクセス前：{Amazon=11111, Apple=22222, MicroSoft=33333, TOYOTA=44444, NISSAN=55555}
アクセス後：{MicroSoft=33333, TOYOTA=44444, NISSAN=55555, Amazon=11111, Tesla=66666}
put処理は要素アクセスしたと見做されるのでputした順に要素アクセスしたことになります。
5個putした時点では、一番最後にputした要素がNISSANなので一番最後にアクセスした要素もNISSANとなります。
ですが、 次の行でAmazonをgetしています。get処理もput処理と同様に要素にアクセスしたと見做されるため、この処理により一番最後にアクセスした要素がAmazonに変わります。
このタイミングでTeslaをputすると、アクセス順が若い要素(最も使われていない要素)はAppleとなるので、Appleが消え、代わりにTeslaが格納される結果となります。
以上で記事の解説はお終い！
もっとJavaやSpringを勉強したい方にはUdemyがオススメ！同僚に差をつけよう！