1. HashSet은 내부적으로 HashMap을 사용한다

HashSet은 데이터를 직접 별도의 배열에 저장하는 것이 아니라 내부적으로 HashMap을 가지고 있다.

개념적으로 보면 다음과 같다.

HashSet

   ↓

HashMap

HashSet에 데이터를 추가하면 해당 데이터를 HashMap의 Key로 저장한다.

HashSet 값
     ↓
HashMap Key

예를 들어

set.add("Java");

를 실행하면 내부적으로는 개념상 다음과 비슷하게 동작한다.

map.put("Java", PRESENT);

실제 HashSet 구현에서도 내부에 하나의 고정된 객체를 Value로 사용한다.

Key
→ 실제 HashSet에 저장하려는 값

Value
→ 모든 데이터가 동일한 더미 객체

따라서 내부 구조는 개념적으로 다음과 같다.

HashMap

Key       Value

Java   → PRESENT
Spring → PRESENT
Redis  → PRESENT

HashSet에서는 Value 자체가 중요하지 않다.

중요한 것은 Key가 중복될 수 없다는 HashMap의 특성이다.

2. 데이터를 추가하면 어떤 일이 발생할까

다음 코드를 실행한다고 해보자.

Set<String> set = new HashSet<>();

set.add("Java");

HashSet은 내부적으로 HashMap에 "Java"를 Key로 넣는다.

전체적인 과정은 다음과 같다.

"Java"
   ↓
hashCode 계산
   ↓
Hash 값 계산
   ↓
저장할 Bucket 결정
   ↓
같은 Key가 있는지 확인
   ↓
없으면 저장

즉 HashSet의 중복 검사는 모든 값을 처음부터 하나씩 비교하는 방식이 아니다.

Hash를 이용해 데이터가 있을 가능성이 있는 위치부터 빠르게 찾는다.

3. hashCode로 Bucket을 찾는다

HashMap 내부에는 데이터를 저장하기 위한 배열이 있다.

각 위치를 Bucket이라고 생각할 수 있다.

Bucket

0
1
2
3
4
5
6
7

"Java"를 추가하면 먼저 hashCode()가 사용된다.

Java
 ↓
hashCode
 ↓
Hash 계산
 ↓
Bucket 3

그러면 해당 데이터를 Bucket 3에 저장한다.

0
1
2
3 → Java
4
5
6
7

이후 "Java"가 다시 들어오면 똑같은 Hash 계산을 수행한다.

Java
 ↓
hashCode
 ↓
Bucket 3

따라서 HashSet은 전체 데이터를 검색하지 않고 바로 Bucket 3을 확인할 수 있다.

4. hashCode가 같으면 중복일까

그렇지는 않다.

서로 다른 객체도 같은 Hash 값을 가질 수 있다.

예를 들어

A
 ↓
Bucket 3

B
 ↓
Bucket 3

처럼 서로 다른 값이 같은 Bucket에 들어갈 수 있다.

이를 Hash Collision이라고 한다.

따라서 HashSet은 hashCode()만으로 중복 여부를 결정하지 않는다.

hashCode
 ↓
같은 Bucket인지 확인

equals
 ↓
실제로 같은 값인지 확인

두 단계를 사용한다.

5. equals로 실제 중복 여부를 확인

예를 들어 Bucket 3에 이미 "Java"가 있다고 해보자.

Bucket 3

Java

다시 "Java"를 추가한다.

새 Java
   ↓
hashCode
   ↓
Bucket 3

같은 Bucket을 찾은 뒤 기존 Key와 비교한다.

기존 Java.equals(새 Java)

→ true

같은 Key라고 판단하므로 새로운 데이터를 추가하지 않는다.

기존

Bucket 3
Java


Java 다시 추가

        ↓

Bucket 3
Java

변화 없음

반대로 같은 Bucket에 들어왔더라도 equals() 결과가 false라면 서로 다른 데이터로 판단한다.

hashCode 같음

하지만

equals → false

        ↓

