C \ # 해시 표 로 대상 검색

C \ # 해시 표 검색 대상 작성 자: Bill Wagner
소스 코드 다운로드
. NET Framework 의 대부분의 용 기 는 시퀀스 용기 (sequence containers) 입 니 다. 순서대로 대상 을 저장 합 니 다.이런 종류의 용 기 는 기능 이 매우 많다. 너 는 어떤 특수 한 순서 로 든 임의의 수량의 대상 을 저장 할 수 있다.그러나 이런 다기 능 성 은 일정한 성능 을 대가 로 한다.하나의 시퀀스 에서 특수 한 대상 을 찾 는 데 필요 한 시간 은 용기 의 대상 수량 에 달 려 있다.만약 우리 가 용기 에 있 는 요 소 를 정렬 하지 않 았 다 면 요소 의 수량 이 증가 함 에 따라 당신 이 필요 로 하 는 검색 시간 도 직선 으로 증가 할 것 입 니 다. 용기 에 있 는 요소 의 수량 이 배로 증가 하면 특수 요 소 를 찾 는 시간 도 배로 증가 할 것 입 니 다.그러나 만약 에 우리 가 용기 에 있 는 요 소 를 정렬 했다 면 찾 는 시간 은 요소 의 수량 에 따라 증가 하 는 것 입 니 다. 원 소 를 찾 는 시간 을 배로 늘 리 려 면 집합 에 있 는 요소 의 수량 을 4 배로 늘 려 야 합 니 다.키 로 대상 을 검색 하면 시퀀스 용기 보다 더 좋 은 방법 으로 대상 을 저장 할 수 있 습 니 다.너 는 해시 표 (hash table) 를 사용 할 수 있다.해시 표 는 hash 라 는 디지털 키워드 (key) 에 따라 대상 을 buckets 에 저장 합 니 다.hash value 는 대상 의 값 으로 계 산 된 숫자 입 니 다.각각 다른 hash value 는 새로운 bucket 을 만 듭 니 다.대상 을 찾 으 려 면 이 대상 의 hash value 를 계산 하고 해당 하 는 bucket 을 검색 하면 됩 니 다.해당 버 킷 을 빠르게 찾 으 면 검색 대상 수 를 줄 일 수 있 습 니 다.예 를 들 어 하나의 데이터 구조 에서 일부 고객 기록 이 있다 고 생각 하고 신용카드 번 호 를 통 해 그 기록 을 검색 하고 싶 습 니 다.간단 한 해시 함 수 는 신용카드 번호 의 뒷 두 자리 숫자 를 사용 합 니 다. 이것 은 100 개의 buckets 를 형성 합 니 다. 00 에서 99 까지 두 자리 수의 숫자 마다 하나의 bucket 을 만 듭 니 다.(마찬가지 로 세 자리 숫자 를 사용 하면 1000 개의 buckets 를 만 들 수 있 습 니 다.) 하나의 bucket 만 조회 하면 모든 buckets 를 조회 하지 않 고 기록 을 찾 을 수 있 습 니 다.그러나 어떤 일과 마찬가지 로 모든 것 이 이렇게 간단 한 것 은 아니다.만약 당신 이 신용카드 번호 로 해시 함 수 를 만 들 었 다 면, 당신 은 이름 을 통 해 고객 을 찾 으 려 면 전체 해시 표를 조회 해 야 합 니 다. 그러면 많은 시간 이 걸 릴 것 입 니 다.이것 은 해시 표 가 다른 필드 를 키 로 하기 때문이다.그리고 만약 당신 이 전체 해시 표를 조회 한다 면 요 소 는 당신 이 원 하 는 순서에 따라 배열 할 필요 가 없습니다.요 소 는 키 에 따라 배열 되 는 것 이 아니 라 hash value 에 따라 배열 된다.이 글 에서 나 는 내 가 앞의 글 ('더 좋 은 집합 을 위 한 클래스 만 들 기') 에서 의 사례 를 상세 하 게 서술 하여 직원 기록 을 수정 하 게 할 것 이다.만약 에 큰 회사 가 있다 고 가정 하면 회사 에 수천 명의 직원 이 있 는데 가장 빠 른 방법 으로 기록 을 찾 고 싶 습 니 다.모든 직원 의 해시 표 는 검색 을 가장 짧 은 시간 에 끝 낼 수 있다.해시 함 수 는 일정한 속성 이 필요 합 니 다.초보 자 에 게 해시 함 수 는 변 하지 않 아야 한다.같은 키 는 같은 hash value 를 만들어 야 하 며, 대상 을 만 들 면 hash value 를 바 꿀 수 없다 는 것 이다.hash value 가 바 뀌 면 해시 표 에서 더 이상 대상 을 찾 을 수 없습니다.해시 함수 에 필요 한 두 번 째 속성 은 buckets 를 평균 적 으로 분배 할 수 있 는 것 입 니 다.모든 대상 이 같은 hash value 를 생 성 한다 면 특별한 대상 을 찾 는 데 더 많은 시간 이 필요 합 니 다.실제로 이 두 가지 원칙 은 따 르 기 쉽다.. NET Framework 에는 178 개의 클래스 가 GetHashCode () 를 다시 불 러 와 그들의 역할 을 더욱 잘 발휘 한다.모든. NET FCL (Framework Class Library) 에서 클래스 의 실현 은 hash value 의 더 좋 은 분 배 를 확보 하고 유일한 원칙 을 따 랐 다.GetHashCode () 방법 을 다시 불 러 올 필요 가 있 는 지 확인 해 야 합 니 다.가장 간단 한 (보통 가장 좋 은) 방법 은 키 에서 변 하지 않 는 멤버 를 선택 하고 그 멤버 가 생 성 한 hash value 를 활용 하 는 것 이다.직원 데이터베이스 의 뚜렷 한 hash key 는 바로 사회 보험 번호 (Social Security Number) 이다.그것 은 변 하지 않 을 뿐만 아니 라 9 자리 수의 이 번호 도 당신 이 원 하 는 성능 을 얻 기 위해 마음대로 사용 할 수 있 습 니 다.hash keys 를 이용 하여 검색 하고 시퀀스 용 기 를 이용 하여 검색 하 는 것 이 어떤 차이 가 있 는 지 샘플 을 다운로드 할 수 있 습 니 다.직원 을 해시 표 에 추가 하려 면 9 자리 숫자 번 호 를 만 들 고 key 로 사용 할 수 있 습 니 다.

