爲BitArray生成一個好的哈希碼（GetHashCode）

我需要在GetHashCode中爲BitArray生成一個快速哈希碼。我有一個字典，其中的鍵是BitArrays，並且所有的BitArrays長度相同。爲BitArray生成一個好的哈希碼（GetHashCode）

有沒有人知道一個快速的方法來從可變數量的位生成一個好的散列，就像在這種情況下一樣？

UPDATE：

我原先採取的方法是直接通過反射來訪問整數的內部陣列（速度比在這種情況下的封裝更重要），然後異或這些值。異或方法似乎運作良好，即我的「等於」在字典搜索時方法不叫過度：

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

然而，馬克拜爾斯建議和StackOverflow上其他地方看到的做法稍好（16570點的Equals我的測試數據用XOR調用vs 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 
}

任何改進建議，歡迎！

來源

2010-06-26 bart

如果位數組是32位或更短，那麼您只需將它們轉換爲32位整數（如果需要，填充零位）。

如果它們可能更長，那麼可以將它們轉換爲一系列32位整數並異或，或者更好：使用Effective 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。字段1，字段2對應於前32位，後32位等。

來源

2010-06-26 22:35:30

我已經看到你的方法在其他地方提到過，但我並不真正理解它背後的理論或選擇'魔術'素數。這種方法比我原先採用的異或方法稍微有效（對於我的測試數據，異或爲16570等於16608）。查看我的編輯瞭解更多細節。 – bart 2010-06-29 10:21:02

這是一個可怕的類，充當字典中的關鍵字。實現GetHashCode（）的唯一合理方法是使用其CopyTo（）方法將位複製到byte []中。這不是很好，它會產生大量的垃圾。

請求，竊取或借用BitVector32來代替。它對GetHashCode（）有很好的實現。如果你有超過32位，那麼考慮旋轉你自己的類，這樣你就可以進入底層數組而不必複製。

來源

2010-06-27 13:28:01

我需要超過32位。我正在考慮編寫我自己的類（來自Reflector的一些幫助），但沒有充分利用內置的BitArray似乎是一種恥辱。有點反省黑客給了我內部數組，這當然可以在未來版本的框架中改變 - 例如64位版本可能在64位硬件上效率更高。不過，我現在對這個解決方案很滿意。 – bart 2010-06-29 10:27:08

爲BitArray生成一個好的哈希碼（GetHashCode）

回答

相關問題