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

우리가 일반적으로 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일 추가 -
오늘 또 어느 익명의 정의에 사도께서는 "이 딴 글은 내려버려라~" 고 적어 주셔서, 내용을 일부 수정합니다.
 
어흑. 진짜 글을 내려 버려야 하나.. 쩝ㅋㅋㅋ


신고
크리에이티브 커먼즈 라이선스
Creative Commons License
  1. 지민아빠 2008.11.19 00:40 신고

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

  2. 2009.08.27 12:41 신고

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

    결론이 좀....ㅋㅋㅋ

    여튼 잘봤음

    • Chan 2009.08.27 13:50 신고

      우왕~
      요즘에 오래된 글에 많은 사람들이 코멘트를 남겨주시네~ ㅎㅎ
      위의 글은 제대로 오해할 소지가 많지~ ㅎㅎ
      하지만, 고치긴 귀찮아. ㅋㅋ

  3. 분홍 2010.10.11 17:04 신고

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

  4. 흠.. 2011.06.20 18:34 신고

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

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

    • Chan 2011.06.23 18:24 신고

      허허.
      이렇게 오래 된 글을 찾아 주셔서 감사합니다.
      아무래도 내용을 수정해야 겠군요. ^^

  5. 지나가다 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이 나옵니다.

    • 2013.10.23 20:57 신고

      바로 위 "지나가다"님의 코멘트는 잘못 된 내용입니다.
      문자열이 달라도 같은 hashCode가 나올 수 있습니다.

      그 이유는 위의 글에 나와 있습니다.

  6. 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

    • 2015.12.15 19:41 신고

      cobus님 //
      댓글 감사합니다. ^_^

      저희 의도는 int의 표현 가능 갯수보다 String은 표현가능 갯수가 더 많기 때문에
      String을 int로 mapping 시킨다면 당연히, int 값이 겹치는 경우가 발생할 수 밖에 없다라는 의미로 적었습니다. ( 원론적인건 코드가 필요 없으니까요 ^_^ )

      제가 그 의미를 정확하게 표현하지 못했네요 ^_^

      이 글을 읽으시는 분이 코멘트 남겨 주신 내용을 읽으시면,
      훨씬 더 잘 이해할 수 있을것으로 보입니다. ^_^
      자세한 설명과 구체적인 예를 들어 코멘트 남겨 주셔서 고맙습니다. ^_^

      해당 글에, cobus 님의 코멘트를 확인하라는 내용을 추가 했습니다. ^_^

일을 하다가 발견한 문제이다.

특정한 동작을 하는것이 있었는데..
이 놈이 유독스럽게 Mac 에서만 무진장 오래 걸린다는 문제 였다.

윈도우에서는 단 1초도 안되어서 끝나는 작업이었지만,
Mac 에서만 22초가 소요되고 있었다.

문제가 어디서 발생하는지는 찾았는데,
왜 Mac 에서만 유독 느린지 이유를 밝혀 내지는 못했다.


여하튼, 문제는 ArrayList의 removeAll 메소드에 있었다.
removeAll 메소드에 대해서 좀 살펴 보자.



ArrayList 의 상속 관계를 보면 아래와 같다.

사용자 삽입 이미지



여기서 removeAll 이라는 메소드는 Collection 에서 interface를 제공하고 있으며,
실제 그 구현은 AbstractCollection 에 아래와 같이 되어 있다.

사용자 삽입 이미지


보다시피 현재의 컬렉션에서 param 으로 들어온 컬렉션에 있는 item들을 모두 지우기 위해서
iterator 를 구하고, next를 하나꺼내와서
param으로 들어온 c 에 이미 들어 있는지 확인을 하고,
들어 있다면 지워주는 형태로 되어 있다.


여기서 다시 "c에 이미 들어 있는지 확인하는 c.contains( .. ) 의 코드는
indexOf(Object)가 0 보다 큰지 확인하게 된다.
이때 ArrayList의 indexOf(Object) 는 아래와 같이 구현되어 있다.

사용자 삽입 이미지

열심히 이미 가지고 있는 배열에서 루프를 돌면서 같은 놈이 있는지 확인을 한다.
물론 이 놈들이 Object 형태를 비교해야 하기 때문에 equals() 메소드를 사용하여서
비교를 한다.


그렇다면 내가 원래 있던 20개의 Collection 에서
10개의 데이터를 removeAll 한다고 해 보자.

1. AbstractCollection의 removeAll을 호출한다.
2. 20개에 대해서 iterator 를 구해서 20번 루프를 돌아야 한다.
2.1. 현재 선택되어 있는 아이템이 10개에 포함되어 있는지 확인해야 한다.
2.2. 이것을 확인하기 위해서는 indexOf() 를 수행해야 한다.
2.3. indexOf 내부에서는 10개에 대해서 루프를 돌아야 한다.
2.4. Object 비교이기 때문에 equals 를 수행하기 위해서 내부적인 연산을 해야 한다.


