정수 해시 집합 MyHashSetV1 만들기

게시글 제목이나 태그처럼 같은 값을 두 번 저장하면 안 되는 데이터가 있습니다. 이런 데이터를 담는 자료구조가 집합(set)입니다. 집합은 순서나 위치가 아니라 '이 값이 들어 있는가'만 다루고, 같은 값은 한 번만 보관합니다. 그래서 집합에서 가장 자주 하는 일은 값이 있는지 확인하는 것이고, 값을 넣을 때도 먼저 이미 있는지 확인해야 합니다.

배열이나 목록으로 집합을 만들면 이 확인에 최악의 경우 원소 수 n에 비례하는 시간이 걸립니다. 원소를 앞에서부터 하나씩 비교해야 하기 때문입니다. 앞 글의 해시 테이블을 쓰면 값의 해시 코드로 버킷 하나를 고른 뒤 그 버킷만 확인하면 됩니다. 이 글에서는 이 방법으로 정수만 담는 해시 집합 MyHashSetV1을 만듭니다. 목표는 표준 HashSet을 그대로 흉내 내는 것이 아니라, 충돌한 값을 잃지 않는 방법과 size를 정확하게 유지하는 조건을 코드로 확인하는 것입니다.

버킷 한 칸에 값 하나만 두면

먼저 가장 단순하게 만들어 보겠습니다. 길이 8인 배열을 두고, 값의 버킷 번호에 해당하는 칸에 그 값을 바로 넣습니다. 그런 다음 1과 9를 차례로 넣고 1이 들어 있는지 확인합니다.

import java.util.Objects;

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 = Objects.equals(slots[Math.floorMod(1, slots.length)], 1);
        System.out.println("contains-1=" + containsOne + ", stored=" + slots[1]);
    }
}

contains-1=false, stored=9

1과 9는 모두 floorMod(값, 8)이 1이라 같은 칸을 고릅니다. 두 번째 대입이 1번 칸의 1을 9로 덮어쓰므로, 1을 찾으러 1번 칸에 가면 9가 있고 Objects.equals(9, 1)은 false입니다. 분명히 넣은 1이 사라진 것입니다. 이 프로그램은 예외도 경고도 없이 정상 종료되므로, 잘못된 결과를 직접 확인하지 않으면 버그를 알아채기 어렵습니다. 원인은 버킷 번호를 값의 자리처럼 다룬 데 있습니다. 버킷 번호는 '이 값이 있다면 여기 있다'는 후보 위치일 뿐, 그 칸의 주인이 하나라는 뜻이 아닙니다.

해결책은 앞 글과 같습니다. 배열의 각 칸을 List<Integer> 버킷으로 바꾸고, 같은 버킷을 고른 값들을 그 목록에 함께 보관합니다. 그러면 add는 버킷 목록에 같은 값이 이미 있는지 먼저 확인하고, 없을 때만 목록에 추가할 수 있습니다. 1과 9처럼 충돌한 서로 다른 값은 한 버킷에 공존하고, 1을 두 번 넣는 것처럼 같은 값을 다시 넣는 요청은 거절됩니다.

반환값으로 집합이 바뀌었는지 알리기

자바의 Set 인터페이스에서 add는 boolean을 돌려줍니다. 새 값이 저장되어 집합이 바뀌었으면 true, 이미 있던 값이라 아무것도 바뀌지 않았으면 false입니다. remove도 마찬가지로 실제로 지운 값이 있을 때만 true를 돌려줍니다. 덕분에 호출하는 쪽은 size를 호출 전후로 비교하지 않아도 반환값만 보고 중복이었는지, 지울 값이 없었는지 알 수 있습니다. MyHashSetV1도 같은 방식을 따르고, 원소 수를 세는 size 필드는 집합이 실제로 바뀐 경우에만 고칩니다.

import java.util.ArrayList;
import java.util.Arrays;
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];
        }

        @Override
        public String toString() {
            return Arrays.toString(buckets);
        }
    }
}

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

세 메서드 모두 bucket(value)로 버킷을 먼저 고르고 그 목록 안에서만 일합니다. add는 목록에 같은 값이 있으면 곧바로 false를 돌려주고, 없을 때만 값을 붙이고 size를 1 늘립니다. contains는 목록의 contains에 확인을 맡깁니다. remove는 목록에서 값을 지우고, 지운 값이 있을 때만 size를 1 줄입니다. 목록의 contains와 remove는 원소를 equals로 비교하므로, 여기서는 Integer 값이 같은지 확인하는 셈입니다. toString은 버킷 배열을 그대로 출력해 내부 상태를 눈으로 볼 수 있게 합니다.

