[자료구조] 맵 (Map)

맵 (Map)

  맵은 데이터가 Key와 Value의 쌍으로 이루어진 자료구조를 의미한다. key를 통해 value에 접근할 수 있으며 key와 value를 연결하는 행위를 맵핑(mapping)이라고 표현한다.

 

맵의 특징

(1) (일반적으로) key는 중복되어서는 안 된다. (대신 value는 중복되어도 무관한다.)

(2) 데이터의 순서는 보장되지 않으며 인덱스도 존재하지 않는다. (애초에 Map에서 순서는 전혀 중요한 개념이 아니다.)

(3) 맵은 검색 연산에서 뛰어난 성능을 보인다.

 

맵의 종류와 특징

1. HashMap

  해싱을 통해서 key와 value를 저장한다. 데이터의 위치는 해싱 결과에 의해 결정되기 때문에 순서는 보장되지 않는다. 하나의 key에 대해 하나의 value만 존재할 수 있다. 만약 이미 존재하는 key를 넣어준다면 value가 새로운 값으로 갱신된다. 해싱 덕분에 다량의 데이터 검색에 아주 뛰어난 성능을 보인다.

 

2. HashTable

  마찬가지로 key를 해싱하여 데이터의 위치를 계산한다. 데이터가 저장되는 곳을 버킷(bucket) 혹은 슬롯(slot)이라고 부른다. 대부분의 해시테이블은 효율성의 측면에서 서로 다른 키에 대해 동일한 해시값이 생성될 수 있는 불완전 해시함수를 채용한다. 그렇다고 사용할 수 있는 모든 키값의 개수만큼 버킷을 만들 수는 없다. (메모리 효율성도 최악이고 현실적으로 모든 키값들에 대비하는 것은 거의 모든 겨우에 불가능하다.) 이렇게 서로 다른 키값에 대해 동일한 해시값이 생성되어 같은 버킷 위치가 지정되는 문제를 해시 충돌(Hash Collision)이라고 부른다.

  해시 충돌에 대응하는 방법은 크게 두 가지가 있다. 하나는 추가적인 메모리를 사용하는 방법이고 다른 하나는 그렇지 않는 방법이다. 추가적인 메모리를 사용하는 방법을 체이닝이라고 표현하며 추가적인 메모리를 통해 동일한 버킷에 지정된 데이터들을 서로 연결한다. 한 버킷 내에서 원하는 데이터를 탐색하는 작업은 일반적인 배열을 훑어보는 방식과 동일하기 때문에 해싱이 가지는 탐색에서의 장점을 상실한다.

  두 번째 방법인 Open Addressing 방법은 해시 테이블 내에 다른 비어있는 위치를 지정해주는 방식이다. Open Addressing 기법을 활용하는 경우 성능을 위해 해시 테이블의 공간을 유동적으로 조정할 때마다 내부 재정리 작업이 필요하다. Open Addressing의 대표적인 기법들은 다음과 같다.

 

(1) Linear Probing : 가장 단순한 방법이다. 자신의 해시값에 해당하는 버킷이 이미 차 있는 경우 비어있는 공간이 나올 때까지 일정 칸만큼 이동하여 다음 버킷을 확인하는 방법이다.

(2) Quadratic Probing : 저장 버킷을 찾기 위해 정해진 칸만큼 이동하는 Linear Probing과 다르게 이동할 때마다 이동하는 칸 수를 제곱으로 늘리는 방법이다. (ex. 1*1 → 2*2 → 3*3)

(3) Double Hashing Probing : 해시된 값을 또 다시 해싱하는 방법이다.

 

  해시 테이블의 성능을 결정짓는 가장 큰 요소는 해시 테이블의 공간 활용률이다. 해시 테이블 내에 데이터가 차지하는 공간의 비중이 높을수록 해시 충돌이 빈번하게 발생하여 해시 테이블 성능이 급격하게 저하된다. 그렇다고 빈 공간이 지나치게 많으면 메모리적인 낭비가 발생한다. 이와 관련해서 할 수 있는 주요 조치는 다음과 같다.

(1) 해시 함수를 잘 구현한다.

(2) 해시 테이블이 가득 차 있는 정도를 분석하여 유동적으로 해시 테이블의 크기를 결정한다. 해시 테이블의 공간 사용률이 일정 수준 이상인 경우 테이블의 크기를 늘리고 일정 수준 이하인 경우 테이블의 크기를 줄인다. 해당 작업을 수행할 때마다 데이터의 위치를 재조정해줘야 하는 번거로움이 존재하지만 평균적인 성능을 고려하였을 때는 해당 방법이 훨씬 효율적인 방법임을 알 수 있다.

 

※ HashMap vs HashTable (Java를 하는 사람들을 위해)

  알다시피 Java는 정말 많은 클래스를 제공해준다. 해쉬테이블과 해쉬맵 역시 Java의 클래스를 통해 이용할 수 있다고 하는데 둘의 차이점이 무엇일까. 가장 큰 차이점은 Thread-safe 여부이다. 해쉬 테이블은 Thread-safe하기 때문에 병렬 프로그래밍이 가능하고 해쉬맵은 그렇지 않다. 한편 해쉬맵은 보조 해시함수를 사용하기 때문에 해시 테이블에 비해서 해시 충돌이 일어날 가능성이 낮다. 앞서 언급했듯 해시 충돌은 해시 함수가 포함된 자료구조의 성능을 결정짓는 요소이다. 따라서 멀티 스레딩 환경에서 개발을 진행한다면 해시 테이블을 활용하고 그렇지 않다면 해시맵을 활용하는 것이 유리한 것으로 보인다. 추가적으로 해쉬 테이블은 key에 null값을 사용할 수 없지만 해쉬맵은 허용된다는 차이점도 존재한다. 

 

 

3. Linked Hashmap

  입력 순서가 보장되는 해시맵이다. Map 인터페이스를 통해 구현하였으며 Linked List와 해시 테이블의 특징을 동시에 가지고 생각하면 된다. key와 value의 쌍을 저장하면서 그 순서를 사용해야할 때 사용한다.

 

 

4. TreeMap

  이진 탐색 트리(BST, Binary Search Tree)의 형태로 key, value의 쌍을 저장한다. key값을 기준으로 데이터를 정렬해야 할 때 사용한다. 그러나 데이터를 추가할 때 정렬 구조를 유지하기 위한 연산이 필요하다.