빠르고 간단한 해시 코드 조합

빠르고 간단한 해시 코드 조합

---

사람들이 두 개체의 해시 코드를 결합하는 빠르고 간단한 방법을 추천 할 수 있습니까? 효율적으로 처리 할 해시 테이블이 있기 때문에 충돌에 대해 너무 걱정하지 않습니다. 가능한 한 빨리 코드를 생성하는 것을 원합니다.

SO와 웹을 둘러 보면 몇 가지 주요 후보가있는 것 같습니다.

1. XORing
2. 소수 곱셈을 사용한 XORing
3. 곱셈 / 나눗셈과 같은 간단한 숫자 연산 (오버플로 확인 또는 래핑 사용)
4. String 빌드 후 String 클래스 Hash Code 메서드 사용

사람들은 무엇을 추천하고 그 이유는 무엇입니까?

---

저는 개인적으로 XOR을 피할 것입니다. 두 개의 동일한 값이 0이됨을 의미합니다. 따라서 hash (1, 1) == hash (2, 2) == hash (3, 3) 등입니다. 또한 hash (5, 0) == hash (0, 5) 등이 가끔 나올 수 있습니다. 나는 한 당신이 해시 항목의 순서를 원하는 경우 당신은 - 의도적으로 설정 해싱을 위해 그것을 사용 하지 않는 순서, 그것의 좋은 걱정.

나는 보통 다음을 사용합니다.

unchecked
{
    int hash = 17;
    hash = hash * 31 + firstField.GetHashCode();
    hash = hash * 31 + secondField.GetHashCode();
    return hash;
}

이것이 Josh Bloch가 Effective Java에서 제안한 형식입니다. 지난번에 비슷한 질문에 대답했습니다. 이에 대해 자세히 논의한 기사를 찾았습니다. IIRC, 왜 잘 작동하는지 아무도 모르지만 실제로 작동합니다. 또한 기억하기 쉽고 구현하기 쉬우 며 여러 필드로 쉽게 확장 할 수 있습니다.

---

Jon Skeet의 답변에 설명 된 템플릿은 일반적으로 해시 함수 제품군으로 잘 작동하지만 상수 선택이 중요하며 답변에 언급 된 시드 17및 요소는 31일반적인 사용 사례에서 전혀 잘 작동하지 않습니다. 대부분의 사용 사례에서 해시 된 값은보다 0에 훨씬 가까우며 int.MaxValue공동으로 해시되는 항목의 수는 수십 개 이하입니다.

정수 튜플 해시 하고 , 거의 98.5 %의 심해 충돌 속도를 가지고 있습니다. 예를 들어 , 또한 N-튜플 포함하는 등 우리는 범위를 확장하면 그것은 38에 대한 %의 충돌 속도 덜 끔찍한 수행을. 그러나 우리는 훨씬 더 잘할 수 있습니다.{x, y}-1000 <= x <= 1000-1000 <= y <= 1000{1, 0} -> {0, 31}{1, 1} -> {0, 32}3 <= n <= 25

public static int CustomHash(int seed, int factor, params int[] vals)
{
    int hash = seed;
    foreach (int i in vals)
    {
        hash = (hash * factor) + i;
    }
    return hash;
}

나는 랜덤 정수의 다양한 랜덤 n- 튜플에 대한 시드 및 인수에 대한 다양한 값으로 위의 방법을 테스트 한 Monte Carlo 샘플링 검색 루프를 작성했습니다 i. 허용되는 범위는 2 <= n <= 25( n무작위이지만 범위의 하단쪽으로 치우친 위치 ) 및 -1000 <= i <= 1000입니다. 각 시드 및 요인 쌍에 대해 최소 1,200 만 개의 고유 충돌 테스트가 수행되었습니다.

약 7 시간 실행 후 가장 좋은 쌍 (시드와 계수가 모두 4 자리 이하로 제한됨)은 seed = 1009,, factor = 9176충돌 률 0.1131 %입니다. 5 자리 및 6 자리 영역에는 더 나은 옵션이 있습니다. 하지만 간결함을 위해 상위 4 자리 수행자를 선택했으며 모든 공통 int및 char해싱 시나리오 에서 꽤 잘 수행됩니다 . 또한 훨씬 더 큰 정수에서도 잘 작동하는 것 같습니다.

"프라임"이 시드 및 / 또는 요소로서의 좋은 성능을위한 일반적인 전제 조건은 아니지만 도움이 될 가능성이 있다는 점은 주목할 가치가 있습니다. 1009위에서 언급 한 것은 사실 프라임이지만 9176그렇지 않습니다. 나는 이것에 대한 변형을 명시 적으로 테스트했는데, 여기서 (떠나는 동안 ) factor근처의 다양한 소수로 변경 했으며 모두 위의 솔루션보다 성능이 떨어졌습니다.9176seed = 1009

