C# - 使用自定义键定义哈希集合

Question

我正在使用C#中的HashSet和Dictionary来实现一个图结构。 当HashSet的键为自定义类时，我遇到了HashSet元素唯一性的问题。下面是我的代码：

public class Point
{
    public int x { get; set; }
    public int y { get; set; }
}

public class Vertex
{
    public Vertex(Point point)
    {
        VertexLabel = point;
    }

    public Point VertexLabel { get; private set; }
}

public class Edge
{
    public Edge(Vertex to, Vertex from, double weight)
    {
        FromVertex = from;
        ToVertex = to;
        Weight = weight;
    }

    public Vertex FromVertex { get; private set; }
    public Vertex ToVertex { get; private set; }
    public double Weight { get; private set; }
}

public class Graph
{
    public Graph()
    {
        _Vertexes = new HashSet<Vertex>();
        _VertexEdgeMapping = new Dictionary<Vertex, LinkedList<Edge>>();
    }
    private HashSet<Vertex> _Vertexes;
    private Dictionary<Vertex, LinkedList<Edge>> _VertexEdgeMapping;
}

问题在于，当我有相同的顶点，并想将它们添加到图形中时，它们会被重复。如何定义一种方法，使得HashSet可以理解我的顶点的唯一性？

- mahsa.teimourikia

---

根据定义，如果相同的值作为输入传递，哈希将始终相同。如果您有两个具有完全相同值的顶点，则它们将具有完全相同的哈希。您确定要使用HashSet吗？编辑：在第二次阅读时，听起来您想避免重复相同的顶点。如果是这样，如果它们具有相同的起点和终点，则可能存在某些其他不同的变量。您尝试过使用类似于表示顶点起点和终点的有序对的元组之类的东西吗？ - IllusiveBrian

@Namfuak 这不正确。请创建两个具有相同点值的顶点对象并比较 GetHashCode。 - paparazzo

Answer 1

选项：

• 在Vertex（和为了简单起见，可能还有Point）中覆盖Equals和GetHashCode，很可能在此过程中也要实现IEquatable<T>
• 创建自己的IEqualityComparer<Vertex>实现，并将其传递给HashSet<Vertex>的构造函数

第一个选项很可能是最简单的，但我强烈建议您首先使Point成为不可变类型：可变类型（或包含可变类型的类型）不适合用作哈希键。 我可能还会将其制作为一个struct：

public struct Point : IEquatable<Point>
{
    private readonly int x, y;

    public int X { get { return x; } }
    public int Y { get { return y; } }

    public Point(int x, int y)
    {
        this.x = x;
        this.y = y;
    }

    public override int GetHashCode()
    {
        return 31 * x + 17 * y; // Or something like that
    }

    public override bool Equals(object obj)
    {
        return obj is Point && Equals((Point) obj);
    }

    public bool Equals(Point p)
    {
        return x == p.x && y == p.y;
    }

    // TODO: Consider overloading the == and != operators
}

如果要实现自定义对象的相等性比较，那么需要重写GetHashCode和Equals方法，并在Vertex类中实现IEquatable<>接口。

// Note: sealed to avoid oddities around equality and inheritance
public sealed class Vertex : IEquatable<Vertex>
{
    public Vertex(Point point)
    {
        VertexLabel = point;
    }

    public Point VertexLabel { get; private set; }

    public override int GetHashCode()
    {
        return VertexLabel.GetHashCode();
    }

    public override bool Equals(object obj)
    { 
        return Equals(obj as Vertex);
    }

    public bool Equals(Vertex vertex)
    {
        return vertex != null && vertex.VertexLabel.Equals(VertexLabel);
    }
}      

- Jon Skeet

---

对于那些想知道为什么他要将 x 和 y 乘以常数，这是为了更均匀地分配哈希码。这使得当 X=12，Y=13 的点与 X=13，Y=12 的点具有不同的哈希码。 - Scott Chamberlain

我认为你在 public virtual bool Equals(object obj) 上漏掉了 override 关键字。 - Dustin Kingen

Answer 2

覆盖 Vertex 类的 GetHashCode() 和 Equals() 方法。

以下是示例，但您应该使用比我更好的哈希算法 :)

public class Vertex
{
    public Vertex(Point point)
    {
        VertexLabel = point;
    }

    public Point VertexLabel { get; private set; }

    public override int GetHashCode()
    {
        return VertexLabel.X + VertexLabel.Y;
    }

    public override bool Equals(object obj)
    {
        //your logic for comparing Vertex
    }
}

- gzaxx

---

+1。那个哈希码也许就是我会提供的例子，哈哈。 - William Morrison

Answer 3

正如其他人所说，重写 Vertex 类的 GetHashCode() 方法。同时还需要重写 .Equals 方法。字典将使用 GetHashCode 和 Equals 来确定相等性。这就是为什么 Dictionary 没有替换顶点的原因。在 Dictionary 看来，坐标相同的顶点仍然是根本不同的。我不会在你的问题中再添加另一个源代码示例，因为 Jon 和 gzaxx 已经提供了两个非常好的示例。

- William Morrison