[JAVA] Collections Framework..2

https://ybdeveloper.tistory.com/43

[JAVA] Collections Framework...1

Set 인터페이스

https://iq.opengenus.org/set-in-java/

Set 인터페이스는 중복을 허용하지 않고 저장순서가 유지되지 않는 컬렉션 클래스를 구현하는데 사용됩니다. Set 인터페이스를 구현한 클래스로는 HashSet, TreeSet 등이 있습니다.

HashSet

HashSet은 Set 인터페이스로 구현한 가장 대표적인 컬렉션이며, Set 인터페이스의 특징대로 HashSet은 중복된 요소를 저장하지 않습니다. HashSet에 새로운 요소를 추가할 때는 add메서드나 addAll메서드를 사용하는데,  만일 HashSet에 이미 저장되어 있는 요소와 중복된 요소를 추가하고자 한다면 이 메서드들은 false를 반환하여 추가에 실패했다는 것을 알립니다. 이러한 HashSet의 특징을 이용하면, 컬렉션 내의 중복 요소들을 쉽게 제거할 수 있죠.

 

ArrayList와 같이 저장순서를 유지하지 않으므로 저장순서를 유지하고자 한다면 LinkedHashSet을 사용해야만 합니다. 따라서 List의 중복데이터를 제거하기 위해서 LinkedHashSet을 사용한다면 손쉽게 중복 데이터들을 제거할 수 있습니다. 

HashSet과 hashCode(), equals()

만약 name과 age를 멤버변수로 갖는 Person 클래스가 있다고 가정해봅시다. 이름과 나이가 같으면 같은 사람으로 인식하려는 의도로 작성하였지만, 정작 HashSet 컬렉션에 이름과 나이가 같은 두개의 인스턴스를 넣어보니  같은 것으로 인식하지 못하는 것 같습니다. 그렇다면 이 두 인스턴스가 같은 것으로 인식하게 하려면 어떻게 해야할까요? HashSet의 add메서드는 새로운 요소를 추가하기 전에 기존에 저장된 요소와 같은 것인지 판별하기 위해 추가하려는 요소의 equals()와 hashCode()를 호출하기 때문에 두 가지 메서드를 목적에 맞게 오버라이딩 해야만 합니다. 따라서 이름과 나이가 같으면 equals()가 true를 반환하도록 오버라이딩 해야하며, hashCode()를 특정 방식대로 구현해야만 합니다. 이에 대한 코드는 아래와 같습니다.

class Person {
    String name;
    int age; 
    
    /*
    생략...
    */ 

    public boolean equals(Object obj) {
        if(obj instanceof Person2) {
            Person2 tmp = (Person2)obj;
            return name.equals(tmp.name) && age==tmp.age; 
        }
        return false; 
    }

    public int hashCode() {
        return Objects.hash(name,age);
    }
}

TreeSet

TreeSet은 이진 검색 트리라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스입니다. 이진 검색 트리는 정렬, 검색, 범위검색에 높은 성능을 보이는 자료구조이며 TreeSet은 '레드-블랙 트리'로 구현되어 있습니다. 그리고 TreeSet 또한 Set 인터페이스를 구현했으므로 중복된 데이터의 저장을 허용하지 않으며 정렬된 위치에 저장하므로 저장순서를 유지하지 않습니다. 

 

이진 트리는 링크드 리스트처럼 여러 개의 노드가 서로 연결된 구조로서, 각 노드에 최대 2개의 노드를 연결할 수 있으며 '루트'라고 불리는 하나의 노드에서 계속적으로 밑으로 확장해 나가는 구조입니다. TreeSet은 이진 검색 트리의 특성을 유지해야 하기 때문에 데이터를 저장할 때 왼쪽에는 부모노드의 값보다 작은 값을, 오른쪽에는 부모노드의 값보다 큰 값을 저장합니다. 따라서 데이터를 저장할 때 값들을 비교해야만 하는데 이에 대해 구현할 수 있는 두가지 방법이 존재합니다. 

 

1. TreeSet에 저장되는 객체가 Comparable을 구현한다. 
2. Comparator를 제공해서 두 객체를 비교할 방법을 알려준다. 

 

이 두 가지 방법 중 하나라도 사용하지 않는다면 TreeSet에 객체를 저장할 때 예외가 발생하게 됩니다. TreeSet은 이처럼 정렬된 상태를 늘 유지하기 때문에 단일 값 검색과 범위검색, 예를 들면 3과 7사이의 범위에 있는 값을 검색하는 것이 굉장히 빠릅니다. 대신 데이터를 순차적으로 저장하는 것이 아니라 저장위치를 찾아서 저장해야하며 삭제하는 경우 트리 일부를 재구성할 필요가 있으므로 링크드리스트보다 데이터의 추가/삭제 시간은 더 걸리는 편입니다.