해시 테이블의 동작 원리

14장에서 만든 목록에서 원하는 게시글을 찾으려면 앞에서부터 하나씩 꺼내 비교해야 했습니다. 게시글이 n개면 최악에는 n번을 비교해야 하므로, 데이터가 늘어날수록 조회도 그만큼 느려집니다. 반면 배열은 인덱스만 알면 몇 번째 칸이든 한 번에 읽습니다. 그렇다면 게시글 ID를 그대로 배열 인덱스로 쓰면 어떨까요? ID가 3인 게시글을 values[3]에 넣어 두면 조회는 계산 한 번으로 끝납니다.

이 방법은 키가 0부터 시작하는 작은 정수일 때만 통합니다. 키가 -7이면 음수 칸이 없고, 10억이면 배열이 지나치게 커지며, 문자열이면 애초에 인덱스로 쓸 수 없습니다. 이 글에서는 어떤 키든 정해진 크기의 배열 안 번호로 바꾸는 방법과, 서로 다른 키가 같은 번호를 받았을 때 처리하는 방법을 배웁니다. 이 두 가지가 HashSet과 HashMap이 동작하는 기본 원리입니다.

키를 그대로 인덱스로 쓰면 생기는 일

다음 코드는 길이 10인 배열에 키 3과 키 -7의 값을 넣으려고 합니다. 3은 유효한 인덱스 0부터 9 사이에 있지만 -7은 그렇지 않습니다.

public final class DirectIndexFailure {
    public static void main(String[] args) {
        String[] values = new String[10];
        values[3] = "hash";
        values[-7] = "collision";
        System.out.println(values[3]);
    }
}

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -7 out of bounds for length 10
	at DirectIndexFailure.main(DirectIndexFailure.java:5)

4번째 줄의 values[3] = "hash"는 정상으로 실행됩니다. 5번째 줄에서 -7번 칸에 쓰려는 순간 ArrayIndexOutOfBoundsException이 발생하고 프로그램이 멈춥니다. 배열의 유효 인덱스는 0부터 length - 1, 즉 9까지이기 때문입니다. 그래서 6번째 줄의 println은 실행되지 않고 표준 출력에는 아무것도 나오지 않습니다. 스택 트레이스 끝의 DirectIndexFailure.java:5가 예외가 난 5번째 줄을 가리킵니다.

배열을 더 크게 만든다고 해결되지는 않습니다. 길이를 100만으로 늘려도 음수 인덱스는 여전히 없습니다. 키가 10억까지 갈 수 있다고 길이 10억짜리 배열을 만들면, 게시글이 몇 개뿐이어도 칸 10억 개의 메모리를 먼저 차지합니다. String 같은 키는 숫자가 아니니 인덱스로 쓸 방법조차 없습니다. 문제의 뿌리는 키와 저장 위치를 같은 값으로 본 데 있습니다. 키가 가질 수 있는 값의 범위는 넓은데, 배열 칸은 0부터 length - 1까지 정해진 개수뿐입니다.

키를 작은 번호로 바꾸는 해시

해결책은 키를 저장 위치로 바로 쓰지 않고, 키에서 배열 범위 안의 번호를 계산해 쓰는 것입니다. 이 계산은 두 단계로 나뉩니다. 먼저 키를 int 하나로 요약합니다. 자바에서는 모든 객체가 hashCode() 메서드로 이 일을 하고, 그 결과를 해시 코드(hash code)라고 부릅니다. 다음으로 해시 코드를 배열 길이에 맞게 0 이상 length - 1 이하의 번호로 줄이고, 이 번호로 배열 칸을 고릅니다.

그런데 넓은 범위의 키를 좁은 범위의 번호로 줄이면 서로 다른 키가 같은 번호를 받는 일을 피할 수 없습니다. 그래서 배열의 한 칸에는 값 하나가 아니라, 그 번호를 받은 키와 값의 목록을 둡니다. 이렇게 같은 번호를 받은 항목들이 모이는 칸을 버킷(bucket)이라고 합니다. 이 장의 도표에서는 같은 뜻으로 '그룹'이라는 말도 씁니다.

