제네릭 해시 집합과 재해시 구현하기

정수 해시 집합 MyHashSetV1 만들기에서 만든 집합에는 두 가지 한계가 있었습니다. 첫째, int만 담을 수 있어서 문자열이나 앞 글에서 만든 PostKey 같은 객체를 저장하지 못합니다. 둘째, 버킷 수가 8개로 고정되어 있어서 원소가 늘어날수록 버킷마다 비교할 후보가 길어집니다. 원소가 800개라면 버킷 하나에 평균 100개가 모이고, 해시를 쓰는 의미가 거의 사라집니다.

이 글에서는 두 한계를 차례로 해결합니다. 먼저 원소 타입을 타입 매개변수 E로 바꾸어 어떤 객체든 담을 수 있게 하되, 잘못된 타입은 컴파일 단계에서 막습니다. 그다음 원소 수가 버킷 수에 비해 많아지면 버킷 배열을 두 배로 늘리고 모든 원소를 다시 배치하는 재해시(rehash)를 구현합니다. 원소를 담을 때 필요한 equals와 hashCode의 규칙은 앞 글에서 정리한 것을 그대로 전제합니다.

raw 타입으로는 아무 객체나 들어간다

여러 타입을 담는 가장 쉬운 방법은 원소 타입을 Object로 바꾸는 것입니다. 하지만 그러면 문자열을 담으려고 만든 집합에 정수가 들어가도 아무도 막지 못합니다. 표준 HashSet도 타입 인자 없이 쓰면 같은 일이 생깁니다. 다음 프로그램은 Set<String>으로 만든 집합을 타입 인자를 뺀 Set 변수로 다시 가리킨 뒤, 그 변수로 정수 100을 넣습니다.

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

Exception in thread "main" java.lang.ClassCastException: class java.lang.Integer cannot be cast to class java.lang.String (java.lang.Integer and java.lang.String are in module java.base of loader 'bootstrap')
	at RawSetHeapPollutionFailure.main(RawSetHeapPollutionFailure.java:10)

Set처럼 타입 인자를 생략한 타입을 raw 타입(raw type)이라고 합니다. 제네릭 클래스와 타입 매개변수에서 보았듯이 raw 타입을 거치면 컴파일러의 타입 검사도 함께 빠집니다. 그래서 raw.add(100)은 컴파일되고 실행도 문제없이 지나갑니다. 컴파일러가 하는 일은 Note: lab/RawSetHeapPollutionFailure.java uses unchecked or unsafe operations.라는 안내를 남기는 것뿐이고, -Xlint:unchecked로 컴파일해야 raw.add(100)이 있는 9번째 줄을 [unchecked] 경고로 짚어 줍니다.

문제는 나중에 드러납니다. for문은 typed의 원소를 String으로 꺼내는데, 그중 하나가 Integer이므로 ClassCastException이 납니다. 스택 트레이스가 가리키는 10번째 줄은 정수를 넣은 9번째 줄이 아니라 원소를 꺼내는 for문입니다. 이 실행에서는 정수 100이 먼저 나와 HASH가 출력되기도 전에 예외가 났습니다. 반복 순서에 따라 HASH가 먼저 출력될 수도 있지만, 정수를 꺼내는 순간 예외가 나는 것은 같습니다.

이처럼 Set<String> 타입 변수가 가리키는 집합에 String이 아닌 원소가 들어 있는 상태, 즉 매개변수화 타입의 변수가 그 타입에 맞지 않는 객체를 가리키게 된 상태를 힙 오염(heap pollution)이라고 합니다. 오류가 원인에서 멀리 떨어진 곳에서 터지므로 원인을 찾기가 어렵습니다. raw 타입은 제네릭이 없던 시절의 코드와 함께 쓰기 위해 남아 있는 것이니, 새 코드에서는 쓰지 않습니다.

MySet 인터페이스로 집합의 연산 정하기

