Object.gethashCode ()의 기본 구현

StackOverflow https://stackoverflow.com/questions/720177

  •  23-08-2019
  •  | 
  •  

문제

기본 구현은 어떻게됩니까? GetHashCode() 일하다? 그리고 그것은 구조, 클래스, 어레이 등을 효율적이고 충분히 처리합니까?

나는 어떤 경우에 내가 내 자신을 포장 해야하는지, 어떤 경우에 어떤 경우에 기본 구현에 안전하게 의존 할 수있는 경우에 결정을 내려고 노력하고 있습니다. 가능하다면 바퀴를 재창조하고 싶지 않습니다.

도움이 되었습니까?

해결책 

namespace System {
    public class Object {
        [MethodImpl(MethodImplOptions.InternalCall)]
        internal static extern int InternalGetHashCode(object obj);

        public virtual int GetHashCode() {
            return InternalGetHashCode(this);
        }
    }
}

내부 도식 코드 맵핑됩니다 Objectnative :: gethashcode CLR의 기능은 다음과 같습니다.

FCIMPL1(INT32, ObjectNative::GetHashCode, Object* obj) {  
    CONTRACTL  
    {  
        THROWS;  
        DISABLED(GC_NOTRIGGER);  
        INJECT_FAULT(FCThrow(kOutOfMemoryException););  
        MODE_COOPERATIVE;  
        SO_TOLERANT;  
    }  
    CONTRACTL_END;  

    VALIDATEOBJECTREF(obj);  

    DWORD idx = 0;  

    if (obj == 0)  
        return 0;  

    OBJECTREF objRef(obj);  

    HELPER_METHOD_FRAME_BEGIN_RET_1(objRef);        // Set up a frame  

    idx = GetHashCodeEx(OBJECTREFToObject(objRef));  

    HELPER_METHOD_FRAME_END();  

    return idx;  
}  
FCIMPLEND

전체 구현 gethashcodeex 상당히 크기 때문에 링크하는 것이 더 쉽습니다. C ++ 소스 코드.

다른 팁

클래스의 경우, 기본값은 본질적으로 평등을 참조하며 일반적으로 괜찮습니다. 구조물을 작성하는 경우 평등을 무시하는 것이 더 일반적이지만 (권투를 피하기 위해) 어쨌든 구조물을 쓰는 것은 매우 드 rare니다!

평등을 무시할 때는 항상 일치해야합니다. Equals() 그리고 GetHashCode() (즉, 두 값의 경우 Equals() 진실을 반환합니다 ~ 해야 하다 동일한 해시 코드를 반환하지만 대화는입니다 ~ 아니다 필수) - 그리고 또한 제공하는 것이 일반적입니다. ==/!=운영자, 그리고 종종 구현해야합니다 IEquatable<T> 도.

해시 코드를 생성하기 위해서는 쌍을 이루는 값에 대한 충돌을 피하기 때문에 사실적인 합계를 사용하는 것이 일반적입니다 (예 : 기본 2 필드 해시).

unchecked // disable overflow, for the unlikely possibility that you
{         // are compiling with overflow-checking enabled
    int hash = 27;
    hash = (13 * hash) + field1.GetHashCode();
    hash = (13 * hash) + field2.GetHashCode();
    return hash;
}

이것은 다음과 같은 이점이 있습니다.

  • {1,2}의 해시는 {2,1}의 해시와 동일하지 않습니다.
  • {1,1}의 해시는 {2,2}의 해시와 동일하지 않습니다.

기타 - 비가 중 합 또는 XOR을 사용하는 경우 일반적 일 수 있습니다 (^), 등.

에 대한 문서 GetHashCode 방법 물체 말한다 "이 방법의 기본 구현은 해싱 목적으로 고유 한 개체 식별자로 사용해서는 안됩니다." 그리고 하나를위한 것 valueType 말한다 "파생형 유형의 gethashcode 메소드를 호출하면 해시 테이블에서 키로 사용하기에 반환 값이 적합하지 않을 것입니다.".

기본 데이터 유형은 다음과 같습니다 byte, short, int, long, char 그리고 string 좋은 gethashcode 방법을 구현하십시오. 다른 클래스와 구조와 같은 구조 Point 예를 들어, 구현 a GetHashCode 특정 요구에 적합하거나 적합하지 않을 수있는 방법. 당신은 그것이 충분히 좋은지 확인하기 위해 그것을 시도해야합니다.

각 클래스 또는 구조에 대한 문서는 기본 구현을 무시하는지 여부를 알려줄 수 있습니다. 그것을 무시하지 않으면 자신의 구현을 사용해야합니다. 사용해야 할 곳에 자신을 만드는 모든 클래스 나 구조에 대해 GetHashCode 방법, 해시 코드를 계산하기 위해 적절한 멤버를 사용하는 자체 구현을해야합니다.

설명하는 답을 찾을 수 없었기 때문에 왜 우리는 무시해야합니다 GetHashCode 그리고 Equals 맞춤형 구조를 위해 왜 기본 구현은 "해시 테이블에서 키로 사용하기에 적합하지 않을 것입니다", 링크를 남겨 두겠습니다. 이 블로그 게시물, 이는 발생한 문제의 실제 사례로 이유를 설명합니다.

전체 게시물을 읽는 것이 좋습니다. 그러나 여기에 요약이 있습니다 (강조 및 설명이 추가).

스트러크의 기본 해시가 느리고 좋지 않은 이유는 다음과 같습니다.

CLR이 설계된 방식, 정의 된 멤버에게 모든 호출 System.ValueType 또는 System.Enum 유형 [5 월] 원인 a 권투 할당 [...]