버킷에 값만이 아니라 원래 키도 함께 보관한다는 점이 중요합니다. 한 버킷에는 여러 키의 항목이 섞여 있을 수 있으므로, 값을 찾을 때는 버킷 안의 키와 찾는 키를 다시 비교해야 하기 때문입니다. 정리하면 해시 테이블(hash table)에서 값을 찾는 과정은 '번호 계산, 버킷 선택, 버킷 안에서 키 비교'의 세 단계입니다. 배열 전체를 훑지 않고 버킷 하나만 보면 되므로, 버킷이 짧게 유지되는 한 조회는 거의 한 번에 끝납니다.

해시 코드를 버킷 번호로 줄이기: %와 Math.floorMod

버킷이 8개라면 해시 코드를 8로 나눈 나머지를 번호로 쓰는 방법이 가장 간단합니다. 해시 코드가 양수라면 hashCode % 8은 언제나 0부터 7 사이입니다. 문제는 해시 코드가 음수일 때입니다. 해시 코드는 int 범위의 어떤 값이든 될 수 있는데, 자바의 %는 결과의 부호가 왼쪽 피연산자를 따르므로 -7 % 8은 1이 아니라 -7입니다. 산술 연산과 문자열 결합에서 본 바로 그 성질입니다.

음수에서도 0 이상의 나머지를 주는 메서드가 Math.floorMod입니다. Math.floorMod(x, y)는 x ÷ y보다 크지 않은 가장 큰 정수를 몫으로 삼고 나머지를 구합니다. -7 ÷ 8 = -0.875보다 크지 않은 가장 큰 정수는 -1이므로 몫은 -1이고, -7 = (-1) × 8 + 1이므로 나머지는 1입니다. 반면 %는 몫의 소수 부분을 그냥 버려(0 쪽으로 잘라) 몫을 0으로 보기 때문에 나머지가 -7이 됩니다. Math.floorMod 공식 문서에 따르면 결과는 0이거나 나누는 수 y와 부호가 같고, 크기는 y의 절댓값보다 작습니다. 그래서 y가 양수이면 결과는 언제나 0 이상 y 미만이고, 그대로 배열 인덱스로 쓸 수 있습니다.

음수가 문제라면 Math.abs로 부호를 없앤 뒤 %를 써도 되지 않을까요? 대부분의 값에서는 맞지만 한 값에서 틀립니다. int의 가장 작은 값인 Integer.MIN_VALUE(-2147483648)는 절댓값 2147483648이 int의 가장 큰 값 2147483647보다 커서 표현할 수 없고, Math.abs는 이 값을 그대로 -2147483648로 돌려줍니다. 해시 코드가 하필 이 값일 일은 드물어 보이지만 실제로 있습니다. 예를 들어 문자열 "polygenelubricants"의 hashCode()가 정확히 -2147483648입니다. 다음 코드로 세 방법을 비교해 보겠습니다.

public final class BucketIndexFromHash {
    public static void main(String[] args) {
        System.out.println("-7 % 8 = " + (-7 % 8));
        System.out.println("floorMod(-7, 8) = " + Math.floorMod(-7, 8));

        int min = Integer.MIN_VALUE;
        System.out.println("abs(MIN_VALUE) = " + Math.abs(min));
        System.out.println("abs(MIN_VALUE) % 13 = " + (Math.abs(min) % 13));
        System.out.println("floorMod(MIN_VALUE, 13) = " + Math.floorMod(min, 13));
    }
}

-7 % 8 = -7
floorMod(-7, 8) = 1
abs(MIN_VALUE) = -2147483648
abs(MIN_VALUE) % 13 = -11
floorMod(MIN_VALUE, 13) = 2

