Using a logical array as a user dictionary key

Question

I am trying to make a dictionary in C # that uses a boolean array for its keys.

Dictionary<bool[], string> 

the bool array has a fixed length of 1000 and all have the same length. I am having problems with a hash code, and the generic "exclusive" or "method doesn't make much sense because of the length of the array."

Similar StackOverflow questions are addressed using the "exclusive" or "GetHashCode method". I do not think this works in this context. I would like to use it like:

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

where EquaityComparer does something like:

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

Of course, all the usual problems associated with changing the bool array, and the size of any derived key related to performance, are here ... although I have no solution.

Answer 1

Both Equals and HashCode are incorrect.

Presumably you want to use SequenceEqual to compare arrays for equality or just for a loop.

To calculate the hash code, you can use any of the standard methods. It is very important that if two elements are compared in the same way, they must have the same hash.

Example

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

Similar

• Guidelines and rules for GetHashCode

Answer 2

For performance and consistency, I would recommend storing your bool[] in another class. You already know that the key may not change, so you can take advantage of this by storing the hash in the key class. Dictionary internal operations can use this hash several times for single access (we do not need to know the internal implementation details, so it’s best to assume that this can be done many times).

For performance, you can still access or even save the link to bool[] from the outside, but the safest method is to make a safe copy in the key class.

 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 hash implementation here, store the result in `hash`. } return hash; } } 

If you expect a frequent hash value of 0, you can use another bool variable to indicate whether there was a computed value.

Answer 3

For best performance, do not use the bool [] array, which will make hashing and comparison very slow. For example, you can store the same information in a 1/32 Uint32 [] array, making hashing and comparison much faster.

If you are storing a bool [] array, consider using unsafe code for hashing / comparison.

If you want to use only safe code, at least remove the condition in a loop:

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

Also compare, using your own loop, should be faster than SequenceEqual

Answer 4

The implementation rule for GetHashCode is that any two identical objects must generate the same hash code. One recommendation is to have as few collisions as possible (this is not a requirement for hash codes to be unique).

In this implementation, the BitArray class is used to take your logical array in groups of 32, treat them as bits, and calculate the hash code of the resulting 32-bit integers:

 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 hash code return ints.Aggregate((i1, i2) => i1 ^ i2).GetHashCode(); }