[Set]
중복을 허용하지 않는 자료구조로, 모든 데이터가 Unique 하다.
Set Interface 를 구현하는 HashSet, LinkedHashSet, TreeSet 은 위와 같은 성질을 따른다.
[HashSet]
내부적으로 HashMap 을 사용
순서 보장 X
null 입력은 가능하나 null도 한 번만 저장 가능하며 중복될 수 없다
[LinkedHashSet]
내부적으로 LinkedHashMap을 사용
순서 보장 O (입력한 순서)
null 입력은 가능하나 null도 한 번만 저장 가능하며 중복될 수 없다
[TreeSet]
내부적으로 TreeMap을 사용
인자값으로 받은 Comparator 를 기준으로 정렬, 인자값이 없는 경우 오름차순 정렬
null 입력 불가
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
Set<Integer> set = new HashSet<>();
set.add(null);
set.add(null); //중복허용X
set.add(3);
set.add(2);
set.add(1);
set.add(1); //중복허용X
System.out.print("HashSet: ");
Iterator<Integer> si = set.iterator();
while(si.hasNext()) {
System.out.print(si.next()+" ");
}
System.out.println();
Set<Integer> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add(3);
linkedHashSet.add(2);
linkedHashSet.add(1);
linkedHashSet.add(1); //중복허용 X
System.out.print("linkedHashSet: ");
for(int i : linkedHashSet) {
System.out.print(i+" ");
}
System.out.println();
Set<Integer> treeSet = new TreeSet<>();
treeSet.add(3);
treeSet.add(2);
treeSet.add(1);
treeSet.add(1); //중복허용X
System.out.print("TreeSet: ");
for(int i : treeSet) {
System.out.print(i+" ");
}
System.out.println();
Set<Integer> treeSetDescending = new TreeSet<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
//내림차순
return o2-o1;
}
});
System.out.print("TreeSetDescending: ");
try {
treeSetDescending.add(null); //null 허용 X
}catch(NullPointerException ne) {
System.out.println("exception:"+ne.getMessage());
}
treeSetDescending.add(3);
treeSetDescending.add(2);
treeSetDescending.add(1);
treeSetDescending.add(1); //중복허용X
for(int i : treeSetDescending) {
System.out.print(i+" ");
}
|
cs |
[실행 결과]
HashSet: 1 2 3
linkedHashSet: 3 2 1
TreeSet: 1 2 3
TreeSetDescending: 3 2 1
[시간복잡도]
HashSet 이 LinkedHashSet, TreeSet보다 성능이 좋으며 메모리를 적게 사용.
| HashSet | LinkedHashSet | TreeSet | |
| performance | Θ(1) | Θ(1) | Θ(log(n)) |
참고 :
https://javaconceptoftheday.com/hashset-vs-linkedhashset-vs-treeset-in-java/
반응형
'Computer Science > data structure' 카테고리의 다른 글
| [Data Structure] Queue 큐, array로 구현하기 (java) (0) | 2020.01.05 |
|---|---|
| [Data Structure] Stack 스택, array 로 구현하기 (java) (0) | 2020.01.05 |
| [Data Structure] ArrayList, LinkedList, Vector (0) | 2019.12.20 |
| [Data Structure] HashMap, HashTable, LinkedHashMap, TreeMap (0) | 2019.12.20 |
| 트리 순회 (0) | 2019.11.26 |