[Java/Tip] String.hashCode()는 유일한 값을 반환할까?

요즘에도 댓글이 달려, 내용을 좀 다듬었습니다. HashMap 내부 소개와 더불어 hashCode()에 대한 설명을 하려다보니 내용에 혼돈이 있었습니다. 해당 내용은 Java7 을 기준으로 작성된 내용입니다. Java 8부터는 내부 구현이 바뀌었을겁니다.

----------
안녕하세요.
 찬 입니다.

 

hashCode()는 어디에 사용할까요?

우리가 일반적으로 Map이나 HashTable을 쓸때 다음과 같이 사용하지요.

Map map = new HashMap(100);
map.put("찬", new Person( Person.MEN, 29 ) );
map.put("철수", new Person( Person.MEN, 15) );
map.put("영희", new Person( Person.WOMAN , 13 ) );

이때 map에
key로 "찬", "철수", "영희" 와 같이 String을 주고,
value로는 Person 객체를 만들어서 넣어 줍니다.

이때,
map에서는 key 값이 중복되면 기존에 있던 value에다가 새로운 value를 덮어 써 버리게 되는 것처럼 보입니다.

map.put("찬", new Person( Person.MEN, 29 ) );
map.put("철수", new Person( Person.MEN, 15) );
map.put("영희", new Person( Person.WOMAN , 13 ) );
map.put("철수", new Person( Person.WOMAN, 15 ) ) ;  // 으악! 철수를 여자로 만들어 버렸어!!

이 때 HashMap은 기존에 있던 "철수"를, 찾아서 어떻게 새 "철수"로 덮어쓰게 될까요?

HashMap 내부에서는 hashCode()를 사용하여 기존의 "철수"를 찾게 됩니다. 바로 이런곳이 hashCode를 사용하는 대표적인 예입니다.

오래전에 대충 정리해둔 글이 논란이 되니, 잘못된곳을 바로잡고 정리합니다.

더 정확히 HashMap의 구현을 설명드리면 key의 hashCode뿐만 아니라, 기존에 존재하던 key들의 equals()까지 검사해서, 그것까지도 동일하다면 덮어쓰게 됩니다. 그러므로 위 예제에서는 equals() 까지 동일하므로, 기존의 "철수"정보를 반환하고, 새 "철수" 정보를 넣게 됩니다.

만약 hashCode() 값이 동일한 "key"라고 해도 실제 내용이 달라 equals()가 false가 나오면 덮어쓰지 않습니다.

물론, get을 수행할때도 hashCode 값 이외에, 실제로 key의 equals가 동일한지 보고 반환하도록 되어 있습니다.

다시 원래 이야기 하려던 String.hashCode()는 유일한 값을 반환할까로...

그렇다면 String의 hashCode()에 대해서 좀 알아 봅시다. 아래는 String의 hashCode()에 대한 API문서 내용입니다.

hashCode

public int hashCode()

Returns a hashcode for this string. The hashcode for a String object is computed as

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

using int arithmetic, where s[i] is the ith character of the string, n is the length of the string, and ^ indicates exponentiation. (The hash value of the empty string is zero.)

Overrides:

hashCode in class Object

Returns:

a hash code value for this object.

 

보다시피 String의 hashCode()는 "s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]" 요런 공식에 의해서
값이 반환되게 되어 있는데요, 공식이 무진장 어렵죠. 무슨 말인지도 잘 모르겠고..

공식보다는

hashCode()의 반환값

에 대해서 이야기 해 보죠.
hashCode()의 반환값은

int

입니다. String 객체의 hashCode()를 가지고 오면 int형태를 반환하게 되죠.


자, 그럼 다시 생각해 봅시다.

int는 총 4byte

를 차지할 수 있는 정수형 기본 타입입니다.
4byte로 표현할 수 있는 갯수는

0부터 0xFFFFFFFF(4,294,967,295)

입니다.
즉,

hashCode()의 결과는 그 많은 int값 중에서  하나를 반환

됩니다.


그렇다면 또 다시 String의 hashCode를 생각해 봅시다.

하지만

String은 무한개라고 표현할 수 있을정도의 문자열을 생성해 낼 수 있습니다.

( "A", "A1",..."AZ", "AA1", "ZZ....ZZZ", "가1A" .... 등등 )
그런데, 이렇게 많이 생성해 낼 수 있는 String 객체의 hash code는

int가 반환할 수 있는 숫자중에 하나 

입니다.

그러므로 확률상 서로 다른 String 인데도, 같은 hashcode를 가지는 String이 있을 수 있습니다.