순서에 관계없이 문자열 목록의 해시 가져 오기

순서에 관계없이 문자열 목록의 해시 가져 오기

---

GetHashCodeOfList()순서에 관계없이 문자열 목록의 해시 코드를 반환 하는 함수를 작성하고 싶습니다 . 동일한 문자열을 가진 2 개의 목록이 주어지면 동일한 해시 코드를 반환해야합니다.

ArrayList list1 = new ArrayList()    
list1.Add("String1");
list1.Add("String2");
list1.Add("String3");    

ArrayList list2 = new ArrayList()    
list2.Add("String3");    
list2.Add("String2"); 
list2.Add("String1");

GetHashCodeOfList(list1) = GetHashCodeOfList(list2) //this should be equal.

몇 가지 생각이있었습니다.

1. 먼저 목록을 정렬 한 다음 정렬 된 목록을 하나의 긴 문자열로 결합한 다음 GetHashCode(). 그러나 정렬은 느린 작업입니다.

2. string.GetHashCode()목록에서 를 호출하여 각 개별 문자열의 해시를 얻은 다음 모든 해시를 곱하고 Mod를 호출 할 수 UInt32.MaxValue있습니다. 예 : "String1".GetHashCode() * "String2".GetHashCode * … MOD UInt32.MaxValue. 그러나 이로 인해 숫자 오버플로가 발생합니다.

누구 생각이 있습니까?

도움을 주셔서 미리 감사드립니다.

---

여기에는 두 가지 주요 범주 아래에 다양한 접근 방식이 있으며, 각 범주에는 일반적으로 효율성과 성능 측면에서 고유 한 장점과 단점이 있습니다. 응용 프로그램에 대해 가장 간단한 알고리즘을 선택하고 상황에 따라 필요한 경우에만 더 복잡한 변형을 사용하는 것이 가장 좋습니다.

이 예제 EqualityComparer<T>.Default는 null 요소를 깔끔하게 처리하므로 사용 합니다. 원하는 경우 null에 대해 0보다 더 잘 할 수 있습니다. T가 struct로 제한된 경우에도 필요하지 않습니다. EqualityComparer<T>.Default원하는 경우 함수 에서 조회 를 끌어 올 수 있습니다 .

교환 작업

교환 가능한 개별 항목의 해시 코드에 대한 작업을 사용하면 순서에 관계없이 동일한 최종 결과를 얻을 수 있습니다.

숫자에 대한 몇 가지 분명한 옵션이 있습니다.

XOR

public static int GetOrderIndependentHashCode<T>(IEnumerable<T> source)
{
    int hash = 0;
    foreach (T element in source)
    {
        hash = hash ^ EqualityComparer<T>.Default.GetHashCode(element);
    }
    return hash;
}

한 가지 단점은 { "x", "x"}의 해시가 { "y", "y"}의 해시와 동일하다는 것입니다. 하지만 이것이 귀하의 상황에 문제가되지 않는다면 아마도 가장 간단한 해결책 일 것입니다.

부가

public static int GetOrderIndependentHashCode<T>(IEnumerable<T> source)
{
    int hash = 0;
    foreach (T element in source)
    {
        hash = unchecked (hash + 
            EqualityComparer<T>.Default.GetHashCode(element));
    }
    return hash;
}

여기서 오버플로는 괜찮으므로 명시적인 unchecked컨텍스트입니다.

여전히 몇 가지 불쾌한 경우 (예 : {1, -1} 및 {2, -2})가 있지만 특히 문자열에서는 괜찮을 가능성이 더 높습니다. 이러한 정수를 포함 할 수있는 목록의 경우에는 항상 다음을 구현할 수 있습니다. 사용자 지정 해싱 함수 (아마도 특정 값의 반복 색인을 매개 변수로 사용하고 이에 따라 고유 한 해시 코드를 반환하는 함수).

다음은 상당히 효율적인 방식으로 앞서 언급 한 문제를 해결하는 알고리즘의 예입니다. 또한 생성 된 해시 코드의 분포를 크게 늘릴 수있는 이점도 있습니다 (일부 설명은 마지막에 링크 된 문서 참조). 이 알고리즘이 "더 나은"해시 코드를 생성하는 정확한 방법에 대한 수학적 / 통계적 분석은 상당히 발전 할 수 있지만 광범위한 입력 값에 대해 테스트하고 결과를 플로팅하면 충분히 검증되어야합니다.