마지막으로 위에서 언급 한대로 일반 ReSharper 권장 기능 제품군 hash = (hash * factor) ^ i;과 원본 CustomHash()을 비교하여 성능이 훨씬 뛰어납니다. ReSharper XOR 스타일은 일반적인 사용 사례 가정에서 충돌 률이 20-30 % 범위 인 것으로 보이며 제 생각에는 사용해서는 안됩니다.

---

.NET Core 2.1 이상을 사용 하는 경우 복합 해시 코드 생성에 도움이 되도록 System.HashCode 구조체를 사용하는 것이 좋습니다. 추가 및 결합의 두 가지 작동 모드가 있습니다.

Combine일반적으로 더 간단하고 최대 8 개 항목에 대해 작동하는를 사용하는 예 :

public override int GetHashCode()
{
    return HashCode.Combine(object1, object2);
}

사용 예 Add:

public override int GetHashCode()
{
    var hash = new HashCode();
    hash.Add(this.object1);
    hash.Add(this.object2);
    return hash.ToHashCode();
}

장점 :

• .NET 자체의 일부, .NET Core 2.1 / .NET Standard 2.1 기준 (아래의 con 참조)
• 작성자와 검토자가 이를 corefx 저장소에 병합 하기 전에 수행 한 작업을 기반으로하여 우수한 성능과 혼합 특성 이있는 것으로 보입니다.
• 자동으로 null 처리
• IEqualityComparer인스턴스를 사용 하는 오버로드

단점 :

• Not available on .NET Framework. HashCode is part of .NET Standard 2.1, but as of September 2019, the .NET team has no plans to support .NET Standard on the .NET Framework, as .NET Core/.NET 5 is the future of .NET.
• General purpose, so it won't handle super-specific cases as well as hand-crafted code

---

I presume that .NET Framework team did a decent job in testing their System.String.GetHashCode() implementation, so I would use it:

// System.String.GetHashCode(): http://referencesource.microsoft.com/#mscorlib/system/string.cs,0a17bbac4851d0d4
// System.Web.Util.StringUtil.GetStringHashCode(System.String): http://referencesource.microsoft.com/#System.Web/Util/StringUtil.cs,c97063570b4e791a
public static int CombineHashCodes(IEnumerable<int> hashCodes)
{
    int hash1 = (5381 << 16) + 5381;
    int hash2 = hash1;

    int i = 0;
    foreach (var hashCode in hashCodes)
    {
        if (i % 2 == 0)
            hash1 = ((hash1 << 5) + hash1 + (hash1 >> 27)) ^ hashCode;
        else
            hash2 = ((hash2 << 5) + hash2 + (hash2 >> 27)) ^ hashCode;

        ++i;
    }

    return hash1 + (hash2 * 1566083941);
}

Another implementation is from System.Web.Util.HashCodeCombiner.CombineHashCodes(System.Int32, System.Int32) and System.Array.CombineHashCodes(System.Int32, System.Int32) methods. This one is simpler, but probably doesn't have such a good distribution as the method above:

// System.Web.Util.HashCodeCombiner.CombineHashCodes(System.Int32, System.Int32): http://referencesource.microsoft.com/#System.Web/Util/HashCodeCombiner.cs,21fb74ad8bb43f6b
// System.Array.CombineHashCodes(System.Int32, System.Int32): http://referencesource.microsoft.com/#mscorlib/system/array.cs,87d117c8cc772cca
public static int CombineHashCodes(IEnumerable<int> hashCodes)
{
    int hash = 5381;

    foreach (var hashCode in hashCodes)
        hash = ((hash << 5) + hash) ^ hashCode;

    return hash;
}

---

Use the combination logic in tuple. The example is using c#7 tuples.

(field1, field2).GetHashCode();

---

If your input hashes are the same size, evenly distributed and not related to each other then an XOR should be OK. Plus it's fast.

The situation I'm suggesting this for is where you want to do

H = hash(A) ^ hash(B); // A and B are different types, so there's no way A == B.

of course, if A and B can be expected to hash to the same value with a reasonable (non-negligible) probability, then you should not use XOR in this way.

---

If you're looking for speed and don't have too many collisions, then XOR is fastest. To prevent a clustering around zero, you could do something like this:

finalHash = hash1 ^ hash2;
return finalHash != 0 ? finalHash : hash1;

Of course, some prototyping ought to give you an idea of performance and clustering.

---

Assuming you have a relevant toString() function (where your different fields shall appear), I would just return its hashcode:

this.toString().hashCode();

This is not very fast, but it should avoid collisions quite well.

---

I would recommend using the built-in hash functions in System.Security.Cryptography rather than rolling your own.

ReferenceURL : https://stackoverflow.com/questions/1646807/quick-and-simple-hash-code-combinations