F015 - Set (작성 중)

✍️ 이번 시간에는 Set과 Queue 인터페이스와 이를 구현한 클래스에 대해서 알아보고, 각 클래스 별로 어떻게 해당 자료구조를 구현했는지, 특징은 무엇인지 알아보는 시간을 가져보려 한다.

---

Set

수학에서의 집합의 개념과 동일하게 중복 집합을 제외하고 집합 내 존재하는 원소들은 서로 다르며, 같은 원소가 여러 개 존재 할 수 없다. 이를 바탕으로 Set 자료구조는 객체 내에 담긴 데이터의 중복을 허용하지 않는다.

또한, Set 자료구조는 순서에 상관없이 데이터를 담는다. 때문에 특정 순서에 존재하는 데이터를 꺼내어 사용할 때 사용하기 보다는 특정 데이터가 존재하는지 확인하거나 해당 객체 내에 데이터가 얼마나 존재하는지 확인하기 위해 주로 사용된다.

이러한 Set 인터페이스는 Collection 인터페이스를 확장하여 메소드를 명세하고 있으며, 이를 구현한 클래스는 대표적으로 HashSet, LinkedHashSet, TreeSet 클래스가 존재한다.

Set 뽑아먹기

📍 객체 내 존재하는 데이터의 중복을 허용하지 않는다.

📍 순서에 상관없이 데이터를 담지만, 특정 클래스는 순서 및 정렬을 지원한다.

📍 대표적으로 HashSet, LinkedHashSet, TreeSet 클래스가 있다.

---

HashSet

HashSet 클래스는 List 인터페이스를 구현한 클래스와 비슷하게 Serializable, Cloneable 인터페이스를 구현하고, AbstractSet 클래스를 확장했다.

이는 앞서 배웠던 것 처럼 직렬화를 통해 외부 서버로 해당 객체를 전송하거나 파일로 저장하고, 해당 클래스로 생성된 객체는 클론이 가능하다는 것을 의미하며, AbsctractSet 클래스를 통해 Set 인터페이스를 구현하는 클래스들의 공통적인 메소드를 상속받아 최소한의 메소드만 구현하여 중복 요소들을 제거했음을 뜻한다.

// 기본 생성자
public HashSet() {
    map = new HashMap<>();
}

public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}

public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}

위의 코드와 이름을 통해 HashSet 클래스는 내부적으로 HashMap 객체를 생성하여 해시 알고리즘을 이용해 구현한 것을 알 수 있다.

생성자의 매개 변수로 들어가는 initalCapacity는 리스트 인터페이스를 구현한 클래스 내에서 자주 접해서 알고 있듯, 객체가 처음 선언되고 메모리에 할당될 때의 길이 혹은 크기를 의미한다.

근데 loadFactor 라는 매개 변수를 인자로 받는 생성자가 존재하는데 loadFactor는 무엇에 사용하는 것일까?

LoadFactor

LoadFactor(이하 로드팩터)는 (데이터의 개수) / (저장 공간) 의미하며 기본적으로 0.75f 값을 가지는데, 이는 처음 메모리에 할당된 메모리의 75%가 채워 졌을 때 해당 객체의 크기를 늘리고, 기존 객체 내의 데이터를 다시 정리해야 하는 Rehash 작업을 수행한다.

때문에 로드 팩터라는 값이 크면 클 수록 Rehash 작업을 수행하기 전까지 사용 가능한 메모리 공간은 많아지지만, 데이터를 찾아오는 시간은 그만큼 증가한다.

어떻게 동일한 객체인지 확인하고 제거할까?

// HashMap.put(K key, V value)
public V put(K key, V value) {
    // 1) hash() > Key로 받아온 객체의 메모리 주소를 비트연산
    // 2) putVal() > Value로 받아온 객체를 Node에 저장 >
    //    해당 데이터를 저장 할 수 없다면 null 반환
    return putVal(hash(key), key, value, false, true);
}

// HashSet.add(E e)
public boolean add(E e) {
    // putVal() 메소드의 리턴값이 null일 경우 데이터 중복으로 Set 객체에 담을 수 없다.
    return map.put(e, PRESENT)==null;
}

