Theme:

HashSet과 중복 제거 — 유일성을 보장하는 자료구조의 원리

자료구조HashSet
2026-03-03·6 min read

"이 데이터가 이전에 나온 적이 있는가?"라는 질문에 가장 빠르게 답하는 방법은 무엇일까요?

HashSet이란

HashSet은 중복을 허용하지 않는 집합(Set) 을 구현한 자료구조입니다.

  • 요소의 순서를 보장하지 않습니다
  • add, remove, contains가 O(1) 평균입니다
  • null을 하나만 저장할 수 있습니다
JAVA
Set<String> set = new HashSet<>();
set.add("apple");   // true (추가됨)
set.add("banana");  // true
set.add("apple");   // false (이미 존재 → 무시)

set.contains("apple"); // true — O(1)
set.size();            // 2

내부 구현 — HashMap 래핑

HashSet의 코드를 열어보면 놀라울 정도로 단순합니다.

JAVA
// HashSet 내부 (실제 Java 소스 기반)
public class HashSet<E> implements Set<E> {
    private transient HashMap<E, Object> map;
    private static final Object PRESENT = new Object(); // 더미 값

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

    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }

    public boolean remove(Object o) {
        return map.remove(o) == PRESENT;
    }

    public boolean contains(Object o) {
        return map.containsKey(o);
    }

    public int size() {
        return map.size();
    }
}

HashSet은 HashMap의 키만 사용하고, 값은 더미 객체(PRESENT) 로 채우는 구조입니다. Set의 모든 연산은 HashMap의 연산으로 위임됩니다.

equals()와 hashCode() — 가장 중요한 계약

HashSet이 "같은 객체"를 판단하는 기준은 두 메서드입니다.

판단 과정

PLAINTEXT
1. hashCode()로 버킷 위치 결정
2. 같은 버킷 내에서 equals()로 동등성 비교

규칙 (equals-hashCode 계약)

  • equals()가 true인 두 객체는 반드시 같은 hashCode()를 가져야 합니다
  • hashCode()가 같다고 equals()가 true인 것은 아닙니다 (충돌 가능)
  • equals()를 재정의하면 ** 반드시** hashCode()도 재정의해야 합니다

잘못된 예시

JAVA
public class User {
    private Long id;
    private String name;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof User)) return false;
        User user = (User) o;
        return Objects.equals(id, user.id); // id가 같으면 같은 사용자
    }

    // hashCode를 재정의하지 않음! — 문제 발생
}

Set<User> users = new HashSet<>();
User u1 = new User(1L, "Alice");
User u2 = new User(1L, "Alice");

users.add(u1);
users.add(u2);

u1.equals(u2);          // true — 같은 사용자
users.size();            // 2 — 중복이 제거되지 않음!
users.contains(u2);     // false일 수도 있음!

hashCode가 다르면 다른 버킷에 저장되어, equals를 비교할 기회조차 없습니다.

올바른 구현

JAVA
public class User {
    private Long id;
    private String name;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof User)) return false;
        User user = (User) o;
        return Objects.equals(id, user.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id); // equals에서 사용하는 필드로 hashCode 계산
    }
}

Set<User> users = new HashSet<>();
users.add(new User(1L, "Alice"));
users.add(new User(1L, "Alice"));
users.size(); // 1 — 중복이 정상적으로 제거됨

Lombok 또는 record 활용

JAVA
// Lombok 사용
@EqualsAndHashCode(of = "id")
public class User {
    private Long id;
    private String name;
}

// Java 16+ record 사용 (자동으로 equals/hashCode 생성)
public record UserId(Long id) {}

가변 객체의 위험성

HashSet에 저장된 객체의 hashCode가 바뀌면 큰 문제가 생깁니다.

JAVA
List<String> list = new ArrayList<>();
list.add("hello");

Set<List<String>> set = new HashSet<>();
set.add(list);

set.contains(list); // true

// 리스트를 수정하면 hashCode가 변경됨!
list.add("world");

set.contains(list); // false! — 같은 객체인데 찾지 못함
set.size();         // 1 — 여전히 들어있지만 접근 불가

이런 이유로 HashSet의 요소는 ** 불변 객체 **가 적합합니다. String, Integer, record 등이 좋은 선택입니다.

집합 연산

JAVA
Set<String> a = new HashSet<>(Set.of("apple", "banana", "cherry"));
Set<String> b = new HashSet<>(Set.of("banana", "cherry", "date"));

// 합집합
Set<String> union = new HashSet<>(a);
union.addAll(b);       // {apple, banana, cherry, date}

// 교집합
Set<String> intersection = new HashSet<>(a);
intersection.retainAll(b); // {banana, cherry}

// 차집합
Set<String> diff = new HashSet<>(a);
diff.removeAll(b);     // {apple}

// 부분집합 확인
boolean isSubset = b.containsAll(Set.of("banana", "date")); // true

