HashSet和Dictionary的C＃性能替代品，不使用GetHashCode

Question

我正在寻找HashSet和Dictionary对象的内置替代品，这些对象具有比列表更好的性能但不使用内部GetHashCode方法。我需要这个，因为对于我写的课程，没有办法编写一个GetHashCode方法来实现与Equals的通常合同，而不是

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

这将把HashSet和Dictionary变成普通的名单（表现明智）。

所以我需要的是一个set实现和一个映射实现。有什么建议？

编辑：

我的类是基于容差的三维矢量类：

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方法不具有传递性。但是，在我的用例中，我可以使它“本地”传递，因为在某些时候，我将知道我需要放入我的set / mapping键集中的所有向量，并且我也知道它们将成簇。因此，当我收集了所有向量时，我将为每个簇选择一个代表，并由代表替换所有原始向量。然后Equals将在我的set / mapping键集的元素之间传递。

当我有我的设置或映射时，我将从另一个源收集向量（为了这个问题，让我们假设我会要求用户输入一个向量）。这些可以是任何可能的载体。那些永远不会被添加到集合/映射中，但我需要知道它们是否包含在映射的集合/密钥集中（关于容差），我需要从映射中知道它们的值。

Answer 1

您需要一个支持排序，二进制搜索和快速插入的数据结构。不幸的是，.NET Framework中没有这样的集合。 SortedDictionary不支持二进制搜索，而SortedList因未分类数据的O（n）插入而受到影响。所以你必须搜索第三方工具。一个好的候选人似乎是TreeDictionary图书馆的C5。这是一个红黑树实现，提供重要的方法RangeFromTo。这是一个不完整的Dictionary实现，它将Vectors作为键，由C5.TreeDictionary内部支持：

public class VectorDictionary<TValue>
{
    private 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

Answer 2

在您的情况下，您可以获得相当好的哈希码实现。请记住，哈希代码最重要的规则如下：

• 两个相等的向量必须返回相同的值

这并不意味着两个不同的向量不能返回相同的值;他们显然必须在某些情况下，哈希的数量是有限的，用于所有目的的不同向量的数量不是。

那么，考虑到这一点，只需根据截断到公差的有效数字减去1的向量坐标来评估哈希码。所有相等的向量将为您提供相同的哈希值和一小部分非等值向量，这些向量在最后一个十进制数字中不同...您可以使用它。

更新：已更改舍入为截断。舍入不是正确的选择。