[자료구조] LRU Cache 알고리즘

LRU Cache는 자료구조는 아니지만 그래도 doubly linked list와 hash map을 사용해서 구현하였다는 것을 강조하기 위해 자료구조 카테고리에 넣었다. (나중에 변경할지도..)

 

LRU Cache : Least Recently Used

• 캐시에서 메모리를 다루는 알고리즘 중 가장 많이 사용되는 알고리즘

• 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘

다음은 java를 사용한 예제 코드이다.

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
	private Map<Integer, node> nodeMap;
	private int capacity;
	private node head;
	private node tail;

	private class node {
		private int key;
		private int value;
		private node prev;
		private node next;

		public node(int key, int value) {
			this.key = key;
			this.value = value;
			this.next = null;
			this.prev = null;
		}
	}

	public LRUCache(int capacity) {
		this.nodeMap = new HashMap<>();
		this.capacity = capacity;
		head = new node(0, 0);
		tail = new node(0, 0);
		head.next = tail;
		tail.prev = head;

	}

	//시간 복잡도 O(1)
	private void remove(node node) {
		node.prev.next = node.next;
		node.next.prev = node.prev;

		nodeMap.remove(node.key);
	}

	//시간 복잡도 O(1)
	private void insertToHead(node node) {
		this.head.next.prev = node;
		node.next = this.head.next;
		node.prev = this.head;
		this.head.next = node;

		nodeMap.put(node.key, node);
	}

	//시간 복잡도 O(1)
	public int get(int key) {
		if (!nodeMap.containsKey(key))
			return -1;
		node getNode = nodeMap.get(key);
		remove(getNode);
		insertToHead(getNode);
		return getNode.value;

	}

	//시간 복잡도 O(1)
	public void put(int key, int value) {
		node newNode = new node(key, value);
		if (nodeMap.containsKey(key)) {
			node oldNode = nodeMap.get(key);
			remove(oldNode);
		} else {
			if (nodeMap.size() >= this.capacity) {
				node delNode = tail.prev;
				remove(delNode);
			}
		}
		insertToHead(newNode);
	}

}

Dobuly linked list와 Hashmap을 사용하여 LRU Cache를 구현하였다.

여기서 head와 tail은 data를 가지고 있는 것이 아니고 포인터의 역할만 한다. 즉, head.next 값이 실제 리스트에서 최근에 추가된 원소가 되고, tail.prev 값이 가장 오래된 원소가 된다.

(새로 추가되거나 가장 최근에 사용한 것은 head와 가까이 있다.)

 

Hashmap을 사용하여 노드를 탐색하는 속도를 빠르게했다. (이론적으로 Hashmap의 탐색 속도는 O(1)이고 Linked List는 O(N)이다.)