MyHashSetV1 구현

Set은 “값이 있는가”를 표현하고 같은 값은 한 번만 보관합니다.

배열 전체를 매번 검색하면 포함 여부는 O(n)입니다.

MyHashSetV1은 정수 값을 해시 인덱스로 좁힌 뒤 한 그룹만 확인합니다.

이번 구현의 목표는 Java HashSet 복제가 아니라 충돌 처리와 size 갱신 조건을 코드로 증명하는 것입니다.

단일 충돌 칸의 원소 손실

다음 실패 예제는 1을 넣은 뒤 같은 index의 9를 넣습니다.

저장 칸 하나를 덮어써서 포함 여부(1)이 false가 됩니다.

해시 index는 원소 식별자가 아니라 후보 그룹 번호입니다.

public final class SingleSlotSetCollisionBug {
    public static void main(String[] args) {
        Integer[] slots = new Integer[8];
        slots[Math.floorMod(1, slots.length)] = 1;
        slots[Math.floorMod(9, slots.length)] = 9;
        boolean containsOne = java.util.Objects.equals(slots[Math.floorMod(1, 8)], 1);
        System.out.println("contains-1=" + containsOne + ", stored=" + slots[1]);
    }
}

contains-1=false, stored=9

해결은 각 slots 칸을 List<Integer> 그룹으로 바꾸는 것입니다.

add는 해당 목록에서 같은 값을 먼저 찾고, 없을 때만 추가합니다.

충돌 값은 공존하지만 논리적으로 같은 값은 거부됩니다.

boolean 반환값으로 상태 변화 여부를 표현

Set.add의 결과는 새 값이 저장되면 true, 이미 있으면 false입니다.

호출자는 add 전후 size를 다시 비교하지 않고 중복 여부를 알 수 있습니다.

remove도 실제 제거가 있었는지 boolean으로 알립니다.

size는 성공한 add와 remove에서만 변해야 합니다.

import java.util.ArrayList;
import java.util.List;

public final class MyHashSetV1 {
    public static void main(String[] args) {
        IntHashSet set = new IntHashSet(8);
        System.out.println("add1=" + set.add(1));
        System.out.println("add9=" + set.add(9));
        System.out.println("again1=" + set.add(1));
        System.out.println("contains9=" + set.contains(9));
        System.out.println("remove1=" + set.remove(1));
        System.out.println("size=" + set.size() + ", buckets=" + set);
    }

    private static final class IntHashSet {
        private final List<Integer>[] buckets;
        private int size;

        @SuppressWarnings("unchecked")
        IntHashSet(int bucketCount) {
            if (bucketCount <= 0) throw new IllegalArgumentException("bucketCount");
            buckets = (List<Integer>[]) new List<?>[bucketCount];
            for (int i = 0; i < buckets.length; i++) {
                buckets[i] = new ArrayList<>();
            }
        }

        boolean add(int value) {
            List<Integer> bucket = bucket(value);
            if (bucket.contains(value)) return false;
            bucket.add(value);
            size++;
            return true;
        }

        boolean contains(int value) {
            return bucket(value).contains(value);
        }

        boolean remove(int value) {
            boolean removed = bucket(value).remove(Integer.valueOf(value));
            if (removed) size--;
            return removed;
        }

        int size() {
            return size;
        }

        private List<Integer> bucket(int value) {
            int index = Math.floorMod(Integer.hashCode(value), buckets.length);
            return buckets[index];
        }

        public String toString() {
            return java.util.Arrays.toString(buckets);
        }
    }
}

remove(Integer.valueOf(value))가 중요한 이유는 List의 remove 오버로드입니다.

List<Integer>에 int를 직접 넘기면 remove(int index)가 선택됩니다. 이 메서드는 그 위치의 원소를 반환하며, 인덱스가 목록 범위 밖이면 예외를 던집니다. 값으로 찾는 remove(Object)는 실제 삭제 여부를 boolean으로 반환합니다. List.remove 공식 문서

Integer 객체로 감싸 “이 값과 같은 원소”를 제거한다는 뜻을 고정합니다.

여기서 1과 9는 값이고 그룹 목록의 인덱스는 0과 1입니다. [1, 9, 17]의 새 복사본에서 remove(1)을 호출하면 int 인수라 인덱스 1의 값 9가 제거됩니다. 별도의 새 복사본에서 remove(Integer.valueOf(1))을 호출하면 값 1이 제거되어 [9, 17]이 남습니다. 두 호출을 같은 목록에 차례로 적용한 결과가 아닙니다.

생성자의 배열 형변환은 별개의 Java 타입 제약입니다. new List<Integer>[bucketCount]처럼 타입 인수가 정해진 제네릭 배열은 직접 만들 수 없어 List<?>[]를 만든 뒤 형변환합니다. @SuppressWarnings("unchecked")는 컴파일러의 경고를 숨길 뿐 안전성을 검사해 주지 않습니다. 이 예제는 배열을 private으로 소유하고 각 칸에 ArrayList<Integer>만 넣으며 외부에 배열을 넘기지 않는 방식으로 타입 전제를 지킵니다. 이 부분이 낯설면 앞 절의 List<List<Entry>>처럼 목록의 목록을 쓰는 구조와 비교해 보세요. JLS의 실행 시 확인 가능한 타입 규칙

원 main의 출력은 다음과 같습니다. 첫 두 추가만 성공하고 중복 추가와 포함 여부 조회는 저장 상태를 바꾸지 않습니다.

