LRU(Least Recently Used) Cache 알고리즘이란
새로운 데이터가 캐시에 저장될 때나 캐시에 있는 데이터에 접근할 때마다 해당 데이터를 "가장 최근에 사용된 데이터"로 표시하고 가장 오래 전에 사용된 데이터를 먼저 제거하여 가장 최근에 사용된 데이터를 캐시에 보존하는 데 사용됩니다.
이러한 방식으로 LRU Cache는 Cache Hit를 최대화하고, CPU나 메모리 등 시스템 자원을 효율적으로 활용할 수 있도록 도와줍니다.
LRU Cache 알고리즘을 구현하는 방법은 다양하며, 이중 연결 리스트(Double Linked List)나 해시 맵(Hash Map)과 같은 자료 구조를 사용하여 구현할 수 있습니다. 이를 통해 가장 오래된 데이터를 O(1)의 시간복잡도로 식별하고 제거할 수 있습니다.
구현 방법
아이디어
기본적으로 캐쉬 데이터 관리는 HashMap key-value 형식으로 관리하여 조회할때 O(1)의 성능을 챙겨줍니다. (key : key, value: Node)
HashMap<String, Node> hashMap = new HashMap<>();
그리고 캐쉬 데이터가 오래된 데이터를 식별하기 위해서 LinkedList로 제일 오래된 데이터는 Head, 가장 최근 데이터는 Tail로 구분하여 데이터를 관리해줍니다.
LinkedList<Node> nodes = new LinkedList<>();
데이터 캐쉬 저장 코드, Node save(String key, String value)
private static Node save(String key, String value) {
Node node = new Node(key, value);
nodes.addLast(node);
hashMap.put(key, node);
if(hashMap.size() > CACHE_MAX_SIZE) {
Node removedNode = nodes.removeFirst();
hashMap.remove(removedNode.key);
}
return node;
}cache할 데이터 key, value를 받아 Node형태로 만들어 준뒤 LinkedList의 Tail(가장 최신 데이터)에 추가해줍니다.
또한 Node를 실질적으로 조회할때 속도를 챙기기 위해 HashMap으로 저장해줍니다.
저장하고 난뒤 Cache 데이터 사이즈가 일정사이즈를 넘어갔다면 HEAD(가장 호출이 오래 안된 데이터)의 데이터를 삭제해주면서 HashMap에서 삭제해줍니다.
값 가져오기 코드 String get(String key)
private static String get(String key) {
Node node = hashMap.get(key);
if (node != null) {
nodes.remove(node);
nodes.addLast(node);
return node.value;
} else {
return save(key, generateValue(key)).value;
}
}캐쉬된 데이터를 가져오기 위해 key값으로 HashMap에 get()하여 조회를 합니다.
캐쉬된 데이터가 있다면 LinkedList에서 해당 Node를 찾아 제일 뒤로 이동시켜줍니다.
캐쉬된 데이터가 없다면 새로운 데이터를 Node save(String key, String value)로 저장해줍니다.
결과
초기 데이터 세팅
기존 데이터 입력
cache list에 보시면 key값이 0, 1, 2 순으로 저장되어 있던 list가 0을 입력했을때 1, 2, 0으로 cache리스트가 최신화 된것을 확인할 수 있습니다.
새로운 데이터 추가
새로운 데이터 aaa를 입력했을때는 list에서 Head에 있던 Node Node{key=1, value='old value 1'}가 삭제되고 Tail에 Node{key=aaa, value='new value aaa'}가 추가 된것을 확인할 수 있습니다.
HashMap에서도 cache 데이터가 같이 관리되고 있는것을 확인할 수 있습니다.
전체 코드
package code;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
public class LRUCache {
static LinkedList<Node> nodes = new LinkedList<>();
static HashMap<String, Node> hashMap = new HashMap<>(); // key : key, value: Node
static final int CACHE_MAX_SIZE = 3;
public static void main(String[] args) throws IOException {
for (int i = 0; i < 3; i++) {
save(String.valueOf(i), "old value " + i);
}
log();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while (true) {
String input = br.readLine();
String value = get(input);
System.out.println("result value => " + value);
log();
}
}
private static String get(String key) {
Node node = hashMap.get(key);
if (node != null) {
nodes.remove(node);
nodes.addLast(node);
return node.value;
} else {
return save(key, generateValue(key)).value;
}
}
private static Node save(String key, String value) {
Node node = new Node(key, value);
nodes.addLast(node);
hashMap.put(key, node);
if(hashMap.size() > CACHE_MAX_SIZE) {
Node removedNode = nodes.removeFirst();
hashMap.remove(removedNode.key);
}
return node;
}
private static String generateValue(String key) {
return "new value " + key;
}
private static void log() {
System.out.println("* cache list *");
nodes.forEach(System.out::println);
System.out.println("----------------------------------------------------");
System.out.println("* hashMap *");
hashMap.entrySet().forEach(System.out::println);
System.out.println("----------------------------------------------------");
}
public static class Node {
private String key;
private String value;
public Node(String key, String value) {
this.key = key;
this.value = value;
}
@Override
public String toString() {
return "Node{" +
"key=" + key +
", value='" + value + '\'' +
'}';
}
}
}
reference :