출력을 한 줄씩 보면 다음과 같습니다. 1과 9는 둘 다 1번 버킷을 고르지만 서로 다른 값이므로 둘 다 추가되어 true가 두 번 나옵니다. 세 번째 줄에서 1을 다시 넣으면 1번 버킷에 이미 1이 있으므로 false가 나오고 집합은 그대로입니다. contains(9)는 1번 버킷에서 9를 찾아 true를 돌려줍니다. remove(1)은 1번 버킷의 1만 지우고 같은 버킷의 9는 남겨 둡니다. 그래서 마지막 줄의 size는 1이고, 1번 버킷에는 [9]만 남았습니다.

remove에 Integer.valueOf를 넘기는 이유

remove의 bucket(value).remove(Integer.valueOf(value))에서 굳이 Integer.valueOf로 감싸는 데는 이유가 있습니다. List에는 이름이 같은 remove 메서드가 두 개 있습니다. remove(int index)는 그 위치의 원소를 지우고 지운 원소를 돌려주며, remove(Object o)는 o와 같은 원소를 찾아 지우고 지웠는지를 boolean으로 돌려줍니다. List<Integer>에 int 값을 그대로 넘기면 컴파일러는 박싱이 필요 없는 remove(int index)를 고릅니다. 메서드 오버로딩과 자동 형변환의 '더 깊이' 단락에서 본 것처럼, 컴파일러는 박싱 없이 호출할 수 있는 후보를 먼저 찾고 거기서 하나라도 찾으면 박싱이 필요한 후보는 검토하지 않기 때문입니다. 다음 코드로 차이를 확인해 보겠습니다.

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

public final class RemoveOverloadTrap {
    public static void main(String[] args) {
        List<Integer> byIndex = new ArrayList<>(List.of(1, 9, 17));
        byIndex.remove(1);
        System.out.println("remove(1)                  -> " + byIndex);

        List<Integer> byValue = new ArrayList<>(List.of(1, 9, 17));
        byValue.remove(Integer.valueOf(1));
        System.out.println("remove(Integer.valueOf(1)) -> " + byValue);

        List<Integer> tooFar = new ArrayList<>(List.of(1, 9, 17));
        tooFar.remove(17);
    }
}

remove(1)                  -> [1, 17]
remove(Integer.valueOf(1)) -> [9, 17]
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 17 out of bounds for length 3

세 목록은 모두 [1, 9, 17]로 새로 만든 것이라 서로 영향을 주지 않습니다. 첫 줄에서 remove(1)은 값 1이 아니라 인덱스 1에 있는 9를 지웁니다. 둘째 줄의 remove(Integer.valueOf(1))은 remove(Object)가 선택되어 값 1을 지웁니다. 마지막의 remove(17)은 인덱스 17을 지우려다 목록 길이가 3이라 IndexOutOfBoundsException을 던집니다(실제 출력에는 이 줄 뒤에 스택 트레이스가 이어집니다).

MyHashSetV1에서 이 실수가 특히 위험한 이유는 값과 인덱스가 우연히 맞아떨어질 수 있기 때문입니다. 버킷 [1, 9]에서 remove(1)을 인덱스로 해석하면 예외 없이 값 9가 지워져 버그가 조용히 숨습니다. 다행히 지금 코드에서는 컴파일러가 이 실수를 잡아 줍니다. remove(int)는 boolean이 아니라 Integer를 돌려주므로, boolean removed = bucket.remove(value);라고 쓰면 incompatible types: Integer cannot be converted to boolean 컴파일 오류가 납니다. 그래도 반환값을 쓰지 않는 코드라면 이런 도움을 받을 수 없으니, 값을 지울 때는 Integer.valueOf로 의도를 분명히 하는 습관을 들이는 편이 안전합니다. 두 메서드의 동작은 List.remove 공식 문서에서 확인할 수 있습니다.

제네릭 배열을 만드는 우회로

생성자의 (List<Integer>[]) new List<?>[bucketCount]는 자바의 다른 제약 때문에 생긴 코드입니다. new List<Integer>[bucketCount]처럼 타입 인수를 지정한 제네릭 배열은 만들 수 없고, 그렇게 쓰면 generic array creation 컴파일 오류가 납니다. 배열은 실행 중에 원소 타입을 검사하는데, 타입 소거 때문에 실행 중에는 List<Integer>와 List<String>을 구별할 수 없기 때문입니다. 이 제약의 이유는 타입 소거와 런타임 한계에서 다뤘습니다.

