11년도에 EhCache를 쓸때 HashCodeCacheKeyGenerator 로 Cache Key를 생성했던적이 있다.

당시에 HashCodeCacheKeyGenerator 소스를 봐보니 @Cacheable 메소드 인자값들을 toString 하여 각 자리 char int에 31을 곱셈더함을 하면서 key를 만들어갔다.

당시엔 왜 31을 곱하는지 이해가 안됬지만. 자세히 보지도 않았다.

추억팔이.당시에 cacheKey 값이 중복발생되어 문제가 되는 상황이 있었는데.
원인은 파라미터값이 문제였다. 당시 "01", "02" 등 문자열과 숫자타입의 상품번호 등으로 키를 생성했는데.
타입="01" , 상품Id=10031
타입="02" , 상품Id=10000
31을 곱하는 알고리즘으로 두개의 데이터는 동일한 cacheKey를 뱉어냈다.
당시에는 케시를 적용한 전체 로직을 뒤져가며 파라미터를 손보기 힘들었기 때문에.
무지했을때라(지금도 크게 다르지 않음) 겨우 생각한 방법은 인자값들을 크기 순서로 정렬하여 처리하는 방법 이었다.인자값이 큰순서대로 정렬되어 처리되면 순차대로 처리되는 hash값이 크게 벌어져서 작은
타입코드 차이 보다도 훨씬 큰값으로 키가 생성되어 충돌을 방지할거란 생각이었다.
이슈가 될만한 데이터가 없어서 인지 이후로 충돌이 발생하지는 않았었다.

우연히 보게된 String hashCode 를 설명한 글에서 31을 사용한 이유를 찾았다.

<! — 여기서 부터 Naver D2 내용 >
String 객체에 대한 해시 함수 수행 시간은 문자열 길이에 비례한다.

때문에 JDK 1.1에서는 String 객체에 대해서 빠르게 해시 함수를 수행하기 위해, 일정 간격의 문자에 대한 해시를 누적한 값을 문자열에 대한 해시 함수로 사용했다.

예제 10 JDK 1.1에서의 String 클래스 해시 함수

public int hashCode() {  
int hash = 0;
int skip = Math.max(1, length() / 8);
for (int i = 0; i < length(): i+= skip)
hash = s[i] + (37 * hash);
return hash;
}

예제 10에서 볼 수 있듯이 모든 문자에 대한 해시 함수를 계산하는 게 아니라, 문자열의 길이가 16을 넘으면 최소 하나의 문자를 건너가며 해시 함수를 계산했다.

그러나 이런 방식은 심각한 문제를 야기했다. 웹상의 URL은 길이가 수십 글자에 이르면서 앞 부분은 동일하게 구성되는 경우가 많다. 이 경우 서로 다른 URL의 해시 값이 같아지는 빈도가 매우 높아질 수 있다는 문제가 있다. 따라서 이런 방식은 곧 폐기되었고, 예제 11에서 보는 방식을 현재의 Java 8까지도 계속 사용하고 있다.

예제 11 Java String 클래스 해시 함수

public int hashCode() {  
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}

예제 11은 Horner’s method를 구현한 것이다. Horner’s method는 다항식을 계산하기 쉽도록 단항식으로 이루어진 식으로 표현하는 것이다. 즉 예제 11에서 계산하고자 하는 해시 값 h는 다음과 같다.

Image for post
Image for post
Image for post
Image for post
Image for post
Image for post

이렇게 단항식을 재귀적으로 사용하여 다항식 연산을 표현할 수 있다.

String 객체 해시 함수에서 31을 사용하는 이유는, 31이 소수이며 또한 어떤 수에 31을 곱하는 것은 빠르게 계산할 수 있기 때문이다. 31N=32N-N인데, 32는 2의 5승 이니 어떤 수에 대한 32를 곱한 값은 shift 연산으로 쉽게 구현할 수 있다. 따라서 N에 31을 곱한 값은, (N << 5) — N과 같다. 31을 곱하는 연산은 이렇게 최적화된 머신 코드로 생성할 수 있기 때문에, String 클래스에서 해시 값을 계산할 때에는 31을 승수로 사용한다.
<! — 여기까지 Naver D2 내용 >

Modern VM 에서는 이런 최적화를 자동으로 수행한다고 한다.

정리하며 생각한 것은
세상에 알아서 좋을 건 너무나 많기 때문에 대충넘어가지 말고
찾아 읽어보기라도 하고 넘어가자는 것이다.

대충넘어가지말고, 찾아보고, Effective Java를 보자.
(기승전 Effective Java)

Written by

엘디는 사랑입니다.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store