처음 두 줄은 앞에서 계산한 그대로입니다. 셋째 줄에서 Math.abs를 거친 값이 여전히 음수이므로, 버킷이 13개일 때의 나머지도 넷째 줄처럼 -11이 됩니다. 이 값을 인덱스로 쓰면 예외가 납니다. 같은 해시 코드에 floorMod를 쓰면 마지막 줄처럼 2가 나옵니다. 그래서 이 장의 학습용 코드는 부호를 미리 손보지 않고 Math.floorMod(hashCode, bucketCount) 한 번으로 버킷 번호를 구합니다.

나누는 수가 0이면 %와 floorMod 모두 ArithmeticException: / by zero를 던집니다. 버킷 수는 해시 테이블을 만들 때 정하므로 생성자에서 한 번 양수인지 검사해 둡니다. 뒤에서 버킷을 늘릴 때도 양수가 더 큰 양수로 바뀔 뿐이므로, 값을 넣거나 찾을 때마다 다시 검사할 필요는 없습니다.

서로 다른 키가 같은 버킷을 고를 때

버킷이 8개일 때 키 1, 9, -7의 번호를 구하면 모두 1입니다. 1 = 0 × 8 + 1, 9 = 1 × 8 + 1, -7 = (-1) × 8 + 1이기 때문입니다. 이처럼 서로 다른 키가 같은 버킷을 고르는 것을 해시 충돌(hash collision)이라고 합니다. 정수의 해시 코드는 Integer.hashCode(key)로 구합니다. Integer 공식 문서에 따르면 Integer 객체의 해시 코드는 감싼 int 값 자체이고, 정적 메서드 Integer.hashCode(int)도 그와 같은 값을 돌려줍니다. 즉 정수의 해시 코드는 정수 자기 자신입니다. 즉 세 키는 해시 코드가 1, 9, -7로 모두 다른데도, 해시 코드를 버킷 수로 줄이는 단계에서 충돌합니다. 해시 코드 자체가 같아서 생기는 충돌도 있는데, 그 예는 문자열 해시를 다룰 때 봅니다.

충돌은 오류가 아닙니다. 버킷 수보다 많은 키를 넣으면 어느 두 키는 반드시 같은 버킷을 고르고, 키가 적어도 우연히 겹칠 수 있습니다. 그래서 충돌은 막을 대상이 아니라 처리할 대상입니다.

버킷 한 칸에 값 하나만 두면 나중에 온 키가 먼저 온 키를 덮어써 데이터를 잃습니다. 이 문제는 다음 글에서 직접 재현합니다. 아래 코드는 이를 피하려고 버킷마다 작은 목록을 두고, 충돌한 항목을 그 목록에 함께 보관합니다. 이렇게 충돌한 항목을 버킷의 목록에 이어 붙이는 방식을 체이닝(separate chaining)이라고 합니다.

아래 IntTable은 정수 키와 문자열 값을 저장하는 학습용 해시 테이블입니다. 버킷 배열 대신 목록의 목록(List<List<Entry>>)을 써서 제네릭 배열을 만드는 번거로움을 피했고, 항목 하나는 키와 값을 묶은 record Entry로 나타냈습니다.

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

public final class IntegerBucketTable {
    public static void main(String[] args) {
        IntTable table = new IntTable(8);
        table.put(1, "array");
        table.put(9, "hash");
        table.put(-7, "negative");
        System.out.println(table.get(1));
        System.out.println(table.get(9));
        System.out.println(table.get(-7));
        System.out.println("sizes=" + table.bucketSizes());
    }

    private record Entry(int key, String value) {}

    private static final class IntTable {
        private final List<List<Entry>> buckets = new ArrayList<>();

        IntTable(int bucketCount) {
            if (bucketCount <= 0) throw new IllegalArgumentException("bucketCount");
            for (int i = 0; i < bucketCount; i++) {
                buckets.add(new ArrayList<>());
            }
        }

        void put(int key, String value) {
            List<Entry> bucket = buckets.get(index(key));
            for (int i = 0; i < bucket.size(); i++) {
                if (bucket.get(i).key() == key) {
                    bucket.set(i, new Entry(key, value));
                    return;
                }
            }
            bucket.add(new Entry(key, value));
        }

