문자열 hashCode

정수는 자기 값을 해시 재료로 쓸 수 있지만 문자열은 여러 문자를 하나의 int로 요약해야 합니다.

중요한 조건은 암호학적 보안이 아니라 같은 문자열이 같은 실행 상태에서 같은 hashCode를 내고, 흔한 입력이 그룹 전체에 비교적 고르게 퍼지는 것입니다.

hashCode가 같아도 문자열이 같다는 뜻은 아니므로 마지막 equals 비교는 남습니다.

문자 합 해시와 순서 소실

ab와 ba는 문자 코드의 합이 같습니다.

게시글 slug에서 글자 순서가 의미를 가지는데 단순 합은 순열을 모두 같은 결과로 만듭니다.

다음 출력은 문자 합에서 순서 정보가 사라져 서로 다른 두 문자열이 충돌하는 모습을 보여 줍니다.

lab/AdditiveStringHashCollision.java

public final class AdditiveStringHashCollision {
    public static void main(String[] args) {
        String left = "ab";
        String right = "ba";
        int leftHash = additive(left);
        int rightHash = additive(right);
        System.out.println(left + "=" + leftHash);
        System.out.println(right + "=" + rightHash);
        System.out.println(
                "different=" + !left.equals(right) + ", collision=" + (leftHash == rightHash));
    }

    private static int additive(String value) {
        int hash = 0;
        for (int i = 0; i < value.length(); i++) {
            hash += value.charAt(i);
        }
        return hash;
    }
}

관찰

ab=195
ba=195
different=true, collision=true

충돌 자체는 허용되지만 이런 입력 패턴이 많으면 특정 그룹이 길어집니다.

문자를 읽을 때 이전 결과에 31을 곱한 뒤 다음 문자를 더하면 앞 문자의 위치가 이후 계산에 계속 영향을 줍니다.

실패 판단은 충돌 존재가 아니라 편향 정도다

두 값이 충돌했다는 사실 하나만으로 해시 함수가 틀렸다고 판단하지 않습니다.

int 결과보다 가능한 문자열 수가 훨씬 많으므로 충돌은 수학적으로 피할 수 없습니다.

실제 문제 신호는 게시글 제목처럼 자주 등장하는 입력군이 몇 개 그룹에 반복해서 몰려 평균 후보 길이가 커지는 현상입니다.

평가할 때는 입력 표본을 고정하고 그룹별 개수, 최대 길이, 빈 그룹 비율을 함께 출력합니다.

단순 문자 합은 철자 순서를 바꾼 모든 문자열을 같은 코드로 만들기 때문에 이런 분포 검사에서 명확한 편향을 보입니다.

31배 누적은 충돌을 제거하지 않지만 순서 정보를 계산에 반영해 해당 실패 패턴을 줄입니다.

Java 문자열 해시의 중간 계산

문자열 abc는 ((0 * 31 + 'a') * 31 + 'b') * 31 + 'c'로 누적됩니다. charAt으로 읽는 값은 UTF-16 코드 단위이며, 이번 세 입력은 모두 ASCII 문자입니다.

곱셈은 int 범위를 넘을 수 있으며 Java 오버플로를 포함한 결과가 공식의 일부입니다.

해시 테이블은 음수 hashCode도 정상 입력으로 받아 floorMod로 배열 범위에 넣습니다.

src/StringHashWalkthrough.java

public final class StringHashWalkthrough {
    public static void main(String[] args) {
        trace("abc", 8);
        trace("ab", 8);
        trace("ba", 8);
        System.out.println("jdk-match=" + (polynomial("abc") == "abc".hashCode()));
    }

    private static void trace(String value, int bucketCount) {
        int hash = 0;
        for (int index = 0; index < value.length(); index++) {
            char character = value.charAt(index);
            hash = 31 * hash + character;
            System.out.println(
                    value + "[" + index + "] char=" + (int) character + ", hash=" + hash);
        }
        int bucketIndex = Math.floorMod(hash, bucketCount);
        System.out.println(value + " -> hash=" + hash + ", bucket=" + bucketIndex);
    }

    private static int polynomial(String value) {
        int hash = 0;
        for (int index = 0; index < value.length(); index++) {
            hash = 31 * hash + value.charAt(index);
        }
        return hash;
    }
}

같은 누적 규칙으로 구한 세 문자열의 해시와 인덱스
문자열	문자 처리 직후의 누적 계산	최종 hash	8개 그룹의 index
`"abc"`	`0×31 + 97 = 97` `97×31 + 98 = 3105` `3105×31 + 99 = 96354`	`96354`	`2`
`"ab"`	`0×31 + 97 = 97` `97×31 + 98 = 3105`	`3105`	`1`
`"ba"`	`0×31 + 98 = 98` `98×31 + 97 = 3135`	`3135`	`7`

"abc": 문자 처리 직후의 누적 계산:
0×31 + 97 = 97
97×31 + 98 = 3105
3105×31 + 99 = 96354
최종 hash: 96354
8개 그룹의 index: 2
"ab": 문자 처리 직후의 누적 계산:
0×31 + 97 = 97
97×31 + 98 = 3105
최종 hash: 3105
8개 그룹의 index: 1
"ba": 문자 처리 직후의 누적 계산:
0×31 + 98 = 98
98×31 + 97 = 3135
최종 hash: 3135
8개 그룹의 index: 7

인덱스는 최종 해시에 floorMod(hash, 8)을 적용한 값입니다. 앞의 문자 합 예제에서는 ab와 ba가 모두 195이지만, 여기서는 각각 3105와 3135입니다. 마지막 jdk-match=true는 abc만 비교합니다.

