使用布尔数组作为自定义字典键

Question

我想在C＃中使用布尔数组作为其键的字典。

Dictionary<bool[], string> 

布尔数组的固定长度为1000，并且都是相同的长度。由于数组的长度，我在散列码方面遇到了问题，而'exclusive or'的通用方法并没有那么有意义。

StackOverflow上的类似问题在GetHashCode方法中用'exclusive或'来解决。我不认为这在这方面起作用。我想用它作为：

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

当然，所有关于布尔数组是可变的普遍关注和任何派生密钥是有关大小以性能适用于此...虽然我没有解决方案。

Answer 1

您的Equals和HashCode都不正确。

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

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

例

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

相关

• Guidelines and rules for GetHashCode

Answer 2

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

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

如果你只想使用安全的代码，至少去除有条件的循环：

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

而且比较使用自己的循环应该比SequenceEqual

更快

Answer 3

实现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(); 
} 

Answer 4

对于性能和一致性我想建议将您的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变量来表示如果该值已经计算。