        String get(int key) {
            for (Entry entry : buckets.get(index(key))) {
                if (entry.key() == key) {
                    return entry.value();
                }
            }
            return null;
        }

        private int index(int key) {
            return Math.floorMod(Integer.hashCode(key), buckets.size());
        }

        List<Integer> bucketSizes() {
            List<Integer> sizes = new ArrayList<>();
            for (List<Entry> bucket : buckets) {
                sizes.add(bucket.size());
            }
            return sizes;
        }
    }
}

array
hash
negative
sizes=[0, 3, 0, 0, 0, 0, 0, 0]

put은 index로 버킷을 고른 뒤 그 버킷에 같은 키가 이미 있는지 찾습니다. 있으면 그 자리의 항목을 새 항목으로 바꾸고(set), 없으면 목록 끝에 붙입니다(add). 맵에서는 키 하나에 값이 하나만 있어야 하기 때문입니다. 세 번의 put이 끝날 때마다 1번 버킷은 다음과 같이 바뀝니다.

세 키가 한 버킷에 모였지만 get은 세 값을 정확히 구별합니다. get(9)를 예로 들면, 먼저 floorMod(9, 8)로 1번 버킷을 고릅니다. 버킷의 첫 항목은 키가 1이라 9와 다르므로 건너뛰고, 둘째 항목의 키 9가 일치하므로 "hash"를 돌려줍니다. 값을 찾는 순간 메서드가 끝나므로 셋째 항목 -7은 비교하지 않습니다. 출력의 처음 세 줄이 이렇게 나온 값이고, 마지막 줄의 sizes는 버킷마다 항목 수를 센 것입니다. 세 항목이 모두 1번 버킷에 있고 나머지 일곱 버킷은 비어 있습니다.

get이 키를 다시 비교해야 하는 이유도 여기서 분명해집니다. 1번 버킷을 골랐다는 것은 '키 9가 있다면 이 버킷에 있다'는 뜻일 뿐, 버킷의 첫 항목이 키 9라는 뜻은 아닙니다. 이 예제의 키는 기본형 int라서 ==로 값을 비교했습니다. 키가 객체라면 ==는 같은 객체인지를 비교하므로, 내용이 같은지 보려면 equals를 써야 합니다. 객체 키에서 hashCode와 equals가 어떻게 짝을 이뤄야 하는지는 equals와 hashCode를 다루는 글에서 자세히 봅니다.

버킷이 길어지면 느려진다: 적재 계수와 재해시

해시 테이블의 조회 속도는 결국 고른 버킷의 길이에 달려 있습니다. 버킷 번호를 계산하는 비용은 항목 수와 상관없이 일정하지만, 버킷 안에서는 항목을 하나씩 비교하기 때문입니다. 그래서 해시 테이블의 성능을 이야기할 때는 다음 세 숫자를 봅니다.

• 버킷 수: 너무 적으면 충돌이 늘고, 너무 많으면 빈 버킷이 메모리를 차지합니다.
• 적재 계수(load factor): 저장한 항목 수를 버킷 수로 나눈 값으로, 버킷 하나에 평균 몇 개가 들어 있는지를 나타냅니다.
• 가장 긴 버킷의 길이: 평균에는 드러나지 않는 쏠림을 보여 줍니다.

앞 예제는 항목 3개를 버킷 8개에 넣었으므로 적재 계수가 3/8 = 0.375입니다. 평균으로는 버킷 하나에 0.4개도 안 되지만, 실제로는 세 항목이 한 버킷에 몰려 가장 긴 버킷의 길이가 3이고, get(-7)은 세 번을 비교해야 답을 찾습니다. 평균이 작아도 키가 고르게 퍼지지 않으면 느려질 수 있다는 뜻입니다. 해시 코드를 만드는 방법, 즉 해시 함수(hash function)가 키를 버킷에 고르게 흩어 놓는 것이 중요한 이유입니다.