31은 홀수 소수이고 31 * value를 JVM이 shift와 subtraction으로 최적화할 여지도 있습니다.

숫자 31 자체를 외우는 것보다 이전 상태를 곱해 위치 정보를 남긴다는 구조가 핵심입니다.

마지막 jdk-match는 abc의 직접 계산 결과와 Java String.hashCode() 결과를 비교합니다.

hashCode·index·equals의 역할

hashCode는 객체를 int로 요약합니다.

index는 그룹 수에 맞춰 그 int의 범위를 줄입니다.

equals는 같은 그룹 후보 중 논리적으로 같은 값을 판단합니다.

index가 같다는 이유로 equals를 생략하면 충돌한 문자열을 같은 원소로 오판합니다.

같은 문자열의 hashCode가 호출할 때마다 바뀌면 add와 포함 여부가 서로 다른 그룹을 봅니다.

hashCode 계산에 현재 시간이나 난수를 넣어서는 안 됩니다.

문자열은 불변이므로 저장 뒤 코드가 바뀌지 않는 안전한 키입니다.

빈 문자열의 누적 결과는 0입니다.

null은 String 인스턴스가 아니므로 메서드 호출 전에 별도 정책이 필요합니다.

표준 HashSet은 null 하나를 허용하지만 직접 구현은 금지할 수도 있으며, 어느 쪽이든 API 사용 규칙에 명시해야 합니다.

게시글 저장소 태그는 정규화한 뒤 집합에 포함

Java, java, JAVA를 같은 태그로 볼지 결정하는 일은 해시 함수가 아니라 도메인 정책입니다.

CLI는 앞뒤 공백을 제거하고 소문자로 바꾼 뒤 HashSet에 저장합니다.

정규화 전 원문을 키로 쓰면 hashCode가 올바르게 달라도 논리 중복이 남습니다.

app/NormalizedTagCli.java

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

public final class NormalizedTagCli {
    public static void main(String[] args) {
        Set<String> tags = new HashSet<>();
        for (String raw : new String[] {"Java", " hash ", "JAVA", "Hash"}) {
            String normalized = normalize(raw);
            System.out.println(raw + " -> " + normalized + ":" + tags.add(normalized));
        }
        System.out.println("tags=" + tags.stream().sorted().toList());
    }

    private static String normalize(String raw) {
        if (raw == null) throw new IllegalArgumentException("tag");
        String value = raw.strip().toLowerCase(Locale.ROOT);
        if (value.isEmpty()) throw new IllegalArgumentException("blank tag");
        return value;
    }
}

정규화한 태그를 추가할 때의 실제 결과
원문 입력	정규화된 키	add 반환값	호출 뒤 size
`"Java"`	`"java"`	`true`	`1`
`" hash "`	`"hash"`	`true`	`2`
`"JAVA"`	`"java"`	`false`	`2`
`"Hash"`	`"hash"`	`false`	`2`

"Java": 정규화된 키: "java"
add 반환값: true
호출 뒤 size: 1
" hash ": 정규화된 키: "hash"
add 반환값: true
호출 뒤 size: 2
"JAVA": 정규화된 키: "java"
add 반환값: false
호출 뒤 size: 2
"Hash": 정규화된 키: "hash"
add 반환값: false
호출 뒤 size: 2

입력·정규화된 키·add 결과는 실제 출력에 있고, 각 행의 size는 원문의 추가 과정을 추적한 값입니다. 마지막 tags=[hash, java]는 sorted()의 결과이며 HashSet의 반복 순서를 뜻하지 않습니다.

Locale.ROOT는 실행 환경의 언어 설정에 따라 소문자 결과가 달라지지 않게 합니다.

HashSet에는 정규화된 값만 들어가므로 equals와 hashCode가 도메인 동등성에 맞게 작동합니다.

출력 정렬은 표현을 안정시키기 위한 별도 단계이며 HashSet 순서 규칙이 아닙니다.

연습 문제

각 문자 코드와 처리 직후 해시를 출력하고 마지막 값을 Java String.hashCode()와 비교하세요.

그룹 16개일 때 index도 구합니다.

정답과 해설

c=99, a=97, t=116을 차례로 사용합니다.

이전 결과를 31배 하므로 같은 문자 집합을 다른 순서로 배치하면 보통 다른 값이 됩니다.

exercise/StringHashTraceSolution.java

public final class StringHashTraceSolution {
    public static void main(String[] args) {
        String value = "cat";
        int hash = 0;
        for (int i = 0; i < value.length(); i++) {
            int code = value.charAt(i);
            hash = 31 * hash + code;
            System.out.println(i + ": code=" + code + ", hash=" + hash);
        }
        System.out.println("same=" + (hash == value.hashCode()));
        System.out.println("bucket=" + Math.floorMod(hash, 16));
    }
}

직접 계산과 JDK 결과가 같아야 합니다.

그룹 수가 달라지면 마지막 index를 다시 계산해야 하지만, 결과가 항상 달라지는 것은 아닙니다. 문자열 hashCode는 그룹 수와 무관합니다.

이 구분이 rehash 때 모든 키의 index를 다시 계산하는 이유입니다.

문자열 해시 절을 마쳤다면 순서 누적이 필요한 이유, 음수 hashCode가 유효한 이유, 충돌 뒤 equals가 필요한 이유를 별개의 문장으로 설명할 수 있어야 합니다.