gpt4 book ai didi

c# - 为 BitArray 生成良好的哈希码 (GetHashCode)

转载 作者:太空狗 更新时间:2023-10-29 23:27:05 25 4
gpt4 key购买 nike

我需要在 GetHashCode 中为 BitArray 生成一个快速哈希码。我有一个字典,其中的键是 BitArray,并且所有 BitArray 的长度都相同。

有谁知道从可变位数生成良好散列的快速方法,就像在这种情况下一样?

更新:

我最初采用的方法是直接通过反射访问内部的整数数组(在这种情况下速度比封装更重要),然后对这些值进行异或。 XOR 方法似乎运行良好,即在字典中搜索时,我的“等于”方法没有被过度调用:

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

但是,Mark Byers 建议并在 StackOverflow 其他地方看到的方法稍微好一些(16570 Equals calls vs 16608 for XOR for XOR for my test data)。请注意,此方法修复了前一个中的错误,即超出位数组末尾的位可能会影响哈希值。如果位数组的长度减少,就会发生这种情况。

    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
}

欢迎提出任何改进建议!

最佳答案

在字典中充当键是一个糟糕的类。实现 GetHashCode() 的唯一合理方法是使用其 CopyTo() 方法将位复制到 byte[]。这不是很好,它会产生大量垃圾。

乞求、偷窃或借用 BitVector32 代替。它有一个很好的 GetHashCode() 实现。如果你有超过 32 位,那么考虑旋转你自己的类,这样你就可以到达底层数组而无需复制。

关于c# - 为 BitArray 生成良好的哈希码 (GetHashCode),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3125676/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com