Tạo mã băm tốt (GetHashCode) cho một BitArray

Question

Tôi cần tạo mã băm nhanh trong GetHashCode cho một BitArray. Tôi có một từ điển mà các khóa là BitArrays, và tất cả các BitArrays có cùng độ dài.

Có ai biết cách nhanh chóng để tạo ra băm tốt từ số bit thay đổi, như trong trường hợp này không?

UPDATE:

Cách tiếp cận ban đầu tôi mất đã để truy cập mảng nội ints trực tiếp thông qua phản xạ (tốc độ là quan trọng hơn cả đóng gói trong trường hợp này), sau đó XOR những giá trị đó. Cách tiếp cận XOR dường như làm việc tốt tức là của tôi 'Equals' phương pháp không được gọi là quá mức khi tìm kiếm trong từ điển:

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

Tuy nhiên, cách tiếp cận đề nghị Mark Byers và nhìn thấy ở đâu đó trên StackOverflow là tốt hơn một chút (16.570 Equals cuộc gọi so với 16608 cho XOR cho dữ liệu thử nghiệm của tôi). Lưu ý rằng cách tiếp cận này sửa lỗi trong phần trước, trong đó bit ngoài phần cuối của mảng bit có thể ảnh hưởng đến giá trị băm. Điều này có thể xảy ra nếu mảng bit bị giảm độ dài.

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; 
    } 

Các GetInternalValues ​​phương pháp khuyến nông được thực hiện như thế này:

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 
} 

Bất kỳ đề xuất cải tiến được hoan nghênh!

Answer 1

Nếu mảng bit là 32 bit hoặc ngắn hơn thì bạn chỉ cần chuyển đổi chúng thành số nguyên 32 bit (đệm với bit không nếu cần).

Nếu chúng có thể dài hơn, bạn có thể chuyển đổi chúng thành chuỗi số nguyên 32 bit và XOR hoặc tốt hơn: sử dụng thuật toán được mô tả trong Java hiệu dụng.

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

Lấy từ here. Trường 1, trường2 sửa đổi 32 bit đầu tiên, 32 bit thứ hai, v.v.

Answer 2

Đây là một lớp khủng khiếp hoạt động như một khóa trong từ điển. Cách hợp lý duy nhất để thực hiện GetHashCode() là sử dụng phương thức CopyTo() của nó để sao chép các bit thành một byte []. Đó không phải là tuyệt vời, nó tạo ra một tấn rác.

Bắt đầu, đánh cắp hoặc mượn để sử dụng BitVector32 thay thế. Nó có một triển khai tốt cho GetHashCode(). Nếu bạn đã có hơn 32 bit thì hãy xem xét quay lớp của riêng bạn để bạn có thể truy cập vào mảng cơ bản mà không phải sao chép.