C# - xác định hashset với khóa tùy chỉnh

Question

Tôi đang sử dụng HashSet và Dictionary trong C# để triển khai cấu trúc Graph. Tôi gặp vấn đề với tính duy nhất của các phần tử băm khi khóa băm là một lớp được tùy chỉnh. Ở đây tôi có:

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

Vấn đề là khi tôi có cùng một đỉnh và tôi muốn thêm chúng vào biểu đồ, chúng sẽ được nhân đôi. làm thế nào tôi có thể xác định một cách mà các HashSet sẽ hiểu được sự độc đáo của các đỉnh của tôi?

Answer 1

Options:

• Override Equals và GetHashCode trong Vertex (và có lẽ Point vì đơn giản), hoàn toàn có thể triển khai [IEquatable][1]<T> khi bạn đi
• Tạo triển khai của riêng bạn IEqualityComparer<Vertex> và chuyển đến constructor của HashSet<Vertex>

Tùy chọn đầu tiên có khả năng là đơn giản, nhưng tôi sẽ mạnh khuyên bạn thực hiện Point bất biến đầu tiên: có thể thay đổi các loại (hoặc các loại có chứa các loại có thể thay đổi) không thực hiện băm tốt phím. Tôi có lẽ muốn làm cho nó một struct, quá:

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 
} 

... sau đó ghi đè GetHashCode và Equals và thực hiện IEquatable<> trong Vertex quá, ví dụ

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

Answer 2

Ghi đè GetHashCode() và Equals() phương thức của Vertex lớp.

Dưới đây là ví dụ, nhưng bạn nên sử dụng một chút tốt hơn thuật toán băm hơn tôi :)

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

Answer 3

Như những người khác đã nói, ghi đè GetHashCode() của lớp Vertex.

Cũng ghi đè phương thức .Equals. Từ điển sẽ sử dụng cả hai số GetHashCode và Equals để xác định sự bình đẳng.

Đây là lý do tại sao Dictionary không thay thế đỉnh. Các đỉnh có cùng tọa độ vẫn khác nhau về cơ bản với mức độ liên quan là Dictionary.

Tôi sẽ không gây ô nhiễm câu hỏi của bạn với một ví dụ mã nguồn khác như Jon và gzaxx đã cung cấp 2 ví dụ rất tốt rồi.