add1=true
add9=true
again1=false
contains9=true
remove1=true
size=1, buckets=[[], [9], [], [], [], [], [], []]

상태 변화 예측하기

MyHashSetV1의 원 main이 끝난 뒤 remove(1), add(9), remove(9)를 차례로 더 호출한다면 반환값과 최종 size는 무엇인가요?

연산별 불변식 검산

빈 집합은 모든 그룹이 비어 있고 size가 0입니다.

add(1) 뒤 1번 그룹 길이와 size가 1이 됩니다.

add(9)는 같은 그룹 길이를 2로 만들고 전체 size도 2입니다.

add(1)을 반복하면 두 값 모두 바뀌지 않습니다.

remove(1) 뒤에는 9가 같은 그룹에 남아야 합니다.

그룹 자체를 비우면 충돌 값을 함께 잃습니다.

없는 값 remove는 false이며 음수 size를 만들지 않습니다.

계속 유지할 불변식은 “모든 그룹 길이의 합이 size와 같다”와 “같은 값이 중복 저장되지 않는다”입니다. 빈 상태에서 참이고, 새 값의 추가는 두 개수를 함께 1 늘리며 실제 삭제는 함께 1 줄입니다. 중복 추가·없는 값 삭제·조회는 둘 다 그대로 두므로 이 조건이 이어집니다. size가 그룹 수나 가장 긴 그룹 길이를 뜻하지 않는다는 점도 확인하세요.

이 상태표를 손으로 예측한 뒤 실행 출력과 비교합니다.

평균 O(1)의 전제와 V1의 한계

그룹 수가 충분하고 값이 고르게 분산되면 포함 여부는 짧은 목록만 봅니다.

V1은 원소가 계속 늘어도 그룹 배열을 확장하지 않으므로 적재 계수가 커지고 결국 한 그룹 검색이 길어질 수 있습니다.

“해시니까 항상 O(1)”이 아니라 분산과 재해시 정책을 전제로 한 평균 설명입니다.

원소 수를 n, 그룹 수를 m이라고 하면 고르게 분산될 때 한 그룹의 후보 수는 평균 n/m입니다. 학습용 V1의 포함 여부는 그룹 선택과 후보 비교를 합쳐 평균 O(1 + n/m)로 볼 수 있고, 그룹 수를 8로 고정한 채 n만 늘리면 이 비용도 커집니다. 반면 저장된 size를 읽는 메서드는 후보를 순회하지 않아 O(1)입니다. HashSet 공식 문서도 기본 연산의 상수 시간 설명에 고른 해시 분산이라는 전제를 둡니다.

또한 V1은 int만 받습니다.

문자열이나 PostTag를 저장하려면 값마다 hashCode와 equals를 사용할 수 있어야 합니다.

다음 절에서 문자열 해시 계산을 추적하고, 이후 제네릭 Set으로 타입 범위를 넓힙니다.

게시글 저장소에서 공개된 제목 중복 차단

CLI는 공개한 게시글 제목을 Set에 넣습니다.

같은 명령이 두 번 들어와도 공개 수는 한 번만 증가합니다.

사용자에게는 add boolean을 이용해 새 공개인지 이미 처리된 명령인지 알려 줍니다.

import java.util.HashSet;
import java.util.Set;

public final class PublishedTitleCli {
    public static void main(String[] args) {
        Set<String> published = new HashSet<>();
        publish(published, "hash-index");
        publish(published, "bucket-chain");
        publish(published, "hash-index");
        System.out.println("count=" + published.size());
    }

    private static void publish(Set<String> published, String title) {
        if (title == null || title.isBlank()) throw new IllegalArgumentException("title");
        System.out.println(title + "=" + (published.add(title) ? "new" : "already"));
    }
}

표준 HashSet은 내부 버킷을 노출하지 않습니다.

애플리케이션은 중복 없는 공개 목록이라는 규칙만 사용합니다.

입력 순서가 필요하다는 요구가 생기면 구현을 바꾸되 Set.add의 의미는 유지합니다.

여기서 중복 기준은 제목 문자열의 동등성입니다. "hash-index"와 "HASH-INDEX"는 서로 다른 값이며, 제목이 같은 서로 다른 게시글도 이 정책에서는 하나로 취급합니다. 실제 서비스가 게시글 단위의 중복 공개를 막으려면 제목 대신 게시글 ID를 키로 삼아야 합니다. 이 예제의 공개 수는 지정한 제목 기준에서만 계산됩니다.

연습 문제

1, 9, 17을 같은 그룹에 넣고 9만 제거하세요.

포함 여부(1), 포함 여부(9), 포함 여부(17), size를 출력해 한 값만 사라졌는지 확인합니다.

import java.util.ArrayList;
import java.util.List;

public final class BucketRemovalSolution {
    public static void main(String[] args) {
        List<Integer> bucket = new ArrayList<>(List.of(1, 9, 17));
        boolean removed = bucket.remove(Integer.valueOf(9));
        System.out.println("removed=" + removed);
        System.out.println(
                "1="
                        + bucket.contains(1)
                        + ", 9="
                        + bucket.contains(9)
                        + ", 17="
                        + bucket.contains(17)
                        + ", size="
                        + bucket.size());
    }
}

MyHashSetV1을 끝냈다면 add 반복이 size를 늘리지 않는지, 충돌 원소 삭제가 이웃을 지우지 않는지, 음수 값도 유효 인덱스에 들어가는지 설명할 수 있어야 합니다.

세 검사가 그룹 기반 Set의 최소 안전망입니다.