Regular Motion

개발자가 상팔자

[Android] Why ADT recommends SparseArray rather than HashMap?

ADT 21부터였나? Integer type의 Key를 사용하는 HashMap은 SparseArray로 바꿔보는게 어때? 라는 Android Lint의 꿀바른 warning에 따라 변경을 해봤다. 기본적인 get()과 put()에 대해 HashMapSparseArray가 거의 동일한 interface를 제공한다.

 

똑같은데 왜 바꾸라는건가?라는 생각이 들어 검색을 해보니 SparseArray가 HashMap 대비 더 적은 메모리로 더 빠른 속도를 보여준다는 이 많다.

 

테스트 결과에 따르면 Retrieval(get)은 SparseArray가 더 나은 결과를 보여주고, Addition(put)은 HashMap이 더 나은 결과를 결과를 보여준다.  Memory 사용은 SparseArray가 더 적다.

 

둘의 차이점이 궁금해서 source code를 보니까 HashMap과 SparseArray는 Interface만 동일하고 구현방법은 전혀 다르다. HashMap의 동작원리는 이 글에 잘 설명되어있다.

SparseArray는 내부적으로 Key를 저장하는 int array와 Value를 저장하는 Object array 2개의 array를 갖고, key와 value를 배열의 동일한 index에 저장한 뒤, Binary Search로 Retrieval을 구현하고 있다. Linked List로 데이터를 저장하고, Hash Function으로 Retrieval을 구현하는 HashMap과 Interface는 동일하지만, 구현 방법은 전혀 다르다.

그림으로 보면 아래와 같다.

HashMap

HashMap

SparseArray

SparseArray

 

SparseArray의 get() : Binary Search로 index를 찾은 뒤, index에 해당하는 value를 반환한다.

 

SparseArray의 put() : key로 이미 저장된 값이 있는지 확인한 뒤, 있으면 overwrite 하고, 없으면 array의 크기를 키운 뒤 값을 저장한다. 위의 테스트 결과에서 SparseArray가 Addition(put)이 느린 이유는 Binary Search를 위해 데이터를 정렬하는 과정에서 배열 복사 작업이 추가되기 대문인 것 같다.

 

결론 : get이 빈번한 곳에는 SparseArray를 put이 빈번한 곳에는 HashMap을 사용하자.

4 Comments

  1. I think this is a real great article post.Really looking forward to read more. Want more.

  2. The graph will be rather hard to read for a large number of dependencies, but it’s nice to have nevertheless.

답글 남기기

© 2017 Regular Motion

Theme by Anders NorenUp ↑