제네릭 집합을 만들기 전에, 집합을 쓰는 쪽에서 필요한 연산을 인터페이스로 정해 두겠습니다. MyList 인터페이스로 목록 구현 바꾸기에서 MyList<E>를 만든 것과 같은 방식입니다.

private interface MySet<E> extends Iterable<E> {
    boolean add(E value);

    boolean contains(E value);

    boolean remove(E value);

    int size();
}

반환값에는 저마다 뜻이 있습니다. add는 새 원소가 실제로 들어갔으면 true, 같은 원소가 이미 있어서 아무것도 바뀌지 않았으면 false를 돌려줍니다. remove도 원소를 실제로 지웠는지를 boolean으로 알려 주고, contains는 집합을 바꾸지 않고 묻기만 합니다. 그래서 size()는 add를 호출한 횟수가 아니라 지금 들어 있는 서로 다른 원소의 수입니다.

MySet은 Iterable<E>를 확장하므로 향상된 for문으로 원소를 하나씩 꺼낼 수 있습니다. 다만 어떤 순서로 꺼낼지는 인터페이스에서 정하지 않았습니다. 해시 집합은 버킷 순서대로 꺼내는 것이 가장 자연스러운데, 버킷 순서는 해시 값과 버킷 수에 따라 달라지기 때문입니다. 표준 Set 인터페이스도 반복 순서를 정하지 않고, 순서를 약속할지는 각 구현에 맡깁니다.

제네릭 해시 집합 HashMySet

다음은 MySet<E>를 해시로 구현한 HashMySet<E>와, 이 집합에 문자열 네 개를 넣어 보는 main입니다. 구조는 MyHashSetV1과 같습니다. 버킷 배열의 칸마다 List<E>가 하나씩 있고, 원소의 hashCode()로 버킷을 골라 그 목록에서 equals로 비교합니다. 새로 생긴 것은 null 검사, 확장 조건을 확인하는 add의 한 줄, 그리고 확장을 맡는 resize 메서드입니다.

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

true
false
true
true
contains=true, size=3
hash
set
bucket

첫 줄은 빈 집합에 "hash"가 들어갔다는 뜻입니다. 둘째 줄의 new String("hash")는 첫 문자열과 다른 객체이지만 String의 equals가 내용을 비교하므로 같은 원소로 판단되어 false입니다. set과 bucket은 새 원소라 true이고, 크기는 서로 다른 문자열 세 개를 센 3입니다.

마지막 세 줄은 반복자가 버킷 0번부터 차례로 원소를 꺼낸 결과입니다. 세 문자열의 해시 값을 Math.floorMod(hashCode, 4)로 줄이면 모두 2가 나오므로, 세 원소는 2번 버킷의 목록에 넣은 순서대로 들어 있습니다. 반복자는 비어 있는 0번과 1번 버킷을 건너뛰고 2번 버킷의 목록을 앞에서부터 읽습니다. 넣은 순서와 같게 나온 것은 세 원소가 우연히 같은 버킷에 모였기 때문입니다. 원소가 서로 다른 버킷에 들어가면 순서는 버킷 번호를 따릅니다.

코드에서 눈여겨볼 부분은 세 곳입니다. 첫째, 생성자와 resize는 new List<E>[capacity]로 배열을 만들지 못합니다. 배열은 실행 중에도 원소 타입을 기억해 검사하는데, 타입 소거 때문에 List<E>의 타입 인자는 실행 중에 남아 있지 않습니다. 그래서 자바는 타입 인자가 붙은 타입의 배열 생성을 허용하지 않고, 이 코드는 List<?>[]를 만든 뒤 형변환합니다. 이 형변환은 컴파일러가 안전한지 검사할 수 없어 경고가 나오는데, 배열을 private 필드로만 쓰고 각 칸에는 ArrayList<E>만 넣으므로 @SuppressWarnings("unchecked")로 경고를 끕니다. 경고를 끄는 범위는 배열을 만드는 두 메서드로 좁혀 두었습니다.

