LRUCache 파악 해보기

androidx.collection.LruCache

• LRU
  • Least Recently Used
  • 최근에 사용되지 않는 페이지 교체 알고리즘
• 최대 사이즈를 고정적으로 설정해야함
• 데이터를 추가하여 최대 사이즈를 넘었을 때, 가장 오래된 데이터 삭제
• 저장된 데이터를 읽을 경우, 데이터가 가장 최근 추가된 것으로 이동
• 최종적으로 주로 쓰이지 않는 데이터는 삭제
  • 캐시의 히트율 증폭

---

class 내부 구현 구조

package androidx.collection

private const val MAX_SIZE = Int.MAX_VALUE.toLong()

public open class LruCache<K : Any, V : Any>
public constructor(@IntRange(from = 1, to = MAX_SIZE) private var maxSize: Int) {
    init {
        requirePrecondition(maxSize > 0) { "maxSize <= 0" }
    }
    
    private val map = LruHashMap<K, V>(0, 0.75f)
    private val lock = Lock()
	 // ...   
}

package androidx.collection.internal

import androidx.annotation.RestrictTo

internal actual class LruHashMap<K : Any, V : Any>
actual constructor(
    initialCapacity: Int,
    loadFactor: Float,
) {

    actual constructor(original: LruHashMap<out K, V>) : this() {
        for ((key, value) in original.entries) {
            put(key, value)
        }
    }

    private val map = LinkedHashMap<K, V>(initialCapacity, loadFactor, true)

    // ...
}

• LinkedHashMap 을 이용하여 구현됨

package java.util;

public class LinkedHashMap<K, V> extends HashMap<K, V> implements SequencedMap<K, V> {
    private static final long serialVersionUID = 3801124242820219131L;
    transient Entry<K, V> head;
    transient Entry<K, V> tail;
    final boolean accessOrder;
    static final int PUT_NORM = 0;
    static final int PUT_FIRST = 1;
    static final int PUT_LAST = 2;
    transient int putMode = 0;
    
	 // ...   
}

---

LinkedHashMap

• HashMap의 기능
• 입력한 순서 유지
  • 이중 linkedList를 이용하여 관리
• accessOrder를 true로 설정하면 접근 데이터의 순서가 뒤로 이동하게 됨

---

LruCache Lock

• LinkedHashMap이 동기화 처리가 되지 않기 때문에 선언

public operator fun get(key: K): V? {
    var mapValue: V?
    lock.synchronized {
        mapValue = map[key]
        if (mapValue != null) {
            hitCount++
            return mapValue
        }
        missCount++
    }

    /*
     * 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.
     */
    val createdValue = create(key) ?: return null

    lock.synchronized {
        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)
        }
    }

    return if (mapValue != null) {
        entryRemoved(false, key, createdValue, mapValue)
        mapValue
    } else {
        trimToSize(maxSize)
        createdValue
    }
}