[Algorithm] Set, Map개요
★Set은 원소의 집합을 관리한다. 기본적인 연산은 비슷하게 추가, 삭제, 검색이다. List와 다르게 Set에 들어온 데이터들에게 순서는 없으며, 중복된 데이터는 저장되지 않는다. 순서가 없기 때문에 위치 정보 index를 가지고 검색할 수는 없다.
★Java에서 Set 인터페이스는 TreeSet과 HashSet, LinkedHashSet으로 구현되어 있다. add, remove, containes등의 메소드를 기본적으로 갖추고 있다.
-
TreeSet : 이진 탐색 트리의 개량 버전인 Red Black Tree에 데이터를 저장한다. 데이터의 추가나 삭제에는 시간이 걸리지만 검색과 정렬이 뛰어나다. TreeSet은 add, remove, contains외에도 headSet(기준 객체보다 작은 객체들을 반환), subSet(범위 내의 객체들을 반환), tailSet(기준 객체보다 큰 객체들을 반환)을 가지고 있다. TreeSet은 이진 탐색 트리로 데이터가 이미 정렬되어 있으므로 꺼낼 때에도 정렬된 상태로 꺼내어 진다.
-
HashSet : Hashing을 이용해 데이터를 저장한다. Hashing이 판단하는 동일한 객체는 반드시 같은 인스턴스를 뜻하는 것이 아니다. 객체의 hashCode()의 결과값이 같고, 두 객체를 equals비교했을 때 true값이 반환된다면 두 객체는 같다고 보는 것이다. 즉 Set에 들어갈 객체에서 hashCode()와 equals()를 어떻게 정의했는지에 따라 일치/불일치 판단 기준이 바뀔 수 있다. 놀랍게도 Java에서는 내부적으로 HashSet을 HashMap으로 구현한다. Entry의 Key를 현재 Set에서 다루는 Key로 사용하고, Value는 Dummy를 넣는 방식으로 사용하므로 사실 HashMap을 구현한다면 Set은 자동으로 구현되게 되어있다.
-
LinkedHashSet : 기본적으로 순서가 없는 Set이지만 LinkedHashSet은 순서를 유지할 수 있도록 구현되어 있다.
★Map은 key-value Entry형식의 데이터를 저장한다. 각 key와 value는 서로 매칭되며, key값을 이용해 value를 찾는다. 따라서 key값은 중복 될 수 없지만 value값은 중복될 수 있다.
★Java에서 Map 인터페이스는 TreeMap, HashMap, HashTable로 구현 되어 있으며 put, get, remove메소드를 기본적으로 가지고 있다.
- TreeMap : 레드 블랙 트리로 구현된 Map이다. TreeSet에서 Key에 객체하나를 묶어 놓은 모양새이다. tree이므로 key를 정렬시킬 수 있다. key가 정렬된 순서대로 무엇인가 해야 한다면 좋은 성능으로 사용할 수 있다. 그러나 랜덤접근의 경우 O(log n)으로 HashMap보다 좀 느리다.
- HashMap : key를 정렬시킬 수 없지만, 탐색의 시간복잡도가 O(1)이다. 랜덤 접근에 강하다. 내부적으로는 Entry<K, V>[]에 저장되며 데이터의 index는 k.hashCode()로 결정된다. 하나의 K값이 중복된(해시 충돌) 경우를 대비해 각 Entry는 next값을 갖게 되어 있다. K값이 같은 Entry들을 단일연결리스트로 묶는 것이다. 이를 Chaning 기법이라 함. Java에서는 충돌된 노드들이 일정 갯수 이상으로 늘어나면 연결리스트가 아닌 레드 블랙 트리로 변경하게 해 놓았다. 그래서 성능이 더 좋아짐.
- HashTable : 사실상 HashMap이지만 약간 다름. HashTable과 HashMap의 관계는 Vector와 ArrayList의 관계와 비슷하다. HashMap은 thread safe하지 않은 반면 HashTable은 접근 시 동기화를 사용하므로 싱글 스레드 환경에서는 HashMap보다 느릴 수 있다. 또한 HashMap은 key나 value에 null을 저장할 수 있지만 HashTable은 못 한다.
★Set(TreeSet, HashSet)과 Map(TreeMap, HashMap)은 접두사를 보면 알 수 있듯 서로 비슷한 방식으로 대응시킬 수 있다. TreeSet과 TreeMap은 레드 블랙 트리 자료구조를, HashSet과 HashMap은 해싱을 이용한 방식을 사용한다. 알고리즘이 비슷하므로 Set과 Map을 함께 구현해 보자.