해시 기능의 구현자는 딜레마에 직면 해 있습니다. 해시 기능을 잘 분포하거나 빠르게 만들 수 있습니다. 어떤 경우에는 둘 다 달성 할 수 있지만 이것을 일반적으로하기 어렵습니다 안에 ValueType.GetHashCode.

구조물의 표준 해시 함수는 모든 필드의 "해시 코드"를 결합합니다. 그러나 필드의 해시 코드를 얻는 유일한 방법은 ValueType 방법은 다음과 같습니다 반사를 사용하십시오. 따라서 CLR 저자는 분포와 기본값에 대한 속도를 거래하기로 결정했습니다. GetHashCode 버전 첫 번째 비 널 필드의 해시 코드를 반환합니다. 그리고 유형의 ID [...]로 "건너"는 그렇지 않으면 합리적인 동작입니다. 예를 들어, 당신이 충분히 운이 좋고 구조물의 첫 번째 필드가 대부분의 인스턴스에 대해 동일한 값을 갖는 경우 해시 함수는 동일한 결과를 제공합니다. 항상. 또한 상상할 수 있듯이 이러한 인스턴스가 해시 세트 또는 해시 테이블에 저장되면 급격한 성능 영향을 미칩니다.

[...] 반사 기반 구현은 느립니다. 아주 느린.

...] 둘 다 ValueType.Equals 그리고 ValueType.GetHashCode 특별한 최적화가 있습니다. 유형에 "포인터"가없고 올바르게 포장 된 경우 [...] 더 최적의 버전이 사용됩니다. GetHashCode 4 바이트의 인스턴스 및 XORS 블록을 반복하고 Equals 메소드는 사용하는 두 인스턴스를 비교합니다 memcmp. [...] 그러나 최적화는 매우 까다 롭습니다. 첫째, 최적화가 언제 활성화되었는지 알기가 어렵습니다 [...] 둘째 메모리 비교가 반드시 올바른 결과를 줄 필요는 없습니다.. 간단한 예는 다음과 같습니다. [... -0.0 그리고 +0.0 동일하지만 이진 표현이 다릅니다.

게시물에 설명 된 실제 문제 :

private readonly HashSet<(ErrorLocation, int)> _locationsWithHitCount;
readonly struct ErrorLocation
{
    // Empty almost all the time
    public string OptionalDescription { get; }
    public string Path { get; }
    public int Position { get; }
}

우리는 기본 평등 구현이있는 사용자 정의 구조물이 포함 된 튜플을 사용했습니다. 그리고 불행히도, 구조물은 거의 항상 [빈 문자열]과 거의 같은 선택적 첫 필드를 가졌습니다.. 세트의 요소 수가 크게 증가하여 실제 성능 문제가 크게 증가하여 수만 개의 항목으로 컬렉션을 초기화하는 데 몇 분이 걸릴 때까지 성능이 괜찮 았습니다.

따라서 적어도의 경우 "내가 어떤 경우에 내 자신을 포장하고 어떤 경우에는 기본 구현에 안전하게 의존 할 수있는 경우"라는 질문에 대답하기 위해 스트러크, 당신은 무시해야합니다 Equals 그리고 GetHashCode 해시 테이블에서 사용자 정의 구조물을 키로 사용하거나 Dictionary.
또한 구현을 권장합니다 IEquatable<T> 이 경우 권투를 피하기 위해.

다른 대답이 말했듯이, 당신이 쓰고 있다면 수업, 참조 평등을 사용하는 기본 해시는 일반적으로 괜찮 으므로이 경우에 귀찮게하지 않을 것입니다. ~하지 않는 한 재정의해야합니다 Equals (그러면 당신은 무시해야 할 것입니다 GetHashCode 따라서).

일반적으로 말하면, 동등한 것을 무시하는 경우 gethashcode를 무시하고자합니다. 그 이유는 둘 다 계급/구조물의 평등을 비교하는 데 사용되기 때문입니다.

Foo A, B를 확인할 때 동등한 것이 사용됩니다.

if (a == b)

포인터가 일치하지 않을 가능성이 없다는 것을 알고 있으므로 내부 멤버를 비교할 수 있습니다.

Equals(obj o)
{
    if (o == null) return false;
    MyType Foo = o as MyType;
    if (Foo == null) return false;
    if (Foo.Prop1 != this.Prop1) return false;

    return Foo.Prop2 == this.Prop2;
}

gethashcode는 일반적으로 해시 테이블에서 사용됩니다. 클래스에서 생성 된 해시 코드는 항상 등급의 상태에 대해 동일해야합니다.

나는 일반적으로한다.

GetHashCode()
{
    int HashCode = this.GetType().ToString().GetHashCode();
    HashCode ^= this.Prop1.GetHashCode();
    etc.

    return HashCode;
}

어떤 사람들은 해시 코드가 객체 수명 당 한 번만 계산되어야한다고 말하지만, 나는 그것에 동의하지 않습니다 (그리고 아마도 잘못).

객체가 제공 한 기본 구현을 사용하면 클래스 중 하나에 대한 동일한 참조가 없으면 서로 동일하지 않습니다. Equals 및 gethashcode를 재정의함으로써 객체 참조보다는 내부 값에 따라 평등을보고 할 수 있습니다.

Pocos를 다루는 경우이 유틸리티를 사용하여 인생을 다소 단순화 할 수 있습니다.

var hash = HashCodeUtil.GetHashCode(
           poco.Field1,
           poco.Field2,
           ...,
           poco.FieldN);

...

public static class HashCodeUtil
{
    public static int GetHashCode(params object[] objects)
    {
        int hash = 13;

        foreach (var obj in objects)
        {
            hash = (hash * 7) + (!ReferenceEquals(null, obj) ? obj.GetHashCode() : 0);
        }

        return hash;
    }
}
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top