ArrayMap, SparseArray, LruCache란

기본 자료 구조보다 더 메모리 효율적으로 구현한 자료 구조로, android.util 패키지에 포함되어 있습니다.

ArrayMap

HashMap을 개선한 버전입니다. HashMap보다 좀 더 메모리 효율적입니다.

HashMap

HashMap

ArrayMap

ArrayMap

특징

  • 구조
    • HashMap
      • 배열 1개를 사용합니다.
      • 키와 값을 저장하는 배열
      • 키에 대해 Hash값을 구함 -> Hash값을 배열의 Index로 사용 -> 해당 Index에 값을 가져온다.
    • ArrayMap
      • 배열 2개를 사용합니다.
      • 키와 Hash값을 저장하는 배열, 키와 값의 쌍을 저장하는 배열
      • 키에 대해 Hash값을 구함 -> Hash값으로 Key Index를 구함 -> 키와 값 쌍 배열에서 Key Index에 해당하는 값을 가져온다.
  • 키 값 배열 크기 관리
    • 데이터가 추가(제거)되면 배열을 사용되는 만큼 확장(축소)합니다.’

장점

  • 낭비되는 메모리가 없습니다.
    • HashMap
      • Map이 비어있더라도 기본적인 크기만큼 메모리가 할당되어 메모리가 낭비됩니다.
    • ArrayMap
      • Map이 비어있으면, 아무것도 가지고 있지 않아 메모리가 할당되어 있지 않아 낭비되는 부분이 없습니다.
  • 데이터 처리 시 메모리 효율직입니다.
    • 키를 가지고 값을 찾을때 HashMap은 Iterator를 통해서 값을 찾지만, ArrayMap은 배열의 Index로 값을 찾기 때문에 메모리를 좀더 효율적으로 사용하게 됩니다.

단점

  • 데이터 조회 성능이 HashMap보다 떨어집니다.
    • ArrayMap은 대량의 데이터를 처리하기에는 적합하지 않습니다.
    • Hash계산으로 바로 값을 가져올 수 있는 HashMap와 달리 ArrayMap은 Hash계산 후 키와 값
  • 스레드 동기화에 취약합니다.
    • 인스턴스에 대해 동기화가 필요 없는 단일 스레드 환경에서 사용하기 적합합니다.

예제 코드

val arrayMap = ArrayMap<Long, String>()
arrayMap.put(1, "Dave") // id가 1인 Dave를 저장
val value = arrayMap.get("Name") // get name by id 1

SparseArray

기본 HashMap보다 더 메모리 효율적인 Map구조를 제공합니다. ArrayMap과 매우 유사합니다.

SparseArray

특징

  • 구조
    • Hashing없이 Primitive Int type인 키를 이진 검색으로 찾고, 값을 관리합니다.

장점

  • 메모리 효율적입니다.
    • AutoBoxing이 없습니다.
      • 일반적으로 Map은 키를 기본(Prmitive) Type(int)이 아닌 Wrapper Type(Integer)을 사용하기 때문에 추가적인 메모리 할당을 하고, 메모리 사용량이 늘어납니다. (Integer : 16 bytes, int : 4 bytes)
      • 그러나 SparseArray는 Primitive Type(int)을 사용하기 때문에 추가적인 메모리 할당이 없기 때문에 메모리 사용량이 더 적습니다.

단점

  • 데이터 조회 성능이 HashMap보다 떨어집니다.
    • SparseArray는 대량의 데이터를 처리하기에는 적합하지 않습니다.
    • Hash계산으로 바로 값을 가져올 수 있는 HashMap와 달리 SparseArray는 이진 검색으로 값을 찾기 때문에 처리 시간이 조금더 소요됩니다.
val sparseArray = SparseArray<String>()
sparseArray.put(1, "Dave") // id가 1인 Dave를 저장
val value = sparseArray.get(1) // get name by id 1

ArrayMap, SparseArray를 사용하기에 적합한 경우

  • 처리할 데이터의 개수가 1,000개 미만
  • Map의 값에 Map이 사용되는 경우

HashMap, ArrayMap, SparseArray 성능 비교

메모리 사용량 비교(낮을수록 우위)

SparseArray -> ArrayMap, HashMap(ArrayMap, HashMap은 비슷한 메모리 사용량을 보입니다.)

hashmap,arraymap,sparsearray메모리비교

데이터 조회 성능 비교(낮을수록 우위)

SparseArray -> HashMap -> ArrayMap 처리해야할 데이터의 개수가 5,000개 이상이 되면서부터 격차가 크게 벌어집니다.

hashmap,arraymap,sparsearray데이터조회성능비교

데이터 삽입 처리 시간 비교(낮을수록 우위)

SparseArray -> HashMap -> ArrayMap 처리해야할 데이터의 개수가 5,000개 이상이 되면서부터 격차가 크게 벌어집니다.

hashmap,arraymap,sparsearray데이터삽입처리소요시간비교

LruCache(Least Recently Used Cache)

Queue를 기반으로, 데이터 사용빈도에 따라 데이터가 삭제 및 관리되는 Caching 자료구조 입니다.

LruCache

특징

  • 구조
    • 내부적으로 LinkedListHashMap으로 구현되어 있으며 Queue를 기반으로 동작합니다.
    • Cache크기를 개발자가 정할 수 있습니다.
  • 동작
    • 데이터를 삽입할 때
      • Queue의 맨 앞에 데이터를 삽입합니다.
      • Cache크기가 가득 차있으면, 가장 오래된 데이터를 삭제하고 새로운 데이터를 삽입합니다.
      • Cache크기가 가득 차있지 않으면, 새로운 데이터를 삽입합니다.
    • 데이터를 조회할 때
      • 데이터가 존재하면, 해당 데이터를 반환하고, Queue의 맨 앞으로 이동시킵니다.
      • 데이터가 존재하지 않으면, null을 반환합니다.

Android 개발 시 주로 쓰이는 Glide 라이브러리가 기본적으로 사진 캐싱을 처리할 때 LruCache를 사용합니다.

잘 안쓰이는 데이터는 자동으로 제거되기 때문에 불필요한 메모리 할당을 막을 수 있어, 상당히 효율적인 자료구조라고 생각됩니다.

val nameCache = LruCache<Long, String>(10) // id to name
nameCache.put(1, "Dave") // id가 1인 Dave를 저장
val name = lruCache.get(1) // get name by id 1