c# - Write fast 包含列表的方法，listitem 是一个向量

Question

我有给定的列表项类:

class Vector
{
    public int Column { get; set; }
    public int Row { get; set; }
    public int TableID { get; set; }

    public Vector(int column, int row, int tableID)
    {
        TableID = tableID;
        Row = row;
        Column = column;
    }
}

后来我有一个这个项目的类型列表，我想知道给定的向量(列、行、表)是否已经添加到这个列表中。当然是简单的解决方案:

    var items = new List<Vector>();
    items.Add(new Vector(1, 2, 3));
    items.Add(new Vector(5, 6, 7));

    for (int i = 0; i < 1000; i++)
    {
        if (items.Any(e => e.Column == 1 && e.Row == 2 && e.TableID == 3))
        {
            // do something
        }
    }

是的，它正在工作，但是......恐怕随着列表中的项目越来越多，它会呈指数级变慢，因为你必须枚举所有项目才能找到匹配的项目。

最后我的问题是:

你能推荐其他数据结构来允许“快速包含”吗？我的意思是至少是线性算法。任何都可以，我只需要存储 3 个相关的 int 并稍后检查包含。

Answer 1

你可以实现IEquatable<T>类的接口(interface)(方法 public bool Equals(T other) 和 public override int GetHashCode())并使用 HashSet 来存储唯一项:

class Vector :  IEquatable<Vector>
{
    /*Some fields and methods*/

    public bool Equals(Vector other)
    {
        if (ReferenceEquals(other, null)) return false;

        if (ReferenceEquals(this, other)) return true;

        return Column.Equals(other.Column) && Row.Equals(other.Row) && TableID.Equals(other.TableID);
    }

    public override int GetHashCode()
    {
        return Column.GetHashCode() ^ Row.GetHashCode() ^ TableID.GetHashCode();
    }
}

并使用哈希集:

var set = new HashSet<Vector>();
    var vect = new Vector { ... };
set.Add(vect);