有没有办法对集合类型进行概率恒定时间相等性检查？

Question

问题

我想知道如何有效地比较两种集合类型(列表,集合,地图等).应该指出的是,结构上的平等不是基于参考的平等.

通常,必须遍历集合的所有元素并在它们之间进行比较,每次比较的成本为O(1),从而产生惊人的O(n)比较时间.

这可能会影响使用列表的哈希表,其中冲突检查相当昂贵或使用契约设计(例如,比较和旧的集合与新的).

当前解决方案的方向

我虽然有办法确定快速解决方案,但它们看起来都是开放式/非确定性的.如果能够使用可存储和比较的所有元素的某种独特散列,则可以使用这些想法.一个好的散列算法应该提供足够的enthropy,以便碰撞的可能性很小.

这种基于散列的比较技术可以通过使用一些列表头的恒定时间比较来加强(比如前10个元素).在开始时使用相同元素并使用良好散列算法的两个列表在理论上应该提供一些独特的比较.

问题

是否有可能创建一种常数时间比较(在某些时候像整数一样泛化和专用),是否可以通过唯一哈希技术实现？

更新

为了澄清这个问题,我不需要一个完美的平等检查,而是一个快速的"平等前"检查,作为一种加速真正的平等检查的方法.虽然许多哈希代码实现对集合比较很有用,但我也对列表(有序)比较感兴趣.

Answer 1

我花了几分钟用 C# 编写了这样一个集合类，源代码如下。我使用泛型是System.Collections.ObjectModel.Collection<T>因为它很容易覆盖它的功能。

根本没有测试过，但恕我直言，这应该是一个坚实的开始。请注意，UpdateHash考虑了索引（使散列函数稍微好一些），而类似物HashedSet<T>会跳过这一部分。

此外，由于XOR运算符的可逆性，在添加/删除时重新计算哈希会变得O(1)复杂。如果需要更好的哈希，这些操作将增长到O(n)，因此我建议进行分析，然后决定最好的。

public class HashedList<T> : Collection<T>, IEquatable<HashedList<T>>
{
    private int _hash;
    private void UpdateHash(int index, T item)
    {
        _hash ^= index;
        if (item != null)
            _hash ^= item.GetHashCode();
    }

    #region Overriden collection methods

    protected override void InsertItem(int index, T item)
    {
        UpdateHash(index, item);
        base.InsertItem(index, item);
    }

    protected override void RemoveItem(int index)
    {
        UpdateHash(index, this[index]);
        base.RemoveItem(index);
    }

    protected override void ClearItems()
    {
        _hash = 0;
        base.ClearItems();
    }

    protected override void SetItem(int index, T item)
    {
        UpdateHash(index, this[index]);
        UpdateHash(index, item);
        base.SetItem(index, item);
    }

    #endregion 

    #region Value equality

    public bool Equals(HashedList<T> other)
    {
        if (other == null)
            return false;

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

        if (other.Count != this.Count)
            return false;

        if (other._hash != this._hash)
            return false;

        return CompareElements(other);
    }

    private bool CompareElements(HashedList<T> other)
    {
        for (int i = 0; i < this.Count; i++)
        {
            if (this[i] == null)
            {
                if (other[i] != null)
                    return false;
            }

            if (this[i].Equals(other[i]) == false)
                return false;
        }

        return true;
    }

    public override bool Equals(object obj)
    {
        var hashed = obj as HashedList<T>;
        if (hashed != null)
            return Equals(hashed);

        return base.Equals(obj);
    }

    public override int GetHashCode()
    {
        return _hash;
    }

    #endregion
}

您还可以认为，如果传递object.Equals任何具有相同元素的实现，则应该返回 true ，但由于它们的哈希码会不同，因此会破坏一致性。IList<T>这是 IIRC 的推荐实施object.Equals。