둘째, add는 확장 조건보다 중복 검사를 먼저 합니다. 이미 있는 원소를 다시 넣는 호출은 원소 수를 늘리지 않으니 확장할 이유도 없기 때문입니다. 셋째, 세 연산 모두 Objects.requireNonNull로 null을 거부합니다. 표준 HashSet은 null을 원소 하나로 받아 주지만, 이 구현은 null을 받지 않기로 정한 것입니다. 이런 정책은 사용하는 쪽이 알 수 있도록 문서에 적어 두어야 합니다. 빈 문자열은 null이 아니므로 그대로 받아들이니, 빈 태그 같은 값을 막으려면 도메인 쪽에서 따로 검사해야 합니다.

잘못된 타입은 넣는 줄에서 막힌다

이제 처음의 raw 타입 예제와 비교해 보겠습니다. GenericMyHashSet의 main 본문을 다음 세 줄로 바꾸고 컴파일해 보세요.

MySet<String> set = new HashMySet<>(4);
set.add("hash");
set.add(100);

src/GenericMyHashSet.java:11: error: incompatible types: int cannot be converted to String
        set.add(100);
                ^
Note: Some messages have been simplified; recompile with -Xdiags:verbose to get full output
1 error

set의 타입이 MySet<String>이므로 add의 매개변수 타입은 String이고, 정수 100은 그 자리에 들어갈 수 없습니다. raw 타입 예제에서는 정수가 아무 경고 없이 들어갔다가 한참 뒤 원소를 꺼낼 때 예외가 났지만, 이번에는 정수를 넣으려 한 바로 그 줄에서 컴파일이 멈춥니다. 실행 중에는 타입 소거 때문에 버킷 안의 목록에 그냥 객체 참조가 담길 뿐이고, E별로 다른 배열이 만들어지는 것도 아닙니다. 그래도 안전한 것은 집합에 원소를 넣는 길이 add(E) 하나뿐이고, 컴파일러가 그 호출마다 타입을 검사하기 때문입니다.

적재 계수가 0.75를 넘으면 버킷을 두 배로

해시 테이블의 동작 원리에서 원소 수를 버킷 수로 나눈 값을 적재 계수(load factor)라고 했습니다. 적재 계수는 버킷 하나에 들어 있는 원소의 평균 개수입니다. 해시 값이 고르게 퍼진다면 이 값이 곧 contains 한 번에 비교할 후보 수의 대략적인 평균이 됩니다. 그래서 적재 계수를 일정 값 아래로 유지하면 원소가 아무리 많아져도 평균 비교 횟수가 늘지 않습니다.

add의 확장 조건 (size + 1.0) / buckets.length > MAX_LOAD는 새 원소를 넣은 뒤의 적재 계수를 미리 계산해 0.75를 넘는지 봅니다. 넘는다면 원소를 넣기 전에 resize로 버킷 배열을 두 배로 늘립니다. size + 1.0처럼 1.0을 더하는 것은 정수 나눗셈을 피하기 위해서입니다. (size + 1) / buckets.length라고 쓰면 정수끼리 나누어 소수 부분이 버려지므로, 넣은 뒤의 원소 수가 버킷 수와 같아지기 전까지는 결과가 언제나 0입니다. 그러면 적재 계수가 0.75를 넘어도 확장하지 않다가 1.0에 이르러서야 확장하게 됩니다. 연습 문제 2에서 이 차이를 확인합니다.

앞의 main에서 일어난 일을 따라가 보면 다음과 같습니다. 용량은 버킷 배열의 길이입니다.

add를 네 번 호출했지만 확장은 한 번도 일어나지 않았습니다. 중복인 두 번째 호출은 확장 조건을 계산하기 전에 돌아갔고, 마지막 bucket을 넣은 뒤의 적재 계수는 정확히 0.75라서 0.75보다 크지 않기 때문입니다. 조건을 >=로 썼다면 이 마지막 호출에서 확장했을 것입니다. 같음과 초과 중 무엇을 기준으로 할지는 구현마다 정하는 문제이고, 이 구현은 HashMap의 Javadoc처럼 '넘을 때' 확장합니다.

재해시를 직접 확인하기

