C#: optimizing dictionary access (hash in key structures)

Question

So, I need to create a struct in C# that will act as a key into a (quite large) dictionary, will look like this:

private readonly IDictionary<KeyStruct, string> m_Invitations;

Problem is, I REALLY need a struct to use as a key, because it is only possible to identify entries via two separate data items, where one of them can be a null (not only empty!) string.

What will I need to implement on the struct? How would you go about creating the hash? Would a hash collision (occassional) hurt the performance heavily or would that be negligible?

I'm asking because this is "inner loop" code.

Answer 1

You need to implement (override) two methods.
1. bool Equals(object)
2. int GetHashCode()

The hash code need not be unique but the less different objects will return the same hash code the better performance you will have.

you can use something like:

public int GetHashCode()
{
    int strHash = str == null ? 0 : str.GetHashCode();
    return ((int)lng*397) ^  strHash;
}

Answer 2

If KeyStruct is structure (declared with struct C# keyword), don't forget to override Equals and GetHash code methods, or provide custom IEqualityComparer to dictionary constructor, because default implementation of ValueType.Equals method uses Reflection to compare content of two structure instances.

It is prefer to make KeyStruct immutable, if you do so, you can calculate structure instance hash once and then simply return it from GetHashCode method. But it may be premature optimization, depends of how often do you need to get value by key.

Generally, it is OK to use structure as a dictionary key.

Or maybe you are asking how to implement GetHashCode method?

Answer 3

If you have resharper, you can generate these method with Alt-Ins -> Equality members.

Here is the generated code for you KeyStruct:

public struct KeyStruct : IEquatable<KeyStruct>
{
    public string Value1 { get; private set; }
    public long Value2 { get; private set; }

    public KeyStruct(string value1, long value2)
        : this()
    {
        Value1 = value1;
        Value2 = value2;
    }

    public bool Equals(KeyStruct other)
    {
        return Equals(other.Value1, Value1) && other.Value2 == Value2;
    }

    public override bool Equals(object obj)
    {
        if (ReferenceEquals(null, obj)) return false;
        if (obj.GetType() != typeof (KeyStruct)) return false;
        return Equals((KeyStruct) obj);
    }

    public override int GetHashCode()
    {
        unchecked
        {
            return ((Value1 != null ? Value1.GetHashCode() : 0)*397) ^ Value2.GetHashCode();
        }
    }

    public static bool operator ==(KeyStruct left, KeyStruct right)
    {
        return left.Equals(right);
    }

    public static bool operator !=(KeyStruct left, KeyStruct right)
    {
        return !left.Equals(right);
    }
}