1. Set이란?
중복을 허용하지 않고, 순서를 보장하지 않는 자료구조
중복을 허용하지 않고, 순서를 보장하지 않는다면 어떤 장점이 있는걸까?
가장 많이 쓰이는 곳은 특정 요소가 집합에 있는지를 검증하는데 쓰인다.
ex) A = [1, 3, 5] / A는 4를 포함하고 있나요?
이런 문제에서 Set을 사용한다면, 굉장히 효율적으로 문제를 해결할 수 있다.
[ Set의 구조 ]
뭐가 참 많다.
SortedSet, NavigableSet은 인터페이스이기 때문에 해당 인터페이스를 구현한 TreeSet 및
HashSet, LinkedHashSet 총 3개의 Set에 대해 알아보도록 하자.
2. HashSet
Set은 방금 글 읽고 알겠는데, Hash는 뭔지 모르겠어요. 당연한거다. 해시를 설명한 적이 없다.
HashSet을 이해하기 전에, 우선 Hash에 대해 알아보자.
[ Hash란? ]
Set에서 특정 데이터를 포함하는가를 찾는 과정은 평균 O(1)의 시간복잡도를 가진다. 어떻게 O(n)이 아닌, 상수시간에 해결이 가능한걸까?
우선 기본적인 데이터 포함 과정 코드를 살펴보자.
[1,3,5,7,9] 의 배열에서 9를 포함하고 있는지 찾는 코드를 작성한다면,
public boolean contains(int value) {
for (int data : elementData) {
if (data == value) {
return true;
}
}
return false;
}
이런 함수를 통해 비교할 수 있을 것이다.
운이 좋다면 상수시간 만에 찾을 수 있지만, 해당 예시처럼 9를 찾는 과정에서는 모든 배열과 비교를 진행해야 하기 때문에 O(n)의 시간복잡도를 가진다.
Hash는 해당 문제를 해결하기 위해 나온 신박한 개념이다.
[1,3,5,7] 의 배열이 있다면,
1-> index 1
3 -> index 3
5 -> index 5
7 -> index 7
즉, [1, null, 3, null, 5, null, 7 ] 과 같은 배열이 만들어진다. 이렇게 배열을 저장한다면, 상수시간만에 배열에 접근이 가능하다. 한계점 또한 존재한다. [1, 100] 이라는 배열이 있다면 어떡할 것인가? [1, null, null, ... 100] 과 같은 배열이 만들어지고,
심한 메모리 낭비가 발생하게 된다. 이 문제를 해결하기 위해 해시 인덱스 (HashIndex) 가 도입되었다.
[ 해시 인덱스란? ]
배열의 가용량 즉, 저장공간이 10인 배열이 있다고 가정하자.
해시 인덱스는 값 % 저장공간 을 계산한 나머지 값을 배열에 담는 과정이다.
그림을 통해 이해해보자.
[1,3,5,14,99] 가 수용량 10인 배열에 저장되는 과정이다.
14의 경우 14%10 = 4이기 때문에 index 4에 저장이 되었고, 99의 경우 99%10 = 9 이기 때문에 index9에 저장이 되었다.
배열의 크기를 효율적으로 관리할 수 있지만, 이 경우 해시 충돌이 발생할 수도 있다.
[1,3,5,9,14,99] 의 값을 넣는다고 할 때, index 9에 [9, 99] 값이 동시에 들어가 충돌이 발생한다는 것이다.
이 문제는 배열 안에 배열을 넣으면 해결될 수 있는 문제다.
즉, index 9 내부에 충돌이 발생한다면, [9, 99] 를 배열로 관리하고, 해당 index 안의 배열 값을 비교하면 되는것이다.
[9, 19, 29, 99] 라는 값이 들어올 경우, index 9에 [9, 19, 29, 99] 가 들어올 것이고, 하나씩 비교해야하기때문에
최악의 경우 O(n)의 시간복잡도를 가지게 된다. 하지만 확률적으로 보면 넓게 퍼지기 때문에 평균적으로 본다면
O(1) 의 성능을 제공한다는 것을 알 수 있다.
[ 해시 인덱스를 사용하는 경우의 시간복잡도 ]
| 평균 | 최악 | |
| 데이터 저장 | O(1) | O(n) |
| 데이터 조회 | O(1) | O(n) |
해시 인덱스를 사용하는 방식은 배열의 크기만 잘 조정해주면 되기 때문에 사실 최악의 경우는 거의 발생하지 않는다.
배열의 크기만 적절하게 잡아주면 대부분 O(1)에 가까운 성능을 보여준다.
해시 자료 구조를 사용해 요소를 저장한것이 바로 HashSet이다.
3. LinkedHashSet
HashSet에 LinkedList를 추가하여 요소들의 순서를 유지한 것이다.
LinkedList를 추가했기에 요소들이 추가된 순서대로 유지된다. 즉, 순서대로 조회 시 요소들이 추가된 순서대로 반환된다.
어떤 구조인지 그림을 통해 보다 명확하게 이해해보자.
위와 같은 구조가 된다. 그림은 단방향 구조이지만, 실제로는 양방향 구조를 하고 있다.
first의 링크를 순서대로 따라가면서 출력하면 순서대로 출력할 수 있는 것이다.
Set 자료구조를 사용하되 삽입 순서를 유지하고 싶다면 LinkedHashSet을 사용해보자.
4. TreeSet
Java에서의 TreeSet은 레드-블랙 트리를 사용한다.
[언제 사용하면 좋을까?]
Set의 특징, 즉 집합의 특성을 유지하면서 데이터들을 정렬된 순서로 유지해야 할 때 사용하면 좋다.
예시를 통해 알아보자.
[3, 1, 2, 4] 와 같은 값을 삽입해야 하는데, 정렬 과정을 거치지 않고 삽입 하는 동시에 정렬이 되면 좋겠다.
이 과정에서 TreeSet은 아주 적합하다. 어떻게 정렬이 되는걸까?
이진탐색트리에 대해 간단하게 설명하자면,
- 트리는 부모와 자식 노드루 구성이 된다.
- 가장 높은 조상을 루트라고 함.
- 자식이 2개까지 올 수 있는 트리를 이진 트리라 함.
- 왼쪽 자손은 더 작은 값을, 오른쪽 자손은 더 큰 값을 가짐
[3,1,2,4]을 차례대로 Insert 하는 과정을 아래 그림을 통해 알아보자.
1) 3 삽입
2) 1 삽입, 1은 3보다 작기에 왼쪽에 위치
3) - 2 삽입, 2는 1보다 크기에 오른쪽에 위치, 3보다 작기에 왼쪽에 위치
- 회전 (자세히 알고싶다면 Red-Black 트리에 대해 따로 공부를 해보자)
4) 4 삽입, 4는 3보다 크기에 오른쪽에 위치
이런 과정이 이뤄지고, 삽입과 동시에 정렬이 되는 모습을 알 수 있다.
출력을 할 때는 중위 표기를 통해 출력을 하기에 [1, 2, 3, 4] 가 출력이 되는것을 볼 수 있다.
[ TreeSet의 시간복잡도 ]
삽입, 삭제, 수정의 연산들은 O(log n)의 시간복잡도를 가진다.
왜 O(log n) 의 시간 복잡도를 가지는지 검색과정을 통해 살펴보자.
35를 찾는 과정이다.
1) 20 < 35 이기에 오른쪽으로 간다.
2) 35 < 40 이기에 왼쪽으로 간다.
3) 30 < 35 이기에 오른쪽으로 간다.
노드값을 비교한다. 35와 같다.
상수시간인 Hash보다는 조금 오래 걸리는 것을 볼 수 있다. 다만, 삽입과 동시에 정렬이 이뤄지기에 필요한 상황에 적절하게 사용해보자.
'java' 카테고리의 다른 글
| Thread(2) - 스레드의 상태 (6) | 2025.01.15 |
|---|---|
| Thread(1) - java의 메모리 구조, 프로세스의 메모리 구조 (4) | 2025.01.14 |
| Java 컬렉션 정리 for 코딩테스트 - Queue (9) | 2024.12.25 |
| Java 컬렉션 정리 for 코딩테스트 - Map (7) | 2024.12.23 |
| Java 컬렉션 정리 for 코딩테스트 - List (5) | 2024.12.21 |
