[Android] SparseArray 찍먹해보기

안드로이드 개발시 사용할 수 있는 다양한 자료구조 중, SparseArray 라는 것이 있다. 사람들은 이것을 종종 키 값을 정수형으로 가지는 HashMap 자료구조를 사용할 때 알게 된다. 왜냐하면 안드로이드 스튜디오에서 Integer 타입을 키 값으로 가지는 HashMap 을 사용하면, SparseArray 를 사용하라는 워닝을 띄우기 때문이다. 그렇다면 SparseArray 는 뭐가 그리 잘났길래 안드로이드 차원에서 밀어주는 것일까?

SparseArray

우선, 영어단어 Sparse 에 대해 알아보면 다음과 같은 뜻을 지니고 있다.

‘드문’, ‘희박한

SparseArray 의 특성을 이해한다면, 이름이 왜 Sparse 인지 이해될 것이다.

SparseArray 개념

우선, 공식문서에서 소개하는 SparseArray 의 개념은 다음과 같다.

SparseArray maps integers to Objects and, unlike a normal array of Objects, its indices can contain gaps. SparseArray is intended to be more memory-efficient than a [HashMap](https://developer.android.com/reference/java/util/HashMap), because it avoids auto-boxing keys and its data structure doesn't rely on an extra entry object for each mapping.

위 설명대로, SparseArray 는 Integer 키 값에 대해 Object를 매핑해주는 자료구조이다. 그리고 배열임에도 각 인덱스 사이에 빈 공간을 만들 수 있다. 예를 들어 1번에 객체가 담겨있는데, 2번을 건너뛰고 3번에 객체가 담겨있을 수 있다는 의미이다. 즉, Sparse(드문드문)하게 객체가 담겨있는 배열이라는 닉값을 하는 녀석이다.

이 때, HashMap 과는 달리 내부에서 별다른 객체를 생성하지 않고, 그렇기 때문에 Wrapper 클래스로 Boxing 할 필요가 없어 공간적으로 퍼포먼스가 더욱 우수하다. (즉, Auto-Boxing 을 피한다)

공식 문서는 아래와 같이 SparseArray 에 적용된 최적화 관련 설명도 덧붙여주고 있다.

To help with performance, the container includes an optimization when removing keys: instead of compacting its array immediately, it leaves the removed entry marked as deleted. The entry can then be re-used for the same key or compacted later in a single garbage collection of all removed entries. This garbage collection must be performed whenever the array needs to be grown, or when the map size or entry values are retrieved.

위 설명에 따르면, SparseArray 는 성능 향상을 위해 특정 Key-Value 매핑 데이터 제거 시에 실제로 제거하여 배열 컴팩팅을 진행하는 것이 아닌, Deleted 상태로 표시만 해둔다. 만약 해당 Value 를 가리키는 Key 에 또 다른 데이터가 추가된다면 다시 채워진다. 이러한 최적화 덕에 삭제 연산 효율이 높아진다.

SparseArray 는 다음과 같이 사용할 수 있다. (이번 포스팅에선 자세한 사용법은 다루지 않겠다)

private val DEFAULT_ORIENTATIONS = SparseIntArray().apply {
    append(Surface.ROTATION_0, 90)
    append(Surface.ROTATION_90, 0)
    append(Surface.ROTATION_180, 270)
    append(Surface.ROTATION_270, 180)
}

private val INVERSE_ORIENTATIONS = SparseIntArray().apply {
    append(Surface.ROTATION_0, 270)
    append(Surface.ROTATION_90, 180)
    append(Surface.ROTATION_180, 90)
    append(Surface.ROTATION_270, 0)
}

SparseArray 사용시 주의점

SparseArray 는 배열 구조로 Key→Value 매핑 정보를 저장하고, 해당 배열을 이분 탐색하여 키를 찾게 된다. 이러한 특성때문에, 매우 많은 수의 아이템을 저장하는 상황에는 그리 적합하지 않다. 이분 탐색을 수행한다는 점, 그리고 데이터가 방대한 경우 삽입 삭제 연산이 배열 자료구조에선 느리게 동작한다는 점 등이 원인이다. 즉, 시간 복잡도 측면에서의 성능은 비교적 안 좋다.

다만 수백 개 데이터가 넘어가지 않는 한 이분 탐색 소요시간도 상수시간에 수렴하고, 삽입 삭제 등의 연산도 빠르기 때문에 HashMap 보다 좋은 성능을 낸다. 따라서 적절히 적은 데이터를 매핑할 때 사용하면 좋을 것 같다.