[Java] 코딩 테스트에서 문자열 해시를 쓰면 안되는 이유 (HashMap, HashSet)

얼마 전, 아는 동생이 코테 대비 문제를 푸는데 똑같아야 할 것 같은 두 코드의 실행 시간이 너무 차이 난다는 이야기를 했다.

 

좌표를 다루어야 하는 문제인데, 한 코드는 다음과 같이 좌표를 int를 변환시켜 HashMap에 적용하였다.

Map<Integer, Integer> map = new HashMap<>();
while (/* 반복 */) {
    int x = /* x 좌표 */;
    int y = /* y 좌표 */;

    int key = y * HEIGHT + x;
    map.put(map.getOrDefault(key, 0) + 1);
}

 

또 다른 코드는 좌표를 String으로 변환하여 적용하였다.

Map<String, Integer> map = new HashMap<>();
while (/* 반복 */) {
    int x = /* x 좌표 */;
    int y = /* y 좌표 */;

    String key = String.format("%d, %d", x, y);
    map.put(map.getOrDefault(key, 0) + 1);
}

 

위 코드의 실행 시간은 0.3초, 아래 코드의 실행 시간은 1.8초로 어마어마한 성능 차이를 보였다.

 

어디서 이런 차이가 발생하는 걸까?

---

HashMap, HashSet 이해하기

많은 사람들이 HashMap이나 HashSet과 같이 해시라는 이름이 들어간 자료구조는 연산은 상수 시간 O(1)만에 한다고 생각하는 경향이 있다.

 

아니라는 것을 인지하고 있어도, 대부분 해시 충돌에 대해서만 신경쓴다.

 

하지만 HashMap과 HashSet을 사용할 때 가장 먼저 생각해 봐야 할 것은 해시 충돌이 아니다.

 

바로 키의 해시 코드를 어떻게 구하는 가이다.

 

이에 따라서 이 자료들에 대해서 알고 있는 시간 복잡도가 크게 바뀔 수 있기 때문이다.

연산 시간 복잡도

이 자료구조들은 내부적으로 키의 해시 코드를 이용하여 삽입, 삭제, 검색 등 연산을 수행한다.

 

이 연산들의 시간 복잡도는 일반적으로 O(1)을 기대할 수 있다.

 

문제는 해시 코드를 구할 때의 시간 복잡도이다.

 

해시를 활용하는 자료구조들은 자바의 Object 클래스에 선언된 hashCode() 메서드를 사용하여 해시를 구한다.

 

즉, hashCode()의 시간 복잡도가 이 자료구조들의 연산에 대한 시간 복잡도를 결정짓는 중요한 요소가 되는 것이다.

Integer::hashCode

위에서 첫 번째 코드는 키로 Integer를 사용하였다.

 

Integer의 hashCode()는 그 값 자체를 해시 값으로 사용할 수 있을 것 같다.

 

실제로 구글에 "java Integer implementation"이라고 검색하여 깃헙에 올라와있는 구현체를 살펴보면 다음과 같다.

@Override
public int hashCode() {
    return Integer.hashCode(value);
}

public static int hashCode(int value) {
    return value;
}

 

예상한 대로, 가지고 있는 값을 그대로 반환하여 상수 시간 안에 처리하게 된다.

 

이러한 경우 해시 충돌을 제외한다면 해시를 활용한 연산에 O(1)의 시간 복잡도를 기대할 수 있다.

String::hashCode

그렇다면 String의 시간 복잡도는 어떻게 될까?

 

직관적으로 생각해 보자.

 

문자열에 대한 해시 값을 생성하려면 문자열에 있는 모든 문자들을 순회하며 어떠한 처리를 해야 할 것 같다.

 

여기서부터 문자열의 hashCode()는 문자열의 길이 N에 비례하는 O(N)의 시간 복잡도가 걸릴 것 같다는 것을 의심할 수 있다.

 

구글에 "java String implementation"을 검색하여 이를 확인해 보자.

public int hashCode() {
    int h = hash;
    if (h == 0 && !hashIsZero) {
        h = isLatin1() ? StringLatin1.hashCode(value)
                       : StringUTF16.hashCode(value);
        if (h == 0) {
            hashIsZero = true;
        } else {
            hash = h;
        }
    }
    return h;
}

< String::hashCode 정의 >

 

라틴인지 여부에 따라 분기가 되어 다른 메서드로 해시 코드를 구한다.

 

더 일반적일 StringUTF16.hashCode()부터 쭉 따라가 보자.

public static int hashCode(byte[] value) {
    return ArraysSupport.hashCodeOfUTF16(value, 0, value.length >> 1, 0);
}

< StringUtf16::hashCode 정의 >

 public static int hashCodeOfUTF16(byte[] a, int fromIndex, int length, int initialValue) {
    return switch (length) {
        case 0 -> initialValue;
        case 1 -> 31 * initialValue + JLA.getUTF16Char(a, fromIndex);
        default -> vectorizedHashCode(a, fromIndex, length, initialValue, T_CHAR);
    };
}

< ArraysSupport::hashCodeOfUTF16 정의 >

@IntrinsicCandidate
private static int vectorizedHashCode(Object array, int fromIndex, int length, int initialValue,
                                      int basicType) {
    return switch (basicType) {
        case T_BOOLEAN -> unsignedHashCode(initialValue, (byte[]) array, fromIndex, length);
        case T_CHAR -> array instanceof byte[]
                ? utf16hashCode(initialValue, (byte[]) array, fromIndex, length)
                : hashCode(initialValue, (char[]) array, fromIndex, length);
        case T_BYTE -> hashCode(initialValue, (byte[]) array, fromIndex, length);
        case T_SHORT -> hashCode(initialValue, (short[]) array, fromIndex, length);
        case T_INT -> hashCode(initialValue, (int[]) array, fromIndex, length);
            default -> throw new IllegalArgumentException("unrecognized basic type: " + basicType);
    };
}

< ArraysSupport::vectorizedHashCode 정의>

private static int utf16hashCode(int result, byte[] value, int fromIndex, int length) {
    int end = fromIndex + length;
    for (int i = fromIndex; i < end; i++) {
        result = 31 * result + JLA.getUTF16Char(value, i);
    }
    return result;
}

< ArraysSupport::utf16hashCode 정의>

 

드디어 O(N)이 걸리는 부분이 등장했다.

 

utf16hashCode() 메서드는 fromIndex부터 fromIndex + length까지 반복을 돌며 O(length)만큼의 시간 복잡도를 갖는다.

 

처음부터 따라가 보면 이 length는 문자열의 길이가 되므로 String의 hashCode() 메서드는 O(N)이 걸리는 것을 실제로 확인할 수 있는 셈이다.

 

---

마무리

실제로 두 코드의 시간 차이를 보면 0.3초와 1.8초로 약 6배 차이가 난다.

 

이는 x, y에 두 자릿수 좌표값이 들어갔을 때 문자열의 길이가 6이 되는 것과 일치하는 증가량이다.

 

이렇게 해시 자료구조라고 하더라도 사용하는 자료형에 따라 상수 시간이 걸리지 않음을 확인할 수 있었다.

 

 

문제를 풀기 전 반드시 시간 복잡도를 계산하는 시간을 가져야 한다.

 

이때 해시를 구하는 시간 복잡도를 빼먹지 않도록 주의하자.