String 의 hashcode

mongBrown·2026년 4월 18일

String의 hashCode는 왜 이런 구현인가

"hello".hashCode()를 백 번 호출하면 백 번 모두 같은 값이 나온다. 당연한 것처럼 보이지만, 이 당연함 뒤에는 꽤 구체적인 설계 결정들이 있다.

String은 불변 객체다. 한 번 만들어지면 내부 문자열이 절대 바뀌지 않는다. 그래서 hashCode를 계산하면 결과가 항상 같다.

매번 계산하는 건 낭비다. 그래서 처음 호출 시 계산한 값을 hash 필드에 저장해두고, 이후 호출에서는 저장된 값을 바로 반환한다.

멀티스레드에서 두 스레드가 동시에 hashCode()를 호출해 둘 다 계산하더라도, 결과가 항상 같기 때문에 어떤 값이 저장되든 상관없다. synchronized 없이도 안전하다.

hash 필드의 초기값은 0이다. 여기서 문제가 생긴다.

실제 해시값이 0인 String이 존재한다면, "아직 계산 안 됨(초기값 0)"과 "계산했는데 결과가 0"을 구분할 수 없다. 구분하지 못하면 실제 해시값이 0인 String을 호출할 때마다 재계산하게 된다.

이를 해결하기 위해 hashIsZero 플래그를 별도로 둔다.

hash == 0, hashIsZero == false  →  아직 계산 안 됨  →  계산 후 저장
hash == 0, hashIsZero == true   →  실제 해시값이 0  →  0 반환

hashCode의 반환 타입은 int다. int는 음수까지 포함해 약 42억(2^32) 가지 값만 표현할 수 있다. 세상에 만들 수 있는 String의 종류는 무한하기 때문에, 저장하는 String이 42억 개를 넘으면 충돌은 수학적으로 피할 수 없다.

그래서 설계의 목표는 "충돌을 없애는 것"이 아니라 "충돌을 최대한 줄이는 것"이다.

충돌을 줄이려면 서로 다른 String이 최대한 다른 해시값을 가져야 한다. 특히 같은 문자로 이루어진 "abc"와 "bac"처럼 순서만 다른 경우도 구분할 수 있어야 한다.

이를 위해 각 문자에 위치마다 다른 가중치를 곱하는 방식을 쓴다.

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

이 방식을 다항식 롤링 해시라 부른다. 앞쪽 문자일수록 31의 더 높은 거듭제곱이 곱해져 가중치가 커진다.

"abc"를 예시로 보면 이렇다. 각 문자의 유니코드 값은 a=97, b=98, c=99다.

'a' * 31^2  +  'b' * 31^1  +  'c' * 31^0
= 97 * 961  +  98 * 31     +  99 * 1
= 93217     +  3038        +  99
= 96354

실제로 "abc".hashCode()를 호출하면 96354가 반환된다.

계산 과정에서 int 범위(약 42억)를 넘으면 어떻게 되는가. 명시적으로 나누거나 나머지를 취하지 않는다. Java는 그냥 int 오버플로우를 활용한다. 범위를 넘으면 자동으로 음수로 돌아가는 방식이다. 그래서 hashCode()는 음수 값도 반환할 수 있다.

31을 선택한 이유는 두 가지다. 소수이기 때문에 충돌 확률이 낮고, 31 * n == (n << 5) - n으로 비트 시프트 연산으로 치환할 수 있어 CPU 연산 속도가 빠르다.

앞쪽 문자의 가중치가 압도적으로 크다는 게 역으로 약점이 된다. 뒤쪽 수백 글자가 달라도 앞 몇 글자가 같으면 해시 충돌 가능성이 높아진다.

https://www.으로 시작하는 URL이 수없이 많다면, 이들이 같은 버킷에 몰려 HashMap 탐색 성능이 떨어질 수 있다. 긴 문자열을 HashMap 키로 자주 쓰는 상황에서는 이 점을 염두에 두어야 한다.

화이팅!