확장이 실제로 일어나는 모습을 보려면 고유한 원소를 하나 더 넣으면 됩니다. GenericMyHashSet의 main 본문을 다음 코드로 바꾸고, 파일 맨 위에 import java.util.Arrays;를 추가해 실행해 보세요. HashMySet과 MySet은 그대로 둡니다. 이 main은 HashMySet과 같은 바깥 클래스 안에 있으므로 private 필드인 buckets를 직접 읽을 수 있습니다. 확인을 위한 코드일 뿐, 집합을 쓰는 쪽에 버킷을 보여 주려는 것은 아닙니다.

HashMySet<String> set = new HashMySet<>(4);
set.add("hash");
set.add("set");
set.add("bucket");
System.out.println("before=" + Arrays.toString(set.buckets));
System.out.println("add(key)=" + set.add("key"));
System.out.println("after=" + Arrays.toString(set.buckets));
System.out.println("size=" + set.size() + ", capacity=" + set.buckets.length);

before=[[], [], [hash, set, bucket], []]
add(key)=true
after=[[], [], [set, bucket], [], [], [], [hash], [key]]
size=4, capacity=8

key를 넣으면 적재 계수가 4/4 = 1.0이 되어 0.75를 넘으므로, add는 key를 넣기 전에 resize(8)을 호출합니다. 확장 전에는 세 원소가 모두 2번 버킷에 있었지만, 확장 뒤에는 hash가 6번으로 옮겨 가고 set과 bucket은 2번에 남았습니다. 각 원소의 해시 값과 버킷 번호를 계산해 보면 그 이유가 보입니다.

해시 값은 원소가 정하는 값이라 버킷 수와 상관없이 그대로이지만, 버킷 번호는 해시 값을 버킷 수로 나눈 나머지라서 버킷 수가 바뀌면 달라질 수 있습니다. hash는 버킷 4개일 때 나머지가 2였는데 8개일 때는 6이 됩니다. bucket처럼 해시 값이 음수여도 floorMod는 언제나 0 이상의 번호를 돌려줍니다. 그래서 resize는 옛 버킷의 목록을 같은 번호의 새 칸으로 통째로 옮기지 않고, 원소 하나하나의 버킷 번호를 새 배열 길이로 다시 계산합니다. 이것이 재해시라는 이름의 뜻입니다.

목록을 통째로 옮기면 어떻게 되는지도 확인해 보았습니다. resize의 이중 for문을 buckets[i] = old[i]로 옛 목록을 같은 번호의 칸에 옮기는 반복문으로 바꾸면, hash는 여전히 2번 칸에 남습니다. 그런데 contains("hash")는 버킷 8개 기준으로 계산한 6번 칸을 보므로 false를 돌려줍니다. 원소는 집합 안에 있는데 찾을 수가 없게 되는 것입니다.

resize 안에서는 size를 건드리지 않는다는 점도 중요합니다. 재해시는 이미 있는 원소의 자리만 옮길 뿐 원소 수를 바꾸지 않습니다. 실수로 resize가 원소마다 add를 호출하게 만들면 옮기는 원소마다 size가 하나씩 늘어, 위 실행의 마지막 줄이 size=7이 됩니다. 실제 원소는 네 개인데 크기는 7이라고 답하는 집합이 되는 것입니다.

이 구현이 언제나 지키는 조건을 정리하면 두 가지입니다. 모든 버킷의 원소 수를 더하면 size와 같고, 같은 원소는 한 번만 저장됩니다. 빈 집합에서 시작할 때 두 조건은 참입니다. 성공한 add는 원소 하나와 size 1을 함께 늘리고, 성공한 remove는 함께 줄입니다. 중복 add, 없는 원소의 remove, contains는 둘 다 그대로 두고, resize는 원소를 옮기기만 하므로 이 조건은 어떤 호출 뒤에도 유지됩니다. 단, 버킷 안의 List.contains와 List.remove가 equals로 비교하므로, 원소의 equals와 hashCode가 앞 글의 규칙을 지키고 저장한 뒤에 바뀌지 않는다는 전제가 붙습니다.