항목이 계속 늘어나면 버킷 수가 고정된 테이블은 적재 계수가 커지고 버킷이 점점 길어집니다. 이를 막으려면 적재 계수가 정해 둔 값을 넘을 때 더 큰 버킷 배열을 만들고 모든 항목을 옮겨야 합니다. 이 과정을 재해시(rehash)라고 합니다. 앞의 IntTable에는 아직 이 기능이 없고, 제네릭 Set과 재해시를 다루는 글에서 직접 구현합니다.

항목을 옮길 때 기존 버킷 번호를 그대로 쓸 수는 없습니다. 버킷 번호는 해시 코드를 버킷 수로 나눈 나머지이므로, 버킷 수가 바뀌면 번호도 다시 계산해야 합니다. 버킷을 8개에서 16개로 늘리면 세 키의 번호는 다음과 같이 바뀝니다.

키 1은 그대로 1번에 남고 9와 -7은 9번으로 옮겨 갑니다. 재해시는 모든 키의 번호를 새 버킷 수로 다시 정하는 일이지, 모든 키가 반드시 자리를 옮긴다는 뜻은 아닙니다. 또 9와 -7은 16개에서도 여전히 같은 버킷에 있습니다. 두 해시 코드의 차이 16이 새 버킷 수 16으로도 나누어떨어지기 때문입니다. 버킷을 늘리면 대체로 충돌이 줄지만 모든 충돌이 사라지지는 않고, 해시 코드 자체가 같은 키들은 버킷을 아무리 늘려도 갈라지지 않습니다.

재해시는 모든 항목을 한 번씩 옮기므로 한 번 할 때는 비쌉니다. 하지만 버킷 수를 두 배씩 늘리면 용량이 늘어나는 동적 배열에서 본 것과 같은 이유로, 항목을 많이 넣는 전체 과정에 나눠 보면 넣기 한 번에 드는 옮기기 비용은 상수에 머뭅니다. 물론 키가 버킷에 고르게 퍼진다는 가정이 있어야 버킷도 짧게 유지됩니다.

해시 테이블이 제대로 동작하려면 전제가 하나 더 필요합니다. 프로그램이 실행되는 동안 같은 키는 언제 계산해도 같은 해시 코드를 내야 합니다. 저장할 때와 찾을 때 해시 코드가 다르면 다른 버킷을 보게 되어, 분명히 넣은 키를 찾지 못합니다. 해시 코드 계산에 현재 시각이나 난수를 넣으면 안 되는 이유이고, 키를 저장한 뒤 해시 코드 계산에 쓰이는 필드를 바꾸면 안 되는 이유이기도 합니다. 그래서 키로는 값을 바꿀 수 없는 불변 객체가 안전합니다.

더 깊이: 표준 HashMap은 실제로 어떻게 하는가

지금까지의 원리는 표준 HashMap에도 그대로 적용됩니다. 다만 세부 사항에는 Javadoc이 약속하는 동작과 OpenJDK가 그 약속을 구현한 방식이 섞여 있으니 구분해서 알아 두는 편이 좋습니다. HashMap 공식 문서가 정한 것은 다음과 같습니다. 용량(capacity)은 버킷 수이고, 기본 생성자는 초기 용량 16과 적재 계수 0.75로 맵을 만듭니다. 항목 수가 '용량 × 적재 계수'를 넘으면 버킷이 약 두 배가 되도록 재해시합니다. get과 put의 상수 시간 성능은 해시 함수가 원소를 버킷에 고르게 흩어 놓는다는 가정 아래의 이야기이고, 같은 hashCode를 내는 키가 많으면 어떤 해시 테이블이든 느려진다는 경고도 있습니다.