서로 다른 데이터

따라서 HashSet의 중복 판단에는 hashCode()와 equals()가 모두 중요하다.

6. HashSet이 중복을 제거하는 전체 과정

다음 코드가 있다고 해보자.

Set<String> set = new HashSet<>();

set.add("Java");
set.add("Spring");
set.add("Java");

첫 번째 "Java"가 들어온다.

Java
 ↓
hashCode
 ↓
Bucket 결정
 ↓
기존 값 없음
 ↓
저장

다음으로 "Spring"이 들어온다.

Spring
 ↓
hashCode
 ↓
Bucket 결정
 ↓
Bucket이 비어있으면 바로 저장 / Bucket에 기존 데이터가 있다면
 ↓
같은 Key인지 비교
 ↓
저장

마지막으로 "Java"가 다시 들어온다.

Java
 ↓
hashCode
 ↓
기존 Java와 같은 Bucket
 ↓
equals 비교
 ↓
true
 ↓
이미 존재하는 값
 ↓
저장하지 않음

최종적으로는

Java
Spring

만 남는다.

7. add의 반환값으로 중복 여부를 알 수 있다

HashSet의 add()는 boolean 값을 반환한다.

Set<String> set = new HashSet<>();

System.out.println(set.add("Java"));
System.out.println(set.add("Java"));

결과는 다음과 같다.

true
false

첫 번째 "Java"는 새로 추가되었기 때문에 true가 반환된다.

두 번째 "Java"는 이미 존재하기 때문에 추가되지 않고 false가 반환된다.

새로운 값
→ true

이미 존재하는 값
→ false

따라서 add()의 반환값을 이용해 중복 여부를 바로 확인할 수도 있다.

8. 객체를 저장할 때 hashCode와 equals가 중요한 이유

문자열이 아니라 직접 만든 객체를 HashSet에 저장한다고 해보자.

public class User {

    private Long id;
    private String name;
}

그리고 다음 객체를 만든다.

User user1 = new User(1L, "Kim");
User user2 = new User(1L, "Kim");

사람이 보기에는 같은 회원처럼 보인다.

하지만 User가 equals()와 hashCode()를 적절하게 구현하지 않았다면 HashSet은 두 객체를 서로 다른 객체라고 판단할 수 있다.

Set<User> users = new HashSet<>();

users.add(user1);
users.add(user2);

원하는 결과가

User 1개

라면 객체의 동일성을 판단할 기준을 정의해야 한다.

예를 들어 id가 같을 때 같은 사용자라고 판단한다면 equals()와 hashCode()도 id를 기준으로 일관되게 구현해야 한다.

같은 객체로 판단하고 싶음

  ↓

equals
+
hashCode

일관되게 구현

9. equals와 hashCode 간의 규칙

HashSet에서 중요한 규칙이 있다.

두 객체가 equals() 기준으로 같다면 hashCode()도 같아야 한다.

a.equals(b) == true

        ↓

a.hashCode() == b.hashCode()

가 되어야 한다.

반대로 Hash 값이 같다고 해서 반드시 같은 객체인 것은 아니다.

hashCode 같음

        ↓

같은 객체일 수도 있음
다른 객체일 수도 있음

        ↓

equals로 최종 확인

이 규칙이 깨지면 HashSet에서 중복을 제대로 판단하지 못할 수 있다.

10. Hash Collision이 많이 발생하면

같은 Bucket에 여러 데이터가 들어갈 수도 있다.

Bucket 3

A → B → C → D

이런 충돌이 계속 증가하면 해당 Bucket 안에서 데이터를 찾는 시간이 길어진다.

Java 8 이후 HashMap에서는 특정 Bucket에 충돌이 많이 발생하고 전체 배열 크기도 충분한 경우 내부 구조를 Red-Black Tree로 변경할 수 있다.

충돌이 적을 때

A → B → C


충돌이 많을 때

       B
      / \
     A   D
        /
       C

이를 통해 충돌이 심한 상황에서도 탐색 성능이 지나치게 떨어지는 것을 줄인다.

