경량급 int - object 키 쌍 - SparseArray

SparseArray 는 Android framework 에서 제공 하 는 경량급 키 값 이 데이터 구조 에 대한 것 입 니 다. 공간 과 효율 은 항상 서로 어 긋 나 는 것 을 알 고 있 습 니 다. SparseArray 의 실현 은 바로 시간 으로 공간 효율 을 바 꾸 고 소 규모 데이터 저장 에 적합 합 니 다.
다음은 SparseArray 의 특징 을 파악 하고 사용 하 며 일부 소스 코드 를 분석 합 니 다.
SparseArray 특징
SparseArray 는 키 쌍 으로 데 이 터 를 저장 합 니 다. key 는 int 형식 이 며 중복 이 허용 되 지 않 는 유일한 key 입 니 다. value 는 모든 object 일 수 있 습 니 다.
SparseArray 는 경량급 으로 2 개의 배열 을 사용 하여 각각 key 와 value 를 저장 하고 배열 아래 표 시 를 통 해 관련 성 을 대응 합 니 다.key 배열 은 질 서 를 유지 합 니 다.
장점.
HashMap 에 비해 메모리 공간 을 더욱 절약 하고 데이터 저장 은 key 와 value 2 개의 배열 에 만 의존 하 며 배열 공간 은 재 활용 가능 하 며 데이터 의 저장 밀도 가 비교적 높다.key 배열 은 질서 가 있 기 때문에 key 를 통 해 value 를 얻 는 것 이 상대 적 으로 효율 적 입 니 다.
단점:
key 배열 은 질 서 를 유지 하고 삽입 하고 찾 을 때 이분법 으로 위치 key 의 아래 표 시 를 확인 하 는 데 시간 이 걸 립 니 다.삭제 등 을 삽입 하면 배열 데 이 터 를 이동 할 수 있 습 니 다.
종합 적 으로 말 하면 SparseArray 는 작은 데이터 양의 키 값 이 장면 에 적용 된다.데이터 양 이 수백 에 이 르 렀 을 때 효율 우 위 는 HashMap 에 비해 뚜렷 하지 않다.
SparseArray 사용 하기
끼어들다

SparseArray 초기 화 시 저 장 된 데이터 의 구체 적 인 유형 을 지정 해 야 합 니 다

사용 put 방법, key 와 대응 하 는 value 삽입

        SparseArray strArray = new SparseArray<>();
        strArray.put(3, "DDDD");
        strArray.put(1, "AAAA");
        strArray.put(4, "CCCC");
        strArray.put(2, "BBBB");

두루
SparseArray 는 Iterable 을 실현 하지 못 했 습 니 다. 수 동 순환 으로 만 옮 겨 다 닐 수 있 습 니 다.

        for(int i = 0;i<strArray.size();i++){
            String value = strArray.valueAt(i);
            //do sth
        }

삽 입 된 4 개의 데 이 터 는 키 값 이 어 릴 때 부터 큰 순서 로 출력 되 었 습 니 다. 이것 은 삽입 을 실행 한 후에 키 배열 이 질서 가 있 음 을 증명 합 니 다.

value at 0:AAAA
value at 1:BBBB
value at 2:DDDD
value at 3:CCCC

삭제
요 소 를 삭제 하 는 방법 은 2 가지 가 있 습 니 다. 1. removeAt 지정 한 아래 표 시 된 value 를 삭제 합 니 다.2. delete 키 를 통 해 대응 하 는 value 를 삭제 합 니 다.
위 에 삽 입 된 4 개의 데이터 중 2 개 를 삭제 합 니 다.

strArray.remove(3);//  key 3  ， DDDD
strArray.removeAt(0);//          ， AAAA

결국 BBBB 와 CCCC 만 남 았 다.

value at 0:BBBB
value at 1:CCCC

키 로 요소 가 져 오기get 방법 으로 key 에 전송 하여 대응 하 는 value 를 가 져 옵 니 다.

Log.i(TAG, "get 1:" +strArray.get(1));
Log.i(TAG, "get 4:" +strArray.get(4));

출력:

get 1:null //key=1   AAAA，     ，    null
get 4:CCCC