OpenJDK 구현(이 글은 JDK 21에서 확인했습니다)은 여기에 몇 가지 결정을 더합니다. 버킷 수를 항상 2의 거듭제곱으로 두고, 재해시 때 정확히 두 배로 늘립니다. 그래서 기본 생성자로 만든 맵은 항목 12개까지는 버킷 16개로 버티다가 13번째 항목을 넣을 때 32개로 커집니다. 버킷 번호도 floorMod가 아니라 비트 연산으로 구하는데, 그 식은 HashSet·LinkedHashSet·TreeSet을 비교하는 글에서 살펴봅니다. 또 Java 8부터는 이미 항목이 8개 있는 버킷에 하나가 더 들어오면 그 버킷의 목록을 레드-블랙 트리로 바꿔 최악의 조회 시간을 줄입니다. 이때 버킷 배열이 64칸보다 작으면 트리로 바꾸는 대신 배열을 먼저 키웁니다. Javadoc은 이런 수치를 약속하지 않고 '키가 Comparable이면 비교 순서를 이용할 수 있다'고만 적어 두었으므로, 8이나 64 같은 숫자에 기대는 코드를 써서는 안 됩니다.

실무에서 바로 쓸 수 있는 차이도 하나 있습니다. new HashMap<>(100)의 100은 넣을 항목 수가 아니라 초기 용량입니다. OpenJDK는 이 값을 2의 거듭제곱인 128로 올리는데, 128 × 0.75 = 96이므로 항목 100개를 넣는 도중 97번째에서 재해시가 일어납니다. 넣을 항목 수를 미리 안다면 Java 19에 추가된 HashMap.newHashMap(100)을 쓰세요. Javadoc에 따르면 이 메서드는 그만큼의 항목을 대개 재해시 없이 넣을 수 있을 만큼 큰 초기 용량으로 맵을 만듭니다.

게시글 ID로 게시글 찾기: HashMap

실제 프로그램에서는 해시 테이블을 직접 만들지 않고 표준 HashMap을 씁니다. 다음 코드는 게시글 저장소에서 게시글 ID를 키로, 게시글을 값으로 저장하고 ID로 게시글을 찾습니다. Map 인터페이스와 여러 구현은 16장에서 자세히 다루므로, 여기서는 앞에서 만든 IntTable과 어떻게 대응하는지만 봅니다.

import java.util.HashMap;
import java.util.Map;

public final class HashedBoardPostCli {
    public static void main(String[] args) {
        Map<Integer, Post> posts = new HashMap<>();
        add(posts, new Post(101, "hash-index", 45));
        add(posts, new Post(205, "collision", 55));

        Post found = posts.get(205);
        System.out.println("found=" + found.title());
        System.out.println("missing=" + posts.get(999));

        int total = 0;
        for (Post post : posts.values()) {
            total += post.viewCount();
        }
        System.out.println("total=" + total);
    }

    private static void add(Map<Integer, Post> posts, Post post) {
        if (posts.putIfAbsent(post.id(), post) != null) {
            throw new IllegalArgumentException("duplicate id=" + post.id());
        }
    }

    private record Post(int id, String title, int viewCount) {}
}

found=collision
missing=null
total=100

add의 putIfAbsent는 키에 연결된 값이 없을 때만 새 값을 넣고 null을 돌려주며, 이미 값이 있으면 아무것도 바꾸지 않고 그 값을 돌려줍니다. 그래서 반환값이 null이 아니면 중복 ID로 보고 예외를 던집니다. posts.get(205)는 키 205(자동으로 Integer로 박싱됩니다)의 해시 코드로 버킷을 고르고, 버킷 안의 키들과 equals로 비교해 일치하는 키의 값을 돌려줍니다. 첫 줄의 found=collision이 그렇게 찾은 게시글의 제목입니다. HashMap이 값인 Post의 필드를 뒤지는 것은 아니며, 비교 대상은 언제나 키뿐입니다.

둘째 줄처럼 없는 키를 찾으면 get은 null을 돌려줍니다. 실제 CLI라면 found.title()을 호출하기 전에 null인지 확인해야 하고, 그러지 않으면 NullPointerException이 납니다. HashMap은 값으로 null을 넣는 것도 허용하므로, null이 '키 없음'인지 'null이 저장됨'인지 구별해야 할 때는 containsKey를 씁니다. 셋째 줄의 합계는 values()를 돌며 조회 수를 더한 45 + 55입니다. HashMap은 반복 순서를 보장하지 않지만 덧셈은 순서와 상관없으므로 결과는 언제나 100입니다.