int hash = 111223333;
for (int i = 0; i < 100; i++)
{
   string lastname = "Person" + i.ToString();
   e = new Employee ("Employee", lastname, (200-i)*200);
   members.Add(hash++, e);
}

사회 보험 번 호 는 좋 은 hash key 의 요 구 를 만족 시 켰 다. 변 하지 않 고 합 리 적 으로 분배 할 수 있 으 며 value 는 reference 가 아니 라 번호 에 달 려 있다.(reference 기반 hash key 가 아 닌 value 기반 hash key 를 사용 하여 내 가 이전에 언급 한 문 제 를 피해 야 합 니 다.) 이 hash key 를 사용 하여 대상 을 찾 는 것 도 간단 합 니 다.

 int ssn = Int32.Parse(this.SSN.Text);
currentEmp = (Employee)members[ssn];
if (currentEmp != null)
{
  LastName.Text = currentEmp.LastName;
  FirstName.Text = 
    currentEmp.FirstName;
  Salary.Text = 
    currentEmp.Salary.ToString ();
} else
  LastName.Text = "Not Found";

C \ # 에서 해시 표 에서 대상 을 찾 을 수 있 습 니 다.이 문법 은 일정한 시간 검색 의 개념 을 강조 한다. 배열 방문 을 대가 가 높 은 함수 호출 이 아니 라 빠 른 조작 으로 볼 수 있다.해시 표 의 마지막 포 인 트 는 모든 집합 과 마찬가지 로 인용 (references) 도 저장 하 는 것 이다.너 는 해시 표 의 대상 을 업데이트 하기 위해 서 어떠한 추가 작업 도 필요 없다.하 쉬 표 의 대상 을 인용 하면 마음대로 수정 할 수 있다.같은 원칙 은 keys 에 적용 되 지 않 는 다 는 것 을 기억 하 세 요.keys 를 바 꾸 기 위해 코드 를 작성 할 수 있 지만, 그 코드 가 hash value 를 수정 하면 집합 대상 을 잃 어 버 릴 것 입 니 다.해시 시 계 는 매우 유용 하고 효과 적 인 용기 이다.하지만 이 를 효과적으로 활용 하려 면 용기 와 용기 의 대상 상태 간 의 관 계 를 알 아야 한다.대상 으로 부터 계 산 된 변 하지 않 는 value 로 대상 을 검색 할 수 있 을 때, 해시 표 는 매우 유용 하 다.만약 당신 이 서로 다른 순서 (성명, 사회 보험 번호, 또는 나 이 를 통 해) 로 대상 을 검색 한다 면, 해시 표 는 그다지 유용 하지 않 을 것 이다.