HashSet 역시 내부적으로 HashMap을 사용하므로 같은 원리가 적용된다.

11. HashSet이 중복 체크에 효율적인 이유

만약 일반적인 List를 이용해 중복 여부를 확인한다고 해보자.

List<String> list = new ArrayList<>();

if (!list.contains("Java")) {
    list.add("Java");
}

ArrayList.contains()는 원하는 데이터를 찾기 위해 앞에서부터 순차적으로 비교한다.

A
↓
B
↓
C
↓
D
↓
Java

데이터가 n개라면 최악의 경우 모든 데이터를 확인해야 하므로

O(n)

의 시간이 걸린다.

반면 HashSet은

Java
 ↓
hashCode
 ↓
Bucket 계산
 ↓
해당 Bucket만 확인

한다.

따라서 평균적인 검색과 중복 확인의 시간 복잡도는

O(1)

이다.

이것이 HashSet이 중복 확인에 효율적인 가장 큰 이유이다.

12. ArrayList와 HashSet의 중복 확인 비교

데이터가 다음과 같이 있다고 해보자.

A B C D E F G H

ArrayList에서 "H"가 존재하는지 확인하려면

A 확인
↓
B 확인
↓
C 확인
↓
...
↓
H 확인

처럼 순차 탐색이 발생할 수 있다.

반면 HashSet에서는

H
↓
hashCode
↓
Bucket 계산
↓
해당 위치 확인

이 가능하다.

정리하면 다음과 같다.

13. HashSet을 언제 사용하면 좋을까

HashSet은 다음과 같은 경우에 적합하다.

중복된 값을 제거하고 싶을 때

List<String> names = List.of(
        "Kim",
        "Lee",
        "Kim",
        "Park"
);

Set<String> uniqueNames = new HashSet<>(names);

결과는

Kim
Lee
Park

처럼 중복이 제거된다.

또 특정 값이 이미 존재하는지 빠르게 검사할 때도 사용할 수 있다.

if (users.contains(user)) {
    // 이미 존재
}

따라서 HashSet은

중복 제거

빠른 존재 여부 확인

이미 처리한 데이터 확인

등의 상황에서 유용하다.

14. HashSet은 순서를 보장하지 않는다

HashSet은 Hash 값을 기준으로 저장 위치를 결정하기 때문에 입력한 순서를 보장하지 않는다.

Set<String> set = new HashSet<>();

set.add("A");
set.add("B");
set.add("C");

입력 순서는

A
B
C

이지만 순회할 때 반드시 같은 순서로 나온다고 보장할 수 없다.

입력 순서를 유지해야 한다면

LinkedHashSet

을 사용할 수 있고,

정렬된 상태가 필요하다면

TreeSet

을 사용할 수 있다.

15. 핵심 정리

HashSet은 내부적으로 HashMap을 사용한다.

HashSet 값
     ↓
HashMap Key

데이터를 추가할 때는 다음 과정으로 중복을 검사한다.

데이터
 ↓
hashCode
 ↓
Hash 계산
 ↓
Bucket 찾기
 ↓
equals 비교
 ↓
같으면 중복
다르면 새로운 값

hashCode()는 어디에서 찾을지 결정하고 equals()는 실제로 같은 값인지 판단한다고 이해하면 쉽다.

hashCode
→ 어느 Bucket인가

equals
→ 같은 객체인가

HashSet이 중복 검사에 효율적인 이유는 모든 데이터를 순차적으로 탐색하지 않고 Hash를 통해 필요한 Bucket으로 바로 접근하기 때문이다.

따라서 평균적인 추가, 검색, 중복 확인은

O(1)

의 시간 복잡도를 가진다.

한 문장으로 정리하면

HashSet은 내부적으로 HashMap의 Key를 이용해 값을 저장하며, hashCode로 저장 위치를 찾고 equals로 실제 동일성을 확인하기 때문에 평균 O(1)의 빠른 중복 체크가 가능하다.