LruCache 기본 원리 와 분석

8648 단어 nginx
1. LruCache 기본 원리
LRU 는 모두 Least Recently Used 라 고 하 는데, 즉 최근 에 가장 적 게 사용 하 는 것 이다.
LRU 알고리즘 은 캐 시 공간 이 가득 찼 을 때 최근 에 가장 적 게 사용 한 데 이 터 를 캐 시 공간 에서 삭제 하여 사용 가능 한 캐 시 공간 을 늘 려 새 데 이 터 를 캐 시 하 는 것 입 니 다.
이 알고리즘 은 내부 에 캐 시 목록 이 있 습 니 다. 캐 시 데이터 가 접근 할 때마다 이 데 이 터 는 목록 의 끝 부분 에 언급 됩 니 다. 매번 이 럴 때마다 목록 의 머리 데 이 터 는 최근 에 가장 자주 사용 되 지 않 습 니 다. 캐 시 공간 이 부족 할 때 열 표 머리의 캐 시 데 이 터 를 삭제 합 니 다.
2. LruCache 의 사용
//                  
int maxMemory=(int)(Runtime.getRuntime().maxMemory()/1024);
int cacheSize=maxMemory/8; 
private LruCache mMemoryCache;
// LruCache  1/8 
mMemoryCache = new LruCache(mCacheSize){  
    //     ,   Bitmap     
    @Override  
    protected int sizeOf(String key, Bitmap value) {  
        return value.getRowBytes() * value.getHeight()/1024;  
    }  
};


