🧐 Set Interface란?
Set 인터페이스는 중복을 허용하지 않고, 저장순서가 유지되지 않는 컬렉션 클래스를 구현하는데 사용된다.
(LinkedHashSet은 Set을 상속받음에도 불구하고 입력 순서대로의 저장순서를 보장하고 있다. 그러나 중복은 아니다.)
기본적으로 List 계열은 index(Node)로 관리하기에 add()같은 메서드를 쓰면 순서대로 저장이 되었다.
Queue 계열 또한 PriorityQueue(우선순위 큐)를 제외하고는 입력 순서대로 객체가 연결되어 있다.
하지만 Set의 경우 일반적으로 입력받은 순서와 상관없이 데이터를 집합시키기 때문에 입력받은 순서를 보장할 수 없다.
이러한 순서 보장을 개선하기 위해 만들어진 것이 LinkedHashSet이다.
만약 중복은 허용하고 싶지 않으나 순서를 보장받고 싶다면 이것을 사용하면 된다.
Queue를 상속받은 Deque 인터페이스가 있듯이, Set을 상속받은 SortedSet 인터페이스도 있다.
📝 SortedSet의 대표적인 메서드
Set은 Collection 인터페이스로부터 상속받은 메서드를 쓰기때문에 SortedSet의 메서드만 적었다.
📝 Set/ SortedSet Interface를 구현하는 클래스
1. HashSet
Set 인터페이스의 가장 대표적인 컬렉션 클래스이다.
입력 순서를 보장하지 않고, 중복도 보장되지 않는다.
이것은 Hash에 의해 데이터 위치를 특정시켜 해당 데이터를 빠르게 색인(search)할 수 있게 만든 것이다.
따라서 Hash 기능과 Set컬렉션이 합쳐진 것이 HashSet이라 볼 수 있다.
그렇기 때문에 삽입, 삭제, 색인이 매우 빠른 컬렉션 중 하나이다.
🥲 HashSet의 add() 메서드를 쓸 때 주의할점!!!
HashSet의 add()는 새로운 요소를 추가하기 전에 저장된 요소와 같은지 판별하기 위해 새로운 요소의 equals()와 hashCode()를 호출한다.
위의 add메서드의 설명을 번역해보자.
Adds the specified element to this set if it is not already present.
More formally, adds the specified element e to this set if this set contains no element e2 such that (e==null ? e2==null : e.equals(e2)).
If this set already contains the element, the call leaves the set unchanged and returns false.
명시된 요소가 아직 없는 경우 이 집합(Set)에 추가합니다.
대부분 일반적으로, 이 집합에 (e==null ? e2==null : e.equals(e2)) 와 같은 요소 e2가 포함되어 있지 않으면 지정된 요소 e를 이 집합에 추가합니다.
만약 이 집합에 이미 요소가 포함된 경우, 호출은 집합을 변경하지 않고 false를 반환합니다.
즉 HashSet에 있는 요소인지 파악하기 위해 내부적으로 다음과 같은 과정을 거치는 것이다.
- 추가하려는 요소의 hashCode() 메서드를 호출하여 반환된 해시값으로 검색할 범위를 결정한다.
- 해당 범위 내의 요소들을 equals() 메서드로 비교한다.
따라서 HashSet의 add() 메서드를 사용하여 중복없이 새로운 요소를 추가하려면 hashCode()와 equals()메서드를 상황에 맞게 오버라이딩해야 한다.
🧐 만약 hashCode와 equals를 함께 오버라이딩하지 않으면 어떻게 될까?
hash값을 사용하는 Collection(HashSet, HashMap, HashTable)을 사용할 때 문제가 발생한다.
hash값을 사용하는 컬렉션은 객체가 논리적으로 같은지 비교할 때 위와 같은 과정을 거친다고 한다.
hashCode 메서드 리턴값이 일치하고 equals 메서드의 리턴값이 true여야 논리적으로 같은 객체라고 판단한다.
만약 hashCode를 재정의하지 않으면 Object 클래스의 hashCode 메서드가 사용된다.
Object 클래스의 hashCode 메서드는 heap에 저장된 객체 고유한 주소 값을 int값으로 변환하기 때문에 객체마다 다른 값을 리턴한다.
즉, 두 개의 객체는 equals로 비교하기 전에 hashCode 메서드의 리턴값으로 인해 다른 객체로 판단되는 것이다.
이렇게 Member를 생성하여 HashSet에 add로 넣었는데 "abc"는 중복을 제거했지만 Member객체는 저장되었다.
즉, 저 두 객체는 서로 다른 객체라고 인식했기 때문이다.
이렇게 추가하였더니 중복으로 받아들이고 제거됐다.
이 때 hashCode는 Objects.hash 메서드를 호출하는 로직이다.
간편하게 재정의했지만 속도가 느리다. 왜냐하면 인자를 담기위한 배열이 만들어지고 박싱과 언박싱도 거칠 수 있기 때문이다.
(성능에 민감하다면 직접 재정의를 해야한다.)
2. LinkedHashSet
이름처럼 Link + Hash + Set이 결합된 형태이다.
LinkedList에서 보면 add() 메서드를 통해 요소들을 넣은 순서대로 연결한다. 즉, 순서를 보장한다는 의미이다.
Set의 경우 저장순서를 보장하지 않는데, "중복은 허용하지 않으면서 순서를 보장받고 싶은 경우"에는 불편하다.
이걸 보완하기위해 존재하는 것이 LinkedHashSet이다.
e.g. 웹페이지의 캐시를 지울때 이 캐시는 중복되는 페이지는 없지만 지울 때는 가장 오래된 것을 지우는것이 현명하다. 이를 LRU 알고리즘(Least Recently Used Algorithm)으로 지우는데 이 때 입력된 순서를 알아야지 오래된 캐시를 지울 수 있다. 이에 적용할 수 있는 자료구조라 보면 되겠다.
3. TreeSet
TreeSet은 이진 탐색 트리(Binary Search Tree)라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스이다.
이진 탐색 트리는 정렬, 검색, 범위검색(range search)에 높은 성능을 보이는 자료구조이다.
Set 인터페이스를 구현했으므로 중복x, 저장순서 x 이다.
TreeSet은 생성자의 매개변수로 Comparator객체를 입력하여 정렬 방법을 지정할 수 있다.
TreeSet은 이진탐색트리 중에서도 성능을 향상한 레드-블랙 트리(Red-Black Tree)로 구현되어 있다.
(TreeSet 클래스는 NavigableSet 인터페이스의 이진 검색 트리의 성능을 향산시킨 레드-블랙 트리로 구현한 것)
이것은 부모노드보다 작은 값은 왼쪽 자식으로, 큰 값은 오른쪽 자식으로 배치한다.
참고
http://www.tcpschool.com/java/java_collectionFramework_set
https://tecoble.techcourse.co.kr/post/2020-07-29-equals-and-hashCode/
'프로그래밍 > Java' 카테고리의 다른 글
| Java - 값이 null,공백 등 Blank인지 확인하기 (0) | 2022.04.07 |
|---|---|
| Map 인터페이스 (0) | 2022.02.24 |
| Queue 인터페이스 (0) | 2022.02.22 |
| List 인터페이스 (0) | 2022.02.22 |
| Java 줄바꿈문자 \n 이란? (0) | 2022.02.17 |