不使用 GetHashCode 的 HashSet 和 Dictionary 的 C# 高性能替代品

Question

我正在寻找比列表具有更好性能但不使用内部 GetHashCode 的 HashSet 和 Dictionary 对象的内置替代品> 方法。我需要这个，因为对于我编写的类，除了

public override int GetHashCode() { return 0; } // or return any other constant value

这会将 HashSet 和 Dictionary 变成普通列表(性能方面)。

所以我需要的是集合实现和映射实现。有什么建议吗？

编辑:

我的类是一个基于公差的 3 维向量类:

public class Vector
{
    private static const double TOL = 1E-10;
    private double x, y, z;

    public Vector(double x, double y, double z)
    {
        this.x = x; this.y = y; this.z = z;
    }

    public override bool Equals(object o)
    {
        Vector other = o as Vector;

        if (other == null)
            return false;

        return ((Math.Abs(x - other.x) <= TOL) &&
                (Math.Abs(y - other.y) <= TOL) &&
                (Math.Abs(z - other.z) <= TOL));
    }
}

请注意，我的 Equals 方法不是可传递的。但是，在我的用例中，我可以使它“本地”传递，因为在某些时候，我会知道我需要放入我的集合/映射键集中的所有向量，而且我也知道它们会成簇出现。因此，当我收集了所有向量后，我将为每个簇选择一个代表，并用该代表替换所有原始向量。然后 Equals 将在我的集合/映射键集的元素之间传递。

当我有我的集合或映射时，我会从另一个来源收集向量(为了这个问题，我们假设我会要求用户输入一个向量)。这些可以是任何可能的向量。这些永远不会添加到集合/映射中，但我需要知道它们是否包含在映射的集合/键集中(关于容差)，并且我需要从映射中知道它们的值。

Answer 1

你需要一个支持排序、二分查找和快速插入的数据结构。不幸的是，.NET Framework 中没有这样的集合。 SortedDictionary 不支持二进制搜索，而 SortedList 对于未排序的数据插入 O(n)。所以你必须搜索第三方工具。 C5 的 TreeDictionary 似乎是一个不错的选择。图书馆。它是一个红黑树实现，提供了重要的方法RangeFromTo。这是一个不完整的字典实现，它以向量作为键，由 C5.TreeDictionary 内部支持:

public class VectorDictionary<TValue>
{
    private readonly C5.TreeDictionary<double, (Vector, TValue)> _tree =
        new C5.TreeDictionary<double, (Vector, TValue)>();

    public bool TryGetKeyValue(Vector key, out (Vector, TValue) pair)
    {
        double xyz = key.X + key.Y + key.Z;
        // Hoping that not all vectors are crowded in the same diagonal line
        var range = _tree.RangeFromTo(xyz - Vector.TOL * 3, xyz + Vector.TOL * 3);
        var equalPairs = range.Where(e => e.Value.Item1.Equals(key));
        // Selecting a vector from many "equal" vectors is tricky.
        // Some may be more equal than others. :-) Lets return the first for now.
        var selectedPair = equalPairs.FirstOrDefault().Value;
        pair = selectedPair;
        return selectedPair.Item1 != null;
    }

    public Vector GetExisting(Vector key)
    {
        return TryGetKeyValue(key, out var pair) ? pair.Item1 : default;
    }

    public bool Contains(Vector key) => TryGetKeyValue(key, out var _);

    public bool Add(Vector key, TValue value)
    {
        if (Contains(key)) return false;
        _tree.Add(key.X + key.Y + key.Z, (key, value));
        return true;
    }

    public TValue this[Vector key]
    {
        get => TryGetKeyValue(key, out var pair) ? pair.Item2 : default;
        set => _tree.Add(key.X + key.Y + key.Z, (key, value));
    }

    public int Count => _tree.Count;
}

使用示例:

var dictionary = new VectorDictionary<int>();
Console.WriteLine($"Added: {dictionary.Add(new Vector(0.5 * 1E-10, 0, 0), 1)}");
Console.WriteLine($"Added: {dictionary.Add(new Vector(0.6 * 1E-10, 0, 0), 2)}");
Console.WriteLine($"Added: {dictionary.Add(new Vector(1.6 * 1E-10, 0, 0), 3)}");
Console.WriteLine($"dictionary.Count: {dictionary.Count}");
Console.WriteLine($"dictionary.Contains: {dictionary.Contains(new Vector(2.5 * 1E-10, 0, 0))}");
Console.WriteLine($"dictionary.GetValue: {dictionary[new Vector(2.5 * 1E-10, 0, 0)]}");

输出:

Added: True
Added: False
Added: True
dictionary.Count: 2
dictionary.Contains: True
dictionary.GetValue: 3