Dictionary.Get(A) 대신 Dictionary.Get(A.GetHashCode())를 사용해서는 안 되는 이유
최근에 "Jeffrey Richter"가 쓴 "
CLR via C#" (송기수 MVP 님이 번역하신 바로 그 책! 3rd edition이 새롭게 나왔다는 데 이번에도 송기수 님이 번역하셨으면 좋겠습니다. ^^) 책을 보다가 다음과 같은 문구가 들어왔습니다.
"
System.ValueType의 GetHashCode 메서드는 내부적으로 리플렉션과 인스턴스 필드들 중 일부 필드의 값을 XOR 연산을 사용하여 구하도록 되어 있다.
"
위와 같이 언급하기 이전에 GetHashCode에 대한 코드 예제를 하나 제공하고 있는데요. 아래와 같습니다.
internal sealed class Point
{
private Int32 m_x, m_y;
public override Int32 GetHashCode()
{
return m_x ^ m_y;
}
...
}
위의 코드는 "참조" 타입이라는 점이 다르고, 또한 CLR에서 System.ValueType의 GetHashCode를 위와 같이 구현되어 있다는 식의 이야기는 없었습니다. 그런데... 여기서 문득 호기심이 생기더군요. ^^ 정말 CLR에서도 위와 같이 구현했을까?
간단한 테스트를 해보면 알 수 있는 문제였습니다. 위에서 제시된 Point.GetHashCode의 구현을 보면 한가지 오류를 직관적으로 발견할 수 있습니다. 즉, m_x와 m_y 값이 서로 바뀐 상태라고 해도 같은 해시 코드값이 나온다는 점입니다. 어떤 구현에서는 값이 바뀌어도 크게 문제가 없을 수도 있지만 분명 문제가 되는 경우도 많습니다. 예를 들자면,
struct GeoLocation
{
public int Latitude; // 편의상 int로 정의
public int Longitude;
}
명확하지요. ^^ 지리 좌표가 앞 뒤 값이 바뀌는 것은 용서가 안되는 경우입니다.
자, 그럼 CLR이 정말 단순히 값형식의 경우에 필드값을 XOR해서 구한 것일까요?
GeoLocation t = new GeoLocation();
t.Latitude = 5;
t.Longitude = 6;
int hash1 = t.GetHashCode(); // 결괏값: 373079212 (CLR 2.0 기준)
int hash2 = (int)t.Latitude ^ (int)t.Longitude; // 결괏값: 3
아하... 꼭 그렇지는 않군요. 어떤 다른 변수가 있는 것 같습니다. 일단 그것까지는 관심이 없고.
이제 필드의 값 순서를 바꿔서 해시를 구해볼까요?
GeoLocation t1 = new GeoLocation();
t1.Latitude = 5;
t1.Longitude = 6;
GeoLocation t2 = new GeoLocation();
t2.Latitude = 6;
t2.Longitude = 5;
int hash1 = t1.GetHashCode(); // 결괏값: 373079212
int hash2 = t2.GetHashCode(); // 결괏값: 373079212
이런 ... ^^ 값이 같습니다.
여기서 갑자기 의문이 생겼습니다. GetHashCode를 직접적으로 사용하는 Hashtable과 같은 타입은 키가 같은 데이터가 2번 Add되지 못하도록 합니다. 실제로 아래와 같은 코드는 System.ArgumentException 예외가 발생합니다.
var dict = new Hashtable();
dict.Add(t1, 1);
dict.Add(t1, 2); // System.ArgumentException 예외 발생
그렇다면 다음의 구문도 예외가 발생할까요?
var dict = new Hashtable();
dict.Add(t1, 1); // t1.GetHashCode == 373079212
dict.Add(t2, 2); // t2.GetHashCode == 373079212
발생하지 않습니다. 이유는? Hashtable.Insert 메서드를 검사해 보니 GetHashCode 값이 같은 경우에 한해서 이전에 있던 데이터와 새로운 데이터의 Equals 메서드를 호출해서 값이 같은지를 비교하는 코드가 더 추가되어 있었습니다. 즉, t1과 t2가 같지 않으니 해시값은 같지만 인정하고 포함을 시켜주는 것입니다.
확인을 위해 GeoLocation의 Equals 메서드를 다음과 같이 재정의하면, 여지없이 예외가 발생합니다.
struct GeoLocation
{
public override bool Equals(object obj)
{
return obj.GetHashCode() == this.GetHashCode();
}
}
var dict = new Hashtable();
dict.Add(t1, 1); // t1.GetHashCode == 373079212
dict.Add(t2, 2); // t2.GetHashCode == 373079212 // System.ArgumentException 예외 발생
그럼, 제목에서 제시한 이유가 명확해 졌습니다. 위와 같은 이유 때문에, GetHashCode를 Dictionary 타입에 전달할 키로 사용해서는 안되는 것입니다. 사실, 그동안 무심코 써왔던 GetHashCode인데... 이제는 좀 상황을 가려가면서 써야 겠습니다. ^^
그건 그렇고.
그렇다면, 위와 같은 경우에 유일성을 보장하기 위해서 어떻게 GetHashCode를 재정의하는 것이 좋을까요?
애석하게도 이 질문은 잘못되었습니다. "유일성을 보장"하는 것은 욕심이고, "가능한 유일성을 보장"하는 것이 맞습니다. 다들 아시는 것처럼 다양한 정보를 가진 개체가 단지 4byte의 정수값으로 유일성을 보장받는다는 것은 애당초 불가능합니다. 단적으로 아무리 이상적으로 Hash 값을 구하는 경우라 하더라도 UInt32.MaxValue를 넘게 포함하는 데이터에는 무조건 중복이 될 수밖에 없습니다.
즉, 충돌을 감안해야 하고 대신에 이를 해결하기 위해 Equals만 제대로 정의해주면 Hashtable 등의 Dictionary 타입을 사용하는 데에는 (충돌된 해시값을 가진 데이터 검색 시간으로 속도저하가 될 지언정) 문제가 되지 않습니다. 나아가서, 여러분들이 임의로 Hashtable 등의 타입을 만들어준다면 해당 데이터의 GetHashCode만을 사용해서는 안되고 반드시 Equals 검증을 거쳐서 해시값 충돌을 해결해 줘야 합니다.
그래도, 가능하면 충돌을 적게 하는 것이 좋겠지요. ^^
이것은 GetHashCode 계산을 해야하는 값의 업무 도메인 영역마다 틀릴 수 있는 문제입니다. 만약 필드의 앞/뒤값이 틀린 것에 대해서 서로 다른 해시값을 사용하고 싶다면 다음과 같은 식으로 필드마다 일정한 SHIFT 연산을 한 후 XOR 연산을 하는 것도 방법일 수 있습니다.
Make Types Hashable with GetHashCode()
; http://www.c-sharpcorner.com/uploadfile/freebookarticles/samspublishing/2010mar24003215am/VersatileTypes/5.aspx
위의 방법도 사실 정답이 아닐 수 있는데, 오히려 비트 연산하기 전에는 충돌이 안 나던 "경우의 수"가 이제는 충돌이 발생할 수 있기 때문입니다. 다시 원점으로 돌아가서, 그냥 충돌은 인정하고 Equals를 기대하는 것이 맞습니다. 물론, 시간적인 여유가 된다면 가능한 적게 충돌이 나도록 적절한 알고리즘을 업무 도메인 영역에서 충분한 테스트를 거친 후 선택할 수 있다면 좋은 정도겠죠!
[이 토픽에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]