면접준비 - LRU Cache는 2가지 자료구조로 만들어졌다.

Posted Oct 2, 2022

nil}" class="preview-img" alt="Preview Image" w="1200" h="630" >

By ,

8 min read

오타, 지적 환영입니다.

개요

카카오 다니는 형이 면접준비 도와준다고 하나의 질문을 던졌다.

“실제 나온 내용이고 LRU cache 2가지 자료구조로 만들어졌는데 뭔지 아니?”

답변 못했다.

LRU cache?

LRU Cache는 운영체제 페이지 교체 알고리즘인데, Least Recently Used라는 의미로 가장 오랫동안 참조되지 않은 페이지를 교체 대상으로 삼는 기법이다.

오랫동안 사용되지 않은 페이지는 앞으로도 사용되지 않을 가능성이 크다. 라는 이론에 따라 캐시 히트율을 높이는 것이다.

자료구조

2가지 자료구조는 Double Linked List와 HashMap이다.

Java기준 코드를 보겠다.

전체코드

출처 : https://hee96-story.tistory.com/47

  
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);
	}

}

1. node

  
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;
    }
}

key와 value를 가지는 특이한 노드이다. 기존 링크드 리스트의 노드는 value하나만 갖는데 키 값도 갖는다는게 특이점이다. 그 외에는 앞 뒤 노드를 가르킬 next와 prev이다.

2. LRU Cache

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

    ...

	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;

	}
}

capacity는 LRU Cahce의 사이즈겠고, 탐색속도를 높이기 위한 Map이 들어가있다. 링크드리스트는 탐색속도가 O(N)이기에 O(1)로 탐색하기 위해 넣은 것이다.

초기 노드는 더미 노드로 의미없는 노드 2개를 생성해서 head와 tail이 가리키고 있다.

이렇게 해놓은 이유는 만들기.. 쉬워서다. 노드를 애초에 생성하지 않는다면 맨 처음 노드가 들어올때 이를 감지하고 head, tail 셋팅을 매 번 해줘야하기 때문이다.

3. remove(node node)

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

    nodeMap.remove(node.key);
}

링크드 리스트에서 노드 삭제하는것처럼 구현된다.

이전노드 -> 현재노드(삭제할 노드) -> 다음노드
        <-                      <-

//삭제 과정
   ┌---------------------------┐
   ↓                           ↑
이전노드     현재노드(삭제)     다음노드
   ↓                           ↑
   └---------------------------┘

이렇게 연결한다.

4. get(int key)

  
//시간 복잡도 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;

}

만약 맵에 키가 없다면 -1를 리턴하고 있다면 그 값을 빼어서 위에서 구현한 remove()함수를 호출하여 맵에서 제거하고 링크드 리스트를 이어준다. 그리고 최근 참조되었으므로 insertToHead(getNode)를 통하여 헤드에 값을 넣고 가리킬 것이다.

5.insertToHead(node node)

  
//시간 복잡도 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);
}

헤드의 다음노드의 이전 포인터는 새로운 노드를 가리켜야할 것이고, 새로 들어온 노드는 그 노드를 또 가리켜야 양방향으로 이어질것이다. 그리고 헤드 노드와 새로운 노드 또한 양방향으로 잇고, Map에 노드의 키값을 추가하여 탐색시의 속도를 높인다.

6. put(int key, int 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);
}

int형 key와 value를 받아 새로운 노드를 생성한다.
만약 새로운 노드가 Map에 존재한다면 Map에 저장된 노드를 꺼내서 링크드리스트에서 삭제시킨다. (새로 갱신해줘야하기 때문에)
만약 없고, 수용범위를 초과하거나 동일하다면 맨 끝에있는 노드를 삭제한다.
새로운 노드를 헤드에 넣는다.

결론

어렵지는 않지만 이해는 하고 있어야한다고 생각했다.

Interview

Java

This post is licensed under CC BY 4.0 by the author.

개요