← 질문 목록
#371깊이 0
LRU 캐시를 O(1)로 구현하려면 어떤 자료구조들을 조합하는가?
자료구조 · 알고리즘
답변 연습
내 답변 적어보기접힘
이 브라우저에 자동 저장 · 0자
모범답안 확인하기내 답변 뒤에 열어보세요
- 해시 맵Key를 노드 주소로 매핑
- 이중 연결 리스트데이터의 순서를 유지
해시 맵은 데이터 탐색을 상수 시간에 마친다. 이중 연결 리스트는 노드를 리스트 맨 앞으로 옮기거나 삭제하는 연산을 상수 시간에 처리한다.
캐시를 읽거나 쓸 때 해시 맵으로 노드 위치를 바로 찾는다. 찾은 노드는 연결 리스트의 앞쪽으로 끊어 옮긴다. 이 방식으로 최근에 쓴 데이터를 앞쪽에 유지한다.
배열이나 단일 연결 리스트만 쓰면 한계가 생긴다. 배열은 탐색이 빠르지만 중간 데이터를 삭제하고 밀어내는 비용이 크다. 단일 연결 리스트는 이전 노드 주소를 알 수 없어 O(1) 삭제가 어렵다.