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

2008.11.18 21:50

hashcode, HashMap, Hashtable, java, string, TIP, 자바

네이버 카페 코드인에 심심해서 적어 놨던 글을 다시 옮겨옴.
( 워낙 포스팅이 없어서 ;; 요런걸로 때움. ㅋㅋㅋ )
-------
안녕하세요.
찬 입니다.

우리가 일반적으로 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 ) ) ; // 으악! 철수를 여자로 만들어 버렸어!!

put할때에는 key의 hashcode를 보고 쓰게 되어 있죠.
즉, "철수".hashCode() 값이 같기 때문에, 예전에 있던 값에다가 덮어써 버리게 됩니다.
( 정확하게 말하면, 원래의 Hash 개념으로는 hashCode가 같은 애들은 bucket에 저장됩니다. 덮어 써 버리지는 않습니다. 하지만 자바의 기본 구현에서는 Key의 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이 있을 수 있습니다.

그렇기 때문에,
HashMap이나 Hashtable를 사용할때 아무런 생각없이 String을 key으로 주고 쓰고 있습니다.
재수가 없으면 데이터가 날아 가는 문제가 발생할 수 있습니다.
( 또 다시 이야기 하자면, 데이터가 날아 가지는 않습니다. - 자세한 사항은 HashMap의 코드를 분석해 보세요~ )

그러므로 정말로 반드시 유일한 값이 필요하다고 한다면, hashCode()를 사용해서는 안될것입니다.
char[]을 일일이 가지고 와서 적당히 조작해서 int값으로 만드는 방법을 쓰던지 해야 할것입니다.
( 하지만, 위에서도 말했다시피 - int는 제한적이고 string은 무제한이므로, int를 가지고 어찌할 방법은 없습니다. )

2009년 8월 27일 추가 - 최근에 오래된 글에 대한 코멘트가 많이 달리네요. ㅎ.

지민아빠님의 코멘트처럼, 사실은 hashCode가 같다고 해서 꼭 문제가 되는것은 아닙니다.
이미 들어 있는 hashCode를 가진 key를 이용해서 put하면, return으로 이전에 들어 있던 Object가 나오거든요.

이 글에서 이야기 하고 싶은것은,
String.hashCode()는 유일한 값을 반환하지 않는다는 것입니다.
그러므로 이글 오해할 가능성이 있는 내용을 포함하고 있습니다.

잘 이해가 되지 않으시는 분들은 이 게시물에 cobus 님께서 달아 두신 comment를 참고하시면 이해가 되실 겁니다. ^_^

2011년 6월 23일 추가 -
오늘 또 어느 익명의 정의에 사도께서는 "이 딴 글은 내려버려라~" 고 적어 주셔서, 내용을 일부 수정합니다.

어흑. 진짜 글을 내려 버려야 하나.. 쩝ㅋㅋㅋ

공감

sns신고

'공부 > 컴퓨터' 카테고리의 다른 글

[Java/Tip] String.intern()은 메모리를 아낄 수 있다? (21)	2008.11.25
[Java/Tip] Hashtable을 제대로 활용하지 못하는 경우... (12)	2008.11.20
[Java/Tip] String.hashCode()는 유일한 값을 반환할까? (13)	2008.11.18
[Java/Tip] Specifc Debugging Tips for Swing - 4.2.1 Incorrect Threading (2)	2008.11.05
Character에서 나오는 hanzi, kanji 는 뭥미? (2)	2008.09.03
[책읽기] 테스트 주도 개발 - 켄트백 지음, 김창준 강규영 옮김. (2)	2008.03.03

지민아빠 2008.11.19 00:40 신고

hashcode 는 같은 값이 나오지만, 그래서 equals 도 같이 사용하는 거잖아요. 내부적으로는 그래서 예비 버킷이 있는.... 흠. 암튼. 유용한 글.. 좋아요. ㅎㅎ

# Delete Reply
- Chan 2008.11.19 00:47 신고
  
  크크. 너무 예리하세요~ ^^
  
  # Delete
- 쇼니 2008.11.19 10:25 신고
  
  그니깐여..ㅎ
  
  # Delete
쓩 2009.08.27 12:41 신고

해쉬가 같으면 같은 빠겟스에 담는다는거고...
빠겟스 수는 적절하게 조절되어질테고~

결론이 좀....ㅋㅋㅋ

여튼 잘봤음

# Delete Reply
- Chan 2009.08.27 13:50 신고
  
  우왕~
  요즘에 오래된 글에 많은 사람들이 코멘트를 남겨주시네~ ㅎㅎ
  위의 글은 제대로 오해할 소지가 많지~ ㅎㅎ
  하지만, 고치긴 귀찮아. ㅋㅋ
  
  # Delete
분홍 2010.10.11 17:04 신고

잘봤습니다. hashcode 의 문제점을 아주 잘 파악한 좋은글이네요...

# Delete Reply
- Chan 2010.10.11 22:21 신고
  
  방문 고맙습니다.
  
  # Delete
흠.. 2011.06.20 18:34 신고

오해할 소지가 있는 글이 아니고
아예 개념을 잘 모르고 쓴 글이네요...

아직도 안지우고 냅두고 있다는 것이 신기합니다..
나는 바로 내릴 것 같은데..

# Delete Reply
- Chan 2011.06.23 18:24 신고
  
  허허.
  이렇게 오래 된 글을 찾아 주셔서 감사합니다.
  아무래도 내용을 수정해야 겠군요. ^^
  
  # Delete
지나가다 2013.08.29 01:55 신고

해쉬코드는 문자열에 유일합니다.
char val[] = value;

for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
위가 hashCode() 소스입니다.
value는 해싱할 문자열이고
각 글자자릿수의 지수승을 해서 각 문자의 ASCII코드를 더합니다.
abc 를 입력하면 96354이 나옵니다.

# Delete Reply
- 찬 2013.10.23 20:57 신고
  
  바로 위 "지나가다"님의 코멘트는 잘못 된 내용입니다.
  문자열이 달라도 같은 hashCode가 나올 수 있습니다.
  
  그 이유는 위의 글에 나와 있습니다.
  
  # Delete
cobus 2015.11.27 11:10 신고

글 내용을 잘 이해를 못하신건지 아니면 .hashCode()를 맹신하시는건지...
본문에 String class의 hashCode() 를 사용했을 때 같은 값이 나오는 예제를 추가하면 논란이 없을 것 같습니다.

약간 수정되어야 할 부분은 hashCode() 값이 중복될 수 있는 이유를 int의 수와 String의 표현 가능 수가 차이가 나서 중복이 생길 수 있다고 하셨는데 사실은 ASCII code값을 이용해 비트연산의 합으로 hash값을 만들다보니 길이와 상관없이 Hash값 중복이 발생할 수 있습니다. 본문에 추가하면 좋을것 같은 hashCode() 중복 문자열은 아래와 같습니다.

String a = "Z@S.ME";
String b = "Z@RN.E";
if(a.hashCode() == b.hashCode()) {
System.out.println("same hashcode");
} else {
System.out.println("different hashcode");
}

결과: same hashcode

# Delete Reply
- 찬 2015.12.15 19:41 신고
  
  cobus님 //
  댓글 감사합니다. ^_^
  
  저희 의도는 int의 표현 가능 갯수보다 String은 표현가능 갯수가 더 많기 때문에
  String을 int로 mapping 시킨다면 당연히, int 값이 겹치는 경우가 발생할 수 밖에 없다라는 의미로 적었습니다. ( 원론적인건 코드가 필요 없으니까요 ^_^ )
  
  제가 그 의미를 정확하게 표현하지 못했네요 ^_^
  
  이 글을 읽으시는 분이 코멘트 남겨 주신 내용을 읽으시면,
  훨씬 더 잘 이해할 수 있을것으로 보입니다. ^_^
  자세한 설명과 구체적인 예를 들어 코멘트 남겨 주셔서 고맙습니다. ^_^
  
  해당 글에, cobus 님의 코멘트를 확인하라는 내용을 추가 했습니다. ^_^
  
  # Delete

PREV 1 ···18 19 20 21 22 23 24 25 26 ···211 NEXT

Chan != *