7

我正在尝试在 C# 中创建一个使用布尔数组作为其键的字典。

 Dictionary<bool[], string>

bool 数组的长度固定为 1000，并且都是相同的长度。我在使用哈希码时遇到问题，并且由于数组的长度，“异或”的常用方法没有多大意义。

StackOverflow 上的类似问题通过 GetHashCode 方法中的“异或”来解决。我认为这在这种情况下是行不通的。我想将其用作：

 Dictionary<bool[], string> myDict = 
             new Dictionary<bool[], string>(EqualityComparer);

其中 EquaityComparer 执行以下操作：

   public class EqualityComparer : IEqualityComparer<bool[]>
    {
        public bool Equals(bool[] x, bool[] y)
        {
            return x.SequenceEqual(y);
        }

        public int GetHashCode(bool[] x)
        {
            // this part doesn't work correctly
            int hc = x.GetHashCode();
            return hc;
        }
    }

当然，关于 bool 数组是可变的以及与性能相关的任何派生键的大小的所有常见问题都适用于此……尽管我没有解决方案。

4

4 回答 4

8

你的Equals和HashCode都是不正确的。

大概您希望用于SequenceEqual比较数组是否相等，或者使用简单的 for 循环。

要计算哈希码，您可以使用任何标准方法。如果两个项目比较相等，那么它们必须具有相同的哈希，这一点非常重要。

例子

public int GetHashCode(bool[] x)
{
    int result = 29;
    foreach (bool b in x)
    {
        if (b) { result++; }
        result *= 23;
    }
    return result;
}

有关的

于 2012-07-17T17:42:06.010 回答
1

为了性能和一致性，我建议将您存储bool[]在另一个类中。您已经知道密钥可能不会更改，因此您可以通过将哈希存储在密钥类中来利用这一点。字典内部操作可能会多次使用这个散列来进行一次访问（尽管我们不应该知道内部实现细节，所以最好假设这可能会执行很多次）。

为了性能，您可能仍希望访问甚至保留对bool[]外部的引用，但最安全的技术是在密钥类中制作安全副本。

public class BoolArrayKey
{
    private int hash;
    private bool[] data;

    public BoolArrayKey(bool[] source)
    {
        data = new bool[source.Length];
        Array.Copy(source, data, source.Length);
    }

    public override bool Equals(object obj)
    {
        BoolArrayKey other = obj as BoolArrayKey;
        if (other == null)
        {
            return false;
        }

        return other.data.SequenceEqual(data);
    }

    public override int HashCode()
    {
        if (hash == 0)
        {
            // Mark's hash implementation here, store the result in `hash`.
        }

        return hash;    
    }
}

如果您期望频繁的哈希值为 0，那么您可以使用另一个bool变量来指示该值是否已被计算。

于 2012-07-17T19:33:09.900 回答
0

为了获得最佳性能，不要使用 bool[] 数组，这会使散列和比较非常慢。例如，您可以将相同的信息存储在长度为 1/32 的 Uint32[] 数组中，从而使散列和比较更快。

如果您保留 bool[] 数组，请考虑使用不安全的代码进行散列/比较。

如果您只想使用安全代码，请至少在循环中删除条件：

hash = hash * 3 + (int) x[i];

还比较使用自己的循环应该比 SequenceEqual 快

于 2012-07-17T18:39:45.363 回答
0

实现 GetHashCode 的规则是任何两个相等的对象必须生成相同的哈希码。一个指导方针是尽可能少地发生冲突（哈希码不是唯一的要求）。

此实现使用 BitArray 类以 32 组为一组获取布尔数组，将它们视为位并计算生成的 32 位整数的哈希码：

public int GetHashCode(bool[] x)
{
    // Trivial case
    if (x.Length == 0) return 0;

    // Convert the bool array to a BitArray to use framework functions
    BitArray binary = new BitArray(x);

    //Determine the max # of 32-bit INTS this array represents
    int intLength = (x.Length-1)/32 + 1;
    int [] ints = new int[intLength];

    // Copy each block of 32-bits to an int
    binary.CopyTo(ints, 0);

    // Take the exclusive OR of each int and return the result's hash code
    return ints.Aggregate((i1, i2) => i1 ^ i2).GetHashCode();
}
于 2012-07-17T18:42:34.413 回答