Using a Boolean Array as Custom 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 fixed length of 1000, and all are the same length. I'm having trouble with the hashcode and the common method of an 'exclusive or' doesn't make as much sense because of the length of the array.

Similar questions on StackOverflow are addressed with the 'exclusive or' in the GetHashCode method. I don't think that works in this context. I would like to use it as:

 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 of the usual concerns about the bool array being mutable and the size of any derived key being relevant to performance apply here...though I don't have a solution.

Answer 1

For performance and consistency I would recommend storing your bool[] in another class. You know already that the key may not change so you can take advantage of this by storing the hash in the key class. The dictionary internal operations may use this hash multiple times for a single access (we are not supposed to have to know the internal implementation details though so it's best to assume this may be executed many times).

For performance you may still want to access or even keep a reference to the bool[] externally but the safest technique would be 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's hash implementation here, store the result in `hash`.
        }

        return hash;    
    }
}

If a you expect a frequent hash value of 0 then you could use another bool variable to indicate if the value had been computed.

Answer 2

Both your Equals and HashCode are incorrect.

Presumably you wish to use SequenceEqual to compare the arrays for equality, or else a simple for loop.

To calculate a hashcode you can use any of the standard methods. It is very important that if two items compare equal then 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;
}

Related

• Guidelines and rules for GetHashCode