제네릭 Set과 재해시
Object 저장소의 타입 손실을 컴파일 오류로 옮기고 `add`·`remove`·포함 여부·확장 규칙을 MyHashSet으로 통합합니다.
정수 전용 MyHashSetV1은 충돌 원리를 보여 주지만 StudyTag나 SessionKey를 저장할 수 없습니다.
Object로 바꾸면 호출자가 타입을 잘못 섞을 수 있습니다.
이번 리팩터링은 MySet<E> 역할을 먼저 선언하고 구현 내부의 그룹만 Object 배열 제약을 처리하게 합니다.
적재 계수가 임계치를 넘을 때 재해시하는 경계도 포함합니다.
잘못된 원소 타입의 저장 거부
원시 타입을 사용하면 String 집합으로 만든 객체에 Integer를 넣을 수 있습니다. 컴파일러는 비검사 경고만 내고 실행은 계속됩니다. 나중에 순회하면서 String으로 사용할 때 ClassCastException이 발생합니다.
import java.util.HashSet;
import java.util.Set;
public final class RawSetHeapPollutionFailure {
public static void main(String[] args) {
Set<String> typed = new HashSet<>();
typed.add("hash");
Set raw = typed;
raw.add(100);
for (String value : typed) {
System.out.println(value.toUpperCase());
}
}
}java.lang.ClassCastException원시 타입은 이전 바이너리 호환을 위한 통로이지 일반 구현 전략이 아닙니다.
MySet<E>의 add가 E만 받으면 Integer 입력은 최초 호출 줄에서 컴파일 실패가 됩니다.
내부 배열 생성 때문에 필요한 비검사 변환은 생성자 한 곳으로 제한합니다.
Set 연산의 결과 의미
boolean add(E)는 새 동등성 그룹이 생겼는지, boolean remove(E)는 실제 원소가 사라졌는지 말합니다.
포함 여부는 상태를 바꾸지 않습니다.
size는 저장 요청 횟수가 아니라 현재 서로 다른 원소 수입니다.
반복자 순서는 MySet의 공통 규칙에 넣지 않아 해시 구현이 자유롭게 그룹 순회할 수 있게 합니다.
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Objects;
public final class GenericMyHashSet {
public static void main(String[] args) {
MySet<String> set = new HashMySet<>(4);
System.out.println(set.add("hash"));
System.out.println(set.add(new String("hash")));
System.out.println(set.add("set"));
System.out.println(set.add("bucket"));
System.out.println("contains=" + set.contains("set") + ", size=" + set.size());
for (String value : set) {
System.out.println(value);
}
}
private interface MySet<E> extends Iterable<E> {
boolean add(E value);
boolean contains(E value);
boolean remove(E value);
int size();
}
private static final class HashMySet<E> implements MySet<E> {
private static final double MAX_LOAD = 0.75;
private List<E>[] buckets;
private int size;
@SuppressWarnings("unchecked")
HashMySet(int capacity) {
if (capacity <= 0) throw new IllegalArgumentException("capacity");
buckets = (List<E>[]) new List<?>[capacity];
initialize(buckets);
}
public boolean add(E value) {
Objects.requireNonNull(value, "value");
if (contains(value)) return false;
if ((size + 1.0) / buckets.length > MAX_LOAD) resize(buckets.length * 2);
bucket(value).add(value);
size++;
return true;
}
public boolean contains(E value) {
Objects.requireNonNull(value, "value");
return bucket(value).contains(value);
}
public boolean remove(E value) {
Objects.requireNonNull(value, "value");
boolean removed = bucket(value).remove(value);
if (removed) size--;
return removed;
}
public int size() {
return size;
}
private List<E> bucket(E value) {
return buckets[Math.floorMod(value.hashCode(), buckets.length)];
}
@SuppressWarnings("unchecked")
private void resize(int capacity) {
List<E>[] old = buckets;
buckets = (List<E>[]) new List<?>[capacity];
initialize(buckets);
for (List<E> bucket : old) {
for (E value : bucket) {
bucket(value).add(value);
}
}
}
private static <E> void initialize(List<E>[] target) {
for (int i = 0; i < target.length; i++) {
target[i] = new ArrayList<>();
}
}
public Iterator<E> iterator() {
return new Iterator<>() {
private int bucketIndex;
private int elementIndex;
public boolean hasNext() {
advanceEmptyBuckets();
return bucketIndex < buckets.length;
}
public E next() {
if (!hasNext()) throw new NoSuchElementException();
return buckets[bucketIndex].get(elementIndex++);
}
private void advanceEmptyBuckets() {
while (bucketIndex < buckets.length
&& elementIndex >= buckets[bucketIndex].size()) {
bucketIndex++;
elementIndex = 0;
}
}
};
}
}
}resize는 기존 그룹 목록을 새 배열 위치에 그대로 복사하지 않습니다.
용량이 바뀌면 floorMod 결과도 달라지므로 모든 원소의 새 index를 계산합니다.
재배치 중 size를 증가시키지 않아 논리 원소 수가 두 번 세어지지 않습니다.
null 정책과 iterator 변경 정책
표준 HashSet은 null 하나를 허용하지만 학습 구현은 Objects.requireNonNull로 금지했습니다.
null에서 hashCode를 호출할 수 없다는 구현 편의뿐 아니라 도메인에서 빈 태그를 인정하지 않는다는 정책입니다.
인터페이스 사용자가 알 수 있도록 문서와 예외를 함께 고정해야 합니다.
위 반복자는 순회 도중 add나 remove를 감지하지 않습니다.
제품 수준 컬렉션은 modCount 같은 구조 변경 횟수로 즉시 실패 진단을 제공할 수 있습니다.
여기서는 순회 중 변경 금지를 사용 규칙으로 두고, Iterator 구현 자체는 그룹을 한 번씩만 방문하는 데 집중합니다.
제네릭이라고 런타임에 E별 배열이 생기는 것은 아닙니다.
타입 소거 뒤에도 그룹에는 실제 객체 참조가 저장됩니다.
안전성은 모든 쓰기가 add(E)를 통과한다는 컴파일 규칙에서 나옵니다.
Study Log의 완료 키 저장소를 역할로 수신
서비스는 HashSet 구체 타입 대신 Set<StudyKey>를 생성자로 받습니다.
순서가 필요하면 LinkedHashSet을, 일반 중복 검사면 HashSet을 조립 지점에서 선택할 수 있습니다.
완료 처리 결과는 add boolean을 그대로 도메인 결과로 번역합니다.
import java.util.HashSet;
import java.util.Set;
public final class CompletionSetService {
public static void main(String[] args) {
CompletionService service = new CompletionService(new HashSet<>());
System.out.println(service.complete(new StudyKey("java", "hash")));
System.out.println(service.complete(new StudyKey("java", "hash")));
System.out.println(service.complete(new StudyKey("java", "set")));
System.out.println("count=" + service.count());
}
private static final class CompletionService {
private final Set<StudyKey> completed;
private CompletionService(Set<StudyKey> completed) {
this.completed = Set.copyOf(completed);
}
String complete(StudyKey key) {
Set<StudyKey> mutable = new HashSet<>(completed);
return mutable.add(key) ? "new" : "already";
}
int count() {
return completed.size();
}
}
private record StudyKey(String track, String topic) {}
}이 예제는 의도적으로 버그가 있습니다.
생성자에서 Set.copyOf로 고정하고 완료마다 임시 복사본만 바꾸므로 서비스 상태가 누적되지 않습니다.
출력은 매번 new이고 count는 0입니다.
불변 스냅숏과 가변 내부 상태를 혼동한 실패를 찾아 다음 연습에서 고칩니다.
연습 문제
내부 Set의 소유권은 서비스가 갖되 외부 초기값 변경은 받지 않게 하세요.
같은 StudyKey 두 번은 new, already를 출력하고 count는 2가 되어야 합니다.
정답과 해설
생성자에서 new HashSet<>(initial)로 방어적 가변 복사를 만들고 완료는 그 필드에 직접 add합니다.
조회 결과를 외부로 보낼 때만 Set.copyOf를 사용합니다.
import java.util.HashSet;
import java.util.Set;
public final class CompletionServiceSolution {
public static void main(String[] args) {
Service service = new Service(Set.of());
System.out.println(service.complete(new Key("java", "hash")));
System.out.println(service.complete(new Key("java", "hash")));
System.out.println(service.complete(new Key("java", "set")));
System.out.println("count=" + service.snapshot().size());
}
private static final class Service {
private final Set<Key> completed;
Service(Set<Key> initial) {
completed = new HashSet<>(initial);
}
String complete(Key key) {
return completed.add(key) ? "new" : "already";
}
Set<Key> snapshot() {
return Set.copyOf(completed);
}
}
private record Key(String track, String topic) {}
}내부는 누적 가능하고 반환값은 불변입니다.
제네릭 Set 규칙, 소유권, 중복 결과가 한 구현에서 함께 맞습니다.
제네릭 MySet 완성 여부는 잘못된 타입이 컴파일에서 막히는지, 재해시 뒤 포함 여부가 유지되는지, 중복 add와 실패 remove가 size를 바꾸지 않는지로 판단합니다.