3. LruCache 부분 소스 코드 분석
LruCache 는 LinkedHashMap 의 한 특성 (accessOrder = true 접근 순서 기반) 을 이용 하여 LinkedHashMap 의 데이터 조작 잠 금 에 대한 캐 시 정책 을 추가 합 니 다.
링크 드 HashMap 의 기본 구조 적 인 파 라 메 터 는 기본 삽입 순서 입 니 다. 즉, 당신 이 삽입 한 순서 가 무엇 인지, 읽 은 순서 가 무엇 인지 말 합 니 다. 하지만 방문 순서 도 있 습 니 다. 즉, 키 를 방문 했다 는 것 입 니 다. 이 키 는 맨 뒤로 달 려 갔습니다.
LruCache 의 데이터 캐 시 는 메모리 에 있 습 니 다.
  • 먼저 내부 링크 드 HashMap 구조 파라미터 accessOrder = true 를 설정 하여 데 이 터 를 방문 순서에 따라 정렬 하 는 것 을 실현 했다.
  • LruCache 클래스 는 get (K key) 방법 을 호출 할 때 LinkedHashMap. get (Object key) 을 호출 합 니 다.accessOrder = true 를 설정 한 후 링크 드 HashMap. get (Object key) 을 호출 하면 링크 드 HashMap 의 after NodeAccess () 방법 을 통 해 데 이 터 를 팀 끝으로 이동 합 니 다.
  • 최근 에 방문 한 데이터 가 끝 에 있 기 때문에 put 와 trimToSize 의 방법 으로 실 행 된 경우 데이터 제거 가 발생 하면 머리 데 이 터 를 우선 제거 합 니 다
  • 1. 구조 방법
     
    
        /**
         * @param maxSize for caches that do not override {@link #sizeOf}, this is
         *     the maximum number of entries in the cache. For all other caches,
         *     this is the maximum sum of the sizes of the entries in this cache.
         */
        public LruCache(int maxSize) {
            if (maxSize <= 0) {
                throw new IllegalArgumentException("maxSize <= 0");
            }
            this.maxSize = maxSize;
            this.map = new LinkedHashMap(0, 0.75f, true);
        }
        
    

    LinkedHashMap 매개 변수 소개:
  • initialCapacity 는 이 링크 드 HashMap 의 크기 를 초기 화 하 는 데 사 용 됩 니 다.
  • loadFactor (부하 인자) 라 는 링크 드 HashMap 의 부모 클래스 HashMap 의 구조 적 인 파 라 메 터 는 확장 문제 와 관련된다. 예 를 들 어 HashMap 의 최대 용량 은 100 이 고 여기에 0.75f 를 설정 하면 75 시 까지 확장 된다.
  • accessOrder, 이 매개 변 수 는 정렬 모드 입 니 다. true 는 방문 할 때 정렬 하 는 것 을 표시 합 니 다 (LruCache 핵심 작업 원리 가 여기에 있 습 니 다). false 는 삽입 할 때 정렬 하 는 것 을 표시 합 니 다.

  • 2. 데이터 추가 LruCache. put (K key, V value)
     
    /**
         * Caches {@code value} for {@code key}. The value is moved to the head of
         * the queue.
         *
         * @return the previous value mapped by {@code key}.
         */
        public final V put(K key, V value) {
            if (key == null || value == null) {
                throw new NullPointerException("key == null || value == null");
            }
    
            V previous;
            synchronized (this) {
                putCount++;
                 //safeSizeOf(key, value)。
                 //        1,          1.
                //           ,  size              ,           sizeOf(key, value)  
                size += safeSizeOf(key, value);
                // map       ,       ,      ,          ,   null
                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;
        }
    
    
    
  • 처음에 LinkedHashMap 에 값 을 넣 었 습 니 다. 설정 한 캐 시 용량 을 초과 하지 않 더 라 도.
  • safeSizeOf 방법 에 따라 이번에 추 가 된 데이터 의 용량 이 얼마 인지 계산 하고 size 에 넣는다.
  • 방법 이 마지막 까지 실 행 될 때 trimToSize () 방법 을 통 해 size 가 max Size 보다 큰 지 판단 한다.

  • put () 방법 은 논리 가 많 지 않 은 것 을 볼 수 있 습 니 다. 중요 한 것 은 캐 시 대상 을 추가 한 후에 trimToSize () 방법 을 사용 하여 캐 시가 가득 찼 는 지 여 부 를 판단 하 는 것 입 니 다. 가득 차 면 최근 에 가장 적 게 사용 한 데 이 터 를 삭제 해 야 합 니 다.
    2.trimToSize(int maxSize)
     
    /**
         * Remove the eldest entries until the total of remaining entries is at or
         * below the requested size.
         *
         * @param maxSize the maximum size of the cache before returning. May be -1
         *            to evict even 0-sized elements.
         */
        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      ,          ,    
                    if (size <= maxSize) {
                        break;
                    }
         //                 ,    ,      ,       map   。
                    Map.Entry toEvict = map.eldest();
                    if (toEvict == null) {
                        break;
                    }
    
                    key = toEvict.getKey();
                    value = toEvict.getValue();
                    map.remove(key);
                    size -= safeSizeOf(key, value);
                    //    +1
                    evictionCount++;
                }
    
                entryRemoved(true, key, value, null);
            }
        }
    
    
    

     
    /**
     * Returns the eldest entry in the map, or {@code null} if the map is empty.
     *
     * Android-added.
     *
     * @hide
     */
    public Map.Entry eldest() {
        Entry eldest = header.after;
        return eldest != header ? eldest : null;
    }
    

    trimToSize () 방법 은 캐 시 크기 가 최대 치 보다 작 을 때 까지 링크 드 HashMap 의 첫 번 째 요 소 를 계속 삭제 합 니 다.
    3.LruCache.get(K key)
     
        /**
         * Returns the value for {@code key} if it exists in the cache or can be
         * created by {@code #create}. If a value was returned, it is moved to the
         * head of the queue. This returns null if a value is not cached and cannot
         * be created.
         *   key       ,                ,                 ,
         * 
         */
        public final V get(K key) {
            if (key == null) {
                throw new NullPointerException("key == null");
            }
    
            V mapValue;
            synchronized (this) {
                  // LinkedHashMap     。
                mapValue = map.get(key);
                if (mapValue != null) {
                    hitCount++;
                    return mapValue;
                }
                missCount++;
            }
        /*
         *          
         *       create(K key)    null
         *                create(K key)   ,              
         */
            /*
             * Attempt to create a value. This may take a long time, and the map
             * may be different when create() returns. If a conflicting value was
             * added to the map while create() was working, we leave that value in
             * the map and release the created value.
             *  :    key              ,     creat(key)         。
             * create(key)       null,             。
             */
    
            V createdValue = create(key);
            if (createdValue == null) {
                return null;
            }
            //     create(key)  ,       ,          。
            synchronized (this) {
                createCount++;
                mapValue = map.put(key, createdValue);
    
                if (mapValue != null) {
                    // There was a conflict so undo that last put
                    map.put(key, mapValue);
                } else {
                    size += safeSizeOf(key, createdValue);
                }
            }
    
            if (mapValue != null) {
                entryRemoved(false, key, createdValue, mapValue);
                return mapValue;
            } else {
                trimToSize(maxSize);
                return createdValue;
            }
        }
    

    LruCache 의 get () 방법 을 호출 하여 집합 에 있 는 캐 시 대상 을 가 져 올 때 이 요 소 를 한 번 방문 한 것 을 의미 합 니 다. 대기 열 을 업데이트 하고 전체 대기 열 을 방문 순서에 따라 정렬 합 니 다. 이 업데이트 과정 은 LinkedHashMap 의 get () 방법 에서 이 루어 집 니 다.
    총결산
  • LruCache 에서 LinkedHashMap 집합 을 유 지 했 습 니 다. 이 LinkedHashMap 은 방문 순서 로 정렬 되 어 있 습 니 다.
  • put () 방법 을 호출 할 때 집합 에 요 소 를 추가 하고 trimToSize () 를 호출 하여 캐 시가 가득 찼 는 지 판단 합 니 다. 가득 차 면 LinkedHashMap 의 교체 기 를 사용 하여 팀 의 첫 번 째 요 소 를 삭제 합 니 다. 즉, 최근 에 가장 적 게 접근 한 요 소 를 삭제 합 니 다.
  • 캐 시 대상 에 get () 방법 으로 접근 할 때 LinkedHashMap 의 get () 방법 으로 대응 하 는 집합 요 소 를 얻 고 이 요 소 를 팀 끝으로 업데이트 합 니 다.
  • 좋은 웹페이지 즐겨찾기