중요한것은 전체 배열에 대해서 이중 for loop 를 돌아서 처리 한다는것이다.




그렇다면 이 loop를 좀 더 덜 돌릴 수 있는 방향이 없을까?
항상 cpu 와 memory 사이에는 trade-off 가 있다.
물론 지금 이야기 하고자 하는 방법은 memory 측면에서는 손해 볼 수 있다.




내가 그래서 선택한 방법은 HashMap을 사용하는 방법이다.
안타깝게도 HashMap 에서는 removeAll 같은 메소드를 제공해주지 않기 때문에.
직접 for 루프를 돌아 가면서 데이터를 지워주어야 하는 귀찮은 점은 있다.

HashMap의 remove(Object) 코드는 아래와 같이 구성되어 있다.

사용자 삽입 이미지


remove(Object)를 수행하게 되면 removeEntryForKey(Object)를 수행하게 된다.

이때 removeEntryForKey(Object) 에서는
param으로 들어온 key에 대해서 hashCode() 를 구하고,
전체 배열 중에서 구해진 hash와 같은 값을 가지는 위치만을 비교 하게 된다.


그렇다면 HaspMap 에서 데이터를 지우는 순서를 보자.

1. removeAll이 없기 때문에 어쩔 수 없이 외부에서 for를 돌려서 remove 를 여러번 시켜 준다.
2. hashCode() 값을 구하고, hash 같은 배열 부분만을 검색한다.
3. equals()를 호출하여 비교하면서 처리 한다.

여기서도 사용자가 for를 외부에서 돌려 주고,
내부에서도 while loop를 도는 2중 loop 구조이기는 하지만,
hash 가 같은것만 돈다는것이 핵심이다.


이 결과는 equals()과 hashCode()를 구현하는 방식에 따라서 다른 결과를 도출할 수도 있다.



약 400개의 데이터에 대한 작업이었는데
ArrayList.removeAll()에서는 22 초가 걸렸었고,
HashMap.remove() + for 로 수정한 뒤에는 0.5 초대의 시간이 걸렸다.


이 결과는 Mac 에서만 유용할 수도 있다. 실제 윈도우에서도 약간 더 빨리 동작하기는 했다.
시간 날때  똑같은 코드가 왜 Mac 에서만 이렇게 느리게 동작하는가에 대한 조사를 해 보아야 겠다.


대학교 자료구조 수업 시간에 자주 등장하는 내용이지만,
실제로 이렇게 -_- 겁나게 차이를 느껴 보기는 처음이었다. -_-;


대학교때 공부 잘했던 사람들이 나와서도 잘 사는 이유가 있나 보다. ㅋㅋ
신고
크리에이티브 커먼즈 라이선스
Creative Commons License
  1. 유야 2007.06.10 00:30 신고

    역시 난 제대로 디버깅한거였어!!!!
    Font의 canDiaplay도 무쟈게 느리더만 -_-

    • Chan 2007.06.10 01:18 신고

      대단해. ㅋㅋ.
      근데 -_- 왜 느릴까 -_-? 쩝쩝쩝..

  2. 옷장수 2007.06.10 12:55 신고

    Font의 canDisplay()가 느린이유는 char를 glyph으로 변환하는 과정을 거치기 때문이 아닐런지..

    • Chan 2007.06.10 21:27 신고

      ㅇㅎㅎ ;; 뭔 말인지 몰겠따.. ㅎㅎ ;;;

  3. 유겸애비 2007.06.11 11:40 신고

    이거 맥하고 상관이 없는글이자나욧!!
    글구 canDisplay()는 글립으로 만들지 않고 그냥 폰트에 어떤 문자가 정의되어있는지를 보는것일듯 싶네요

    • Chan 2007.06.11 18:17 신고

      수정했습니다. ㅋㅋ;;
      그리고 ;; 또 어려운 말들을 하시는군요.;; ㅎㅎ ;;

    • 옷장수 2007.06.12 09:39 신고

      오랜만에 보는거라서 소스를 봤었는데 canDisplay가 호출되면 CharToGlyphMapper라는 놈을 찾아서 여기에서 glyph이 보여질 수 있는지를 체크하던데요.

  4. 유겸애비 2007.06.12 19:16 신고

    Re:옷장수// Font란 char to glyph의 map이라고 추상화 시킬수 있는데 key가 정의되어있난 보는거지 char에서 glyph으로 변환을 시키는건 아닐껍니다.

    • Chan 2007.06.12 23:36 신고

      심도 있는 댓글이군요~ ㅋ
      찾아봐야 겠당~ ㅋㅋ

    • 옷장수 2007.06.14 14:03 신고

      음.. char를 glyph으로 변환한다는게.. char 값을 glyph의 index 값으로 변환한다는 의미였는데요.

+ Recent posts