Set, Map

Set

Set은 array나 list처럼 순열 자료구조이며, 순서라는 개념 또한 존재하지 않는 순열 자료구조를 의미한다.
출처

특징

• 중복 또는 고유한 요소 없이 요소를 뚜렷하게 저장할 때
• 요소의 순서를 신경 쓰지 않을 때
• 이진탐색트리 중 하나인 Red-Black Tree를 통해 구현 (tree set일경우)

Hash function을 사용하는 이유

string 배열에서 조회를 하는 것은 O(N)이 사용된다.
사전순이라는 순서가 있지만, 고려하지 않는다면 당연한 시간복잡도이다.
하지만 Set은 hashFunction을 이용해 값을 매핑하고 그 매핑결과를 통해 이진트리 형태로 저장하기 때문에 조회의 수행이 빠르다. (덕분에 이진트리의 형태를 띄울 수 있다.)
이러한 형태의 set을 hashset이라고 한다.

Map

 Map은 중복 키를 포함할 수 없다. 각 키는 최대 하나의 값에 매핑할 수 있다.
출처

Map 또한 set처험 구현방법에 따라 다양한 특징을 갖는다.

• HashMap
  - key와 value의 쌍으로만 구성이 될뿐 자료구조 안에 묶인 쌍들에 대한 순서는 보장할 수 없다.
  - 사용자는 키와 값이 구성되는 위치를 결정 하거나 알 수 없다.
• TreeMap
  • key의 값을 이용해 순서대로 정렬하여 데이터를 저장하는 자료구조
  • key값을 통한 탐색 뿐 아니라 key값의 정렬을 통한 탐색 등을 하기에 용의 하다.
• LinkedHashMap
  • 데이터를 입력한 순서대로 쌓아지며 데이터를 저장하는 자료구조
  • 배열, 리스트처럼 인덱싱 접근을 하기에 용의 하다.