替代日益慢的Dictionary.Add(Key,Value)？

Question

通过"越来越多"我的意思是,Add当密钥数量较少时,开始时速度很快.插入20%的键后,它变得非常慢.在50%之后它变得无法忍受地缓慢.

我得到的是,键的数量越少,向字典添加新元素时"键碰撞搜索"的速度就越快.但有没有什么方法可以在保持这种情况的同时跳过这个缺点Dictionary？我事先知道密钥不会碰撞所以不需要检查,但我不知道是否有任何方法可以在代码中成功使用此信息.

顺便说一句,由于体系结构的限制,我不得不使用字典结构(这个结构后来被db导出器吞噬).

---

我的代码做了什么:

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

---

编辑:由于人们在询问如何生成哈希码,我将尝试澄清这一点.

从理论上讲,我无法控制哈希码生成,因为不幸的是它使用了通过同一个数据库连接的多个系统之间的约定.

在实践中,生成哈希码的代码片段确实是我的代码(免责声明:我不是选择在代中使用的约定).

密钥生成比这更复杂,但这一切都归结为:

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

首先想到的是创建自己的散列函数.当将字典添加到结构时,字典的Add方法将调用getHashCode()方法的默认实现.如果你在你的键周围放置了一个包装类并覆盖了getHashCode()方法,那么你可以编写自己的哈希函数,这可能会实现一个不易发生碰撞的哈希函数.

Answer 2

您正在为 struct 使用默认的哈希代码生成ResultKey。结构的默认哈希代码生成非常糟糕。您不能在这里依赖它，因为您的结构包含两个会触发不良情况的字符串（请参阅链接的答案）。本质上，只有您的SensorName字段才能进入哈希码，没有其他字段。这会导致所有具有相同键的键SensorName发生冲突。

编写您自己的函数。我使用 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);
    }
}