15

我在 C# 中使用HashSetandDictionary来实现 Graph 结构。当键是自定义类时，我对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理解我的顶点的唯一性？

4

3 回答 3

30

选项：

  • 覆盖Equals和GetHashCode输入Vertex（可能是Point为了简单起见），很可能随时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实现IEquatable<>，Vertex例如

// 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);
    }
}
于 2013-08-06T13:29:56.397 回答
4

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

下面是示例，但您应该使用比我更好的散列算法:)

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
    }
}
于 2013-08-06T13:29:42.330 回答
4

正如其他人所说，覆盖GetHashCode()类的Vertex。

还要覆盖该.Equals方法。Dictionary 将同时使用GetHashCode和Equals来确定相等性。

这就是为什么Dictionary不替换顶点的原因。就其而言，具有相同坐标的顶点仍然有根本的不同Dictionary。

我不会用另一个源代码示例来污染您的问题，因为 Jon 和 gzaxx 已经提供了 2 个非常好的示例。

于 2013-08-06T13:30:28.857 回答