Set 구현체 비교

구현체내부 구조순서add/contains
HashSetHashMap없음O(1)
LinkedHashSetLinkedHashMap삽입 순서O(1)
TreeSetTreeMap (RB Tree)정렬 순서O(log n)
EnumSet비트셋enum 선언 순서O(1)
JAVA
// 삽입 순서 유지가 필요하면
Set<String> ordered = new LinkedHashSet<>();
ordered.add("C");
ordered.add("A");
ordered.add("B");
// 순회: C, A, B (삽입 순서)

// 정렬 순서가 필요하면
Set<String> sorted = new TreeSet<>();
sorted.add("C");
sorted.add("A");
sorted.add("B");
// 순회: A, B, C (사전 순서)

실무 활용

대량 데이터 중복 제거

JAVA
// CSV에서 중복 이메일 제거
Set<String> uniqueEmails = new HashSet<>();
int duplicateCount = 0;

try (BufferedReader reader = new BufferedReader(new FileReader("users.csv"))) {
    String line;
    while ((line = reader.readLine()) != null) {
        String email = extractEmail(line);
        if (!uniqueEmails.add(email)) {
            duplicateCount++; // add가 false를 반환하면 중복
        }
    }
}
System.out.println("중복 제거된 이메일: " + uniqueEmails.size());
System.out.println("중복 건수: " + duplicateCount);

Stream API에서의 distinct()

JAVA
// distinct()는 내부적으로 HashSet을 사용
List<String> names = List.of("Alice", "Bob", "Alice", "Charlie", "Bob");
List<String> unique = names.stream()
    .distinct() // HashSet 기반 중복 제거
    .collect(Collectors.toList());
// [Alice, Bob, Charlie]

// 특정 필드 기준 중복 제거 (커스텀)
List<User> uniqueUsers = users.stream()
    .collect(Collectors.collectingAndThen(
        Collectors.toMap(User::getId, u -> u, (a, b) -> a),
        map -> new ArrayList<>(map.values())
    ));

JPA Entity에서의 Set

JAVA
@Entity
public class Tag {
    @Id @GeneratedValue
    private Long id;
    private String name;

    // equals/hashCode를 name 기반으로 구현하면
    // Set<Tag>로 중복 태그를 자동 방지
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Tag)) return false;
        Tag tag = (Tag) o;
        return Objects.equals(name, tag.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name);
    }
}

@Entity
public class Post {
    @ManyToMany
    private Set<Tag> tags = new HashSet<>(); // 중복 태그 자동 방지
}

캐시에서 처리 완료 확인

JAVA
@Service
public class EventProcessor {
    // 이미 처리한 이벤트 ID를 기록
    private final Set<String> processedIds = ConcurrentHashMap.newKeySet();

    public void processEvent(Event event) {
        // 원자적으로 추가 시도 — 이미 있으면 false
        if (!processedIds.add(event.getId())) {
            log.info("이미 처리된 이벤트: {}", event.getId());
            return; // 중복 처리 방지
        }

        // 실제 처리 로직
        doProcess(event);
    }
}

Collections.unmodifiableSet과 Set.of

JAVA
// 불변 Set 생성
Set<String> immutable1 = Collections.unmodifiableSet(new HashSet<>(Set.of("a", "b")));
Set<String> immutable2 = Set.of("a", "b"); // Java 9+

immutable2.add("c"); // UnsupportedOperationException!

// Set.copyOf — 방어적 복사
Set<String> mutable = new HashSet<>();
mutable.add("hello");
Set<String> copy = Set.copyOf(mutable); // 불변 복사본
mutable.add("world"); // copy에는 영향 없음

정리

  • HashSet은 내부적으로 HashMap을 래핑 하며, 값에 더미 객체를 저장합니다.
  • 중복 판단은 hashCode() → equals() 순서로 이루어집니다. 이 둘을 반드시 함께 재정의해야 합니다.
  • 가변 객체를 HashSet에 저장하면 hashCode 변경으로 인한 유실 위험 이 있으므로, 불변 객체를 사용하는 것이 안전합니다.
  • 실무에서는 대량 데이터 중복 제거, 이벤트 중복 처리 방지, JPA Entity 관리 등에 활용됩니다.
  • 순서가 필요하면 LinkedHashSet, 정렬이 필요하면 TreeSet을 선택합니다.
related posts
댓글 로딩 중...
On This Page
HashSet이란내부 구현 — HashMap 래핑equals()와 hashCode() — 가장 중요한 계약판단 과정규칙 (equals-hashCode 계약)잘못된 예시올바른 구현Lombok 또는 record 활용가변 객체의 위험성집합 연산Set 구현체 비교실무 활용대량 데이터 중복 제거Stream API에서의 distinct()JPA Entity에서의 Set캐시에서 처리 완료 확인Collections.unmodifiableSet과 Set.of정리