Alternative to increasingly slow Dictionary.Add(Key,Value)?

Question

By "increasingly" what I mean is that Add is fast at the beginning when there is a low number of keys. After inserting 20% of the keys, it gets very slow. After 50% it gets unbearably slow.

I get that the lower the number of keys, the faster the "key collision search" when adding new elements to the dictionary. But is there any possible way to skip this downside while keeping the Dictionary? I know beforehand that keys don't collide so no check is needed, but I don't know if there is any way to successfully use this info in the code.

BTW I am forced to use the dictionary structure because of architecture restrictions (this structure is swallowed later by a db exporter).

---

What my code does:

var keyList = GetKeyList();
var resultDict = new Dictionary<T,T>();
foreach (var key in keyList)
{
    resultDict.Add(key,someResult);
}

---

Edit: since people is asking how the hash code is generated, I will try to clarify this.

Theoretically I have no control over the hash code generation, because unfortunately it uses a convention between multiple systems that are connected through the same db.

In practice, the piece of code that generates the hash code is indeed my code (disclaimer: it wasn't me choosing the convention that is used in the generation).

The key generation is way more complicated than that, but it all boils down to this:

private List<ResultKey> GetKeyList(string prefix, List<float> xCoordList, List<float> yCoordList)
{
    var keyList = new List<ResultKey>();
    var constantSensorName = "xxx";
    foreach (float xCoord in xCoordList)
    {
        foreach (float yCoord in yCoordList)
        {
            string stationName = string.Format("{0}_E{1}N{2}", prefix, xCoord, yCoord);
            keyList.Add(new ResultKey(constantSensorName, stationName));
        }
    }
    return keyList;
}

public struct ResultKey
{
    public string SensorName { get; set; }
    public string StationName { get; set; }

    public ResultKey(string sensorName, string stationName)
    {
        this.SensorName = sensorName;
        this.StationName = stationName;
    }
}

Answer 1

The first thing that comes to mind is to create your own hashing function. The Add method for the dictionary is going to call the default implementation of the getHashCode() method when it goes to add it to the structure. If you put a wrapper class around your keys and overwrote the getHashCode() method, then you could write your own hashing function which, presumably, could implement a less collision prone hash function.

Answer 2

You are using the default hash code generation for your struct ResultKey. The default hash code generation for structs is disappointingly bad. You can't rely on that here because your struct contains two strings which trigger a bad case (see the linked answer). Essentially, only your SensorName field makes it into the hash code, nothing else. That causes all keys with the same SensorName to collide.

Write your own function. I quickly generated one using Resharper:

public struct ResultKey : IEquatable<ResultKey>
{
    public string SensorName { get; set; }
    public string StationName { get; set; }

    public ResultKey(string sensorName, string stationName)
    {
        this.SensorName = sensorName;
        this.StationName = stationName;
    }

    public bool Equals(ResultKey other)
    {
        return string.Equals(SensorName, other.SensorName) && string.Equals(StationName, other.StationName);
    }

    public override bool Equals(object obj)
    {
        if (ReferenceEquals(null, obj)) return false;
        return obj is ResultKey && Equals((ResultKey)obj);
    }

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

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

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

Answer 3

Your ResultKey contains two strings, so you need a hashcode that combine them.

"How do I calculate a good hash code for a list of strings?" contains some answer showing how to do this.

However you get do a lot worse then

public override int GetHashCode()
{   
   return (SensorName + StationName).GetHashCode();
}

Answer 4

If you just want to fulfill API requirements and need a dirty solution, you could implement your own Dictionary.

public class FakeFastDictionary<TKey, TValue> : Dictionary<TKey, TValue>
{
    protected IList<KeyValuePair<TKey, TValue>> _list
        = new List<KeyValuePair<TKey, TValue>>();

    public new void Add(TKey key, TValue value)
    {
        _list.Add(new KeyValuePair<TKey, TValue>(key, value));
    }

    public new ICollection<TValue> Values
    {

        get
        {
            // there may be faster ways to to it:
            return _list.Select(x => x.Value).ToArray();
        }
    }

    public new ICollection<TKey> Keys
    {
        get
        {
            // there may be faster ways to to it:
            return _list.Select(x => x.Key).ToArray();
        }
    }
}

This is a running sample: https://dotnetfiddle.net/BDyks0