BitArray에 대한 좋은 해시 코드 (GetHashCode) 생성

Question

BitArray에 대해 GetHashCode에서 빠른 해시 코드를 생성해야합니다. 나는 키가 BitArrays이고, 모든 BitArray가 같은 길이 인 사전을 가지고있다.

누구나이 시나리오에서와 같이 다양한 비트 수에서 좋은 해시를 생성하는 빠른 방법을 알고 있습니까?

업데이트 : 원래했다

접근 한 다음 그 값을 XOR, (속도가이 경우에 캡슐화보다 더 중요하다) 직접 반사를 통해 int 치의 내부 배열에 액세스하는 것이 었습니다. (

public int GetHashCode(BitArray array) 
    { 
     int hash = 0; 
     foreach (int value in array.GetInternalValues()) 
     { 
      hash ^= value; 
     } 
     return hash; 
    } 

그러나, 마크 바이어스에 의해 제안 및 다른 StackOverflow의에 볼 수있는 방법이 약간 더 나았다 16,570 같음을 내는 '같음'즉, XOR 방식은 사전에 검색 할 때 방법이 과도하게 호출되지 않습니다 잘 작동하는 것 같다 내 테스트 데이터 용 XOR에 대해 16608을 호출). 이 방법은 비트 배열의 끝에있는 비트가 해시 값에 영향을 줄 수있는 이전 버그의 버그를 수정합니다. 비트 배열의 길이가 줄어들면 이런 현상이 발생할 수 있습니다.

public int GetHashCode(BitArray array) 
    { 
     UInt32 hash = 17; 
     int bitsRemaining = array.Length; 
     foreach (int value in array.GetInternalValues()) 
     { 
      UInt32 cleanValue = (UInt32)value; 
      if (bitsRemaining < 32) 
      { 
       //clear any bits that are beyond the end of the array 
       int bitsToWipe = 32 - bitsRemaining; 
       cleanValue <<= bitsToWipe; 
       cleanValue >>= bitsToWipe; 
      } 

      hash = hash * 23 + cleanValue; 
      bitsRemaining -= 32; 
     } 
     return (int)hash; 
    } 

GetInternalValues ​​확장 방법은 다음과 같이 구현됩니다 개선을위한

public static class BitArrayExtensions 
{ 
    static FieldInfo _internalArrayGetter = GetInternalArrayGetter(); 

    static FieldInfo GetInternalArrayGetter() 
    { 
     return typeof(BitArray).GetField("m_array", BindingFlags.NonPublic | BindingFlags.Instance); 
    } 

    static int[] GetInternalArray(BitArray array) 
    { 
     return (int[])_internalArrayGetter.GetValue(array); 
    } 

    public static IEnumerable<int> GetInternalValues(this BitArray array) 
    { 
     return GetInternalArray(array); 
    } 

... more extension methods 
} 

모든 제안을 환영합니다!

Answer 1

비트 배열이 32 비트 이하이면 32 비트 정수로 변환하면됩니다 (필요한 경우 0 비트가 채워짐).

더 길면 32 비트 정수로 변환하고 XOR 또는 그 이상을 사용할 수 있습니다. 효과적인 Java에 설명 된 알고리즘을 사용하십시오.

public int GetHashCode() 
{ 
    int hash = 17; 
    hash = hash * 23 + field1.GetHashCode(); 
    hash = hash * 23 + field2.GetHashCode(); 
    hash = hash * 23 + field3.GetHashCode(); 
    return hash; 
} 

취지 : here. field1, field2는 처음 32 비트, 두 번째 32 비트 등을 나타냅니다.

Answer 2

사전에서 키 역할을하는 끔찍한 클래스입니다. GetHashCode()를 구현하는 유일한 방법은 CopyTo() 메서드를 사용하여 비트를 byte []로 복사하는 것입니다. 별로 좋지 않습니다. 쓰레기를 만듭니다.

대신에 BitVector32를 사용하려면 도용하거나 빌리십시오. 그것은 GetHashCode()에 대한 좋은 구현을 가지고있다. 32 비트 이상인 경우 클래스를 회전하여 복사하지 않고도 기본 배열로 이동할 수 있습니다.