LRUCache 의 실현 원리 및 python 을 이용 한 실현 방법

간단 한 소개
LRU(Least Recently Used)는 최근 에 가장 적 게 사용 하고 최근 에 시간 과 공간 이 최근 에 다른 의미 가 있어 서 최근 에 알고리즘 을 가장 적 게 사용 하 라 고 부 르 는 것 을 더 좋아 합 니 다.그것 의 핵심 사상 은 만약 에 데이터 가 방문 되 었 다 면 우 리 는 그것 이 앞으로 방문 할 확률 이 높다 고 믿 을 이유 가 있다 는 것 이다.따라서 LRU 캐 시가 설 정 된 최대 값 에 도 달 했 을 때 캐 시 에서 최근 에 가장 적 게 사용 한 대상 을 삭제 합 니 다.LRUCache 내 부 는 링크 드 HashMap 을 사용 하여 key-value 키 쌍 을 저장 하고 링크 드 HashMap 을 접근 순서 로 설정 하여 LRU 알고리즘 을 구현 합 니 다.
어떤 키 에 대한 get 이 든 set 이 든 이 키 에 대한 한 번 의 사용 이 라 고 할 수 있 습 니 다.set 에 존재 하지 않 는 key 가 있 고 LRU Cache 에서 key 의 수가 cache size 를 초과 할 때 사용 시간 이 현재 가장 긴 키 를 LRU Cache 에서 제거 해 야 합 니 다.
LRU Cache 구현
자바 에서 LRUCache 는 링크 드 해시 맵 을 통 해 이 루어 졌 다.저 는 고양이 가 호 랑 이 를 그 리 는 대로 Python 판 LRU Cache 를 실현 합 니 다.
우선,설명 이 필요 한 것 은:
LRU Cache 대상 내부 에서 양 끝 순환 링크 의 헤드 노드 를 유지 합 니 다.
LRU Cache 대상 내부 에서 dict 를 유지 합 니 다.
내부 dict 의 value 는 모두 Entry 대상 이 고 모든 Entry 대상 은 다음 과 같 습 니 다.

key 의 hashcode（hash_code=hash(key),이 구현 에서 hashcode 와 같은 다른 key 는 하나의 key 로 처 리 됩 니 다.따라서 사용자 정의 클래스 에 대해 마술 방법 을 실현 해 야 합 니 다:hash__）

v-(key,value)쌍 의 value

prev-이전 대상

next-다음 대상

구체 적 인 실현 은:
LRU Cache 에서 key 를 가 져 올 때:

이 키 를 계산 하 는 hashcode

내부 dict 에서 entry

이 entry 를 쌍 단 순환 링크 의 첫 번 째 위치 로 이동 합 니 다

entry.value 를 되 돌려 줍 니 다

LRU Cache 에 set(key,value)을 맞 출 때:
이 키 를 계산 하 는 hashcode，
LRU Cache 내부 dict 에서 이 hash 꺼 내기code 대응 oldentry(존재 하지 않 을 수 있 음),그리고(key,value)에 따라 new 생 성entry,이후 실행:

dict[hash_code] = new_entry

장군 newentry 쌍 단 순환 링크 의 첫 번 째 위치 언급

만약 oldentry 가 존재 하면 링크 에서 old 삭제entry

만약 에 하나의(key,value)쌍 이 추가 되 었 고 cache 에서 key 의 수량 이 cache size 를 초과 했다 면 쌍 단 링크 의 마지막 요 소 를 삭제 하고 내부 dict 에서 이 요 소 를 삭제 합 니 다

.
HashMap 의 실현 원리
(면접 과정 에서 도 자주 묻 습 니 다):배열 과 링크 를 조합 한 링크 해시 구 조 는 hash 알고리즘 을 통 해 배열 의 데 이 터 를 최대한 고 르 게 분포 합 니 다.hashcode 가 같 으 면 equals 방법 을 비교 하고 equals 방법 이 false 로 돌아 가면 데 이 터 를 링크 형식 으로 배열 의 대응 위치 에 저장 합 니 다.그리고 이 위치 에 있 던 데 이 터 를 링크 뒤로 이동 시 키 고 next 속성 을 기록 하여 뒤로 이동 하 는 데 이 터 를 표시 합 니 다.
메모:배열 에 저 장 된 것 은 entry(키 값 으로 저 장 된 것)입 니 다.
파 이 썬 구현

class Entry:
 def __init__(self, hash_code, v, prev=None, next=None):
 self.hash_code = hash_code
 self.v = v
 self.prev = prev
 self.next = next

 def __str__(self):
 return "Entry{hash_code=%d, v=%s}" % (
  self.hash_code, self.v)
 __repr__ = __str__

class LRUCache:
 def __init__(self, max_size):
 self._max_size = max_size
 self._dict = dict()
 self._head = Entry(None, None)
 self._head.prev = self._head
 self._head.next = self._head

 def __setitem__(self, k, v):
 try:
  hash_code = hash(k)
 except TypeError:
  raise

 old_entry = self._dict.get(hash_code)
 new_entry = Entry(hash_code, v)
 self._dict[hash_code] = new_entry

 if old_entry:
  prev = old_entry.prev
  next = old_entry.next
  prev.next = next
  next.prev = prev

 head = self._head
 head_prev = self._head.prev
 head_next = self._head.next

 head.next = new_entry
 if head_prev is head:
  head.prev = new_entry
 head_next.prev = new_entry
 new_entry.prev = head
 new_entry.next = head_next

 if not old_entry and len(self._dict) > self._max_size:
  last_one = head.prev
  last_one.prev.next = head
  head.prev = last_one.prev
  self._dict.pop(last_one.hash_code)

 def __getitem__(self, k):
 entry = self._dict[hash(k)]
 head = self._head
 head_next = head.next
 prev = entry.prev
 next = entry.next

 if entry.prev is not head:
  if head.prev is entry:
  head.prev = prev
  head.next = entry

  head_next.prev = entry
  entry.prev = head
  entry.next = head_next

  prev.next = next
  next.prev = prev

 return entry.v

 def get_dict(self):
 return self._dict

if __name__ == "__main__":
 cache = LRUCache(2)
 inner_dict = cache.get_dict()

 cache[1] = 1
 assert inner_dict.keys() == [1], "test 1"
 cache[2] = 2
 assert sorted(inner_dict.keys()) == [1, 2], "test 2"
 cache[3] = 3
 assert sorted(inner_dict.keys()) == [2, 3], "test 3"
 cache[2]
 assert sorted(inner_dict.keys()) == [2, 3], "test 4"
 assert inner_dict[hash(2)].next.v == 3
 cache[4] = 4
 assert sorted(inner_dict.keys()) == [2, 4], "test 5"
 assert inner_dict[hash(4)].v == 4, "test 6"

총결산
이상 은 이 글 의 전체 내용 입 니 다.본 논문 의 내용 이 여러분 의 학습 이나 업무 에 어느 정도 참고 학습 가치 가 있 기 를 바 랍 니 다.궁금 한 점 이 있 으 시 면 댓 글 을 남 겨 주 셔 서 저희 에 대한 지지 에 감 사 드 립 니 다.