해시 값이 모두 같아도 결과는 맞다

다음 코드로 충돌과 음수 해시 값, 재해시를 한꺼번에 확인해 보겠습니다. CollisionKey는 모든 객체가 해시 값 -7을 돌려주는 record입니다. 앞과 같은 방법으로 main 본문만 바꿔 실행하기 전에, 각 줄의 반환값과 크기를 먼저 예측해 보세요. 메서드 안에 선언한 record는 지역 record라고 부르며, 그 메서드 안에서만 쓸 수 있습니다.

record CollisionKey(int id) {
    @Override
    public int hashCode() {
        return -7;
    }
}
HashMySet<CollisionKey> set = new HashMySet<>(4);
for (int id = 1; id <= 4; id++) {
    set.add(new CollisionKey(id));
}
System.out.println("capacity=" + set.buckets.length + ", size=" + set.size());
System.out.println("duplicate=" + set.add(new CollisionKey(1)) + ", size=" + set.size());
System.out.println("missing=" + set.remove(new CollisionKey(9)) + ", size=" + set.size());
System.out.println("removed=" + set.remove(new CollisionKey(2)) + ", size=" + set.size());
System.out.println("kept=" + (set.contains(new CollisionKey(1))
        && set.contains(new CollisionKey(3)) && set.contains(new CollisionKey(4))));

capacity=8, size=4
duplicate=false, size=4
missing=false, size=4
removed=true, size=3
kept=true

재해시 비용을 나누어 계산하기

원소 수를 n, 버킷 수를 m이라고 하겠습니다. contains는 버킷 하나를 고른 뒤 그 목록을 앞에서부터 비교하므로, 비용은 그 버킷의 원소 수에 비례합니다. 해시 값이 고르게 퍼지면 버킷 하나의 원소 수는 평균 n/m이고, 이 구현은 적재 계수 n/m을 0.75 이하로 유지하므로 평균 비용은 O(1)입니다. 해시 집합의 O(1)은 언제나 '해시 값이 고르게 퍼진다면'이라는 조건이 붙은 평균입니다.

앞의 CollisionKey처럼 모든 원소가 한 버킷에 모이면 contains 한 번이 O(n)이 됩니다. 실제로 CollisionKey를 1,000개 넣어 보면, add마다 중복을 확인하느라 버킷의 기존 원소와 모두 비교하므로 equals가 0 + 1 + … + 999 = 499,500번 호출됩니다. 그동안 버킷 배열은 2,048칸까지 늘어나지만, 원소가 들어 있는 버킷은 여전히 하나뿐입니다. 해시 값이 모두 같으면 버킷 수를 아무리 늘려도 같은 버킷으로 가기 때문에, 재해시로는 충돌을 해결할 수 없습니다.

resize 한 번은 새 버킷 m개를 만들고 기존 원소 n개를 모두 옮기므로 O(n + m)입니다. 그러니 확장을 일으킨 add 호출은 다른 호출보다 훨씬 오래 걸립니다. 그런데 확장이 얼마나 자주 일어나는지를 함께 보면 이야기가 달라집니다. 용량 4에서 시작해 원소를 하나씩 넣으면, 확장은 다음 시점에만 일어납니다.

버킷 수를 두 배로 늘리므로, 확장할 때마다 옮기는 원소 수도 대략 두 배가 되고 확장 사이의 간격도 두 배로 벌어집니다. 그래서 원소 49개를 넣는 동안 옮긴 원소는 모두 93개로, 넣은 원소 수의 두 배를 넘지 않습니다. 등비수열의 합이 마지막 항의 두 배를 넘지 않기 때문입니다. 새 버킷을 만드는 비용도 같은 방식으로 합치면 원소 수에 비례합니다. 결국 add를 n번 호출하는 전체 비용은 O(n)이고, 이를 호출 횟수로 나누면 한 번에 O(1)입니다.