그래서 와일드카드 배열 List<?>[]를 만든 뒤 List<Integer>[]로 형변환했습니다. 이 형변환은 컴파일러가 안전성을 확인할 수 없어 비검사(unchecked) 경고가 나는데, @SuppressWarnings("unchecked")는 그 경고를 숨길 뿐 안전성을 검사해 주지는 않습니다. 이 코드가 안전한 것은 배열을 private 필드에만 두고, 각 칸에 ArrayList<Integer>만 넣으며, 배열을 바깥에 넘기지 않기 때문입니다. 이 부분이 번거롭다면 앞 글처럼 List<List<Integer>>를 써도 동작은 같습니다.

add와 remove를 거치며 지켜야 할 조건

MyHashSetV1이 올바르게 동작하려면 어떤 호출을 거치더라도 항상 참이어야 하는 조건이 두 가지 있습니다. 이런 조건을 불변식(invariant)이라고 합니다.

1. 모든 버킷의 길이를 더하면 size와 같다.
2. 같은 값은 집합 전체에서 한 번만 저장된다.

main의 호출을 하나씩 따라가며 두 조건을 확인해 보겠습니다. 1번 버킷 말고 다른 버킷은 내내 비어 있으므로, 1번 버킷만 적었습니다.

빈 집합은 모든 버킷이 비어 있고 size가 0이므로 두 조건이 참입니다. 새 값을 넣는 add는 버킷 길이와 size를 함께 1 늘리고, 같은 값이 없을 때만 넣으므로 중복도 생기지 않습니다. 실제로 지우는 remove는 둘을 함께 1 줄입니다. 중복된 값의 add, 없는 값의 remove, 그리고 contains는 어느 쪽도 바꾸지 않습니다. 이렇게 모든 호출이 두 조건을 유지하므로, 어떤 순서로 호출하든 두 조건은 계속 참입니다. 표의 size는 원소 수일 뿐이며 버킷 수나 가장 긴 버킷의 길이와는 상관없다는 점도 함께 봐 두세요.

remove가 버킷 전체를 비우지 않고 값 하나만 지운다는 점도 중요합니다. 마지막 단계에서 1번 버킷을 통째로 비웠다면 같은 버킷에 있던 9까지 사라졌을 것입니다. 게다가 size는 1만 줄었을 테니, 버킷 길이의 합 0과 size 1이 어긋나 첫 번째 조건도 깨집니다. 충돌한 값들이 한 버킷에 함께 산다는 사실은 넣을 때뿐 아니라 지울 때도 지켜야 합니다.

평균 O(1)이 성립하는 조건

값이 버킷에 고르게 퍼져 있다면 contains는 짧은 목록 하나만 보면 됩니다. 원소 수를 n, 버킷 수를 m이라고 하면 버킷 하나에 평균 n/m개가 들어 있으므로, contains는 버킷을 고르는 데 상수 시간, 버킷을 훑는 데 평균 n/m에 비례하는 시간이 듭니다. 이를 합쳐 평균 O(1 + n/m)이라고 씁니다. n/m이 앞 글에서 본 적재 계수이므로, 적재 계수를 일정 값 아래로 유지하면 평균 시간은 상수입니다. 반면 size()는 필드 하나를 읽을 뿐이라 언제나 O(1)입니다.

MyHashSetV1은 이 조건을 지키지 못합니다. 버킷을 8개로 고정해 두었으므로 원소가 800개가 되면 버킷 하나에 평균 100개가 들어가고, contains도 그만큼 느려집니다. 값이 고르게 퍼지지 않는 경우도 문제입니다. 8의 배수만 넣으면 모두 floorMod(값, 8)이 0이라 0번 버킷 하나에 몰리고, contains는 사실상 목록 전체를 훑는 O(n)이 됩니다. 그러니 '해시니까 O(1)'이 아니라, 고르게 퍼지는 해시와 적재 계수를 유지하는 재해시가 있어야 평균 O(1)이라고 말할 수 있습니다. HashSet 공식 문서도 기본 연산이 상수 시간이라고 설명하면서 해시 함수가 원소를 버킷에 고르게 흩어 놓는다는 가정을 붙입니다.

또 하나의 한계는 int만 담을 수 있다는 점입니다. 게시글 제목이나 태그를 저장하려면 문자열의 해시 코드가 필요하고, 버킷 안에서 같은 값인지 판단하려면 equals가 필요합니다. 다음 글에서 문자열의 해시 코드가 어떻게 계산되는지 살펴보고, 이어지는 글들에서 직접 만든 클래스의 equals와 hashCode, 그리고 어떤 타입이든 담을 수 있는 제네릭 집합과 재해시로 넓혀 갑니다.

