[자료구조] - Set

Set

---

이번에 공부해 볼 자료구조는 Set이다. Set은 간단하게 설명하면 집합을 의미한다.

그럼 집합에 대해서 조금 살펴보면 임의의 대상이 집합에 속하는지 여부를 명확히 하고 집합 위에는 순서나 연산 따위의 구조가 주어지지 않는다라고 설명한다.

여기서 중요한 포인트는 집합에 속하는지 여부와 순서나 연산을 고려하지 않는다는 점이다.

집합에 속하는지 여부를 판단하는 것은 하나의 집합 안에 중복된 요소를 허용하지 않는다로 이해할 수 있다.

만약 위의 그림과 같이 A라는 집합이 있고 3이라는 숫자를 추가한다고 가정해보자.

3이라는 새로운 숫자는 A 집합에 이미 존재하기 때문에 추가될 수 없게 된다.

또 다른 부분을 살펴보면 현재 A 집합에 들어있는 숫자들은 어떤 순서를 가지지 않고 여기저기 흩어져 있는 상태로 보인다.

이렇듯 Set이라는 자료구조는 중복을 허용하지 않고, 순서를 유지하지 않는 특징을 가지고 있다.

 

Set은 어디에 사용될까?

---

처음에 Set 자료구조를 공부할 때 대체 어디서 사용되는 건지 의문이 들었다.

하지만 내가 했던 프로젝트를 생각해 보니 Set을 사용할만한 곳들이 많이 보이게 되었다.

회원가입을 진행할 때 중복된 아이디인지 확인하기 위해 아이디 중복 체크라는 기능을 만들었는데 이럴 때 사용하면 기존의 아이디를 하나씩 비교하는 방법보다 좋은 효율을 보여줄 것이라 생각했다.

어차피 아이디를 중복 체크하는 것은 어떤 순서를 유지해야 할 필요도 없고 그냥 단순히 사용하고 싶은 아이디가 현재 있는지, 없는지만 판단하면 되기 때문에 이런 부분에서 Set 자료구조를 적절히 활용하면 좋을 것 같았다.

 

Set은 어떤 점이 좋을까?

---

Set 자료구조의 장점으로는 삽입, 삭제, 조회의 시간복잡도가 O(1)을 가지므로 매우 빠른 성능을 보여준다. 따라서 이전에 언급했던 아이디 중복체크와 같이 중복된 요소를 찾을 때 List 자료구조를 사용한다면 하나씩 비교를 해야 되지만 Set은 한 번의 연산으로 바로 알 수 있다.

하지만 이런 Set 자료구조에서도 할 수 없는 것이 있는데 그것은 바로 순서를 알 수 없다는 것이다.

순서를 알 수 없기 때문에 정렬도 하지 못하여 내가 원하는 데이터는 빠르게 찾을 수 있지만 반대로 최댓값이나 최솟값을 찾기에는 적합하지 않은 자료구조다.

그렇다고 걱정할 필요가 없는 것이 자바에서는 Set 자료구조를 인터페이스로 두고 해당 인터페이스를 구현한 3가지 구현체를 제공하고 있다.

3가지 구현체를 간단히 살펴보면 HashSet, LinkedHashSet, TreeSet이 있는데 Set 자료구조를 사용해도 순서를 유지하고, 정렬도 할 수 있도록 제공되기 때문에 적절히 잘 활용만 하면 된다.

 

HashSet

---

HashSet은 가장 기본적인 Set 인터페이스의 구현체로 해시 기능과 Set 기능이 합쳐진 것이다.

가장 일반적으로 사용되는 Set 자료구조로 순서를 보장하지 않는 대신 삽입, 삭제, 조회가 O(1)로 매우 빠르다.

굳이 해시와 같이 사용하는 이유는 Set에 데이터를 삽입할 때 중복된 원소를 확인하기 위해서 모든 원소를 검사한다면 매우 비효율적이기 때문이다. 따라서 해시를 같이 사용하면 동일한 값에 대해서는 같은 값이 나오기 때문에 보다 쉽게 중복 체크가 가능하다.

자료구조 - 해시(Hash)

 

일반적인 값에 대해서는 정상적으로 작동하지만 사용자 클래스를 사용하게 될 경우 해당 클래스 내에 hashCode 메서드를 오버라이드를 하지 않으면 메모리 주소를 기반으로 해싱된 값이 나오기 때문에 객체 내용을 비교해 주기 위해서는 반드시 오버라이드를 해줘야 한다.

또한, 추가할 객체가 HashSet에 중복되는지 확인하기 위해서 eqauls()도 오버라이드해서 객체의 고유성을 보장해야 중복을 확인할 수 있다.

Set_Test_1 test1 = new Set_Test_1("aaa", 10);
Set_Test_1 test2 = new Set_Test_1("aaa", 10);

HashSet<Set_Test_1> hashSet2 = new HashSet<>();
hashSet2.add(test1);
hashSet2.add(test2);

