[java] 스파 스 어레이 vs 해시 맵

HashMap정수 키를 가진 SparseArrays 가 s 보다 훨씬 더 좋은 몇 가지 이유를 생각할 수 있습니다 .

  1. 에 대한 Android 설명서에 SparseArray“일반적으로 기존보다 느립니다 HashMap“라고 표시되어 있습니다.
  2. HashMaps 대신을 사용하여 코드를 작성하면 SparseArray코드가 다른 Map 구현에서 작동하며 Maps 용으로 설계된 모든 Java API를 사용할 수 있습니다.
  3. 당신이 사용하는 코드를 작성하는 경우 HashMap들보다는 SparseArray코드가 아닌 안드로이드 프로젝트에서 작동이야.
  4. 재정의를지도 equals()하고 hashCode()반면 SparseArray하지 않습니다.

그러나 HashMap안드로이드 프로젝트에서 정수 키 를 사용하려고 할 때마다 IntelliJ는 SparseArray대신 사용해야한다고 말합니다 . 나는 이것이 정말로 이해하기 어렵다는 것을 안다. 누구든지 SparseArrays를 사용해야하는 매력적인 이유를 알고 있습니까?



답변

SparseArray 교체하는 데 사용할 수 있습니다 HashMap키가 기본 유형 인 경우 . 모든 키 / 값 유형이 공개되지는 않지만 여러 키 / 값 유형에 대한 변형이 있습니다.

이점은 다음과 같습니다.

  • 무 할당
  • 권투 없음

단점 :

  • 일반적으로 속도가 느리고 대규모 컬렉션에는 표시되지 않습니다
  • Android 이외의 프로젝트에서는 작동하지 않습니다.

HashMap 다음으로 대체 할 수 있습니다.

SparseArray          <Integer, Object>
SparseBooleanArray   <Integer, Boolean>
SparseIntArray       <Integer, Integer>
SparseLongArray      <Integer, Long>
LongSparseArray      <Long, Object>
LongSparseLongArray  <Long, Long>   //this is not a public class                                 
                                    //but can be copied from  Android source code 

메모리 측면 에서 1000 개의 요소에 대한 예제는 다음 SparseIntArrayHashMap<Integer, Integer>같습니다.

SparseIntArray:

class SparseIntArray {
    int[] keys;
    int[] values;
    int size;
}

클래스 = 12 + 3 * 4 = 24 바이트
배열 = 20 + 1000 * 4 = 4024 바이트
총계 = 8,072 바이트

HashMap:

class HashMap<K, V> {
    Entry<K, V>[] table;
    Entry<K, V> forNull;
    int size;
    int modCount;
    int threshold;
    Set<K> keys
    Set<Entry<K, V>> entries;
    Collection<V> values;
}

클래스 = 12 + 8 * 4 = 48 바이트
항목 = 32 + 16 + 16 = 64 바이트
배열 = 20 + 1000 * 64 = 64024 바이트
총계 = 64,136 바이트

출처 : 슬라이드 90의 Romain Guy의 Android Memories

위의 숫자는 JVM이 힙에 할당 한 메모리 양 (바이트)입니다. 사용되는 특정 JVM에 따라 다를 수 있습니다.

java.lang.instrument패키지에는로 객체 크기 확인과 같은 고급 작업에 유용한 방법이 포함되어 있습니다 getObjectSize(Object objectToSize).

추가 정보는 공식 Oracle 문서 에서 구할 수 있습니다 .

클래스 = 12 바이트 + (n 개의 인스턴스 변수) * 4 바이트
배열 = 20 바이트 + (n 개의 요소) * (요소 크기)
항목 = 32 바이트 + (1 번째 요소 크기) + (2 번째 요소 크기)


답변

사용 방법의 예를 원해서 여기에 왔습니다. SparseArray . 이것은 그에 대한 보충 답변입니다.

스파 스 배열 만들기

SparseArray<String> sparseArray = new SparseArray<>();

A SparseArray는 정수를 일부에 매핑 Object하므로 String위의 예에서 다른 것으로 바꿀 수 Object있습니다. 정수를 정수로 매핑하는 경우SparseIntArray .

항목 추가 또는 업데이트

put(또는 append)를 사용 하여 배열에 요소를 추가하십시오.

sparseArray.put(10, "horse");
sparseArray.put(3, "cow");
sparseArray.put(1, "camel");
sparseArray.put(99, "sheep");
sparseArray.put(30, "goat");
sparseArray.put(17, "pig");

있습니다 int키 순서로 할 필요가 없습니다. 또한 특정 int키 의 값을 변경하는 데 사용할 수 있습니다 .

항목 제거

remove(또는 delete)를 사용 하여 배열에서 요소를 제거하십시오.

sparseArray.remove(17); // "pig" removed

int매개 변수는 정수 키입니다.

int 키의 조회 값

get일부 정수 키의 값을 얻는 데 사용하십시오 .

String someAnimal = sparseArray.get(99);  // "sheep"
String anotherAnimal = sparseArray.get(200); // null

누락 된 키 get(int key, E valueIfKeyNotFound)가 발생하지 않도록하려면 사용할 수 있습니다 null.

항목을 반복

키 와는 별도의 인덱스를 유지 관리 하기 때문에 keyAtvalueAt일부 인덱스를 사용 하여 컬렉션을 반복 할 수 있습니다 .SparseArrayint

int size = sparseArray.size();
for (int i = 0; i < size; i++) {

    int key = sparseArray.keyAt(i);
    String value = sparseArray.valueAt(i);

    Log.i("TAG", "key: " + key + " value: " + value);
}

// key: 1 value: camel
// key: 3 value: cow
// key: 10 value: horse
// key: 30 value: goat
// key: 99 value: sheep

