두 숫자의 해시 코드 만들기

두 숫자의 해시 코드 만들기

---

(a + b)C #에서 복소수 클래스 에 대한 빠른 해시 코드 함수를 만들려고합니다 .

나는 그 a.GetHashcode()^b.GetHashCode()방법을 반복해서 보았다 . 그러나 이것은 (a,b)및에 대해 동일한 해시 코드를 제공합니다 (b,a).

이를 수행하는 표준 알고리즘이 있으며 .Net 프레임 워크에 도움이되는 기능이 있습니까?

---

임의의 해시 가능한 항목 집합에 대한 해시 코드를 만드는 일반적인 방법 :

int hash = 23;
hash = hash * 31 + item1Hash;
hash = hash * 31 + item2Hash;
hash = hash * 31 + item3Hash;
hash = hash * 31 + item4Hash;
hash = hash * 31 + item5Hash;
// etc

귀하의 경우에는 item1Hash그저 그럴 수도 a있고 item2Hash그럴 수도 있습니다 b.

23과 31의 값은 소수 (또는 적어도 코 프라임) 인 한 상대적으로 중요하지 않습니다.

분명히 여전히 충돌이 있지만 다음과 같은 일반적인 문제는 발생하지 않습니다.

hash(a, a) == hash(b, b)
hash(a, b) == hash(b, a)

당신이 더 많은 것을의 실제 값에 대한 알고있는 경우에 a와 b있는 것 당신이 아마 더 잘 할 수있을, 그러나 이것은 기억하고 쉽게 구현할 수있는 좋은 초기 구현합니다. "산술 오버플로 / 언더 플로 확인"을 선택한 상태에서 어셈블리를 빌드 할 가능성이있는 경우 모두 확인되지 않은 블록에 넣어야합니다. (이 알고리즘에는 오버플로가 좋습니다.)

---

다음은 순서를 고려한 가능한 접근 방식입니다. (두 번째 방법은 확장 방법으로 정의됩니다.)

public int GetHashCode()
{
    return a.GetHashcode() ^ b.GetHashcode().RotateLeft(16);
}

public static uint RotateLeft(this uint value, int count)
{
    return (value << count) | (value >> (32 - count))
}

Complex.NET 4.0 클래스가 어떻게 작동하는지 보는 것은 확실히 흥미로울 것입니다.

---

한 가지 표준 방법은 다음과 같습니다.

hashcode = 23
hashcode = (hashcode * 37) + v1
hashcode = (hashcode * 37) + v2

23과 37은 코 프라임이지만 다른 숫자도 사용할 수 있습니다.

---

이것에 대해 :

(a.GetHashcode() + b).GetHashcode()

(a, b) 및 (b, a)에 대한 다른 코드를 제공하며 실제로 그렇게 화려하지는 않습니다.

---

@JonSkeet은 n 개의 해시 코드에서 해시 코드를 계산하기위한 공정하고 범용적인 알고리즘을 제공하지만 객체의 어떤 멤버가 해시되어야하는지 이미 알고 있고, 널 ​​멤버에 대해 무엇을해야하는지 알고, n 개의 임의 항목에 대한 구현을 생략한다고 가정합니다. . 그래서 우리는 그의 대답을 확장합니다.

1. 변경 불가능한 공용 속성 및 필드 만 개체 해시 코드에 기여해야합니다. 동일한 해시 코드 (객체 평등과 해시 코드 평등 사이의 관계를 암시)를 가진 동일한 가시적 표면을 가진 두 객체를 신뢰할 수 있어야하므로 공개 (또는 대중에게 동형)되어야하며, 이후 변경 불가능해야합니다. 객체의 해시 코드는 수명 동안 절대 변경되어서는 안됩니다 (그러면 해시 테이블의 잘못된 슬롯에있는 객체로 끝날 수 있기 때문입니다!).
2. null 멤버는 0과 같은 상수로 해시해야합니다.
3. JonSkeet의 알고리즘 @ 대개라는 함수형 프로그래밍 고차 함수를 적용하는 교과서의 예제 fold( AggregateC # LINQ에서)를, 어디에서 23우리의 씨앗과 <hash accumulator> * 31 + <current item hash>우리의 폴딩 기능입니다 :

F #에서

let computeHashCode items =
    items
    |> Seq.map (fun item -> if item = null then 0 else item.GetHashCode())
    |> Seq.fold (fun hash itemHash -> hash * 31 + itemHash) 23

C #에서

Func<IEnumerable<Object>, int> computeHashCode = items =>
    items
    .Select(item => item == null ? 0 : item.GetHashCode())
    .Aggregate(23, (hash, itemHash) => hash * 31 + itemHash);

---

All that depends on what you're trying to achieve. If hashes are meant for hash structures like Dictionary, then you have to balance collision rate and speed of hashing. To have a perfect hash without collision at all it will be more time consuming. Similarly the fastest hashing algorithm will have more collisions relatively. Finding the perfect balance is the key here. Also you should take into consideration how large your effective hash can be, and if hashing should be reversible! Noldorin's approach gives you perfect hash (read no collision) if your real and imaginary parts of your complex number are always positive. This will do even for negative numbers if you're ok with the rare collisions. But I'm concerned over the range of values it can yield, quite big for my taste.

If you're after perfect hashes (out of some academic/research interests) that should work even for negative numbers, you can see this solution (and an array of other solutions in the same thread). In my tests, it is faster and utilizes space better than any other I have seen.

참고URL : https://stackoverflow.com/questions/892618/create-a-hashcode-of-two-numbers