이렇게 연산 하나가 아니라 여러 번의 전체 비용을 횟수로 나누어 계산하는 방법을 분할 상환 분석이라고 합니다. 용량이 늘어나는 동적 배열 만들기에서 배열을 두 배로 키울 때 쓴 것과 같은 논리입니다. 다만 해시 집합의 분할 상환 O(1)에는 앞의 조건이 하나 더 붙습니다. hashCode가 고르게 퍼지고 equals와 hashCode의 계산이 일정한 시간 안에 끝난다고 가정할 때의 이야기입니다.

반복자는 원소가 없는 버킷도 하나하나 지나가므로 전체 순회는 O(n + m)입니다. 원소가 적은데 초기 용량을 지나치게 크게 잡으면 순회가 빈 버킷을 훑느라 느려지는 이유입니다. 이 분석은 이 글의 학습용 구현을 기준으로 한 것이고, 표준 HashSet의 Javadoc도 순회 시간이 원소 수와 버킷 수의 합에 비례하므로 성능이 중요하다면 초기 용량을 너무 크게 잡지 말라고 같은 이야기를 합니다.

더 깊이: 표준 HashMap의 확장 규칙과 미리 크기 정하기

HashMap의 Javadoc이 약속하는 것은 다음과 같습니다. 기본 적재 계수는 0.75이고, 항목 수가 '적재 계수 × 현재 용량'을 넘으면 내부 구조를 다시 만드는 재해시를 해서 버킷 수를 대략 두 배로 늘립니다. 반복 순서는 정해져 있지 않으며, 시간이 지나도 같은 순서가 유지된다는 보장도 없습니다. 이 글의 구현에서 보았듯이 재해시로 원소의 버킷 번호가 바뀌면 버킷 순서로 꺼내는 반복 순서도 함께 바뀔 수 있습니다. 표준 HashSet에서 이런 일이 실제로 일어나는 모습은 다음 글에서 확인합니다.

여기서부터는 OpenJDK 21의 구현 방식이며 Javadoc이 약속하는 내용이 아닙니다. 기본 생성자로 만든 HashSet은 버킷 배열을 바로 만들지 않고, 첫 원소를 넣을 때 버킷 16개짜리 배열을 만듭니다. 16 × 0.75 = 12이므로 13번째 원소를 넣을 때 32개로 늘어납니다. 버킷 수는 언제나 2의 거듭제곱입니다. 또 한 버킷에 모인 항목이 많아지면 그 버킷의 연결 목록을 트리로 바꾸어, 해시 값이 많이 겹쳐도 성능이 크게 떨어지지 않게 합니다. 이 트리 변환은 다음 글에서 조금 더 다룹니다.

원소 수를 미리 안다면 처음부터 크기를 정해 확장을 피할 수 있습니다. 이때 new HashSet<>(100)의 100은 원소 수가 아니라 초기 용량, 즉 버킷 수라는 점에 주의해야 합니다. OpenJDK 21에서 이렇게 만든 집합은 첫 원소를 넣을 때 버킷 128개를 만드는데, 128 × 0.75 = 96이므로 원소 100개를 넣는 동안 97번째 원소에서 한 번 확장합니다. Java 19부터는 원소 수를 기준으로 크기를 정해 주는 정적 메서드 HashSet.newHashSet(int numElements)가 있습니다. Javadoc은 이 메서드가 예상한 원소 수만큼 넣는 동안 대체로 확장할 필요가 없을 만큼 초기 용량을 잡는다고 설명합니다. OpenJDK 21에서 HashSet.newHashSet(100)으로 만든 집합에 원소 100개를 넣어 보면, 첫 원소를 넣을 때 버킷 256개를 만든 뒤 한 번도 확장하지 않습니다.

반복자가 지키는 규칙과 이 구현의 한계