키는 추가 된 순서가 아니라 오름차순으로 정렬됩니다.


답변

그러나 안드로이드 프로젝트에서 정수 키가있는 HashMap을 사용하려고 할 때마다 intelliJ는 대신 SparseArray를 사용해야한다고 말합니다.

문서 의 희소 배열에 대한 경고 일뿐입니다 .

정수를 객체에 매핑하기 위해 HashMap을 사용하는 것보다 메모리 효율성이 뛰어납니다.

SparseArray것으로되어 효율적인 메모리 없는 등의 HashMap 어레이 내의 다수의 갭을 허용하지 않는 것이다 정규 해시 MAP 사용하는 대신. 장치에 대한 메모리 할당에 대해 걱정하지 않으려는 경우 기존 HashMap을 사용할 수 있으므로 걱정할 필요가 없습니다.


답변

Java의 스파 스 배열은 키를 값에 매핑하는 데이터 구조입니다. 지도와 같은 아이디어이지만 다른 구현 :

  1. 지도는 내부적으로 목록의 배열로 표시되며,이 목록의 각 요소는 키, 값 쌍입니다. 키와 값은 모두 객체 인스턴스입니다.

  2. 희소 배열은 단순히 두 개의 배열, 즉 (기본) 키 배열과 (객체) 값 배열로 구성됩니다. 이러한 배열 인덱스에는 차이가있을 수 있으므로 “스파 스”배열이라는 용어가 있습니다.

SparseArray의 주요 관심사는 객체 대신 프리미티브를 키로 사용하여 메모리를 절약한다는 것입니다.


답변

인터넷 검색 후 이미 게시 된 anwers에 정보를 추가하려고합니다.

Isaac Taylor 는 SparseArrays와 Hashmaps의 성능을 비교했습니다. 그는 말한다

Hashmap과 SparseArray는 1,000 미만의 데이터 구조 크기와 매우 유사합니다.

크기가 10,000 표시 […]로 증가하면 해시 맵은 객체를 추가 할 때 성능이 향상되고 SparseArray는 객체를 검색 할 때 성능이 향상됩니다. […] 100,000의 크기에서 […] 해시 맵이 매우 빠르게 성능을 잃습니다.

Edgblog 의 비교에 따르면 SparseArray 는 작은 키 (int와 Integer)로 인해 HashMap보다 훨씬 적은 메모리가 필요하다는 사실과

HashMap.Entry 인스턴스는 키, 값 및 다음 항목에 대한 참조를 추적해야합니다. 또한 항목의 해시를 int로 저장해야합니다.

결론적으로지도에 많은 데이터를 저장하려는 경우 차이가 중요 할 수 있습니다. 그렇지 않으면 경고를 무시하십시오.


답변

SparseArray의 Android 문서에 “일반적으로 기존 HashMap보다 속도가 느립니다”라고 표시되어 있습니다.

네 맞습니다. 그러나 10 개 또는 20 개의 항목 만있는 경우 성능 차이는 중요하지 않습니다.

SparseArrays 대신 HashMaps를 사용하여 코드를 작성하면 코드가 다른 Map 구현에서 작동하며 Maps 용으로 설계된 모든 Java API를 사용할 수 있습니다.

가장 자주 HashMap키와 관련된 값을 검색하는 데만 사용 하지만 SparseArray실제로는 이것에 능숙하다고 생각합니다.

SparseArrays 대신 HashMaps를 사용하여 코드를 작성하면 코드가 안드로이드가 아닌 프로젝트에서 작동합니다.

SparseArray의 소스 코드는 매우 단순하고 이해하기 쉬우므로 간단한 COPY & Paste를 통해 다른 플랫폼으로 옮기는 데 거의 노력을 기울이지 않습니다.

맵은 equals () 및 hashCode ()를 재정의하지만 SparseArray는

내가 말할 수있는 것은 (대부분의 개발자에게) 누가 신경 쓰는가?

또 다른 중요한 양태는 SparseArray단지 동안 모든 요소를 저장하기위한 배열이다 사용 HashMap용도가 Entry있으므로 SparseArray(A)보다 크게 적은 메모리 비용을 HashMap참조 이것을


답변

불행히도 컴파일러가 경고를 발행합니다. HashMap이 항목을 저장하는 데 과도하게 사용 된 것 같습니다.

SparseArray가 그 자리에 있습니다. 이진 검색 알고리즘을 사용하여 배열에서 값을 찾으려면 수행중인 작업을 고려해야합니다. 이진 검색은 O (log n)이고 해시 조회는 O (1)입니다. 이것은 반드시 주어진 데이터 세트에 대해 이진 검색이 느리다는 것을 의미하지는 않습니다. 그러나 항목 수가 늘어남에 따라 해시 테이블의 성능이 대신됩니다. 따라서 적은 수의 항목이 HashMap을 사용하는 것보다 같고 더 나은 주석이 있습니다.

HashMap은 해시만큼 좋고로드 팩터의 영향을받을 수 있습니다 (나중 버전에서는로드 팩터를 무시하므로 더 잘 최적화 할 수 있다고 생각합니다). 또한 해시가 양호하도록 보조 해시를 추가했습니다. 또한 SparseArray가 비교적 적은 수의 항목 (<100)에서 실제로 잘 작동하는 이유입니다.

해시 테이블이 필요하고 원시 정수 (자동 복싱 없음) 등에 더 나은 메모리 사용을 원할 경우 trove를 사용해보십시오. ( http ://trove.starlight-systems.com-LGPL 라이센스). (도서관처럼 트로 브와의 관계 없음)

단순화 된 멀티 덱스 빌딩을 사용하면 필요한 것을 위해 포장재를 다시 포장 할 필요조차 없습니다. (트 로브에는 많은 수업이 있습니다)