왜 이런 이야기를 하는 걸까? 일반적으로 딕셔너리의 키 검색 성능은 O(1)이지만, 연결 리스트의 검색 오버헤드는 O(N)이기 때문이다. 즉, 중복 횟수가 증가하면 검색 성능이 저하된다. 예를 들어 항상 4를 반환하는 GetHashCode 함수가 있다고 가정해 보자.²

public override int GetHashCode() {
    return 4; // 주사위를 던져서 얻은 숫자
}

이 경우 새로운 항목을 추가할 때 딕셔너리의 내부 구조는 그림 2-9와 같다.

▲ 그림 2-9 GetHashCode( )를 엉망으로 만들 때의 딕셔너리