SparseArray: 해석 과 실현
안 드 로 이 드 는 SparseArray 를 제공 하 는데, 이 는 KV 형식의 데이터 구조 로 맵 과 유사 한 기능 을 제공한다.하지만 실현 방법 은 HashMap 과 다르다.그것 은 맵 에 비해 각기 천추 라 고 할 수 있다.
장점.
결점.
전체적으로 말 하면 SparseArray 는 데이터 양 이 많 지 않 고 Key 는 디지털 형식의 장면 에 도 적용 된다.예 를 들 어 한 달 동안 매일 어떤 데 이 터 를 저장 하 는 것 은 최대 31 개 에 불과 하 며 키 도 숫자 (1 - 31 을 사용 할 수도 있 고 시간 스탬프 를 사용 할 수도 있다) 이다.예 를 들 어 userid 와 사용자 데이터 의 맵 을 저장 하려 면 이 걸 로 저장 할 수 있 습 니 다.
이어서 나 는 그것 의 특성 과 실현 세부 사항 을 설명 할 것 이다.
직관 적 인지
이 는 두 개의 배열 로 데 이 터 를 저장 하고 한 배열 은 key 를 저장 하 며 다른 배열 로 value 를 저장 합 니 다.우리 가 계속 증가 하면 서 데 이 터 를 삭제 하면 서 메모리 에 서 는 어 떻 습 니까?우 리 는 우리 가 그것 을 더욱 잘 이해 하고 체험 할 수 있 도록 직관 적 인 인식 이 필요 하 다.
초기 화 된 상태
내부 에 대응 하 는 데 이 터 를 저장 하 는 두 개의 배열 변수 가 있 습 니 다.
mKeys 는 key 를 저장 하 는 데 사 용 됩 니 다. mValues 는 일반적인 데 이 터 를 저장 하 는 데 사 용 됩 니 다. Object[] 이 아 닌 T[] 를 사용 합 니 다.왜 일 까요?이거 뒤에 얘 기해.데이터 삽입
아래 그림 에서 보 듯 이 데 이 터 를 삽입 하면 항상 배열 의 왼쪽 에 붙 어 있 습 니 다. 다시 말 하면 맨 왼쪽 의 빈 자리 부터 사용 합 니 다.내 가 처음에 자세히 탐구 하지 않 았 을 때, 모두 그것 이
HashMap 와 같은 희소 한 저장 소 라 고 생각 했다.또 다른 주의해 야 할 것 은 key 는 항상 질서 가 있 습 니 다. 몇 번 의 삽입 을 거치 더 라 도 key 배열 에서 key 는 항상 작은 것 에서 큰 것 으로 배열 되 어 있 습 니 다.
용량 을 늘리다
데 이 터 를 계속 삽입 하고 꽉 차 면 자동 으로 용량 을 늘 려 더 큰 그룹 을 만 들 고 기 존 데 이 터 를 모두 복사 한 다음 새로운 데 이 터 를 삽입 합 니 다.이것 은 배열 을 바탕 으로 이 루어 진 데이터 구조의 공 통 된 특성 이다.
삭제
삭 제 는 태그 로 삭제 하 는 방법 으로 대상 위치의 유효한 요 소 를 DELETED 태그 대상 으로 직접 설정 합 니 다.
조회 데이터
데 이 터 를 어떻게 찾 습 니까?예 를 들 어 우리 가 5 라 는 데이터
get(5) 를 찾 으 면 mKeys 에서 5 가 존재 하 는 지 찾 아 보고 index 를 되 돌려 준 다음 에 이 index 로 대응 하 는 mValues 에서 해당 하 는 값 을 꺼 내 면 됩 니 다.이루어지다
그 다음 에 우 리 는 자신의 이해 에 따라 이러한 데이터 구 조 를 실현 하고 그의 세부 적 인 부분 과 사상 을 배 우 며 이에 대한 이 해 를 강화 하면 생산 에서 더욱 효과 적 이 고 정확하게 사용 할 수 있다.
인터페이스 확인 (API)
우선 우리 가 어떤 기능 을 다른 사람 에 게 노출 시 켜 야 하 는 지 확인 해 보 자.물론 답 은 뻔 하 다. 당연히 삽입, 조회, 삭제 등 기능 이다.
public class SparseArray {
public SparseArray() {
}
public SparseArray(int initCap) {
}
public void put(int key, E value) {
}
public E get(int key) {
}
public void delete(int key) {
}
public int size() {
}
} 위 에 우리 가 필요 로 하 는 기능, 무 참 구조 함수, 매개 변수 구조 함수 (초기 용량 을 주동 적 으로 설정 할 수 있 기 를 기대 합 니 다), put 데이터, get 데이터, 데 이 터 를 삭제 하고 현재 데 이 터 를 얻 는 것 이 얼마나 되 는 지 열거 하 였 습 니 다.
put 방법 실현
put 데 이 터 는 가장 핵심 적 인 방법 입 니 다. 일반적으로 우 리 는 하 나 를 개발 하고 데 이 터 를 만 드 는 기능 을 먼저 개발 해 야 데 이 터 를 보 여 주 는 기능 을 개발 할 수 있 습 니 다.그 러 니까 우리 가 먼저 put 방법 을 실현 하 자.
이전의 이해 에 따 르 면, 우 리 는 일부 구성원 변수 로 데 이 터 를 저장 해 야 한다.
private int[] mKeys;
private Object[] mValues;
private int mSize = 0;put 가 어느 위치 에 있 는 지 먼저 찾 아야 합 니 다. 여기 에는 두 가지 상황 이 있 습 니 다.
public void put(int key, E value) {
int i = BinarySearch.search(mKeys, mSize, key);
if (i >= 0) {
//
// 1. mValues ，
// 2. mValues DELETED ， ，
mValues[i] = value;
} else {
}
}배열 에서 찾 으 면 조작 이 간단 하고 덮어 쓰 면 끝난다.
만약 에 찾 지 못 하면 우 리 는 데 이 터 를 정확 한 위치 에 삽입 해 야 한다. 이 정확 한 위치 란 삽입 후에 도 배열 의 질 서 를 확보 하 는 상황 을 말한다.예 를 들 어
1, 4, 5, 8 어디 에 삽입 해 야 합 니까? 당연히 3 에 넣 어야 합 니 다. 결 과 는 index=1 입 니 다.그럼 키 가 존재 하지 않 는 다 면 어디 에 두 어야 할 지 어떻게 알 아 요?
우 리 는 이 2 점 찾기 를 살 펴 보 자. 그것 은 우리 가 이 작은 문 제 를 해결 하 는 데 도움 을 주 었 다.
public static int search(int[] arr, int size, int target) {
int lo = 0;
int hi = size - 1;
while (lo <= hi) {
final int mid = (lo + hi) >>> 1;
final int value = arr[mid];
if (value == target) {
return mid;
} else if (value > target) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
return ~lo;
}전통 적 인 사상 에 따 르 면 클래스 의 API 를 찾 습 니 다. 찾 지 못 하면 보통 - 1 을 되 돌려 줍 니 다. 그러나 이 2 분 은 로 의 반 대 를 되 돌려 줍 니 다.이게 무슨 효과 가 있 을 까?
상황 1: 배열 이 비어 있 습 니 다. 그러면 아무것도 찾 지 못 하면 어떻게 됩 니까?코드 에 따 르 면 순환 이 들 어가 지 않 는 다 는 것 을 알 수 있다. 그러면 바로
1, 3, 4, 5, 8, 즉 가장 큰 마이너스 이다.우 리 는 그것 이 마이너스 라 는 것 만 알 아야 한다.상황 2: 배열 이 비어 있 지 않 습 니 다. 예 를 들 어
~0 우 리 는 1, 3, 5 을 찾 습 니 다. 여기 서 간단 한 한 단계 로 실행 합 니 다.lo = 0, size = 3, hi = 2, ，
mid = (0 + 2) / 2 = 1, value = 3
value > 2, hi = 1 - 1 = 0,
mid = (0 + 0) / 2 = 0, value = 1
value < 2, so, lo = 0 + 1;
~1만약 당신 이 다른 상황 을 검산 하려 고 시도 하고 있다 면, 반환 값 은 마침 그것 이 놓 아야 할 위치 에서 반대 하 는 것 을 발견 할 수 있 을 것 입 니 다.다시 말 하면 값 을 되 돌려 서 반대로 가 져 오 면 이 키 가 삽입 해 야 할 위 치 를 얻 을 수 있다.
이것 은 2 분 에 찾 는 작은 기교 일 것 이다.아주 실 용적 이에 요!
그 다음 에 생각해 보 니 0 은 마이너스 이 고 그 어떠한 양수 도 반대 이 며 모두 마이너스 입 니 다. 즉, 마이너스 라면 찾 지 못 한 것 을 의미 합 니 다. 다시 이 수 를 반대 하면 얻 을 수 있 습 니 다. put 해 야 할 위 치 를 얻 을 수 있 습 니 다!
그래서 코드 는 다음 과 같이 계속 실 현 됩 니 다.
public void put(int key, E value) {
int i = BinarySearch.search(mKeys, mSize, key);
if (i >= 0) {
//
// 1. mValues ，
// 2. mValues DELETED ， ，
mValues[i] = value;
} else {
i = ~i;
mKeys = GrowingArrayUtil.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtil.insert(mValues, mSize, i, value);
mSize++;
}
}get 방법 실현
다음은 get 방법 을 실현 합 니 다.get 방법 이 실현 되 는 것 은 비교적 간단 합 니 다. 2 분 을 통 해 해당 하 는 index 를 찾 은 다음 value 배열 에서 대상 을 꺼 내 면 됩 니 다.
public E get(int key) {
// key
int i = BinarySearch.search(mKeys, mSize, key);
if (i < 0) {
return null;
} else {
return (E)mValues[i];
}
}delete 방법 구현
delete 방법 은 키 를 삭제 하 는 것 입 니 다. 해당 하 는 디 테 일 은 이 키 가 존재 하 는 지 찾 는 것 입 니 다. 존재 하면 value 배열 에 해당 하 는 위치 에 있 는 데 이 터 를 상수
2 로 설정 합 니 다.이렇게 하 는 장점 은 요 소 를 진정 으로 삭제 하지 않 고 비교적 빠르다 는 것 이다.물론 이 DELETED 대상 에 value 배열 이 존재 하기 때문에 put 와 get, size 방법 에 영향 을 줄 수 있 습 니 다.다음 코드 는 삭 제 된 변 수 를 표시 하 는 정적 final 변수
DELETED 를 정의 합 니 다.다른 구성원 변 수 는 현재 value 배열 에서 요소 가 삭 제 된 상태 정 보 를 표시 합 니 다.private static final Object DELETED = new Object();
/**
* DELETED
* */
private boolean mHasDELETED = false;
public void delete(int key) {
// ， key， ， ；
// key value DELETED， ，
int i = BinarySearch.search(mKeys, mSize, key);
if (i >= 0 && mValues[i] != DELETED) {
mValues[i] = DELETED;
mHasDELETED = true;
}
}size 방법 구현
size 방법 은 이 용기 에 데이터 대상 이 몇 개 있 는 지 되 돌려 줍 니 다.
DELETED 대상 의 존재 로 인해 key 배열 과 value 배열, 그리고 구성원 변수 DELETED 는 효과 적 인 데 이 터 를 직접 얻 을 수 없 는 count 입 니 다.따라서 내부 도구 방법
mSize 이 필요 하 다. gc() 대상 이 존재 한다 면 배열 을 다시 정리 하고 DELETED 대상 을 모두 제거 하 며 배열 에 유효 데이터 만 유지 하면 된다 는 역할 을 한다.먼저
DELETED 의 실현 을 보다.private void gc() {
int placeHere = 0;
for (int i = 0; i < mSize; i++) {
Object obj = mValues[i];
if (obj != DELETED) {
if (i != placeHere) {
mKeys[placeHere] = mKeys[i];
mValues[placeHere] = obj;
mValues[i] = null;
}
placeHere++;
}
}
mHasDELETED = false;
mSize = placeHere;
}내부 논 리 는 간단 하 다. 바로 처음부터 끝까지 value 배열 을 옮 겨 다 니 며
gc 이 아 닌 모든 대상 을 다시 놓 고 앞의 DELETED 대상 을 덮어 쓰 는 것 이다.그리고 사이즈 의 실현 을 다시 한 번 봅 시다.
public int size() {
if (mHasDELETED) {
gc();
}
return mSize;
}get 방법 보완
만약 에 이런 장면 이 있다 고 가정 하면
DELETED.현재 의 get 실현 에 따라 put(1, a), put(2, b), delete(2), get(2) 대상 으로 돌아 가기 때문에 DELETED 의 존재 로 인해 우 리 는 get 방법의 논 리 를 보완 해 야 한다.public E get(int key) {
// key
int i = BinarySearch.search(mKeys, mSize, key);
//
// key 0， mKeys ， key，
// key 0， ， mValues ， DELETED，
//
if (i < 0 || mValues[i] == DELETED) {
return null;
} else {
return (E)mValues[i];
}
}put 방법 보완
보충 코드 위 에 나 는 설명 을 써 서 이 두 개의 추가 코드 가 어떤 상황 을 처리 하 는 지 설명 했다.
public void put(int key, E value) {
int i = BinarySearch.search(mKeys, mSize, key);
if (i >= 0) {
//
// 1. mValues ，
// 2. mValues DELETED ， ，
mValues[i] = value;
} else {
i = ~i;
//
// 1 2 3 5, delete 5, put 4
if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
return;
}
//
// ， ， GC， key
if (mHasDELETED && mSize >= mKeys.length) {
gc();
i = ~BinarySearch.search(mKeys, mSize, key);
}
mKeys = GrowingArrayUtil.insert(mKeys, mSize, i, key);
mValues = GrowingArrayUtil.insert(mValues, mSize, i, value);
mSize++;
}
}마지막 으로 GrowingArray Util. insert 는 무엇 을 했 습 니까?
사실 말하자면 매우 간단 하 다. 하나의 과정 으로 일반적인 상황 을 개괄 하 자.
[1, 2, 3, 4, 5, 0, 0, 0, 0, 0]
insert(index=2, value=99)
1. index=2 [1, 2, 3, 4, 5, 0, 0, 0, 0, 0]
2. index=2 ， [1, 2, 3, 3, 4, 5, 0, 0, 0, 0]
3. index=2 ， 99 [1, 2, 99, 3, 4, 5, 0, 0, 0, 0]물론 여기 서 처리 해 야 합 니 다. 만약 에 데이터 가 가득 차 면 새로운, 더 큰 배열 을 만들어 서 이전의 데 이 터 를 복사 해 야 합 니 다.
/**
* @param rawArr
* @param size ， ， ， OK
* ， ，
* @param insertIndex index
* @param insertValue index
* */
public static int[] insert(int[] rawArr, int size, int insertIndex, int insertValue) {
if (size < rawArr.length) {
System.arraycopy(rawArr, insertIndex, rawArr, insertIndex + 1, size - insertIndex);
rawArr[insertIndex] = insertValue;
return rawArr;
}
int[] newArr = new int[rawArr.length * 2];
System.arraycopy(rawArr, 0, newArr, 0, insertIndex);
newArr[insertIndex] = insertValue;
System.arraycopy(rawArr, insertIndex, newArr, insertIndex + 1, size - insertIndex);
return newArr;
}
public static Object[] insert(Object[] rawArr, int size, int insertIndex, T insertValue) {
if (size < rawArr.length) {
System.arraycopy(rawArr, insertIndex, rawArr, insertIndex + 1, size - insertIndex);
rawArr[insertIndex] = insertValue;
return rawArr;
}
Object[] newArr = new Object[rawArr.length * 2];
System.arraycopy(rawArr, 0, newArr, 0, insertIndex);
newArr[insertIndex] = insertValue;
System.arraycopy(rawArr, insertIndex, newArr, insertIndex + 1, size - insertIndex);
return newArr;
} 자,
DELETED 에 대한 설명 은 여기까지 입 니 다.완전한 소스 코드 는 내 가 쓴 것 도 볼 수 있 고 공식 적 인 것 도 볼 수 있다.앞서 언급 한 의문점 들
SparseArray 가 아니 라 Object[] T[] 을 사용 하면 범 형 배열 을 만들어 야 합 니 다. 그러면 범 형 배열 을 구성 해 야 합 니 다. 범 형 대상 을 만 들 수 있 습 니 다. 즉, T[] 의 구조 함 수 를 호출 해 야 범 형 대상 을 만 들 수 있 습 니 다. 그러나 범 형 이기 때문에 구조 함 수 는 확실 하지 않 고 반사 적 인 형식 으로 만 호출 할 수 있 습 니 다.이렇게 하면 분명히 효율 과 안정성 에 문제 가 있다.따라서 대부분의 범 형의 실현 은 T 대상 을 통 해 범 형 데 이 터 를 저장 하 는 것 이다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Kotlin의 기초 - 2부지난 글에서는 Kotlin이 무엇인지, Kotlin의 특징, Kotlin에서 변수 및 데이터 유형을 선언하는 방법과 같은 Kotlin의 기본 개념에 대해 배웠습니다. 유형 변환은 데이터 변수의 한 유형을 다른 데이터...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
