C# - defining hashset with custom key

Question

I am using the HashSet and Dictionary in C# to implement a Graph structure. I have a problem with the uniqueness of HashSet elements when the HashSet key is a customized class. Here I have:

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;
}

The problem is that when I have same vertexes and I want to add them to the graph, they get duplicated. how can I define a way that the HashSet would understand the uniqueness of my vertexes?

Solution 1

Options:

• Override Equals and GetHashCode in Vertex (and probably Point for simplicity), quite possibly implement IEquatable<T> as you go
• Create your own implementation of IEqualityComparer<Vertex> and pass that to the constructor of the HashSet<Vertex>

The first option is likely to be the simplest, but I would strongly recommend that you make Point immutable first: mutable types (or types containing mutable types) don't make good hash keys. I'd probably make it a struct, too:

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
}

... then override GetHashCode and Equals and implement IEquatable<> in Vertex too, e.g.

// 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);
    }
}      

Solution 2

As others have said, override the GetHashCode() of the Vertex class.

Also override the .Equals method. Dictionary will use both GetHashCode and Equals to determine equality.

This is why Dictionary isn't replacing vertices. Vertices with the same coordinates are still fundamentally different as far as the Dictionary is concerned.

I won't pollute your question with yet another source code example as Jon and gzaxx have offered 2 very fine examples already.

Solution 3

Override GetHashCode() and Equals() methods of Vertex class.

Below is example, but you should use a bit better hashing algorithm than mine :)

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
    }
}

Comments

[William Morrison]

+1 for example. That hashcode is probably the example I'd have offered too haha.

[Scott Chamberlain]

For those wondering why he multiplies x and y by constants it is to help more distribute the hash code. This makes a point with X=12 and Y=13 have a different hash code than a point with a X=13 and Y=12 .

[Dustin Kingen]

I think you missed the override keyword on public virtual bool Equals(object obj)