Set은 데이터의 중복을 허용하지 않는 자료구조이다. 개발을 하다가 중복되지 않는 값을 저장하고 싶다면 Set을 이용하면 된다. Set은 해시 테이블을 이용하기 때문에 비교적 쉽게 구현할 수 있다. 해시 테이블을 사용한다고 해서 HashSet이라고도 불리기도 한다
핵심 특징
- HashTable의 key 값만 사용하고 value는 사용하지 않는다
- key가 key임과 동시에 data로 사용된다
- 중복은 자동으로 방지한다
HashSet의 추상 자료형
- add(data): 데이터를 삽입 (중복허용 안 함)
- isContain(data): 데이터 존재 여부 확인
- remove(data): 데이터 제거
- clear(): Set의 모든 요소를 비움
- isEmpty(): Set이 비어있는지 확인
- printAll(): 모든 데이터 출력 (테스트용)
HashSet 클래스
package linkedList;
/**
* 해시 테이블을 이용한 제네릭 HashSet 구현
*
* 특징
* - 중복 데이터를 허용하지 않음
* - HashTable에 key만 저장하며 value는 -1로 고정
* - 평균 O(1) 시간 복잡도로 삽입, 삭제, 검색
*
* 구현 원리
* - 내부적으로 HashTable<T, Integer>를 사용
* - data를 key로 저장하고 value는 항상 -1
* - 중복은 key의 고유성으로 자동 방지
*
* @param <T> Set에 저장될 데이터 타입
*/
public class HashSet<T> {
private HashTable<T, Integer> hashTable;
private static final int DUMMY_VALUE = -1; // value로 사용할 더미 값
/**
* 빈 HashSet을 생성한다
*/
public HashSet() {
this.hashTable = new HashTable<>();
}
/**
* Set에 데이터를 추가한다
*
* 중복 방지 원리
* 1. 먼저 hashTable.get(data)로 데이터 존재 여부 확인
* 2. null이 반환되면 → 데이터가 없음 → 추가
* 3. null이 아니면 → 이미 존재 → 추가하지 않음
*
* value는 사용하지 않으므로 -1로 고정
*
* 시간 복잡도: 평균 O(1)
*
* @param data 추가할 데이터
* @return 성공적으로 추가되면 true, 이미 존재하면 false
*/
public boolean add(T data) {
// 중복 확인: 이미 존재하지 않는 경우에만 추가
if (hashTable.get(data) == null) {
// key로 데이터 저장, value는 더미 값 사용
hashTable.set(data, DUMMY_VALUE);
return true; // 추가 성공
} else {
return false; // 이미 존재하여 추가 실패
}
}
/**
* Set에 특정 데이터가 존재하는지 확인한다
*
* 확인 방법
* - hashTable.get(data)의 결과가 null이 아니면 존재
*
* 시간 복잡도: 평균 O(1)
*
* @param data 확인할 데이터
* @return 데이터가 존재하면 true, 없으면 false
*/
public boolean isContain(T data) {
return hashTable.get(data) != null;
}
/**
* Set에서 특정 데이터를 제거한다
*
* 제거 방법
* - hashTable.remove(data)를 호출하여 해당 key 제거
*
* 시간 복잡도: 평균 O(1)
*
* @param data 제거할 데이터
* @return 성공적으로 제거되면 true, 데이터가 없으면 false
*/
public boolean remove(T data) {
Node<HashData<T, Integer>> removed = hashTable.remove(data);
return removed != null;
}
/**
* Set의 모든 데이터를 제거한다
*
* 구현 방식
* - HashTable의 모든 버킷(연결 리스트)을 순회
* - 각 버킷의 clear() 메서드를 호출하여 초기화
*
* 시간 복잡도: O(버킷 수)
*/
public void clear() {
// 모든 버킷을 순회하며 초기화
for (int i = 0; i < hashTable.getTableSize(); i++) {
hashTable.getBucket(i).clear();
}
}
/**
* Set이 비어 있는지 확인한다
*
* 확인 방법
* 1. 모든 버킷을 순회
* 2. 하나라도 데이터가 있으면 false 반환하고 종료
* 3. 모든 버킷이 비어있으면 true 반환
*
* 최적화: 데이터를 찾으면 즉시 break 문으로 루프 종료
*
* 시간 복잡도: 최선 O(1), 최악 O(버킷 수)
*
* @return Set이 비어있으면 true, 데이터가 있으면 false
*/
public boolean isEmpty() {
boolean empty = true; // 비어있다고 가정
// 모든 버킷을 순회
for (int i = 0; i < hashTable.getTableSize(); i++) {
if (hashTable.getBucket(i).getSize() > 0) {
// 데이터가 하나라도 있으면
empty = false;
break; // 더이상 확인할 필요 없음
}
}
return empty;
}
/**
* Set의 크기(저장된 데이터 개수)를 반환한다
*
* 계산 방식
* - 모든 버킷의 크기를 합산
*
* 시간 복잡도: O(버킷 수)
*
* @return 저장된 데이터의 개수
*/
public int size() {
int count = 0;
for (int i = 0; i < hashTable.getTableSize(); i++) {
count += hashTable.getBucket(i).getSize();
}
return count;
}
/**
* Set의 모든 데이터를 출력한다 (테스트/디버깅용)
*
* 출력 순서
* - HashTable의 버킷 순서대로 출력
* - 각 버킷 내에서는 연결 리스트 순서대로 출력
* - 데이터가 없으면 "(비어있음)" 출력
*
* 주의: 삽입 순서와 출력 순서는 다를 수 있음 (해시 함수에 의해 결정)
*/
public void printAll() {
boolean hasData = false;
// 모든 버킷을 순회
for (int i = 0; i < hashTable.getTableSize(); i++) {
Node<HashData<T, Integer>> currentNode = hashTable.getBucket(i).getHead();
// 각 버킷의 연결 리스트를 순회
while (currentNode != null) {
// key만 출력 (value인 -1은 의미 없으므로 출력 안함)
System.out.println(currentNode.getData().getKey());
currentNode = currentNode.getNext();
hasData = true;
}
}
if (!hasData) {
System.out.println("(비어있음)");
}
}
}
HashSetMain
package linkedList;
public class HashSetMain {
public static void main(String[] args) {
HashSet<Integer> hashSet = new HashSet<>();
System.out.println("===== 초기 상태 확인 =====");
System.out.println("isEmpty: " + hashSet.isEmpty());
System.out.println("size: " + hashSet.size());
// ===== 테스트 2: 데이터 삽입 및 중복 방지 =====
System.out.println("\n===== 데이터 삽입 =====");
hashSet.add(1); // 첫 번째 1 추가 → 성공
hashSet.add(1); // 두 번째 1 추가 시도 → 중복으로 실패
hashSet.add(256); // 256 추가 → 성공
hashSet.add(128); // 128 추가 → 성공
hashSet.printAll();
System.out.println("isEmpty: " + hashSet.isEmpty());
System.out.println("size: " + hashSet.size());
// ===== 테스트 3: 데이터 존재 확인 (1) =====
System.out.println("\n===== 데이터 체크1 =====");
System.out.println("isContain(1): " + hashSet.isContain(1)); // true
System.out.println("isContain(999): " + hashSet.isContain(999)); // false
// ===== 테스트 4: 데이터 제거 =====
System.out.println("\n===== 데이터1 제거 =====");
boolean removed = hashSet.remove(1);
System.out.println("1 제거 성공: " + removed);
hashSet.printAll();
System.out.println("isEmpty: " + hashSet.isEmpty());
System.out.println("size: " + hashSet.size());
// ===== 테스트 5: 제거 후 데이터 존재 확인 =====
System.out.println("\n===== 데이터 체크2 =====");
System.out.println("isContain(1): " + hashSet.isContain(1)); // false (제거됨)
// ===== 테스트 6: clear() 테스트 =====
System.out.println("\n===== clear =====");
hashSet.clear();
hashSet.printAll();
System.out.println("isEmpty: " + hashSet.isEmpty());
System.out.println("size: " + hashSet.size());
}
}
/*
실행 결과
===== 초기 상태 확인 =====
isEmpty: true
size: 0
===== 데이터 삽입 =====
1
256
128
isEmpty: false
size: 3
===== 데이터 체크1 =====
isContain(1): true
isContain(999): false
===== 데이터1 제거 =====
1 제거 성공: true
256
128
isEmpty: false
size: 2
===== 데이터 체크2 =====
isContain(1): false
===== clear =====
(비어있음)
isEmpty: true
size: 0
*/
주의사항
hashCode()와 equals() 오버라이드 필요한 이유
사용자 정의 객체를 HashSet에 저장할 때는 반드시 hashCode()와 equals()를 오버라이드 해야한다
HashSet의 중복 판단 알고리즘
// HashSet이 데이터를 추가할 때 내부적으로 수행하는 과정
1단계: hashCode() 호출
↓
2단계: 해시 코드로 버킷 위치 결정
↓
3단계: 해당 버킷에서 equals()로 기존 데이터와 비교
↓
4단계: equals()가 true이면 중복으로 간주되어 추가하지 않음
equals()가 false면 다른 객체 → 추가
오버라이드하지 않으면?
class Person {
String name;
int age;
// hashCode(), equals() 오버라이드 안 함!
}
Person p1 = new Person("홍길동", 25);
Person p2 = new Person("홍길동", 25); // 논리적으로 같은 사람
HashSet<Person> set = new HashSet<>();
set.add(p1);
set.add(p2);
System.out.println(set.size()); // 2 출력 (중복인데)
원인
// Object의 기본 구현 (메모리 주소 기반) p1.hashCode(); // → 366712642 (메모리 주소 기반) p2.hashCode(); // → 1829164700 (다른 주소) p1.equals(p2); // → false (참조 비교: this == obj) // 결과: 논리적으로 같아도 다른 객체로 인식!
해결: 올바른 오버라이드
import java.util.Objects;
class Person {
private String name;
private int age;
@Override
public int hashCode() {
// 의미있는 필드로 해시 코드 생성
return Objects.hash(name, age);
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
Person other = (Person) obj;
return age == other.age && Objects.equals(name, other.name);
}
}
// 이제 정상 동작!
Person p1 = new Person("홍길동", 25);
Person p2 = new Person("홍길동", 25);
HashSet<Person> set = new HashSet<>();
set.add(p1);
set.add(p2);
System.out.println(set.size()); // 1 출력 (중복 제거)
필수 규칙
// 규칙 1: equals가 true면 hashCode도 반드시 같아야 함
if (obj1.equals(obj2) == true) {
// obj1.hashCode() == obj2.hashCode() 보장!
}
// 규칙 2: hashCode가 같아도 equals는 false일 수 있음 (충돌 허용)
if (obj1.hashCode() == obj2.hashCode()) {
// equals는 true일 수도, false일 수도 있음
}
빠른 구현 방법
IDE 자동 생성을 활용하면 빠르게 구현할 수 있다
- IntelliJ: [
Alt + Insert] → Generate →equals() and hashCode()
순서 보장 안 됨
HashSet은 삽입 순서를 보장하지 않는다. 순서가 필요하면 LinkedHashSet을 사용해야 한다