Java / 컬렉션 프레임워크 - Set

Set 인터페이스

중복을 허용하지 않는 유일한 요소의 집합

>> 순서를 보장하지 않으며 특정 요소가 집합에 있는지 여부를 확인하는데 최적화

 

HashSet

구현 : 해시 자료 구조를 사용해서 요소 저장

순서 : 특정 순서 없이 저장

시간 복잡도 : O(1)

용도 : 데이터의 유일성만 중요하고 순서가 중요하지 않은 경우

hashCode(), equals() 모두 사용

 

LinkedHashSet

구현 : HashSet에 연결 리스트를 추가해서 요소들의 순서 유지

순서 : 요소돌은 추가된 순서대로 유지

시간 복잡도 : O(1)

용도 : 데이터의 유일성과 함께 삽입 순서를 유지해야 할 경우

head(first)부터 순서대로 링크를 따라가면 입력 순서대로 데이터 순회 가능

양방향 연결

 

TreeSet

구현 : 이진 탐색 트리를 개선한 레드-블랙 트리를 내부에서 사용

순서 : 요소들은 정렬된 순서로 저장됨

시간 복잡도 : O(log n)

용도 : 데이터들을 정렬된 순서로 유지하면서 집합의 특성을 유지해야 할 때 사용, 입력된 순서가 아닌 데이터 값의 순서

트리는 부모 노드와 자식 노드로 구성

가장 높은 조상을 root라 함

자식이 2개까지 올 수  있는 트리를 이진 트리

>> 노드의 왼쪽 자손은 더 작은 값을 가지고, 오른쪽 자손은 더 큰값을 가지는 것을 이진 탐색 트리

 

중위 순회 순서

>> 자신의 왼쪽의 모든 노드를 처리하고, 자신의 노드를 처리하고, 자신의 오른쪽 모든 노드를 처리하는 방식