HashMySet의 반복자는 Iterator의 기본 규칙을 지킵니다. hasNext()는 비어 있는 버킷을 건너뛰어 다음 원소가 있는 자리까지 위치를 맞출 뿐, 원소를 꺼내지는 않습니다. 그래서 hasNext()를 몇 번 연달아 호출해도 다음 next()가 돌려줄 원소는 같습니다. 원소를 다 꺼낸 뒤 next()를 호출하면 NoSuchElementException을 던집니다. remove()는 구현하지 않았으므로 Iterator 인터페이스의 기본 구현에 따라 UnsupportedOperationException을 던집니다.

이 반복자는 순회하는 동안 집합이 바뀌는지는 확인하지 않습니다. 순회 도중에 집합을 바꾸면 결과가 어긋날 수 있습니다. 예를 들어 1, 5, 9를 넣은 용량 4의 집합은 세 원소가 모두 1번 버킷에 들어갑니다. 이 집합을 순회하면서 1을 만났을 때 remove(1)을 호출하면, 목록의 원소들이 한 칸씩 앞으로 당겨집니다. 그 결과 반복자는 다음 원소 5를 건너뛰고 9로 넘어갑니다. 5는 집합에 남아 있지만 순회에서 한 번도 나오지 않는 것입니다.

표준 HashSet은 이런 실수를 빨리 알리기 위해 구조가 바뀐 횟수(OpenJDK에서는 modCount라는 필드)를 세어 둡니다. 반복자를 만든 뒤 반복자 자신의 remove가 아닌 방법으로 집합이 바뀌면, 다음 next()에서 ConcurrentModificationException을 던집니다. 문제를 발견한 즉시 멈추는 이런 방식을 즉시 실패(fail-fast)라고 합니다. 다만 Javadoc은 이 검사가 최선을 다할 뿐 언제나 일어난다고 보장할 수는 없다고 밝히므로, 이 예외에 기대어 프로그램을 짜서는 안 되고 버그를 찾는 데만 써야 합니다. 여러 스레드가 함께 쓰는 집합을 안전하게 만들어 주는 장치도 아닙니다.

이 글의 구현에서는 '순회하는 동안 집합을 바꾸지 않는다'를 사용 규칙으로 정해 둡니다. 반복자 구현은 모든 버킷의 원소를 한 번씩 꺼내는 데만 집중합니다.

게시글 공개 서비스에 Set 쓰기

이제 만든 집합을 쓰는 쪽을 보겠습니다. 게시글 공개 서비스는 이미 공개한 게시글 키를 집합에 모아 두고, 같은 게시글을 다시 공개하려 하면 already를, 처음이면 new를 돌려줍니다. 서비스는 HashSet 같은 구체 클래스 대신 Set<PostKey>를 생성자로 받습니다. 그런데 다음 코드에는 의도적으로 넣어 둔 버그가 있습니다. 출력을 예측한 뒤 실행해 보세요.

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

public final class PublicationSetService {
    public static void main(String[] args) {
        PublicationService service = new PublicationService(new HashSet<>());
        System.out.println(service.publish(new PostKey("java", "hash")));
        System.out.println(service.publish(new PostKey("java", "hash")));
        System.out.println(service.publish(new PostKey("java", "set")));
        System.out.println("count=" + service.count());
    }

    private static final class PublicationService {
        private final Set<PostKey> published;

        private PublicationService(Set<PostKey> published) {
            this.published = Set.copyOf(published);
        }

        String publish(PostKey key) {
            Set<PostKey> mutable = new HashSet<>(published);
            return mutable.add(key) ? "new" : "already";
        }

        int count() {
            return published.size();
        }
    }

    private record PostKey(String category, String title) {}
}

new
new
new
count=0

같은 게시글을 두 번 공개했는데 두 번 다 new이고, 세 번 공개한 뒤의 개수는 0입니다. 원인은 변경이 일어나는 위치에 있습니다. 생성자는 받은 집합을 Set.copyOf로 복사해 필드에 저장하는데, 이 복사본은 수정할 수 없는 집합입니다. 그래서 publish는 필드를 직접 바꾸지 못하고, 호출할 때마다 필드를 복사한 새 HashSet을 만들어 거기에 add합니다. 이 임시 집합은 메서드가 끝나면 버려지므로, 필드는 처음 받은 빈 집합 그대로 남습니다. 결국 매번 빈 집합에 넣는 셈이라 언제나 new이고, count는 0입니다.

