내부적으로 값을 얻기 위해 해시가 어떻게 키를 조회합니까?

Question

내부적으로 값을 얻기 위해 해시가 어떻게 키를 조회합니까?

빈 분류일까요?

Answer 1

사전은 해시 코드를 사용하여 항목이 저장된 버킷 번호를 계산합니다. 버킷 수는 소수가되도록 선택되고 특정 키의 버킷 수는 버킷 수를 모듈로 나타내는 키의 해시 코드로 계산됩니다. 여러 객체가 동일한 해시 코드를 가질 수 있고 여러 해시 코드가 동일한 버킷에있을 수 있으므로 버킷에서 키가 발견되면 키가 올바른지 비교하기 위해 동등성을 비교해야합니다. 버킷에 잘못된 키가 있으면 잘못된 항목의 구성원 인 next을 사용하여 원하는 키를 검색 할 다음 장소를 찾습니다.

충돌이없는 경우 올바른 버킷은 매우 빠르게 찾을 수 있지만 최악의 경우에는 사전에 저장된 항목 수에 선형 시간이 걸릴 수 있습니다. 여기서는 객체의 해시 코드를 일정 시간 내에 계산할 수 있다고 가정합니다.

닷넷 구현 실제 코드, 또는 .NET 반사경을 이용하여, 기준 구현 소스를 다운로드함으로써 알 수있다 :

private int FindEntry(TKey key) 
{ 
    if (key == null) 
    { 
     ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); 
    } 
    if (this.buckets != null) 
    { 
     int num = this.comparer.GetHashCode(key) & 0x7fffffff; 
     for (int i = this.buckets[num % this.buckets.Length]; i >= 0; i = this.entries[i].next) 
     { 
      if ((this.entries[i].hashCode == num) && this.comparer.Equals(this.entries[i].key, key)) 
      { 
       return i; 
      } 
     } 
    } 
    return -1; 
} 

Answer 2

해시 희망 생성 키에 대하여 단지 알고리즘을 실행 (인) 항목을 저장할 버킷을 가리키는 고유 한 값입니다. 따라서 값을 계산하여 해당 항목을 검색 할 때 해시가 이전에 저장 한 개체를 가리 키기를 바랍니다. 그렇지 않은 경우이 해시 값을 공유하는 다음 개체를 찾을 위치에 대한 포인터가 있어야합니다. 당신이 당신의 품목을 발견 할 때, 그것은 돌려 보낼 것이다. 체인의 끝에 도달하면 항목을 찾을 수 없습니다.

해싱에 대한 자세한 정의는 Hash Tables 및 Hash Function을 참조하십시오.