Map과 Set이란(Hash, Tree 기반 자료형 비교)

Map

---

맵은 비선형 자료구조로 key-value 쌍으로 데이터를 저장하는 특징을 갖고 있다.

맵의 key는 중복이 허용되지 않으나, value는 중복이 허용된다.

자바의 맵 자료형에는 대표적으로 HashMap과 TreeMap이 존재한다.

HashMap은 해시테이블 기반으로 자료를 관리하기에 조회, 삽입, 삭제 연산에 O(1)의 시간복잡도를 갖는다.

TreeMap은 균형 이진탐색트리의 한 종류인 레드블랙 트리를 통해 데이터를 관리하기에 조회, 삽입, 삭제 연산에 O(logN)의 시간복잡도를 갖는다.

 

Set

---

셋은 비선형 자료구조로 중복이 허용되지 않는다.

중복을 허용하지 않는 집합과 같은 개념이다.

자바의 셋에는 HashSet, TreeSet이 존재한다.

HashSet은 해시테이블 기반으로 자료를 관리하기에 조회, 삽입, 삭제 연산에 O(1)의 시간복잡도를 갖는다.

TreeSet은 균형이진탐색트리의 한 종류인 레드블랙 트리를 통해 데이터를 관리하기에 조회, 삽입, 삭제 연산에 O(logN)의 시간복잡도를 갖는다.

 

HashMap, HashSet

---

• HashMap과 HashSet은 내부적으로 해시 테이블을 사용하여 데이터를 관리한다.
  
  • 해시 테이블은 인덱스와 버킷(value 저장)으로 이루어져있다.
    
  • 해시함수의 결과인 해시값을 배열의 크기로 나눈 나머지가 해시 테이블에 인덱스에 해당함 -> 시간복잡도 O(1)
• 키의 삽입 순서를 보장하지 않으며 해시테이블 인덱스 기반으로 저장됨
• HashMap의 경우 키와 값에 null 가능, HashSet도 null 가능
  • 참고로 자바 HashSet은 HashMap을 통해 구현됨
• 해시값 충돌시 저장 전략이 존재함

해시 함수는 임의 길이의 입력을 고정 길이의 출력으로 매핑하는 함수

 

해시충돌

해시테이블에서 충돌에 의한 문제는 분리연결법과 개방주소법으로 해결할 수 있다.

 

분리 연결법(Separate Chaining)은

해시값이 같아 동일한 버킷에 접근을 수행하는 경우 버킷에 저장되는 데이터를 연결리스트로 구현하여 접근 가능하게 하는 방식이다.

실제 자바의 해시맵 구조를 보면 버킷에 존재하는 노드라는 객체는 next라는 참조를 갖고 있는데, 충돌이 일어나게 되면 next 노드에 (key, value)를 저장하여 접근이 가능하도록 한다.

 

개방주소법은(open Addressing)

충돌이 일어나는 경우 고정된 크기만큼 인덱스를 이동시켜 비어있는 버킷을 찾거나,

2^2, 3^2 칸씩 이동하여 비어잇는 버킷을 찾아나가는 방식이다.

이외에도 Double Hashing이라고 하여 해싱한 함수를 한번 더 해싱하는 방법 또한 존재한다.

 

분리연결법은 해시테이블의 크기보다 더 많은 데이터를 저장 가능하고, 구현이 쉽다는 장점이 존재한다.

하지만 충돌이 많이 발생하는 경우 연결리스트에 대한 탐색으로 최악의 경우 시간복잡도가 O(n)으로 커질 수 있다.

개방주소법은 참조기반의 연결리스트를 사용하지 않고 배열만 사용하므로 성능이 빠르다는 장점이 있다.

다만, 많은 데이터를 저장하여 해시테이블이 꽉차는 경우 새로운 배열을 생성하고 복사하는 과정이 생기므로 성능 저하가 발생할 수 있다.

 

* 자바의 해시맵은 충돌이 심해지면 연결리스트(O(N)) 대신 레드블랙 트리(O(logN)으로 변환해 성능을 보장한다.

 

TreeMap, TreeSet

---

• 내부적으로 균형 이진탐색트리인 레드-블랙 트리를 통해 관리됨
• 키의 삽입 순서를 보장하지 않으며 이진 탐색 트리 정렬 기준으로 저장됨
• TreeMap은 key에 null 저장 불가하며 value에는 가능, TreeSet 또한 null 불가
  • 자바 TreeSet은 TreeMap을 통해 구현됨

균형 이진탐색트리의 한종류인 레드블랙트리를 통해 구현되므로 조회, 삽입, 삭제 연산에 모두 O(logN)의 시간복잡도를 갖는다.

TreeMap과 TreeSet은 레드블랙트리가 갖추고 있는 성질을 그대로 갖으므로 아래 레드블랙트리 글을 참고하기 바란다.

https://developer111.tistory.com/entry/%EB%A0%88%EB%93%9C%EB%B8%94%EB%9E%99%ED%8A%B8%EB%A6%AC

 

 

Hash기반 자료형과 Tree기반 자료형의 비교

---

Hash기반 자료형은 해시 테이블을 기반으로 관리되므로 시간복잡도가 O(1),

Tree기반 자료형은 레드블랙트리를 기반으로 관리되므로 시간복잡도가 O(logN)이다.

 

HashMap의 시간복잡도가 더욱 우수하므로 HashMap이 TreeMap보다 모든 면에서 좋아보인다.

그렇다면 TreeMap은 도대체 어떤 경우에 사용되나??

 

key 정렬이 필요한 경우 Tree기반 자료형이 사용될 수 있다.
이진탐색트리를 기반으로 구현되어있으므로 key 탐색시 중위 순회기반으로 조회하여 key 값 오름차순으로 조회할 수 있다.

key를 정렬하고 정렬된 값으로 탐색해야하는 경우 Tree기반 자료형을 사용하는 것이 유리하다.