HashSet 삽입 속도 개선

HashSet<T> 클래스

HashSet은 List처럼 데이터를 담는 콜렉션이지만 몇가지 차이점이 있다.

• 중복을 허용하지 않는다.
• 순서가 없다.

이 말은, HashSet에 데이터를 넣을 때 마다 중복 검사를 한다는 말이 된다. 또는 List를 HastSet으로 바꾸는 경우에도 중복 검사를 한다.

만약 1,000개 정도되는 속성을 가진 Person 클래스가 있다고 하자. HashSet<Person>에 데이터를 넣으려면 항상 1,000개의 속성에 대해 중복 검사를 하게되는데 심각한 낭비가 아닐 수 없다.

다행이 HastSet은 이렇게 무식하게 전부 비교하는게 아니라 이름에서 알 수 있다시피 HashCode를 이용해서 그룹으로 묶은 후 그룹끼리 다시 비교한다.

GetHashCode

HastSet에 데이터를 삽입하면, 먼저 GetHashCode로 해쉬코드 값을 가져오고 해쉬코드가 같은 객체가 없으면 새로운 객체로 판단하여 삽입한다. 해쉬코드가 같은 객체가 있는 경우엔 Equals로 객체를 비교한다.

GetHashCode의 기본구현은 객체의 일부 속성 값을 계산하여 반환하는데, 클래스 별로 GetHashCode를 재정의하여 더 효율적으로 사용할 수 있다.

Equals

해쉬코드가 같을 경우 두 객체를 어떻게 비교할지 재정의한다.

예제

예제 추가 예정

public struct Number
{
   private int n;

   public Number(int value)
   {
      n = value;
   }

   public int Value
   {
      get { return n; }
   }

   public override bool Equals(Object obj)
   {
      if (obj == null || ! (obj is Number))
         return false;
      else
         return n == ((Number) obj).n;
   }

   public override int GetHashCode()
   {
      return n;
   }

   public override string ToString()
   {
      return n.ToString();
   }
}

참고: MSDN GetHashCode 메소드, How does HashSet compare elements for equality?, System.ValueType의 GetHashCode 메서드