xor를 사용한 gethashcode () 문제

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

  •  06-07-2019
  •  | 
  •  

문제

내 이해는 일반적으로 gethashcode ()와 함께 XOR을 사용하여 int를 생성하여 데이터를 값으로 식별해야합니다 (참조와 반대). 간단한 예는 다음과 같습니다.

class Foo
{
    int m_a;
    int m_b;

    public int A
    {
        get { return m_a; }
        set { m_a = value; }
    }

    public int B
    {
        get { return m_b; }
        set { m_b = value; }
    }

    public Foo(int a, int b)
    {
        m_a = a;
        m_b = b;
    }

    public override int GetHashCode()
    {
        return A ^ B;
    }

    public override bool Equals(object obj)
    {
        return this.GetHashCode() == obj.GetHashCode();
    }
}

아이디어는 속성 A와 B의 값에 따라 FOO의 한 인스턴스를 다른 사례와 비교하고 싶습니다. foo1.a == foo2.a 및 foo1.b == foo2.b의 경우, 우리는 평등이 있습니다.

문제는 다음과 같습니다.

Foo one = new Foo(1, 2);
Foo two = new Foo(2, 1);

if (one.Equals(two)) { ... }  // This is true!

이들은 모두 gethashcode ()에 대해 3의 값을 생성하여 equals ()가 true를 반환합니다. 분명히 이것은 사소한 예이며, 두 가지 속성만으로도 () 메소드의 개별 속성을 간단히 비교할 수 있습니다. 그러나 더 복잡한 수업을 통해 이것은 빨리 손을 떼지 못할 것입니다.

때로는 해시 코드를 한 번만 설정하는 것이 좋습니다. 항상 같은 값을 반환하는 것이 좋습니다. 그러나 평등 평가가 필요한 변이 가능한 물체의 경우 이것이 합리적이라고 생각하지 않습니다.

gethashcode ()를 구현할 때 쉽게 교환 할 수있는 속성 값을 처리하는 가장 좋은 방법은 무엇입니까?

또한보십시오

재정의 된 시스템에 가장 적합한 알고리즘은 무엇입니까?

도움이 되었습니까?

해결책

우선 - gethashcode ()의 관점에서만 equals ()를 구현하지 마십시오. hashcodes는 객체가 동일하지 않은 경우에도 충돌합니다.

gethashcode () 계약에는 다음이 포함됩니다.

  • 다른 해시 코드는 객체가 확실히 같지 않다는 것을 의미합니다
  • 동일한 해시 코드는 물체를 의미합니다 ~할 것 같다 동등하다 (그러나 아마도 아닐 수도있다)

Andrew Hare는 그의 대답을 통합 할 것을 제안했습니다.

나는 당신이 읽는 것이 좋습니다 이 솔루션 (우리 자신의 존 스키트, 그건 그렇고, 해시 코드를 계산하는 "더 나은"방법.

아니요, 위는 비교적 느리고 많은 도움이되지 않습니다. 어떤 사람들은 xor (예 : a ^ b ^ c)를 사용하지만 Josh Bloch의 "효과적인 Java"에 표시된 방법을 선호합니다.

public override int GetHashCode()
{
    int hash = 23;
    hash = hash*37 + craneCounterweightID;
    hash = hash*37 + trailerID;
    hash = hash*37 + craneConfigurationTypeCode.GetHashCode();
    return hash;
}

23과 37은 공동 프라임 인 임의의 숫자입니다.

XOR 방법에 대한 위의 이점은 두 가지 값이 자주 동일 한 유형이있는 경우 해당 값이 항상 동일한 결과를 제공하는 반면 (0), 위의 값은 항상 동일한 결과를 제공한다는 것입니다. 불길한.

위의 스 니펫에서 언급했듯이, 당신은 또한 Joshua Bloch의 책, 효과적인 Java, 여기에는 주제에 대한 훌륭한 처리가 포함되어 있습니다 (해시 코드 토론은 .NET에도 적용됨).

다른 팁

Andrew는 더 나은 해시 코드를 생성하기위한 좋은 예를 게시했지만 해시 코드를 평등 점검으로 사용해서는 안된다는 점을 명심하십시오.

이것이 왜 이중 물체를 고려하는지에 대한 사소한 예를 위해서. int보다 더 많은 값이 있으므로 각 더블에 대해 고유 한 int를 갖는 것은 불가능합니다. 해시는 실제로 첫 번째 패스 일 뿐이며, 키를 빨리 찾아야 할 때 사전과 같은 상황에서 사용되는 첫 번째 패스 일뿐입니다. 먼저 해시를 비교하여 가능한 키의 많은 비율을 배제 할 수 있으며 해시가 일치하는 키만 비용을 지불해야합니다. 완전한 평등 점검 (또는 기타 충돌 해결 행동 양식).

해싱에는 항상 충돌이 포함되며이를 처리해야합니다 (Fe, 해시 값을 비교하고 동일하다면 클래스 내부의 값을 정확하게 비교하여 클래스가 동일합니다).

간단한 XOR을 사용하면 많은 충돌이 발생합니다. 덜 원한다면 다른 비트에 값을 분배하는 수학적 기능을 사용하십시오 (비트 이동, 프라임 등을 곱한 등).

읽다 변한 객체에 대한 gethashcode를 우선적으로 하시겠습니까? 씨# 그리고 구현에 대해 생각하십시오 IEquatable<T>

해시의 빠른 생성 및 양호 분포

public override int GetHashCode()
{
    return A.GetHashCode() ^ B.GetHashCode();         // XOR
}

호기심에서 해시 코드는 일반적으로 비교에 나쁜 생각이기 때문에 다음 코드를하는 것이 더 좋지 않습니까, 아니면 뭔가 빠진 것이 더 좋지 않습니까?

public override bool Equals(object obj)
{
    bool isEqual = false;
    Foo otherFoo = obj as Foo;
    if (otherFoo != null)
    {
        isEqual = (this.A == otherFoo.A) && (this.B == otherFoo.B);
    }
    return isEqual;
}

몇 가지 더 나은 해시 구현이 있습니다. FNV 해시 예를 들어.

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