ArrayMap
ArrayMap
이전 글을 통해 HashMap과 기본형(Primitive Type) 변수와 같이 이용했을 때 발생하는 Autoboxing 이슈를 다뤘습니다. 하지만 HashMap은 Autoboxing 이슈뿐만 아니라 메모리 측면에서도 이슈가 있습니다.
이번에는 HashMap 메모리 이슈와 이를 해결할 수 있는 ArrayMap에 대해 알아보겠습니다.
HashMap
키에 대한 해시 값을 이용하여 값을 저장하고 조회하며,
키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 Map
HashMap은 Key와 Value를 한 쌍으로 관리한다는 면에서 활용 가치가 높고, 데이터 조회 시 항상 O(1)의 시간만 소비하기 때문에 일정한 성능을 낼 수 있다는 장점이 있습니다.
#01 HashMap좀 더 살펴보면, 먼저 HashMap에 새로운 데이터를 저장하는 로직을 살펴보면 아래와 같습니다.
1. Key 객체에 Hash를 적용시켜 Index(Hash 값)를 구함.
2. 배열의 해당 Index 에 Value 객체를 저장.
3. 만약 배열의 해당 Index 에 이미 객체가 저장되어 있다면(Hash 충돌), 여러 해시 충돌 해결 방법에 따라 처리
여기서 신경 쓸 부분은 서로 다른 Key의 Hash 값이 같아서 발생하는 Hash 충돌입니다.
Hash 충돌이 일어날수록 Hash의 성능이 저하되기 때문에, 이를 방지하기 위해서는 배열의 크기가 커져야 합니다. 작은 배열일수록 Hash 충돌이 더 많이 일어나기 때문입니다.
하지만 배열의 크기가 커질수록 이용하지 않는 공간도 많아지고, 결국엔 메모리 낭비가 발생하게 됩니다.
http://d2.naver.com/helloworld/831311
ArrayMap
#02 ArrayMap안드로이드에서는 HashMap을 대체할 수 있는 ArrayMap을 제공하고 있습니다.
ArrayMap은 HashMap과 같은 기능을 제공하지만, 큰 배열 하나 대신 작은 배열 두 개를 이용해 낭비하는 메모리가 없습니다.
첫 번째 배열은 주어진 Key의 Hash 값을 정렬된 상태로 저장합니다.
두 번째 배열은 Key와 Value 객체를 저장합니다.
#03 Get value from ArrayMapArrayMap에서 Value를 조회하는 로직을 살펴보면 아래와 같습니다.
1. Key 객체에 Hash를 적용시켜 Index(Hash 값)를 구함.
2. 이미 정렬되어 있는 첫 번째 배열에서 이진 탐색을 통해 두 번째 배열에 저장된 Key Index를 찾음.
3. 만약 두 번째 배열의 해당 Index에 다른 Key가 있다면(Hash 충돌), 이 데이터를 찾기 위해 두 번째 배열을 양방향으로 선형적으로 순회.
ArrayMap의 객체 수가 증가하거나 Hash 충돌이 일어날수록, 해당 객체에 접근하는 데 필요한 시간도 늘어나게 됩니다.
결국 HashMap에 비해 메모리 이슈는 줄어들지만 데이터 조회 성능은 떨어질 수도 있습니다.
ArrayMap에서 데이터를 저장/삭제할 때도 신경 써야 하는 부분이 있습니다.
이미 공간이 할당되어 있다면 간단하게 처리할 수 있지만, 리사이징이 필요하다면 별도의 공간을 만들고 값을 복사하고 이동까지 시켜야 합니다.
즉, 데이터를 처리하는데 비용이 더 들어가게 됩니다.
HashMap vs ArrayMap
#04 HashMap & ArrayMapArrayMap은 Iterator를 써야만 하는 HashMap과는 달리 Index를 이용해 내부를 순회할 수 있습니다.
따라서 Iterator에 비해 메모리 측면에서 더 효율적입니다.
#05 HashMap & ArrayMap게다가 낭비하는 메모리 공간이 없기 때문에 메모리 측면에서는 ArrayMap이 더 좋습니다.
#06 Recommend situation메모리 측면에서 ArrayMap이 훨씬 뛰어나더라도, 앞서 설명한 대로 데이터를 처리하는 성능은 문제가 될 수 있습니다.
ArrayMap을 이용하기에 적합한 경우는 아래와 같습니다.
만약 이 두 가지 경우가 아니라면 그냥 HashMap을 이용하는 게 낫습니다.
1. 데이터 객체의 수가 1000개 미만이고, 데이터 처리(추가, 삭제, 조회)가 잘 일어나지 않는 경우
2. Map이 SubMap들을 가지고 있는 경우
따라서 상황에 맞게 HashMap과 ArrayMap을 이용하는 게 좋습니다.
ArrayMap vs SparseArray
앞 글에서 소개한 SparseArray와 ArrayMap는 두 개의 배열을 이용한다는 점에서 똑같습니다.
따라서 HashMap에 비해 메모리 측면에서는 SparseArray 또한 더 뛰어납니다.
단지 Key와 Value에 객체(참조형)를 이용해야 하는 ArrayMap과 달리 SparseArray는 기본형(Primitive Type)을 이용할 수 있습니다.
ArrayMap이 항상 답은 아닙니다. 상황에 따라 HashMap과 ArrayMap을 이용해야 합니다.
