자바 공부#2_02. Set

Set?

Set은 쉽게 말해 집합이다.

Set 특징

1. 순서 ❌(LinkedHashSet 예외)
2. 중복 허용 ❌

Set 인터페이스를 구현한 대표적인 클래스에는 HashSet, TreeSet, LinkedHashSet가 있다.

 

1. HashSet

HashSet은 가장 기본적인 Set 컬렉션의 클래스인데, 순서를 전혀 보장하지 않는다. hash에 의해 데이터의 위치를 특정시켜 해당 데이터를 빠르게 색인(search)할 수 있게 만든 것이다. 즉, Hash 기능과 Set 컬렉션이 합쳐진 것이 HashSet이다. HashSet은 Set 중에 가장 성능이 좋다.

특징

• 중복 저장 불가 (equals(), hashCode() 기준)
• 입력 순서 유지 ❌
• 검색, 추가, 삭제가 빠름 (평균 O(1))
• null 저장 가능 (1개)
• 삽입, 삭제, 색인이 매우 빠름

따라서 순서에 상관없이 중복 없는 데이터를 빠르게 저장/조회해야 할 때 적합하다.

ex) 태그 목록, 사용자 id 집합 등 고유한 값만 저장

 

2. LinkedHashSet

LinkedHashSet은 HashSet과 거의 동일하지만, 요소가 추가된 순서를 유지한다는 점에서 다르다. 연결된 목록 타입으로 구현된 해시 테이블에 데이터를 저장한다. 성능은 hashSet과 비슷하지만 조금 느릴 수 있다.

특징

• 중복 저장 불가
• 입력 순서 유지 ✅
• 검색 성능은 HashSet보다 약간 느릴 수 있음
• null 저장 가능

따라서 중복 제거와 동시에 입력 순서도 보존하고 싶을 때 적합하다.

ex) 최근 검색어 목록, 사용자 활동 로그 등, (LRU알고리즘(LeastRecently Used Algorithm)에 적용할 수 있는 자료구조 중 하나)

 

3. TreeSet

TreeSet은 데이터의 '가중치에 따른 순서'대로 정렬되어 저장된다. red-black이라는 트리 타입으로 값이 저장되며, set 컬렉션의 구현 클래스 중 가장 느리다.

특징

• 중복 저장 불가
• 요소 자동 정렬 (기본 오름차순 / Comparable 또는 Comparator 사용 가능)
• 탐색, 추가, 삭제는 평균 O(log n)
• null 저장 ❌ (넣으면 NullPointerException 발생)

따라서 정렬된 형태로 데이터를 관리하고 싶을 때  적합하다.

ex) 랭킹, 사전, 정렬된 유저 리스트 등

 

---

 

4. HashSet vs LinkedHashSet vs TreeSet

	HashSet	LinkedHashSet	TreeSet
add()	O(1)	O(1)	O(log n)
remove()	O(1)	O(1)	O(log n)
contains()	O(1)	O(1)	O(log n)
순회	O(n)	O(n)	O(n)

 

Set은 일반적으로 성능 차이가 크지 않지만, 데이터를 출력하거나 특정 요소를 접근할 때 Iterable을 사용해야 하므로 직접적인 인덱스 접근이 불가능하다는 점에서 불리할 수 있다.

HashSet과 LinkedHashSet은 내부적으로 모두 HashMap을 기반으로 동작한다.
두 자료구조의 가장 큰 차이점은 요소 간의 순서를 기억하느냐 여부다.
LinkedHashSet은 HashMap 내부에 앞/뒤 요소를 추적할 수 있는 링크드 리스트 구조가 추가되어 있어, 요소의 입력 순서를 유지할 수 있다.
반면 HashSet은 입력 순서를 보장하지 않으며, 오직 해시값(hashCode()) 기반으로 저장한다.

둘의 시간복잡도는 같지만 LinkedHashSet에서 약간의 오버헤드가 발생한다.

 

	HashSet	LinkedHashSet	TreeSet
정렬 기준	없음 (순서 보장 X)	입력 순서 유지	정렬 순서 유지 (기본 오름차순)
내부 구조	해시 테이블	해시 테이블 + 더블 링크드 리스트	이진 탐색 트리 (TreeMap 기반)
필요 조건	equals() + hashCode() 오버라이딩	equals() + hashCode() 오버라이딩	Comparable 구현 또는 Comparator 제공
성능	가장 빠름 (O(1))	빠름 (HashSet보다 약간 느림)	느림 (O(log n)) — 트리 탐색 기반
중복 허용 여부	❌ 허용하지 않음	❌ 허용하지 않음	❌ 허용하지 않음
순서 보장 여부	❌ 보장하지 않음	✅ 입력 순서 보장	✅ 정렬 순서 보장
적합한 용도	빠른 중복 제거가 중요할 때	순서를 유지하면서 중복 없이 저장할 때	정렬된 상태로 데이터 관리 및 탐색이 필요할 때

 

 

