어떻게 LRU Cache 를 설계 합 니까?

일반적인 문제 설명 은 다음 과 같다.
Question：
[1] Design a layer in front of a system which cache the last n requests and the responses to them from the system.
한 시스템 위 에 Cache, 캐 시 최근 n 개의 요청 과 시스템 응답 을 설계 합 니 다.what data structure would you use to implement the cache in the later to support following operations.
어떤 데이터 구조 로 이 Cache 를 설계 해 야 아래 의 조작 을 만족 시 킬 수 있 습 니까?[a] When a request comes look it up in the cache and if it hits then return the response from here and do not pass the request to the system[b] If the request is not found in the cache then pass it on to the system[c] Since cache can only store the last n requests, Insert the n+1th request in the cache and delete one of the older requests from the cache
Cache 는 최신 n 개의 요청 만 캐 시 하기 때문에 Cache 에 n + 1 번 째 요청 을 삽입 할 때 Cache 에서 가장 오래된 요청 을 삭제 합 니 다.
[d]Design one cache such that all operations can be done in O(1) – lookup, delete and insert.
 Cache 프로필:
캐 시 (캐 시) 는 컴퓨터 에서 거의 수시로 접촉 하 는 개념 이다.CPU 에서 Cache 는 데이터 와 명령 을 액세스 하 는 시간 을 크게 향상 시 켜 전체 메모리 (Cache + 메모리) 가 Cache 의 높 은 속도 와 메모리 의 대 용량 을 가 질 수 있 도록 합 니 다.운영 체제 의 메모리 page 에서 사용 하 는 Cache 는 자주 읽 는 메모리 디스크 파일 을 메모리 로 바 꾸 지 않 고 접근 속 도 를 높 일 수 있 습 니 다.데이터베이스 에서 데이터 조회 도 Cache 로 효율 을 높 인 다.Powerbuilder 의 DataWindow 데이터 처리 도 Cache 와 유사 한 디자인 을 사 용 했 습 니 다.Cache 의 알고리즘 디자인 에서 흔히 볼 수 있 는 것 은 FIFO (first in first out) 와 LRU (least recently used) 이다.제목 의 요구 에 따라 분명히 LRU 의 Cache 를 설계 해 야 한다.
 문제 풀이 방향:
Cache 의 저장 공간 은 유한 합 니 다. Cache 의 저장 블록 이 다 떨 어 지고 새로운 데 이 터 를 Cache 에 로드 해 야 할 때 우 리 는 좋 은 알고리즘 을 설계 하여 데이터 블록 의 교 체 를 완성 해 야 합 니 다.LRU 의 사상 은 '최근 에 사 용 된 데이터 가 중 용 될 확률 이 비교적 일찍 사 용 된 것 이 많다' 는 디자인 규칙 을 바탕 으로 이 루어 진 것 이다.
가장 오랫동안 접근 하지 않 은 데이터 항목 을 신속하게 삭제 하고 최신 데이터 항목 을 삽입 할 수 있 도록 캐 시 에 있 는 데이터 항목 을 양 방향 링크 로 연결 하고 링크 는 데이터 항목 이 최근 에서 가장 오래된 방문 순 서 를 유지 하도록 합 니 다.데이터 항목 이 조 회 될 때마다 이 데이터 항목 을 링크 머리 (O (1) 의 시간 복잡 도) 로 이동 합 니 다.이렇게 여러 번 검색 작업 을 한 후에 최근 에 사 용 된 내용 은 링크 의 머리 로 이동 하고 사용 되 지 않 은 내용 은 링크 의 뒤로 이동 합 니 다.교체 가 필요 할 때 링크 의 마지막 위 치 는 최근 에 가장 적 게 사용 되 는 데이터 항목 입 니 다. 우 리 는 최신 데이터 항목 을 링크 의 머리 에 놓 아야 합 니 다. Cache 가 가득 찼 을 때 링크 의 마지막 위 치 를 도태 시 키 면 됩 니 다.  주: 양 방향 링크 의 사용 에 대해 두 가지 고려 를 바탕 으로 합 니 다.우선 캐 시 에 있 는 블록의 명중 은 랜 덤 일 수 있 으 며 로드 가 들 어 오 는 순서 와 는 무관 합 니 다.그 다음으로 양 방향 링크 의 삽입, 삭제 가 빠 르 고 상호 간 의 순 서 를 유연 하 게 조정 할 수 있 으 며 시간 복잡 도 는 O (1) 이다.    링크 에서 요 소 를 찾 는 시간 복잡 도 는 O (n) 입 니 다. 명중 할 때마다 우 리 는 O (n) 의 시간 을 들 여 찾 아야 합 니 다. 다른 데이터 구 조 를 추가 하지 않 으 면 이것 이 우리 가 실현 할 수 있 는 가장 효율 적 입 니 다.현재 로 서 는 전체 알고리즘 의 병목 이 바로 이곳 을 찾 는 것 인 데 어떻게 해 야 검색 의 효율 을 높 일 수 있 습 니까?Hash 표, 맞 아, 바로 그것 이 야. 데이터 구조 에 있 는 이 유 는 검색 시간의 복잡 도가 O (1) 이기 때 문 이 야.
사고방식 을 정리 하 자. Cache 의 모든 데이터 블록 에 대해 우 리 는 하나의 데이터 구 조 를 설계 하여 Cache 블록의 내용 을 저장 하고 하나의 양 방향 체인 테이블 을 실현 한다. 그 중에서 속성 next 와 prev 시 양 방향 체인 테이블 의 두 바늘, key 는 저장 대상 의 키 값 에 사용 되 고 value 사용 자 는 cache 블록 대상 자 체 를 저장 해 야 한다.
 Cache 인터페이스:
조회:

키 값 에 따라 hashmap 를 조회 하고 명중 하면 노드 를 되 돌려 줍 니 다. 그렇지 않 으 면 null 로 돌아 갑 니 다.

양 방향 링크 에서 명중 한 노드 를 삭제 하고 표 머리 에 다시 삽입 합 니 다.

모든 조작의 복잡 도 는 O (1) 이다.

삽입:

새로운 노드 를 Hashmap

에 연결 합 니 다.

Cache 가 가득 차 면 양 방향 링크 의 끝 노드 를 삭제 하고 Hashmap 에 대응 하 는 기록

을 삭제 합 니 다.

새로운 노드 를 양 방향 링크 의 머리 에 삽입 합 니 다

업데이트:

와 조회 가 비슷 하 다

삭제:

양 방향 링크 와 Hashmap 에서 해당 하 는 기록 을 동시에 삭제 합 니 다.

LRU Cache 의 자바 구현:

public interface Cache<K extends Comparable, V> {
   V get(K obj);  //  
   void put(K key, V obj); //     
   void put(K key, V obj, long validTime);
   void remove(K key); //  
   Pair[] getAll();
   int size();
}
  public class Pair<K extends Comparable, V> implements Comparable<Pair> {
   public Pair(K key1, V value1) {
      this.key = key1;
      this.value = value1;
   }
   public K key;
   public V value;
   public boolean equals(Object obj) {
      if(obj instanceof Pair) {
         Pair p = (Pair)obj;
         return key.equals(p.key)&&value.equals(p.value);
      }
      return false;
   }
   @SuppressWarnings("unchecked")
   public int compareTo(Pair p) {
      int v = key.compareTo(p.key);
      if(v==0) {
         if(p.value instanceof Comparable) {
            return ((Comparable)value).compareTo(p.value);
         }
      }
      return v;
   }
   @Override
   public int hashCode() {
      return key.hashCode()^value.hashCode();
   }
   @Override
   public String toString() {
      return key+": "+value;
   }
}
 public class LRUCache<K extends Comparable, V> implements Cache<K, V>,
      Serializable {
   private static final long serialVersionUID = 3674312987828041877L;
   Map<K, Item> m_map = Collections.synchronizedMap(new HashMap<K, Item>());
   Item m_start = new Item();      //  
   Item m_end = new Item();        //  
   int m_maxSize;
   Object m_listLock = new Object();        //      
   static class Item {
      public Item(Comparable k, Object v, long e) {
         key = k;
         value = v;
         expires = e;
      }
      public Item() {}
      public Comparable key;        //  
      public Object value;          //  
       public long expires;          //   
      public Item previous;
      public Item next;
   }
   void removeItem(Item item) {
      synchronized(m_listLock) {
         item.previous.next = item.next;
         item.next.previous = item.previous;
      }
   }
   void insertHead(Item item) {
      synchronized(m_listLock) {
         item.previous = m_start;
         item.next = m_start.next;
         m_start.next.previous = item;
         m_start.next = item;
      }
   }
   void moveToHead(Item item) {
      synchronized(m_listLock) {
         item.previous.next = item.next;
         item.next.previous = item.previous;
         item.previous = m_start;
         item.next = m_start.next;
         m_start.next.previous = item;
         m_start.next = item;
      }
   }
   public LRUCache(int maxObjects) {
      m_maxSize = maxObjects;
      m_start.next = m_end;
      m_end.previous = m_start;
   }
   @SuppressWarnings("unchecked")
   public Pair[] getAll() {
      Pair p[] = new Pair[m_maxSize];
      int count = 0;
      synchronized(m_listLock) {
         Item cur = m_start.next;
         while(cur!=m_end) {
            p[count] = new Pair(cur.key, cur.value);
            ++count;
            cur = cur.next;
         }
      }
      Pair np[] = new Pair[count];
      System.arraycopy(p, 0, np, 0, count);
      return np;
   }
   @SuppressWarnings("unchecked")
   public V get(K key) {
      Item cur = m_map.get(key);
      if(cur==null) {
         return null;
      }
     //       
      if(System.currentTimeMillis()>cur.expires) {
         m_map.remove(cur.key);
         removeItem(cur);
         return null;
      }
      if(cur!=m_start.next) {
         moveToHead(cur);
      }
      return (V)cur.value;
   }
   public void put(K key, V obj) {
      put(key, obj, -1);
   }
   public void put(K key, V value, long validTime) {
      Item cur = m_map.get(key);
      if(cur!=null) {
         cur.value = value;
         if(validTime>0) {
            cur.expires = System.currentTimeMillis()+validTime;
         }
         else {
            cur.expires = Long.MAX_VALUE;
         }
         moveToHead(cur);  //       ，     
         return;
      }
      if(m_map.size()>=m_maxSize) {
         cur = m_end.previous;
         m_map.remove(cur.key);
         removeItem(cur);
      }
      long expires=0;
      if(validTime>0) {
         expires = System.currentTimeMillis()+validTime;
      }
      else {
         expires = Long.MAX_VALUE;
      }
      Item item = new Item(key, value, expires);
      insertHead(item);
      m_map.put(key, item);
   }
   public void remove(K key) {
      Item cur = m_map.get(key);
      if(cur==null) {
         return;
      }
      m_map.remove(key);
      removeItem(cur);
   }
   public int size() {
      return m_map.size();
   }
}