LRU 및 MRU 캐시 축출 정책에 대한 정렬 된 키 데이터 구조

Question

캐시 제거 정책을 구현하는 간단한 데이터 구조로 작업하고 있습니다. 구현하고자하는 두 가지 가능한 시나리오는 다음과 같습니다. LRU and MRU

키가 가능한 가장 최근에 사용 된 캐시 블록 또는 가장 최근에 사용 된 캐시 블록을 알 수있는 키가 가능한 시간 (또는 자동 증가 된 정수) 인 맵과 같은 데이터 구조를 찾고 있습니다. . 값은 블록의 ID입니다.

삽입시 키를 기준으로 데이터를 정렬하고 O (1) 시간에 특정 키의 값을 검색하는 기존 데이터 구조가 있습니까?

예를 들어 Java의 HashMap은 일정한 시간 조회를 가지고 있지만, 구현중인 알고리즘에 따라 모든 키를 가져 와서 정렬하고 마지막 또는 처음을 선택해야합니다. SortedMap 내가 무엇을 위해 가야합니까? LRU 및 MRU 구현에서 잘 작동하는 다른 데이터 구조를 제안 하시겠습니까?

덕분에

Answer 1

당신은 삽입에의 키를 따라 오른쪽 SortedMap 종류의 항목입니다. SortedMap의 가장 잘 알려진 구현은 TreeMap이며 항목을 균형 이진 트리로 저장합니다. 자신의 javadoc에서

: 더 그 키에 주문 총을 제공

{@link지도}. 지도는 키의 {@linkplain Comparable 자연 순서}에 따라 정렬되거나 Sorted Map 작성시 제공되는 일반적으로 의 {Comparator}에 따라 정렬됩니다. 정렬 된지도의 컬렉션보기 ( entrySet, keySet 및 values ​​메서드에서 반환)를 반복 할 때이 순서가 반영됩니다. 주문을 활용하기 위해 몇 가지 추가 작업이 제공됩니다.

는 항목과 키가 SortedMap에서 정렬 오름차순으로 반환됩니다 있지만, 그것은 또한 helpfull뿐만 아니라 수 있습니다 방법 firstKey() 및 lastKey()을 가지고 있습니다.

특히 LRU의 경우 : Java에서 가장 일반적인 방법은 removeEldestEntry(Map.Entry) 인 LinkedHashMap을 사용하는 것입니다. 기본적으로 아무 것도하지 않지만 클래스를 쉽게 확장하고 해당 메서드를 구현할 수 있습니다. 자세한 내용은 here을 참조하십시오.