---

 

for문보다 Iterable 기반 반복문 (for-each) 사용이 일반적

• Set은 내부적으로 인덱스를 갖고 있지 않기 때문
  (List는 인덱스를 기반으로 접근 가능하지만, Set은 그냥 요소들의 집합일 뿐!)

잘못된 방식 (index 기반 접근 불가)

Set<String> set = new HashSet<>();
set.add("apple");
set.add("banana");

// 오류 발생!
for (int i = 0; i < set.size(); i++) {
    // set.get(i); ← 존재하지 않음
}

일반적인 방식 (Iterable)

for (String item : set) {
    System.out.println(item);
}

혹은

Iterator<String> iterator = set.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

 

 

• Set은 인덱스가 없기 때문에 get(i)처럼 접근할 수 없음
• 그래서 for-each 반복문이나 Iterator 기반 반복이 기본
• 정렬/순서가 필요한 경우 → List나 LinkedHashSet, TreeSet 등으로 변환 후 사용하면 됨

 

Q.정렬/순서가 필요한 경우 애초에 List로 만들면 안됨?

• 처음부터 순서 + 중복 허용 필요하면 → List
• 중복 제거가 우선이면 → Set 사용 후, 필요에 따라 List로 변환

데이터를 어떻게 다룰지에 따라 전략적으로 선택

 

 

---

 

5. Set의 equals(), hashCode()

HashSet과 LinkedHashSet은 내부적으로 해시 테이블(Hash Table) 을 사용한다.
이 때 객체의 해시값을 계산해 저장 위치를 결정하는데, 이 해시값을 생성하는 메서드가 바로 hashCode()이다

hashCode()

• 객체의 해시값(정수) 을 반환하는 메서드
• HashSet, HashMap 와 같이 해시 기반 자료구조는 내부적으로 이 값을 이용해서 객체의 위치(버킷)를 정함.
• 기본 구현은 Object.hashCode()로, 객체의 메모리 주소 기반 값 반환.
  → 동일한 값을 갖고 있어도 hashCode가 다를 수 있음.

 

이렇게 되면 Set.contains()나 Set.add()에서 중복 판단이 제대로 동작하지 않을 수 있다.

 

---

해결 방법 → hashCode(), equals() 오버라이딩

hashCode()는 같은 객체에 대해 같은 값을 반환하도록 오버라이딩 해야 한다.

동일한 논리적 데이터 → 같은 hashCode()

하지만 서로 다른 객체인데도 같은 해시값을 가지는 경우도 있다. 이걸 해시 충돌이라고 한다.

 

해시 충돌이 발생하면?

HashSet, HashMap 같은 자료구조는 내부적으로 해시 버킷이라는 구조를 쓴다. 

해시 충돌 처리 방식

1. 버킷에 이미 값이 있다면? → equals() 호출하여 진짜 같은 값인지 확인
2. equals()가 true → 중복이므로 저장 안 함
   equals()가 false → 같은 hashCode지만 다른 객체이므로 저장

따라서 hashCode()를 오버라이딩 하면 equals()도 오버라이딩 해야한다.

 

 

자바 규약

equals()로 두 객체가 같다고 판단되면, 그 두 객체의 hashCode() 값도 같아야 한다.

또한 위와 같은 자바의 규약으로 인해, equals()를 오버라이딩한다면 hashCode()도 같이 오버라이딩 해야한다.

 

hashCode()와 equals()는 항상 세트로 오버라이딩해야 한다는 걸 알 수 있다.

 

예시 코드는 다음과 같다.

public class A {
    private String str;
    private int n1;

    @Override
    public boolean equals(Object obj) {
        if(this == obj){
            return true;
        }
        if(!(obj instanceof A)){
            return false;
        }

        A a = (A)obj;
        return Objects.equals(this.str, a.str) && this.n1 == a.n1;
    }

    @Override
    public int hashCode() {
        return Objects.hash(str, n1);
    }
}

 

 

 

참고:

https://velog.io/@korea3611/JAVA-Set%EC%97%90-%EB%8C%80%ED%95%98%EC%97%AC

https://st-lab.tistory.com/258

https://readerr.tistory.com/36

https://velog.io/@myway00/JAVA-HashSet%EC%97%90-%EB%8C%80%ED%95%9C-%EA%B3%A0%EC%B0%B0

https://ksabs.tistory.com/188