Set.copyOf는 원소 순서도 지키지 않습니다. 생성자에 LinkedHashSet을 넘겨도 복사본의 반복 순서는 정해져 있지 않습니다. 어느 순간의 내용을 담아 두고 더는 바뀌지 않는 사본, 즉 스냅숏(snapshot)과 계속 바뀌어야 하는 내부 상태를 혼동한 이 버그는 연습 문제 1에서 고칩니다.

정리

• raw 타입을 거치면 타입 검사가 빠져, 잘못된 타입의 원소가 컬렉션에 섞였다가 꺼낼 때 ClassCastException이 납니다. 제네릭 MySet<E>는 잘못된 타입을 넣는 줄에서 컴파일 오류를 냅니다.
• add와 remove의 boolean은 집합이 실제로 바뀌었는지를 알려 주고, size()는 지금 들어 있는 서로 다른 원소의 수입니다.
• 넣은 뒤의 적재 계수가 0.75를 넘으면 버킷 배열을 두 배로 늘립니다. 버킷 번호는 버킷 수에 따라 달라지므로, 재해시는 모든 원소의 버킷 번호를 다시 계산하고 size는 바꾸지 않습니다.
• 두 배씩 늘리면 확장 비용의 합이 원소 수에 비례하므로, 해시 값이 고르게 퍼진다는 가정 아래 add는 분할 상환 O(1)입니다. 확장을 일으킨 그 호출 하나는 O(n + m)입니다.
• 이 구현의 반복자는 순회 중의 변경을 감지하지 않습니다. 표준 HashSet의 반복자는 즉시 실패 방식으로 알려 주지만, 그것도 버그를 찾는 용도일 뿐 언제나 일어나는 동작은 아닙니다.

연습 문제

1. PublicationSetService를 고치세요. 서비스가 내부 집합을 직접 소유하되, 생성자에 넘긴 집합을 바깥에서 나중에 바꿔도 서비스에는 영향이 없어야 합니다. 같은 키를 두 번 공개하면 new, already가 나오고, 다른 키까지 공개한 뒤의 개수는 2여야 합니다.
2. HashMySet의 확장 조건 (size + 1.0) / buckets.length > MAX_LOAD를 정수 나눗셈인 (size + 1) / buckets.length > MAX_LOAD로 바꾸었다고 합시다. 용량 4에서 시작해 고유한 원소를 20개 넣는 동안 확장은 몇 번째 원소에서 일어날까요? 원래 조건과 비교하고, 확장하기 직전의 적재 계수도 구하세요.
3. 용량 8에서 시작한 HashMySet에 고유한 원소 100개를 넣으면 확장은 모두 몇 번 일어나고, 최종 용량은 얼마일까요?

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

public final class PublicationServiceSolution {
    public static void main(String[] args) {
        Service service = new Service(Set.of());
        System.out.println(service.publish(new Key("java", "hash")));
        System.out.println(service.publish(new Key("java", "hash")));
        System.out.println(service.publish(new Key("java", "set")));
        System.out.println("count=" + service.snapshot().size());
    }

    private static final class Service {
        private final Set<Key> published;

        Service(Set<Key> initial) {
            published = new HashSet<>(initial);
        }

        String publish(Key key) {
            return published.add(key) ? "new" : "already";
        }

        Set<Key> snapshot() {
            return Set.copyOf(published);
        }
    }

    private record Key(String category, String title) {}
}

new
already
new
count=2

다음 글

HashSet·LinkedHashSet·TreeSet 비교와 선택에서는 표준 라이브러리의 세 가지 Set 구현을 비교합니다. 이 글에서 만든 해시 집합이 버킷 순서대로 원소를 꺼냈듯이 HashSet의 반복 순서도 정해져 있지 않은데, 순서가 필요할 때 어떤 구현을 골라야 하는지 살펴봅니다.