Set

Set (Interface)

쉽게 말해, 집합이다.

 

특징

• 중복이 허용되지 않는다.
• 순서를 보장하지 않는다.  (단, LinkedHashSet은 연결 구조를 통해 순서를 보장한다.)

 

구현체

구현체로는 아래와 같은 것들이 있다.

• HashSet
• LinkedHashSet
• TreeSet

HashSet

Hash 알고리즘을 활용하는 Set 자료구조이다.

 

Hash 알고리즘이란?

자바에서 hash알고리즘이란, 데이터를 숫자화 하여, 그 값을 자료구조의 인덱스(Index)로서 활용하는 기법이다.

 

특징

• 동일한 자료에 대해, 동일한 hash값이 나온다.
• 불필요한 저장공간 생성(메모리 할당)을 피하기 위해 % CAPACITY 연산이 수행된다.

 

장점

인덱스를 활용하게 되므로, 데이터 접근 속도가 빠르다.

 

단점

Hashing 과정에서 동일한 hash값이 나올 수 있다.

-> 동일 인덱스 사용을 인정함으로서 약점 회피함. 이 때 자료 구조는 List를 사용한다.

-> 최악의 경우, 하나의 인덱스에 값이 집중될 수 있으나, 최적화 돼 있음

 

LinkedHashSet

HashSet + Linked(Node 사용) 자료구조이다.

 

특징

- 입력 순서가 보장된다.

 

============

자료 저장, 조회 등을 위해 Map 자료 구조가 사용된다. 심화는 Map 자료구조 학습 이후 하는 것이 옳겠다.

============

 

TreeSet

이진트리를 사용하는 자료구조이다.

 

특징

Node 와 비슷하게 left, right 의 참조값을 갖는다.

hash값의 대조를 통해 탐색 범위를 2n 으로 반복해서 나누는 log2 N 의 공식을 같는다.

Comporator 를 통해 순차적 조회가 가능하다.

 

장점

데이터 조회, 추가, 제거 등에서 O(log2 N) 의 성능을 발휘한다.