앞의 floorMod는 학습용 IntTable이 고른 번호 계산 방법일 뿐 HashMap의 내부 식이 아닙니다. HashMap을 쓰는 코드가 기대할 수 있는 것은 Map.get 공식 문서에 적힌 동작, 즉 equals로 같은 키에 연결된 값을 돌려주고 없으면 null을 돌려준다는 것입니다. 버킷 수나 번호 계산 방식에 기대는 코드는 쓰지 않습니다.

정리

• 키를 그대로 배열 인덱스로 쓰면 음수, 아주 큰 수, 문자열 키를 다룰 수 없습니다.
• 해시 테이블은 hashCode()로 키를 int 하나로 요약하고, 그 값을 Math.floorMod(hashCode, bucketCount)처럼 버킷 번호로 줄입니다. %는 음수 결과를 낼 수 있고 Math.abs는 Integer.MIN_VALUE에서 음수를 돌려줍니다.
• 서로 다른 키가 같은 버킷을 고르는 충돌은 피할 수 없습니다. 그래서 버킷에 키와 값을 함께 보관하고(체이닝), 찾을 때 버킷 안에서 원래 키를 다시 비교합니다.
• 조회 속도는 버킷 길이에 달려 있습니다. 적재 계수가 커지면 버킷을 늘리는 재해시를 하고, 이때 모든 키의 번호를 새 버킷 수로 다시 계산합니다.
• 같은 키는 실행 중 언제나 같은 해시 코드를 내야 하며, 저장된 키의 해시 코드가 바뀌면 그 키를 찾지 못합니다.

연습 문제

문제 1: 버킷 8개와 16개에 키 나누기

키 1, 9, 2, 10, -7을 버킷 8개에 넣으면 어떤 키끼리 충돌할까요? 버킷을 16개로 늘리면 어떻게 바뀔까요? 손으로 계산한 뒤 해설의 코드로 확인하세요.

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

public final class CollisionGroupSolution {
    public static void main(String[] args) {
        int[] keys = {1, 9, 2, 10, -7};
        System.out.println("buckets(8)=" + place(keys, 8));
        System.out.println("buckets(16)=" + place(keys, 16));
    }

    private static List<List<Integer>> place(int[] keys, int bucketCount) {
        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }
        for (int key : keys) {
            int index = Math.floorMod(Integer.hashCode(key), bucketCount);
            buckets.get(index).add(key);
        }
        return buckets;
    }
}

buckets(8)=[[], [1, 9, -7], [2, 10], [], [], [], [], []]
buckets(16)=[[], [1], [2], [], [], [], [], [], [], [9, -7], [10], [], [], [], [], []]

문제 2: 같은 키를 다시 넣으면

IntegerBucketTable의 main 끝에 다음 네 줄을 붙이면 무엇이 추가로 출력될까요? 키 17도 1번 버킷을 고르지만 넣은 적은 없습니다.

table.put(9, "updated");
System.out.println(table.get(9));
System.out.println(table.get(17));
System.out.println("sizes=" + table.bucketSizes());

updated
null
sizes=[0, 3, 0, 0, 0, 0, 0, 0]

문제 3: floorMod 대신 %를 쓰면

IntTable의 index 메서드 본문을 return Integer.hashCode(key) % buckets.size();로 바꾸면 프로그램은 어디서 어떻게 실패할까요?

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index -7 out of bounds for length 8

다음 글

다음 글에서는 이 원리로 정수를 담는 해시 집합을 직접 만듭니다. 버킷 하나에 값 하나만 두면 충돌한 값이 어떻게 사라지는지 먼저 재현하고, 중복을 막는 add와 값을 지우는 remove가 size와 어긋나지 않도록 구현합니다.