// HashSet 데이터 저장 로직 파악하기
public class HashSetTest {
    public static void main(String[] args) {
        Object[]        objArray = {"1", new Integer(1), "2", "2", "3", "4", "4", "4"};
        HashSet<Object> hashSet  = new HashSet<>();

        for (Object obj : objArray) {
            System.out.println("현재 값 : " + obj +  " / Set에 담겼나요? " + hashSet.add(obj));
        }

        System.out.println(hashSet);
    }
}

/*
    현재 값 : 1 / 할당 여부 true
    현재 값 : 1 / 할당 여부 true
    현재 값 : 2 / 할당 여부 true
    현재 값 : 2 / 할당 여부 false
    현재 값 : 3 / 할당 여부 true
    현재 값 : 4 / 할당 여부 true
    현재 값 : 4 / 할당 여부 false
    현재 값 : 4 / 할당 여부 false
    [1, 1, 2, 3, 4]
*/

위의 코드를 살펴보자.

HashSet 클래스에서는 다른 Collection 클래스들과 비슷하게 add() 메소드를 이용해 데이터를 객체에 담을 수 있다.

이 때, HashSet은 기본 생성자에 의해 HashMap 객체를 내부에 생성하게 되고, add() 메소드를 호출하면서 생성된 HashMap 객체의 put() 메소드를 호출하는데, put() 메소드는 HashMap 내부에 정의된 putVal() 메소드와 hash() 메소드를 호출한다.

HashMap 클래스의 hash() 메소드는 put() 메소드에서 받아온 Key 객체의 hashcode() 메소드를 호출하여 비트연산의 결과값을 반환한다.

이 때 반환된 값을 기준으로 putVal() 메소드 내부에서 value 데이터의 중복을 확인하고 중복되지 않는다면 Node를 생성, 중복된다면 null을 반환한다.

여기서 반환된 값이 null이라면 HashSet 객체에 담길 데이터는 중복으로 인해 담기지 못하고, null이 아니라면 객체에 담길 것이다.

즉, HashMap의 내부 메소드에 의해 equals(), hashcode()를 호출하여 해당 객체가 존재하는지 확인하기에 중복을 제거 할 수 있다.

✔️ 해당 부분을 더 자세히 이해하기 위해서는 HashMap과 HashTable, Hash 알고리즘에 대해 공부해보자!

---

TreeSet

TreeSet 클래스는 HashSet과 달리 이진 탐색 트리를 이용해서 구현되어 있는 클래스이다. 때문에 범위 탐색과 정렬에 유리한데, 위의 클래스 다이어그램을 살펴보면 HashSet 클래스와 달리 SortedSet 인터페이스를 확장한 NavigableSet 인터페이스를 구현한 것을 확인 할 수 있다.

TreeSet 클래스는 이진 탐색 트리의 구조를 가지기 때문에 범위 탐색과 정렬에 유리하다고 하는데 왜 유리한걸까?

Binary Tree

이진 트리는 시작점인 Root 노드를 제외한 노드에 최대 2개의 하위 노드를 가지는 구조를 가지는 자료 구조이다. 일반적인 이진 트리는 O(n)의 시간 복잡도를 가지는데, 이는 루트 노드부터 모든 하위 노드를 순회해야 하기 때문이다.

📍 전위 순회 (preorder)
루트 노드 > 왼쪽 서브 트리 > 오른쪽 서브 트리 순으로 순회한다.

📍 중위 순회 (postorder)
왼쪽 자식 노드 > 부모 노드 > 오른쪽 자식 노드 순으로 순회한다.

📍 후위 순회 (inorder)
왼쪽 사직 노드 > 오른쪽 자식 노드 > 부모 노드 순으로 순회한다.

Bianry Search Tree

이진 탐색 트리는 이진 트리처럼 하나의 노드에 최대 두 개의 노드가 존재 할 수 있는 것은 동일하지만, 자식 노드를 정할 때 규칙이 존재한다.

부모 노드의 값 보다 크면 왼쪽에, 작다면 오른쪽에 자식 노드를 위치하도록 한다. 때문에 데이터를 조회하는 것에 있어 부모 노드 값보다 작거나 큰 경우을 기준으로 트리를 순회하기 때문에 평균적으로 O(logN)의 시간 복잡도를 가지며, 중위 순회를 통해 노드를 찾는다.

📍 모든 노드의 키 값은 유일하다.

📍 왼쪽 서브 트리 키 값들은 루트 노드의 키 값보다 작다.

📍 오른쪽 서브 트리 키 값들은 루트 노드의 키 값보다 크다.