Android LRuCache 캐 시 정책 에 대한 간단 한 설명

1.Android 의 캐 시 정책
일반적으로 캐 시 정책 은 캐 시 추가,가 져 오기,삭제 등 세 가지 작업 을 포함한다.캐 시 를 어떻게 추가 하고 가 져 오 는 지 이해 하기 쉽 습 니 다.그런데 왜 캐 시 를 삭제 해 야 합 니까?메모리 캐 시 든 하 드 디스크 캐 시 든 캐 시 크기 가 제한 되 어 있 기 때문이다.캐 시가 가득 찬 후에 캐 시 를 추가 하려 면 오래된 캐 시 를 삭제 하고 새 캐 시 를 추가 해 야 합 니 다.
따라서 LRU(Least Recently Used)캐 시 알고리즘 이 생 겨 났 다.LRU 는 최근 에 가장 적 게 사용 하 는 알고리즘 으로 캐 시가 가득 찼 을 때 최근 에 가장 적 게 사용 하 는 캐 시 대상 을 우선 도태 시 키 는 것 이 핵심 이다.LRU 알고리즘 을 사용 한 캐 시 는 두 가지 가 있 습 니 다.LRhcache 와 DisLRuCache 는 각각 메모리 캐 시 와 하 드 디스크 캐 시 를 실현 하 는 데 사 용 됩 니 다.그 핵심 사상 은 모두 LRU 캐 시 알고리즘 입 니 다.
2.LruCache 의 사용
루 캐 시 는 안 드 로 이 드 3.1 에서 제공 하 는 캐 시 클래스 이기 때문에 안 드 로 이 드 에 서 는 루 캐 시 를 직접 사용 해 메모리 캐 시 를 구현 할 수 있다.한편,DisLRuCache 는 현재 Android 에서 Android SDK 의 일부분 이 아니 지만 Android 공식 문 서 는 이 알고리즘 을 사용 하여 하 드 디스크 캐 시 를 실현 하 는 것 을 추천 합 니 다.
1.루 카 셰 의 소개
LruCache 는 일반적인 유형 으로 최근 에 사용 한 대상 을 강 한 인용(즉,우리 가 평소에 사용 하 는 대상 참조 방식)으로 LinkedHashMap 에 저장 하 는 것 이 주요 알고리즘 원리 이다.캐 시 가 가득 찼 을 때 최근 에 가장 적 게 사용 한 대상 을 메모리 에서 제거 하고 get 과 put 방법 을 제공 하여 캐 시 가 져 오기 와 추가 작업 을 완성 합 니 다.
2.LruCache 사용
LruCache 의 사용 은 매우 간단 합 니 다.그림 캐 시 를 예 로 들 었 습 니 다.