찾다
키 나 value 를 지정 하여 다음 값 을 찾 습 니 다. 1. indexOfKey 이분법 은 mKeys 배열 에서 키 의 아래 표 시 를 찾 습 니 다. 2. indexOfValue mValues 배열 에서 value 요소 의 아래 표 시 를 찾 습 니 다.

Log.i(TAG, "index of key 4:" +strArray.indexOfKey(4));
Log.i(TAG, "index of value BBBB:" +strArray.indexOfValue("BBBB"));

출력: key = 4 의 값, 배열 아래 1, BBBB 는 value 배열 아래 0 으로 표 시 됩 니 다.

index of key 4:1
index of value BBBB:0

소스 코드 분석
SparseArray 가 실현 한 Cloneable 인 터 페 이 스 는 사실 빈 인터페이스 로 아무런 특성 도 실현 하지 못 했다.

public class SparseArray<E> implements Cloneable 

mKeys 와 mValues 배열
key 와 Object 는 배열 아래 표 시 를 통 해 대응 합 니 다. 성형 배열 mKeys 은 키 를 저장 하 는 데 사용 되 고 mValues 은 Object 인 스 턴 스 를 저장 합 니 다.

    private int[] mKeys; // 
    private Object[] mValues; // 

이 두 배열 은 자동 으로 용량 을 늘 리 지만, 배열 에서 어떤 대상 을 제거 한 후 에는 용량 을 줄 이지 않 고, 배열 은 빈 자 리 를 배열 말단 으로 옮 겨 뒤에 두 고 다시 사용 할 것 이다.
삭제
삭제 작업 이 좀 특이 하기 때문에 이 부분 을 먼저 분석 합 니 다.removeAt 방법 이 든 delete 방법 이 든 key 배열 의 값 을 지우 지 않 고 해당 하 는 value 를 DELETED 로 표시 하고 mGarbage 값 을 true 로 설정 하여 삽입 을 기다 리 고 아래 표 시 를 찾 아 요소 등 을 가 져 올 때 배열 내용 을 다시 구성 합 니 다.이것 은 구 덩이 를 파 는 셈 이 고, 뒤 에는 아직 평평 하 게 메 워 야 한다.

    public void removeAt(int index) {
        if (mValues[index] != DELETED) {
            mValues[index] = DELETED;
            mGarbage = true;
        }
    }

    public void delete(int key) {
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

        if (i >= 0) {
            if (mValues[i] != DELETED) {
                mValues[i] = DELETED;
                mGarbage = true;
            }
        }
    }

gc 방법
이 gc 방법 은 자바 의 메모리 회수 방법 이 아 닙 니 다. 삭 제 된 '구덩이' 를 메 우 는 것 을 책임 집 니 다. 메 우 는 방식 은 뒤의 요 소 를 사용 하여 이 구 덩이 를 덮어 서 빈 자 리 를 배열 백 엔 드 로 옮 기 는 것 입 니 다.

    private void gc() {
        int n = mSize;
        int o = 0;
        int[] keys = mKeys;
        Object[] values = mValues;

        for (int i = 0; i < n; i++) {
            Object val = values[i];

            if (val != DELETED) {
                if (i != o) {
                    keys[o] = keys[i];
                    values[o] = val;
                    values[i] = null;
                }

                o++;
            }
        }

        mGarbage = false;
        mSize = o;
    }

삽입 조작
삽입 작업 은 배열 을 확장 시 킬 수 있 습 니 다.

    public void put(int key, E value) {
        //    key mKeys      ，           index    （  ）
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

        if (i >= 0) { //     key，     value   mValues  
            mValues[i] = value;
        } else { //key   
            i = ~i; //    index   ，          

            if (i < mSize && mValues[i] == DELETED) { //      value     ，      value  
                mKeys[i] = key;
                mValues[i] = value;
                return;
            }

            if (mGarbage && mSize >= mKeys.length) {
                gc(); //       ，    key value  

                //gc        index ，                
                i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
            }

            //    key value
            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
            mSize++;
        }
    }

SparseArray 는 깊이 가 높 은 디자인 과 알고리즘 이 없 기 때문에 안 드 로 이 드 프로그램의 중 소 데 이 터 량 장면 은 사용 을 고려 할 수 있다.일단 여기까지 분석 해.