[ 비선형 자료구조 ] 맵(Map) & 셋(Set)

 

1. 맵(Map)

1) 특징

  map은 key - value 쌍으로 이루어진 자료구조이며, key의 중복을 허용하지 않는 자료구조입니다.(value의 중복은 허용합니다.) 이러한 map의 특징은 각 key에 대응하는 value에 효율적으로 접근 가능하게 해 주며 O(n)의 복잡도를 가집니다.

• key-value쌍을 메모리에 저장
• 순서를 고려하지 않는다.
• key에는 다양한 데이터타입이 올 수 있다.(언어에 따라 약간의 차이를 가진다 ex. python - strings, numbers, tuples, javascript - any data type including objects and functions)
• key의 중복을 허용하지 않는다.
• 데이터에 효율적으로 접근 가능하다.

 

2) 종류

1. HashMap : 순서를 보장하지 않는 map이며 key, value에 null을 허용한다. 기본적인 연산(put, get 등) 에서 상수 시간 복잡도를 가지며 성능이 뛰어나다.
2. LinkedHashMap : 연결 리스트를 통해 구현되는 해시 테이블이며 입력 순서를 보장한다. 연결 리스트의 유지 관리로 인해 HashMap보다 약간 느린 성능을 보인다.
3. TreeMap : 이진 탐색 트리를 기반으로 key, value를 저장하는 정렬된 맵이다. 기본 연산에 대해 O(log n)의 복잡도를 가지며 빠른 검색이 가능하다.(저장 시 정렬을 하기 때문에 다소 느릴 수 있다.)
4. HashTable : HashMap의 여러 스레드가 동시에 액세스 할 수 있도록(병렬로 프로그래밍 가능하도록) 동기화 된 이전의, thread-safe 버전의 HashMap이다. HashMap 보다 처리속도가 느리며 key, value에 null을 허용하지 않는다.

 

2. 셋(Set)

1) 특징

  set은 단일한 데이터들의 집합입니다. set은 저장된 요소의 중복을 허용하지 않으며, 순서는 고려되지 않습니다. set에서 특정 요소가 존재여부에 대한 확인은 매우 효율적으로 가능하며 크기에 상관없이 O(1)의 복잡도를 가집니다.

• 단일 데이터들의 집합이다.(중복을 허용하지 않는다)
• 순서를 고려하지 않는다.
• 요소의 존재여부 확인이 O(1)의 시간 복잡도를 가진다.

 

2) 종류

1. HashSet : 해시값을 기준으로 저장하는 순서를 보장하지 않는 집합이며, null을 허용한다. 기본적인 연산(add, remove, contains 등)에서 상수 시간 복잡도를 가지며 성능이 뛰어나다.
2. LinkedHashSet : 연결 리스트를 통해 구현되는 해시 테이블이며 입력 순서를 보장한다. 연결 리스트의 유지 관리로 인해 HashSet보다 약간 느린 성능을 보인다.
3. TreeSet : 이진 탐색 트리를 기반의 정렬된 Set이다. 추가, 삭제 보다 검색, 정렬에서 빠른 성능을 보인다.

 

3. 프로그래밍 언어(JS, Python)에서의 구현

1) JS

  JS에서는 Map과 Set을 HashTable을 이용해 구현합니다. 해시 테이블은 키를 배열의 인덱스에 매핑하기 위해 해시함수를 사용하는 자료구조이며, key-value 쌍이 HashTable에 추가되면 key는 배열의 인덱스로 해싱되고 value는 해당 인덱스에 저장됩니다. 데이터 조회 시에도 비슷하게 키를 해싱하고 그 결과에 대응되는 인덱스의 값을 반환합니다. (set의 경우 value 그 자체가 key의 역할을 동시에 합니다. value가 인덱스로 해싱되고 해당 인덱스에 value가 저장됩니다.)

 

1) Python

  Python의 경우 버전에 따라 그 구현 방법이 차이를 갖습니다. Python 3.6 이상의 경우 map(dict)와 set은 HashTable과 open addressing 기술(open addressing는 서로 다른 두 key가 동일한 인덱스로 해싱되어 충돌이 발생한 경우 통해 HashTable 상에서 비어있는 다음 슬롯을 찾아 문제를 해결합니다.)을 통해 구현되며, 이때 HashTable의 각 항목은 key-value 쌍과 항목의 비어있는지 여부에 대한 flag를 포함합니다. (HashTable이 가득찰 수록 다음 슬록을 찾는 비용이 증가하고 퍼포먼스가 줄어듭니다.)