[Data Structure] HashSet, LinkedHashSet, TreeSet

[Set]

중복을 허용하지 않는 자료구조로, 모든 데이터가 Unique 하다.

Set Interface 를 구현하는 HashSet, LinkedHashSet, TreeSet 은 위와 같은 성질을 따른다.

 

[HashSet]

내부적으로 HashMap 을 사용

순서 보장 X

null 입력은 가능하나 null도 한 번만 저장 가능하며 중복될 수 없다

 

[LinkedHashSet]

내부적으로 LinkedHashMap을 사용

순서 보장 O (입력한 순서)

null 입력은 가능하나 null도 한 번만 저장 가능하며 중복될 수 없다

 

[TreeSet]

내부적으로 TreeMap을 사용

인자값으로 받은 Comparator 를 기준으로 정렬, 인자값이 없는 경우 오름차순 정렬

null 입력 불가

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+" ");
}

 

[실행 결과]

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/