MyHashSetV1 구현

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

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

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

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

단일 충돌 칸의 원소 손실

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

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

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

lab/SingleSlotSetCollisionBug.java

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에서만 변해야 합니다.

src/MyHashSetV1.java

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 오버로드입니다.

int를 직접 넘기면 값이 아니라 index 삭제로 해석될 수 있습니다.

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

연산별 불변식 검산

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

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

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

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

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

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

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

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

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

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

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

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

또한 V1은 int만 받습니다.

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

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

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

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

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

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

app/PublishedTitleCli.java

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의 의미는 유지합니다.

연습 문제

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

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

정답과 해설

그룹 목록에서 Integer 값 동등성으로 9를 찾습니다.

배열 칸을 null로 만들지 않으므로 나머지 두 충돌 원소가 유지됩니다.

exercise/BucketRemovalSolution.java

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());
    }
}

결과는 1과 17이 true, 9가 false, size가 2입니다.

실제 MyHashSetV1에서는 전체 size도 remove가 true일 때 한 번만 줄입니다.

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

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