public static int GetOrderIndependentHashCode<T>(IEnumerable<T> source)
{
    int hash = 0;
    int curHash;
    int bitOffset = 0;
    // Stores number of occurences so far of each value.
    var valueCounts = new Dictionary<T, int>();

    foreach (T element in source)
    {
        curHash = EqualityComparer<T>.Default.GetHashCode(element);
        if (valueCounts.TryGetValue(element, out bitOffset))
            valueCounts[element] = bitOffset + 1;
        else
            valueCounts.Add(element, bitOffset);

        // The current hash code is shifted (with wrapping) one bit
        // further left on each successive recurrence of a certain
        // value to widen the distribution.
        // 37 is an arbitrary low prime number that helps the
        // algorithm to smooth out the distribution.
        hash = unchecked(hash + ((curHash << bitOffset) |
            (curHash >> (32 - bitOffset))) * 37);
    }

    return hash;
}

곱셈

덧셈에 비해 이점이 거의 없습니다. 작은 숫자와 양수와 음수의 혼합은 해시 비트의 더 나은 분포로 이어질 수 있습니다. 이 "1"을 상쇄하기위한 음수는 아무것도 기여하지 않는 쓸모없는 항목이되고 0 요소는 0이됩니다. 이 중대한 결함을 일으키지 않도록 특별한 경우 0을 사용할 수 있습니다.

public static int GetOrderIndependentHashCode<T>(IEnumerable<T> source)
{
    int hash = 17;
    foreach (T element in source)
    {
        int h = EqualityComparer<T>.Default.GetHashCode(element);
        if (h != 0)
            hash = unchecked (hash * h);
    }
    return hash;
}

먼저 주문

다른 핵심 접근 방식은 먼저 순서를 적용한 다음 원하는 해시 조합 함수를 사용하는 것입니다. 순서 자체는 일관성이있는 한 중요하지 않습니다.

public static int GetOrderIndependentHashCode<T>(IEnumerable<T> source)
{
    int hash = 0;
    foreach (T element in source.OrderBy(x => x, Comparer<T>.Default))
    {
        // f is any function/code you like returning int
        hash = f(hash, element);
    }
    return hash;
}

이것은에서 가능한 결합 작업 f이 훨씬 더 나은 해싱 속성 (예 : 비트 분산)을 가질 수 있다는 점에서 상당한 이점 이 있지만 훨씬 더 높은 비용이 발생합니다. 정렬은 O(n log n)컬렉션의 필수 복사본은 원본을 수정하지 않으려는 욕구를 감안할 때 피할 수없는 메모리 할당입니다. GetHashCode구현은 일반적으로 할당을 완전히 피해야합니다. 의 가능한 구현 중 하나 f는 덧셈 섹션의 마지막 예에서 제공된 것과 유사합니다 (예 : 상수 비트 시프트 후 소수 곱하기-추가 비용없이 각 반복에서 연속 소수를 사용할 수도 있음). 한 번만 생성하면됩니다.)

즉, 해시를 계산하고 캐시 할 수있는 경우를 처리 GetHashCode하고이 접근 방식에 대한 많은 호출에 대한 비용을 상각 할 수있는 경우 우수한 동작을 생성 할 수 있습니다. 또한 후자의 접근 방식은 GetHashCode요소의 유형을 알고있는 경우 요소에서 를 사용할 필요가 없고 대신에 더 나은 해시 분포를 생성하기 위해 바이트 당 작업 을 사용할 필요가 없기 때문에 훨씬 더 유연 합니다. 이러한 접근 방식은 성능이 심각한 병목 현상으로 확인 된 경우에만 사용됩니다.

마지막으로, 해시 코드의 주제와 일반적인 효과에 대해 합리적으로 포괄적이고 상당히 비 수학적 개요를 원한다면 이 블로그 게시물 , 특히 간단한 해싱 알고리즘 구현 (pt II) 게시물을 읽어 볼 가치가 있습니다 .

---

문자열 목록 정렬의 대안은 문자열의 해시 코드를 가져온 다음 해시 코드를 정렬하는 것입니다. (int를 비교하는 것은 문자열을 비교하는 것보다 비용이 적게 듭니다.) 그런 다음 알고리즘을 사용하여 더 나은 배포를 제공하는 해시 코드를 병합 할 수 있습니다.

