안드로이드의 SparseArray

SparseArray는 정수(int) 키를 객체 값에 매핑하는 안드로이드 전용 자료구조로, HashMap<Integer, Object>보다 메모리 효율이 높은 대안으로 설계되었습니다. 원시 타입(primitive type) int 키를 Integer 래퍼 객체로 변환하는 오토박싱(autoboxing) 오버헤드를 피할 수 있으며, 내부적으로 해시 테이블 대신 두 개의 병렬 배열을 사용합니다. SparseArray를 표준 맵 구현체 대신 언제, 왜 사용해야 하는지 이해하는 것은 안드로이드 면접에서 자주 다루어지는 주제입니다. 특히 메모리 제약이 있는 모바일 환경에서 자료구조 선택이 앱 성능에 미치는 영향을 설명할 수 있다면, 면접관에게 깊은 인상을 줄 수 있습니다.

이번 면접 질문을 통하여 아래 내용들을 학습하실 수 있습니다.

• SparseArray의 내부 자료구조와 HashMap과의 차이점을 설명할 수 있습니다.
• 데이터셋 크기에 따른 SparseArray와 HashMap의 성능 트레이드오프를 비교할 수 있습니다.
• SparseArray와 타입별 변형(SparseBooleanArray, SparseIntArray, SparseLongArray)을 올바르게 사용할 수 있습니다.
• SparseArray가 표준 컬렉션보다 실질적인 이점을 제공하는 상황을 파악할 수 있습니다.

내부 구조

SparseArray는 키와 값을 두 개의 별도 배열에 저장합니다. 키 배열은 int[]이고, 값 배열은 Object[]입니다. 키 배열은 항상 정렬된 상태를 유지하며, 특정 키를 조회할 때 이진 탐색(binary search)을 사용하여 인덱스를 찾습니다. 찾은 인덱스를 그대로 값 배열에 적용하여 해당 값을 가져오는 구조입니다.

val sparseArray = SparseArray<String>()
sparseArray.put(10, "ten")
sparseArray.put(3, "three")
sparseArray.put(7, "seven")

// 내부 구조: keys = [3, 7, 10]
//           values = ["three", "seven", "ten"]
val result = sparseArray[7] // 키 배열에서 이진 탐색 -> "seven"

반면 HashMap은 각 키-값 쌍마다 Entry 객체를 별도로 할당하고, 원시 int 키를 Integer 객체로 박싱하며, 충돌 해소를 위해 연결 리스트(linked list) 또는 트리(tree) 구조를 가진 해시 테이블을 사용합니다. 각 Entry는 키, 값, 해시 코드, 다음 Entry에 대한 참조를 모두 보유하고 있어 메모리 사용량이 더 큽니다.

메모리 효율성

SparseArray가 메모리를 절약하는 원리는 크게 세 가지입니다. 첫째, 키를 박싱된 Integer 객체가 아닌 원시 int 값으로 저장하므로, 64비트 런타임 기준으로 항목당 약 16바이트를 절약합니다. 둘째, Entry 래퍼 객체를 생성하지 않아 항목당 약 32바이트의 추가 오버헤드가 사라집니다. 셋째, 두 개의 백업 배열이 메모리상에서 연속적(contiguous)으로 배치되어 캐시 지역성(cache locality)이 높아집니다. 캐시 지역성이란 데이터가 메모리에 가까이 모여 있을수록 CPU 캐시 적중률이 높아져 접근 속도가 빨라지는 것을 의미합니다.

100개 항목을 가진 데이터셋의 경우, HashMap<Integer, String>은 값 자체 외에 약 100개의 Integer 객체와 100개의 Entry 객체를 추가로 할당합니다. SparseArray는 두 개의 백업 배열만 할당하면 됩니다. 메모리가 제한된 모바일 디바이스에서 여러 개의 희소 맵(sparse map)을 동시에 사용하면 이 차이가 누적되어 상당한 영향을 미칠 수 있습니다.