为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）

回答

相关问题