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?

By definition, a hash will always be the same if the same value is passed as input. If you have two vertexes with exactly the same value, they will have exactly the same hash. Are you sure you want to use a HashSet? EDIT: On second reading, it sounds like you want to avoid duplicating vertexes that are the same. If so, if they have the same start and end points, then there may be some other variable that is different. Have you tried using something like a Tuple of the ordered pairs representing the Vertex's start and end points? — IllusiveBrian, Aug 06 '13 at 13:31
@Namfuak That is not correct. Please created two Vertex objects with the same point value and compare GetHashCode. — paparazzo, Aug 06 '13 at 13:35

score 32 · Accepted Answer · edited Nov 15 '18 at 12:04

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

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` . — Scott Chamberlain, Aug 06 '13 at 13:34
I think you missed the `override` keyword on `public virtual bool Equals(object obj)` — Dustin Kingen, Aug 06 '13 at 13:36

score 4 · Answer 2 · answered Aug 06 '13 at 13:29

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

+1 for example. That hashcode is probably the example I'd have offered too haha. — William Morrison, Aug 06 '13 at 13:32

William Morrison · Answer 3 · 2013-08-06T14:14:22.167

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.

C# - defining hashset with custom key

3 Answers3

Linked