C#面试编程练习：HashSet存储int[]四元组是否可行？

为什么HashSet<int[]>不可行 #

C#里int[]的默认相等判断是引用相等，而非内容相等。哪怕两个数组元素完全一致只是顺序不同，只要是不同的数组实例，HashSet就会把它们当成不同元素存储，完全达不到你要的去重效果。

List<List>的问题 #

用List存储的话，每次新增前遍历检查是否存在，时间复杂度是O(n)。当四元组数量很大时，这个操作会变得异常缓慢，根本不适合处理大量数据的场景。

推荐方案 #

方案1：自定义相等比较器配合HashSet #

实现IEqualityComparer<int[]>，比较时先把两个数组排序再对比内容；生成哈希值时，基于排序后的数组元素计算。这样HashSet就能正确识别顺序不同但元素相同的四元组。

示例代码：

public class QuadrupleEqualityComparer : IEqualityComparer<int[]>
{
    public bool Equals(int[] x, int[] y)
    {
        if (x.Length != y.Length) return false;
        var sortedX = x.OrderBy(n => n).ToArray();
        var sortedY = y.OrderBy(n => n).ToArray();
        return sortedX.SequenceEqual(sortedY);
    }

    public int GetHashCode(int[] obj)
    {
        var sorted = obj.OrderBy(n => n).ToArray();
        int hash = 17;
        foreach (int num in sorted)
        {
            hash = hash * 31 + num.GetHashCode();
        }
        return hash;
    }
}

// 使用方式
HashSet<int[]> quadruples = new HashSet<int[]>(new QuadrupleEqualityComparer());
quadruples.Add(new int[] {1,1,1,2});
quadruples.Add(new int[] {1,1,2,1}); // 不会被添加，判定为相等

方案2：用标准化键存储 #

把四元组转换成排序后的元组（C#元组的相等判断基于内容），作为HashSet的存储类型。C# 7.0及以上也可以用性能更优的值元组。

示例代码：

HashSet<(int, int, int, int)> quadruples = new HashSet<(int, int, int, int)>();

int[] quad = new int[] {1,1,1,2};
Array.Sort(quad);
var key = (quad[0], quad[1], quad[2], quad[3]);
quadruples.Add(key);

int[] anotherQuad = new int[] {1,1,2,1};
Array.Sort(anotherQuad);
var anotherKey = (anotherQuad[0], anotherQuad[1], anotherQuad[2], anotherQuad[3]);
quadruples.Add(anotherKey); // 不会被添加，键值相同

方案3：自定义结构体 #

定义结构体表示四元组，重写Equals和GetHashCode方法，基于排序后的元素判断相等性。这种方式类型清晰，性能表现也不错。

示例代码：

public struct Quadruple : IEquatable<Quadruple>
{
    public int A { get; }
    public int B { get; }
    public int C { get; }
    public int D { get; }

    private readonly int[] _sorted;

    public Quadruple(int a, int b, int c, int d)
    {
        A = a;
        B = b;
        C = c;
        D = d;
        _sorted = new[] {a, b, c, d};
        Array.Sort(_sorted);
    }

    public bool Equals(Quadruple other)
    {
        return _sorted.SequenceEqual(other._sorted);
    }

    public override bool Equals(object obj)
    {
        return obj is Quadruple other && Equals(other);
    }

    public override int GetHashCode()
    {
        int hash = 17;
        foreach (int num in _sorted)
        {
            hash = hash * 31 + num.GetHashCode();
        }
        return hash;
    }
}

// 使用方式
HashSet<Quadruple> quadruples = new HashSet<Quadruple>();
quadruples.Add(new Quadruple(1,1,1,2));
quadruples.Add(new Quadruple(1,1,2,1)); // 不会被添加

性能对比 #

• 上述HashSet相关方案的添加、查找操作平均时间复杂度是O(1)，完全适配大量四元组的处理场景。
• List遍历方案的时间复杂度是O(n)，当数据量达到上万级别时，性能差距会非常显著。

针对你正在解决的HackerRank问题，优先选HashSet配合自定义相等判断的方案，既能保证正确性，又能满足性能要求。

内容的提问来源于stack exchange，提问作者VansFannel