SparseArray는 Android 플랫폼에서 제공하는 특화된 데이터 구조로, 특정 사용 사례에서 표준 Java 컬렉션인 HashMap<Integer, E>보다 뛰어난 성능과 메모리 효율성을 제공합니다. 주요 특징은 다음과 같습니다:
- 키-값 쌍 형태로 데이터를 저장하며, 내부적으로 이진 탐색을 사용하므로 탐색 시간 복잡도는 O(logN)입니다.
- 키를
int배열로 직접 저장하여HashMap사용 시 발생할 수 있는Integer객체의 박싱(boxing) 및 언박싱(unboxing) 오버헤드를 방지합니다. 이로 인해 성능이 향상되고,int는Integer객체보다 훨씬 적은 메모리 공간을 차지합니다. - 배열 기반 데이터 구조에서 삭제 및 재정렬로 인한 큰 오버헤드를 최적화하기 위해 지연 삭제(lazy deletion) 메커니즘을 채택합니다.
핵심 필드
public class OptimizedSparseArray<T> implements Cloneable {
private static final Object REMOVED_MARKER = new Object(); // 삭제된 항목을 표시하는 마커 객체
private boolean pendingCleanup = false; // 삭제된 항목이 있어 클린업이 필요한지 여부
private int[] keys; // 키를 저장하는 정수 배열, 항상 오름차순 정렬 상태 유지
private Object[] values; // 값 객체를 저장하는 배열
private int activeSize; // 현재 유효한(삭제되지 않은) 항목의 개수
// ... 기타 필드 및 생성자
}
REMOVED_MARKER:static final객체 인스턴스로, 키-값 쌍이 제거될 때 해당 값 위치에 이 마커를 설정하여 지연 삭제를 표시합니다.pendingCleanup:true일 경우, 데이터 구조 내에 지연 삭제된 항목이 있음을 나타내며, 이후 실제 정리 작업(가비지 컬렉션)이 필요함을 시사합니다.keys배열:int[]형태로 키를 저장합니다.HashMap과 달리 박싱/언박싱이 필요 없어 메모리 효율적이며, 이 배열의 요소들은 항상 오름차순으로 정렬되어 있어 이진 탐색이 가능합니다.values배열:keys배열의 인덱스에 따라 대응하는 값을 저장합니다. 만약 값도int타입이라면SparseIntArray를 사용하여 더욱 효율적인 저장이 가능합니다.activeSize:values배열에서REMOVED_MARKER가 아닌 유효한 항목의 총 개수를 나타냅니다.
삭제 메서드 (remove)
public void remove(int targetKey) {
// targetKey에 해당하는 인덱스를 이진 탐색으로 찾습니다.
// 발견되면 해당 인덱스를, 없으면 음수 값을 반환합니다.
int index = ArrayUtil.binarySearch(this.keys, this.activeSize, targetKey);
// 키가 배열 내에 존재하고, 이미 REMOVED_MARKER로 표시되지 않았다면
if (index >= 0 && this.values[index] != REMOVED_MARKER) {
// 해당 값을 REMOVED_MARKER로 교체하여 지연 삭제를 표시합니다.
this.values[index] = REMOVED_MARKER;
this.pendingCleanup = true; // 클린업이 필요함을 표시합니다.
}
}
// remove 메서드와 동일한 기능을 수행합니다.
public void deleteEntry(int keyToDelete) {
remove(keyToDelete);
}
// 항목을 제거하고 이전 값을 반환하는 메서드
public T removeAndReturn(int keyToRemove) {
int index = ArrayUtil.binarySearch(this.keys, this.activeSize, keyToRemove);
if (index >= 0 && this.values[index] != REMOVED_MARKER) {
@SuppressWarnings("unchecked")
final T oldValue = (T) this.values[index];
this.values[index] = REMOVED_MARKER;
this.pendingCleanup = true;
return oldValue;
}
return null;
}
remove 메서드는 먼저 ArrayUtil.binarySearch를 통해 대상 키의 인덱스를 찾습니다. 키가 발견되면 해당 인덱스에 있는 값을 REMOVED_MARKER 객체로 교체합니다. 이는 해당 항목이 논리적으로 삭제되었음을 의미하지만, 실제 배열에서는 공간을 그대로 차지하고 있습니다. 이와 동시에 pendingCleanup 플래그를 true로 설정하여 나중에 실제 정리 작업이 필요함을 알립니다. 이것이 바로 SparseArray의 지연 삭제 메커니즘입니다.
ArrayUtil.binarySearch 메서드는 일반적인 이진 탐색과 유사하지만, 키를 찾지 못했을 경우 음수 값을 반환한다는 중요한 차이점이 있습니다. 이 음수 값은 해당 키가 삽입되어야 할 이상적인 위치의 비트 반전(~를 사용) 형태입니다. 예를 들어, 배열 [10, 20, 40]에서 30을 찾으면 ~2를 반환하여 40 앞에 삽입되어야 함을 나타냅니다.
삽입 메서드 (put)
public void put(int newKey, T newValue) {
int insertionIndex = ArrayUtil.binarySearch(this.keys, this.activeSize, newKey);
if (insertionIndex >= 0) {
// 키가 이미 존재하면 값을 단순히 업데이트합니다.
this.values[insertionIndex] = newValue;
} else {
// 키를 찾지 못했으므로 삽입 지점을 계산합니다. (~insertionIndex는 실제 삽입될 인덱스)
insertionIndex = ~insertionIndex;
// 삽입 지점이 activeSize 범위 내에 있고, 해당 위치가 지연 삭제된 항목이라면 재활용합니다.
if (insertionIndex < this.activeSize && this.values[insertionIndex] == REMOVED_MARKER) {
this.keys[insertionIndex] = newKey;
this.values[insertionIndex] = newValue;
return;
}
// 지연 삭제된 항목이 있고 배열이 가득 찼다면 실제 정리 작업을 수행합니다.
if (this.pendingCleanup && this.activeSize >= this.keys.length) {
performCleanup(); // 실제 정리 작업을 호출합니다.
// 정리 후 배열 구조가 변경될 수 있으므로 다시 삽입 지점을 찾습니다.
insertionIndex = ~ArrayUtil.binarySearch(this.keys, this.activeSize, newKey);
}
// 새로운 항목을 삽입하고 기존 항목들을 뒤로 밀어냅니다.
this.keys = ArrayUtil.insertElement(this.keys, this.activeSize, insertionIndex, newKey);
this.values = ArrayUtil.insertElement(this.values, this.activeSize, insertionIndex, newValue);
this.activeSize++; // 유효 항목 수를 증가시킵니다.
}
}
put 메서드 또한 ArrayUtil.binarySearch로 시작합니다. 키를 발견하면 기존 값을 단순히 새 값으로 교체합니다. 키를 찾지 못했을 경우, 반환된 음수 값을 비트 반전(~ 연산)하여 실제 삽입되어야 할 인덱스(insertionIndex)를 얻습니다.
여기서 지연 삭제의 장점이 발휘됩니다. 만약 계산된 insertionIndex가 현재 activeSize 범위 내에 있고, 해당 위치의 값이 REMOVED_MARKER라면, 기존의 '삭제된' 슬롯을 새로운 키-값 쌍으로 바로 덮어씁니다. 이로써 배열 요소를 이동시키는 값비싼 작업을 피할 수 있습니다.
하지만 해당 위치가 지연 삭제된 슬롯이 아니거나 배열에 여유 공간이 없는 경우, pendingCleanup 플래그를 확인합니다. 이 플래그가 true이고 배열이 현재 유효한 항목으로 가득 찼다면, performCleanup() 메서드를 호출하여 실제 배열에서 REMOVED_MARKER 항목들을 제거하고 유효한 항목들을 앞으로 압축합니다. 정리 후에는 삽입 지점을 다시 계산한 다음, ArrayUtil.insertElement()를 사용하여 새로운 항목을 삽입하고 필요한 경우 배열을 확장하며 기존 요소들을 뒤로 밀어냅니다.
배열 요소 삽입 (ArrayUtil.insertElement)
public static int[] insertElement(int[] originalArray, int currentCount, int insertionIndex, int newElement) {
assert currentCount <= originalArray.length;
// 현재 배열에 공간이 충분한 경우
if (currentCount + 1 <= originalArray.length) {
System.arraycopy(originalArray, insertionIndex, originalArray, insertionIndex + 1, currentCount - insertionIndex);
originalArray[insertionIndex] = newElement;
return originalArray;
}
// 공간이 부족하여 배열을 확장해야 하는 경우
int[] newArray = new int[calculateNewCapacity(currentCount)]; // 새 크기 계산
System.arraycopy(originalArray, 0, newArray, 0, insertionIndex); // 삽입 지점 이전 복사
newArray[insertionIndex] = newElement; // 새 요소 삽입
System.arraycopy(originalArray, insertionIndex, newArray, insertionIndex + 1, originalArray.length - insertionIndex); // 삽입 지점 이후 복사
return newArray;
}
이 유틸리티 메서드는 배열에 새 요소를 삽입합니다. 현재 배열에 여유 공간이 있다면 System.arraycopy를 사용하여 삽입 지점 이후의 모든 요소를 한 칸씩 뒤로 밀어낸 후 새 요소를 삽입합니다. 공간이 부족하다면, 더 큰 새 배열을 할당하고 기존 요소를 복사한 다음 새 요소를 삽입하고 나머지 요소를 복사하는 방식으로 확장합니다.
정리 메서드 (performCleanup)
private void performCleanup() {
int currentValidCount = this.activeSize;
int writePosition = 0; // 유효한 항목이 작성될 다음 위치
int[] currentKeys = this.keys;
Object[] currentValues = this.values;
for (int readPosition = 0; readPosition < currentValidCount; readPosition++) {
Object valueToCheck = currentValues[readPosition];
// REMOVED_MARKER가 아닌 유효한 값만 앞으로 옮깁니다.
if (valueToCheck != REMOVED_MARKER) {
// 항목이 이미 올바른 위치에 있지 않다면 옮깁니다.
if (readPosition != writePosition) {
currentKeys[writePosition] = currentKeys[readPosition];
currentValues[writePosition] = valueToCheck;
currentValues[readPosition] = null; // 이전 참조 제거 (가비지 컬렉션 도움)
}
writePosition++;
}
}
this.pendingCleanup = false; // 정리 완료
this.activeSize = writePosition; // 유효 항목 수 업데이트
}
performCleanup() 메서드는 SparseArray 내부의 실제 "가비지 컬렉션"을 담당합니다. 이 메서드는 values 배열을 순회하며 REMOVED_MARKER가 아닌 유효한 값들만 배열의 앞부분으로 압축합니다. writePosition 변수는 유효한 항목이 작성될 다음 위치를 추적하며, readPosition은 배열을 순회합니다. 유효한 항목을 발견하면 writePosition으로 옮기고, 이전 위치의 값 참조는 null로 만들어 가비지 컬렉터가 해당 객체를 회수할 수 있도록 돕습니다. 이 과정이 끝나면 pendingCleanup을 false로 설정하고 activeSize를 실제 유효 항목의 개수로 업데이트합니다.
이때 중요한 점은, performCleanup이 호출된 후에도 keys.length와 values.length(배열의 물리적 크기)는 activeSize보다 클 수 있다는 것입니다. 즉, 배열의 끝부분에 이전 데이터의 잔해가 남아있을 수 있지만, activeSize가 유효한 데이터의 범위를 제한하므로 이러한 잔해는 접근되지 않으며 새로운 데이터가 삽입될 때 덮어씌워질 수 있습니다.
조회 메서드 (get)
public T get(int queryKey) {
return get(queryKey, null);
}
public T get(int queryKey, T defaultValue) {
int index = ArrayUtil.binarySearch(this.keys, this.activeSize, queryKey);
// 키가 없거나 해당 위치의 항목이 지연 삭제된 경우 기본값을 반환합니다.
if (index < 0 || this.values[index] == REMOVED_MARKER) {
return defaultValue;
} else {
// 유효한 값을 찾았으면 반환합니다.
@SuppressWarnings("unchecked")
T foundValue = (T) this.values[index];
return foundValue;
}
}
get 메서드는 제공된 키에 해당하는 값을 검색합니다. 먼저 ArrayUtil.binarySearch를 통해 키의 인덱스를 찾습니다. 키를 찾지 못했거나 (인덱스가 음수), 해당 인덱스의 값이 REMOVED_MARKER인 경우 (지연 삭제된 항목), 호출자가 제공한 기본값(또는 null)을 반환합니다. 그렇지 않으면 해당 인덱스의 실제 값을 반환합니다.
요약
SparseArray는 Android 환경에서 특정 상황에 최적화된 데이터 구조입니다:
- 지연 삭제 메커니즘을 사용하여 삭제된 키의
Value를REMOVED_MARKER로 설정함으로써 이후 해당 인덱스의 저장 공간을 재활용할 수 있습니다. - 이진 탐색을 기반으로 하며, 탐색 시간 복잡도는 O(logN)입니다. 키를 찾지 못할 경우, 반환된 음수 값의 비트 반전(~ 연산)을 통해 적절한 삽입 인덱스를 얻을 수 있습니다.
- 삽입 시, 지연 삭제된 슬롯이 있다면
System.arraycopy를 통한 배열 이동 없이 해당 슬롯을 재활용하여 성능을 최적화합니다. 그렇지 않은 경우,pendingCleanup플래그와 배열의 공간 여유에 따라performCleanup()을 호출하거나System.arraycopy를 통해 요소를 이동시키고 삽입합니다. activeSize는keys.length보다 작거나 같으며, 유효한 데이터의 범위를 나타냅니다.activeSize범위 내에 지연 삭제된 요소들이 포함될 수 있습니다.- 잦은 삭제 작업이 발생하고
performCleanup()이 적절히 트리거되지 않으면,activeSize가 실제 유효한 항목의 수보다 훨씬 커져 비효율적인 메모리 사용 및 성능 저하를 초래할 수 있습니다. - 주요
performCleanup트리거는put메서드 내에서 배열 공간이 부족하고pendingCleanup이true일 때입니다.
이러한 특성들을 고려할 때 SparseArray의 적절한 사용 시나리오는 다음과 같습니다:
- 키가 정수(
int) 타입일 때. - 데이터의 삽입 및 조회가 잦고, 삭제가 상대적으로 덜 빈번하거나 지연 삭제의 이점을 활용할 수 있을 때.
- 저장되는 요소의 개수가 극단적으로 많지 않을 때 (여전히 배열 기반이므로 매우 큰 데이터셋에서는 다른 자료구조가 유리할 수 있습니다).