/*
 * 사용자 정의 객체에 equals와 hashCdoe를 재정의하지 않으면 내용이 같은데 중복해서 추가되는 문제가 발생한다.
 * 왜냐하면 같은 내용이라면 같은 해시값이 되어야 하는데 재정의하지 않으면 같은 내용이라도 다른 해시값이 나오기 때문이다.
 */
System.out.println(hashSet2.size());        // 같은 내용이지만 중복 추가가되서 사이즈가 2가 된다.

위의 예시와 같이 두 개의 객체가 "aaa"와 10이라는 값이 동일하기 때문에 HashSet에 넣고 사이즈를 확인해 보면 1이 나와야 하지만 2가 나오게 된다.

이렇게 되는 이유는 eqauls()를 재정의하지 않아 서로 다른 객체라고 판단하여 저장하기 때문이다.

그래서 사용자가 정의한 클래스를 HashSet에 저장할 때는 무조건 eqauls와 hashCode를 오버라이드 해야 한다.

 

LinkedHashSet

---

LinkedHashSet은 기존의 HashSet에서 제공하지 않은 순서를 보장받기 위해 사용되는 클래스이다.

LinkedHashSet<Set_Test_1> linkedHashSet2 = new LinkedHashSet<>();
Set_Test_1 test_1 = new Set_Test_1("aaa", 10);
Set_Test_1 test_2 = new Set_Test_1("bbb", 20);
Set_Test_1 test_3 = new Set_Test_1("ccc", 30);
Set_Test_1 test_4 = new Set_Test_1("aaa", 20);

linkedHashSet2.add(test_1);
linkedHashSet2.add(test_2);
linkedHashSet2.add(test_3);
linkedHashSet2.add(test_4);

// 출력 결과: [aaa] : [10] --> [bbb] : [20] --> [ccc] : [30] --> [aaa] : [20]

예제를 살펴보면 Set_Test_1부터 Set_Test_4까지 차례대로 데이터를 저장하고 출력해 보면 입력한 순서 그대로 나오는 것을 알 수 있다.

입력한 순서를 어떻게 유지하는 것인지 궁금했는데 직접 설명을 뒤져보니 Doubly-Linked List로 순서를 유지한다고 한다.

 

TreeSet

---

TreeSet은 앞서 살펴봤던 LinkedHashSet과는 다르게 입력 순서를 보장하지 않고 중복 데이터를 허용하지 않지만 가중치에 따라 순서대로 정렬되는 특징을 가지고 있다.

중복되지 않으면서 특정 규칙에 의해 정렬된 형태의 집합을 쓰고 싶을 때 사용하게 되는데 이때 특정 규칙이란 정렬에 대한 기준을 의미한다.

TreeSet<Set_Test_1> treeSet = new TreeSet<>(new Comparator<Set_Test_1>() {
    @Override
    public int compare(Set_Test_1 o1, Set_Test_1 o2) {
        if (o1.age == o2.age) {
            return o1.name.compareTo(o2.name);
        } else {
            return o1.age - o2.age;
        }
    }
});

Set_Test_1 treeTest_1 = new Set_Test_1("aaa", 10);
Set_Test_1 treeTest_2 = new Set_Test_1("bbb", 20);
Set_Test_1 treeTest_3 = new Set_Test_1("ccc", 60);
Set_Test_1 treeTest_4 = new Set_Test_1("eee", 30);
Set_Test_1 treeTest_5 = new Set_Test_1("aaa", 20);

treeSet.add(treeTest_1);
treeSet.add(treeTest_2);
treeSet.add(treeTest_3);
treeSet.add(treeTest_4);
treeSet.add(treeTest_5);

for (Set_Test_1 setTest1 : treeSet) {
    System.out.println(setTest1);
}

간단한 예제 코드를 살펴보면 먼저 TreeSet을 만들 때 new Comparator를 사용하여 정렬에 대한 기준을 만들어준다.

Set_Test_1이라는 객체에는 String 타입의 name과 int 타입의 age가 있는 상태로 compare 메서드를 통해 만약 age가 같을 경우 name의 사전 순으로 정렬하고, 그렇지 않을 경우에는 age 순으로 정렬하도록 했다.

그다음 객체를 만들어서 TreeSet에 저장하고 출력을 해보면 아래와 같은 결과가 출력된다.

[aaa] : [10]
[aaa] : [20]
[bbb] : [20]
[eee] : [30]
[ccc] : [60]

결과를 확인해 보면 age를 기준으로 'aaa' : 20과 'bbb' : 20은 동일하지만 name을 보면 aaa가 사전 순으로 앞에 있기 때문에 먼저 출력되는 것을 알 수 있다.

또한, name이 ccc일 때 age가 60으로 TreeSet에 저장할 때 3번째로 저장했지만 출력 결과는 맨 마지막에 출력되는 것을 알 수 있다.

이처럼 입력한 순서는 보장되지 않지만 중복되지 않고 특정 기준을 통해서 정렬이 되는 집합을 만들 때 사용하기 좋다.

 

참고 자료

자바 [JAVA] - Set Interface (셋 인터페이스)