예:

GetHashCodeOfList<T>(IEnumerable<T> list) {
   List<int> codes = new List<int>();
   foreach (T item in list) {
      codes.Add(item.GetHashCode());
   }
   codes.Sort();
   int hash = 0;
   foreach (int code in codes) {
      unchecked {
         hash *= 251; // multiply by a prime number
         hash += code; // add next hash code
      }
   }
   return hash;
}

---

    Dim list1 As ArrayList = New ArrayList()
    list1.Add("0")
    list1.Add("String1")
    list1.Add("String2")
    list1.Add("String3")
    list1.Add("abcdefghijklmnopqrstuvwxyz")

    Dim list2 As ArrayList = New ArrayList()
    list2.Add("0")
    list2.Add("String3")
    list2.Add("abcdefghijklmnopqrstuvwxyz")
    list2.Add("String2")
    list2.Add("String1")
    If GetHashCodeOfList(list1) = GetHashCodeOfList(list2) Then
        Stop
    Else
        Stop
    End If
    For x As Integer = list1.Count - 1 To 0 Step -1
        list1.RemoveAt(list1.Count - 1)
        list2.RemoveAt(list2.Count - 1)
        Debug.WriteLine(GetHashCodeOfList(list1).ToString)
        Debug.WriteLine(GetHashCodeOfList(list2).ToString)
        If list1.Count = 2 Then Stop
    Next


Private Function GetHashCodeOfList(ByVal aList As ArrayList) As UInt32
    Const mask As UInt16 = 32767, hashPrime As Integer = Integer.MaxValue
    Dim retval As UInt32
    Dim ch() As Char = New Char() {}
    For idx As Integer = 0 To aList.Count - 1
        ch = DirectCast(aList(idx), String).ToCharArray
        For idCH As Integer = 0 To ch.Length - 1
            retval = (retval And mask) + (Convert.ToUInt16(ch(idCH)) And mask)
        Next
    Next
    If retval > 0 Then retval = Convert.ToUInt32(hashPrime \ retval) 'Else ????
    Return retval
End Function

---

코드가 훨씬 적지 만 성능이 다른 답변만큼 좋지 않을 수 있습니다.

public static int GetOrderIndependentHashCode<T>(this IEnumerable<T> source)    
    => source == null ? 0 : HashSet<T>.CreateSetComparer().GetHashCode(new HashSet<T>(source));

---

Here is a hybrid approach. It combines the three commutative operations (XOR, addition and multiplication), applying each one in different ranges of the 32bit number. The bit-range of each operation is adjustable.

public static int GetOrderIndependentHashCode<T>(IEnumerable<T> source)
{
    var comparer = EqualityComparer<T>.Default;
    const int XOR_BITS = 10;
    const int ADD_BITS = 11;
    const int MUL_BITS = 11;
    Debug.Assert(XOR_BITS + ADD_BITS + MUL_BITS == 32);
    int xor_total = 0;
    int add_total = 0;
    int mul_total = 17;
    unchecked
    {
        foreach (T element in source)
        {
            var hashcode = comparer.GetHashCode(element);
            int xor_part = hashcode >> (32 - XOR_BITS);
            int add_part = hashcode << XOR_BITS >> (32 - ADD_BITS);
            int mul_part = hashcode << (32 - MUL_BITS) >> (32 - MUL_BITS);
            xor_total = xor_total ^ xor_part;
            add_total = add_total + add_part;
            if (mul_part != 0) mul_total = mul_total * mul_part;
        }
        xor_total = xor_total % (1 << XOR_BITS); // Compact
        add_total = add_total % (1 << ADD_BITS); // Compact
        mul_total = mul_total - 17; // Subtract initial value
        mul_total = mul_total % (1 << MUL_BITS); // Compact
        int result = (xor_total << (32 - XOR_BITS)) + (add_total << XOR_BITS) + mul_total;
        return result;
    }
}

The performance is almost identical with the simple XOR method, because the call to GetHashCode of each element dominates the CPU demand.

참고URL : https://stackoverflow.com/questions/670063/getting-hash-of-a-list-of-strings-regardless-of-order