Request for Comments: fast hashed base class for dictonary keys

Question

In one of my aplications I have to use many dictonarys with custom objects as keys. To improve the performance of the lookups I implemetet an base class that overrites GetHashCode. It seams to work but somehow I still have a bad fealing about it so I decided to post my code and I would be gratefull for any tips or coments. (omg I forgot the code :D )

abstract class FastHashed
{
    private static Dictionary<Type,ulong> _instanceCounters = new Dictionary<Type,ulong>();

    private int hash;

    protected FastHashed()
    {
        Type instanceType = this.GetType();
        if(! _instanceCounters.ContainsKey(instanceType)) _instanceCounters.Add(instanceType,0);  
        this.hash = ((instanceType.ToString())+(_instanceCounters[instanceType]++.ToString())).GetHashCode();
    }

    public override int  GetHashCode()
    {
         return hash;
    }
}

Edit: Do not mess with the hashing if you do not have to. This "sollution" is slower and less reliable then the default GetHashCode().

Edit: I did some performance testing with the Equatec profiler and a simple console aplication.

class Program { static readonly int cycles = 50000; static Dictionary objectsDict = new Dictionary(); static Dictionary foosDict = new Dictionary();

    static void Main(string[] args)
    {

        foo[] foos = new foo[cycles];
        object[] objects = new object[cycles];


        for (int i = 0; i < cycles; i++)
        {
            foos[i] = new foo();
            objects[i] = new object();
            foosDict.Add(foos[i], i);
            objectsDict.Add(objects[i], i);
        }

        ObjectHash(objects);
        FooHash(foos);

    }

    static void ObjectHash(Object[] objects)
    {
        int value; 
        for (int i = 0; i < cycles; i++)
        {
            value = objectsDict[objects[i]];
        }

    }
    static void FooHash(foo[] foos)
    {
        int value;
        for (int i = 0; i < cycles; i++)
        {
            value = foosDict[foos[i]];
        }
    }

    class foo
    {
        private readonly int _hash;
        public foo()
        {
            _hash = this.GetHashCode();
        }
        public override int GetHashCode()
        {
            return _hash;
        }
    }
}

The results: - FooHash 26 774 ms - ObjectHash 7 ms

Obviously the defualt GetHashCode is the best choice.

Answer 1

1. This is not thread-safe.
2. If you only care about reference equality, why do you have different counters for different types?

If all you want is to prevent Hashes from being computed multiple times, why not something like this (or a variant with generics if the dictionary will only hold objects of a certain type):

  public class ObjectWithCachedHashCode : IEquatable<ObjectWithCachedHashCode>
    {
        private int _cachedHashCode;

        public object Object { get; private set; }

        public ObjectWithCachedHashCode(object obj)
        {
            Object = obj;
            _cachedHashCode = obj.GetHashCode();
        }

        public override int GetHashCode()
        {
            return _cachedHashCode;
        }

        public bool Equals(ObjectWithCachedHashCode other)
        {
            return other!=null && Object.Equals(other.Object);
        }

        public override bool Equals(object other)
        {
            return Equals(other as ObjectWithCachedHashCode);
        }


    }

Edit: Made class compatible with Dictionary

Answer 2

You can mark the hash variable readonly.

But to be honest, in C# where you have single inheritance it is not always wise to "waste" the inheritance to implement such specific behavior. Suppose you suddenly wants to inherit from a base class that "does" something. Save class inheritance to modelling purposes, not implementing details.

Answer 3

As far as I can see, this is just functionally equivalent to the object.GetHashCode() default implemntation, apart from being slower and non thread-safe. What is it that makes "Fast Hash" fast?