int maxMemory = (int) (Runtime.getRuntime().totalMemory()/1024);
int cacheSize = maxMemory/8;
mMemoryCache = new LruCache<String,Bitmap>(cacheSize){
  @Override
  protected int sizeOf(String key, Bitmap value) {
  return value.getRowBytes()*value.getHeight()/1024
  ;
}

① 현재 프로 세 스 가 사용 할 수 있 는 용량 의 8 분 의 1 크기 로 LruCache 캐 시 크기 를 설정 합 니 다.
② size Of 를 다시 쓰 는 방법 으로 캐 시 할 그림 의 크기 를 계산 합 니 다.
메모:캐 시 총 용량 은 캐 시 대상 의 크기 에 사용 되 는 단위 와 일치 해 야 합 니 다.
3.LruCache 의 실현 원리
LruCache 의 핵심 사상 은 이해 하기 쉽 습 니 다.캐 시 대상 목록 을 유지 하 는 것 입 니 다.그 중에서 대상 목록 의 배열 방식 은 방문 순서에 따라 이 루어 집 니 다.즉,방문 하지 않 은 대상 은 팀 의 끝 에 두 고 곧 도 태 될 것 입 니 다.최근 방문 대상 은 팀 에 두 고 탈락 한다.
다음 그림 에서 보 듯 이:

그렇다면 이 대기 열 은 누가 지 키 는 것 일 까?앞서 링크 드 하 쉬 맵 이 지 키 는 것 을 소개 했다.한편,링크 드 하 쉬 맵 은 배열+양 방향 링크 의 데이터 구조 로 이 루어 진다.그 중에서 양 방향 링크 의 구 조 는 방문 순서 와 삽입 순 서 를 실현 하여 링크 드 HashMap 의 쌍 을 일정한 순서에 따라 배열 할 수 있다.
아래 구조 함 수 를 통 해 링크 드 HashMap 의 양 방향 링크 구 조 를 방문 순서 로 지정 합 니까?삽입 순서 로 지정 합 니까?

public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

그 중에서 accessOrder 는 true 로 설정 하면 방문 순서 이 고 false 이 며 삽입 순서 입 니 다.
구체 적 인 예 로 설명:true 로 설정 되 었 을 때

public static final void main(String[] args) {
  LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>(0, 0.75f, true);
  map.put(0, 0);
  map.put(1, 1);
  map.put(2, 2);
  map.put(3, 3);
  map.put(4, 4);
  map.put(5, 5);
  map.put(6, 6);
  map.get(1);
  map.get(2);
  for (Map.Entry<Integer, Integer> entry : map.entrySet())
  {
    System.out.println(entry.getKey() + ":" + entry.getValue());
  }
}

출력 결과:0:0 3:3 4:4 5:5 6:6 1:1 2:2
최근 에 방문 한 마지막 출력 이 라면 LRU 캐 시 알고리즘 에 딱 맞 는 생각 입 니 다.이 를 통 해 알 수 있 듯 이 루 캐 시가 교묘 하 게 실현 한 것 은 바로 링크 드 하 쉬 맵 의 이러한 데이터 구 조 를 이용 한 것 이다.
다음은 LruCache 소스 코드 에서 LinkedHashMap 을 어떻게 사용 하여 캐 시 추가,획득,삭 제 를 실현 하 는 지 구체 적 으로 살 펴 보 겠 습 니 다.

public LruCache(int maxSize) {
  if (maxSize <= 0) {
    throw new IllegalArgumentException("maxSize <= 0");
  }
  this.maxSize = maxSize;
  this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}

LruCache 의 구조 함수 에서 바로 LinkedHashMap 의 접근 순 서 를 사용 한 것 을 볼 수 있 습 니 다.
put()방법:

public final V put(K key, V value) {
  //    ，      
  if (key == null || value == null) {
    throw new NullPointerException("key == null || value== null");
  }
  V previous;
  synchronized (this) {
    //         1
    putCount++;
    //         
    size += safeSizeOf(key, value);
    // map       
    previous = map.put(key, value);
    //        ，          
    if (previous != null) {
      size -= safeSizeOf(key, previous);
    }
  }
  //entryRemoved()     ，      
  if (previous != null) {
    entryRemoved(false, key, previous, value);
  }
  //      (    )
  trimToSize(maxSize);
  return previous;
}

put()방법 은 어 려 운 점 이 없 음 을 알 수 있 습 니 다.중요 한 것 은 캐 시 대상 을 추가 한 후 trimToSize()방법 을 사용 하여 캐 시가 가득 찼 는 지 여 부 를 판단 하 는 것 입 니 다.가득 차 면 최근 에 가장 적 게 사용 하 는 알고리즘 을 삭제 해 야 합 니 다.
trimToSize()방법:

public void trimToSize(int maxSize) {
  //   
  while (true) {
    K key;
    V value;
    synchronized (this) {
      //  map      size   0    size  0，    
      if (size < 0 || (map.isEmpty() && size != 0)) {
        throw new IllegalStateException(getClass().getName()+ ".sizeOf() is reporting inconsistent results!");
      }
      //      size      ，  map  ，          ，    
      if (size <= maxSize || map.isEmpty()) {
        break;
      }
      //          ，      ，         
      Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
      key = toEvict.getKey();
      value = toEvict.getValue();
      //     ，       
      map.remove(key);
      size -= safeSizeOf(key, value);
      evictionCount++;
    }
    entryRemoved(true, key, value, null);
  }
}

trimToSize()방법 은 캐 시 크기 가 최대 치 보다 작 을 때 까지 링크 드 HashMap 의 끝 요 소 를 계속 삭제 합 니 다.
LruCache 의 get()방법 을 호출 하여 집합 에 있 는 캐 시 대상 을 가 져 올 때 이 요 소 를 한 번 방문 한 것 을 의미 합 니 다.대기 열 을 업데이트 하고 전체 대기 열 을 방문 순서에 따라 정렬 합 니 다.이 업데이트 과정 은 링크 드 HashMap 의 get()방법 에서 이 루어 졌 습 니 다.
LruCache 의 get()방법 먼저 보기:

public final V get(K key) {
  //key      
  if (key == null) {
    throw new NullPointerException("key == null");
  }
  V mapValue;
  synchronized (this) {
    //         
    //get()                     
    mapValue = map.get(key);
    if (mapValue != null) {
    hitCount++;
    return mapValue;
  }
  missCount++;
}

그 중에서 LinkedHashMap 의 get()방법 은 다음 과 같다.

public V get(Object key) {
  LinkedHashMapEntry<K,V> e = (LinkedHashMapEntry<K,V>)getEntry(key);
  if (e == null)
    return null;
  //         
  e.recordAccess(this);
  return e.value;
}

recordAccess()를 호출 하 는 방법 은 다음 과 같 습 니 다.

void recordAccess(HashMap<K,V> m) {
  LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
  //         
  if (lm.accessOrder) {
    lm.modCount++;
    //     
    remove();
    //            
    addBefore(lm.header);
  }
}

이 를 통 해 알 수 있 듯 이 LruCache 에서 집합 LinkedHashMap 을 유지 하고 있 습 니 다.이 LinkedHashMap 은 방문 순서 로 정렬 되 어 있 습 니 다.put()방법 을 호출 할 때 결합 에 요 소 를 추가 하고 trimToSize()를 호출 하여 캐 시가 가득 찼 는 지 여 부 를 판단 합 니 다.가득 차 면 링크 드 HashMap 의 교체 기 를 사용 하여 팀 의 꼬리 요 소 를 삭제 합 니 다.즉,최근 에 가장 적 게 접근 한 요 소 를 삭제 합 니 다.get()방법 으로 캐 시 대상 에 접근 할 때 링크 드 HashMap 의 get()방법 으로 해당 하 는 집합 요 소 를 얻 고 이 요 소 를 팀 헤드 로 업데이트 합 니 다.
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.