이미 공개한 제목 막기: 표준 HashSet

실제 코드에서는 표준 HashSet을 씁니다. 다음 CLI는 게시글을 공개할 때마다 제목을 집합에 넣고, add의 반환값으로 새로 공개된 제목인지 이미 공개된 제목인지 알려 줍니다. 같은 공개 명령이 두 번 들어와도 공개 수는 한 번만 늘어납니다.

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

hash-index=new
bucket-chain=new
hash-index=already
count=2

처음 두 제목은 집합에 없으므로 add가 true를 돌려주고 new가 출력됩니다. 세 번째 호출의 "hash-index"는 이미 있으므로 add가 false를 돌려주고 already가 출력되며, 집합 크기는 2에 머뭅니다. MyHashSetV1에서 직접 확인한 반환값 규칙이 표준 구현에서도 그대로 쓰이는 것입니다. 표준 HashSet은 버킷을 바깥에 드러내지 않으므로, 이 코드는 '같은 값은 한 번만 들어간다'는 Set의 규칙에만 의존합니다. 나중에 공개 순서대로 출력해야 한다는 요구가 생기면 구현만 LinkedHashSet으로 바꾸면 되고, add의 의미는 그대로입니다.

여기서 중복의 기준은 제목 문자열이 같은지입니다. "hash-index"와 "HASH-INDEX"는 다른 값으로 취급되고, 제목이 같은 서로 다른 게시글은 하나로 취급됩니다. 대소문자를 무시하려면 넣기 전에 값을 정규화해야 하는데, 그 방법은 다음 글에서 다룹니다. 게시글 단위로 중복 공개를 막아야 한다면 제목 대신 게시글 ID를 집합에 넣어야 합니다. 무엇을 같은 값으로 볼지는 해시가 아니라 프로그램이 정하는 규칙입니다.

정리

• 버킷 한 칸에 값 하나만 두면 충돌한 값이 앞의 값을 덮어써서, 예외 없이 데이터가 사라집니다. 버킷을 목록으로 만들어 충돌한 값들을 함께 보관합니다.
• add와 remove는 집합이 실제로 바뀌었는지를 boolean으로 돌려주고, size는 그때만 바뀝니다.
• List<Integer>에서 값을 지울 때는 remove(Integer.valueOf(value))를 씁니다. int를 그대로 넘기면 인덱스로 지우는 remove(int)가 선택됩니다.
• 버킷 길이의 합이 size와 같고, 같은 값이 한 번만 저장된다는 두 조건은 모든 호출에서 유지되어야 합니다.
• 평균 O(1)은 값이 고르게 퍼지고 적재 계수가 일정 값 아래로 유지될 때의 이야기입니다. 버킷 수가 고정된 MyHashSetV1은 원소가 늘면 느려집니다.

연습 문제

문제 1: 같은 버킷의 값 하나만 지우기

MyHashSetV1의 main을 다음으로 바꾸면 무엇이 출력될까요? 1, 9, 17은 모두 1번 버킷을 고릅니다.

IntHashSet set = new IntHashSet(8);
set.add(1);
set.add(9);
set.add(17);
System.out.println("remove9=" + set.remove(9));
System.out.println("1=" + set.contains(1) + ", 9=" + set.contains(9)
        + ", 17=" + set.contains(17) + ", size=" + set.size());
System.out.println("buckets=" + set);

remove9=true
1=true, 9=false, 17=true, size=2
buckets=[[], [1, 17], [], [], [], [], [], []]

문제 2: 바뀌지 않는 요청의 반환값

원래 main이 끝난 뒤 remove(1), add(9), remove(9)를 차례로 더 호출하면 각 반환값과 그 뒤의 size는 무엇일까요?

remove1=false, size=1
add9=false, size=1
remove9=true, size=0

문제 3: 중복 검사를 빼먹으면

add에서 if (bucket.contains(value)) return false; 줄을 지우면, add(1)을 두 번 호출한 뒤 remove(1)을 호출했을 때 어떤 일이 생길까요? size와 contains(1)의 결과로 설명하세요.

다음 글

다음 글에서는 문자열의 해시 코드를 다룹니다. 문자 코드를 단순히 더하면 왜 "ab"와 "ba"가 충돌하는지 확인하고, 자바의 String.hashCode()가 31을 곱해 가며 누적하는 계산을 한 글자씩 따라갑니다.