数组作为字典键会产生很多冲突

Question

我需要使用数字（长整型）列表作为字典键，以便对它们进行一些分组计算。当直接使用长数组作为键时，我遇到了很多冲突。如果我使用 string.Join(",", myLongs) 作为键，它会按照我的预期工作，但速度要慢得多（我认为，因为哈希更复杂）。这是一个演示我的问题的示例：Console.WriteLine("Int32");Console.WriteLine(new[] { 1, 2, 3, 0}.GetHashCode());Console.WriteLine(new[] { 1, 2, 3, 0 }.GetHashCode());Console.WriteLine("String");Console.WriteLine(string.Join(",", new[] { 1, 2, 3, 0}).GetHashCode());Console.WriteLine(string.Join(",", new[] { 1, 2, 3, 0 }).GetHashCode());输出：Int324312407451601393String406954194406954194如您所见，数组返回不同的哈希值。有没有办法既能获得长数组哈希的性能，又能获得字符串哈希的唯一性？请参阅下面我自己的答案，了解所有建议的性能比较。关于潜在的重复- 该问题有很多有用的信息，但由于这个问题主要是关于寻找高性能替代方案，我认为它仍然提供了一些此处未提及的有用解决方案。

Answer 1

第一个不同实际上是件好事。数组是一种引用类型，幸运的是它们在哈希生成期间（以某种方式）使用引用。我猜想这类似于机器代码级别使用的指针，或者某些垃圾收集器级别的值。其中一件事您没有影响，但如果您将相同的实例分配给新的引用变量，则会被复制。

","在第二种情况下，您将获得由和(new[] { 1, 2, 3, 0 }).ToString();应返回的内容组成的字符串的哈希值。默认值类似于类名，因此当然在两种情况下它们都是相同的。当然，字符串具有所有这些有趣的特殊规则，例如“像值类型一样比较”和“字符串驻留”，因此散列应该是相同的。

Answer 2

您的字符串正确地返回相同字符串的相同哈希码，因为string.GetHashCode()是以这种方式实现的。

的实现int[].GetHashCode()对其内存地址进行一些处理以返回哈希码，因此具有相同内容的数组将返回不同的哈希码。

这就是为什么具有相同内容的数组返回不同的哈希码。

您应该考虑为数组编写一个包装类来提供正确的哈希码，而不是直接使用数组作为键。

这样做的主要缺点是计算哈希码将是一个 O(N) 操作（它必须是 - 否则它不会代表数组中的所有数据）。

幸运的是，您可以缓存哈希代码，因此它只计算一次。

使用可变数组作为哈希码的另一个主要问题是，如果在将数组用作哈希容器（例如字典）的键后更改数组的内容，则会破坏该容器。

理想情况下，您只会对从未更改的数组使用这种散列。

考虑到所有这些，一个简单的包装器将如下所示：

public sealed class IntArrayKey

{

    public IntArrayKey(int[] array)

    {

        Array     = array;

        _hashCode = hashCode();

    }

    public int[] Array { get; }

    public override int GetHashCode()

    {

        return _hashCode;

    }

    int hashCode()

    {

        int result = 17;

        unchecked

        {

            foreach (var i in Array)

            {

                result = result * 23 + i;

            }

        }

        return result;

    }

    readonly int _hashCode;

}

您可以使用它来代替实际的数组，以生成更合理的哈希代码。

根据下面的评论，这是该类的一个版本：

• 制作数组的防御性副本，使其无法被修改。

• 实现相等运算符。

• 将底层数组公开为只读列表，因此调用者可以访问其内容，但无法破坏其哈希码。

代码：

public sealed class IntArrayKey: IEquatable<IntArrayKey>

{

    public IntArrayKey(IEnumerable<int> sequence)

    {

        _array    = sequence.ToArray();

        _hashCode = hashCode();

        Array = new ReadOnlyCollection<int>(_array);

    }

    public bool Equals(IntArrayKey other)

    {

        if (other is null)

            return false;

        if (ReferenceEquals(this, other))

            return true;

        return _hashCode == other._hashCode && equals(other.Array);

    }

    public override bool Equals(object obj)

    {

        return ReferenceEquals(this, obj) || obj is IntArrayKey other && Equals(other);

    }

    public static bool operator == (IntArrayKey left, IntArrayKey right)

    {

        return Equals(left, right);

    }

    public static bool operator != (IntArrayKey left, IntArrayKey right)

    {

        return !Equals(left, right);

    }

    public IReadOnlyList<int> Array { get; }

    public override int GetHashCode()

    {

        return _hashCode;

    }

    bool equals(IReadOnlyList<int> other) // other cannot be null.

    {

        if (_array.Length != other.Count)

            return false;

        for (int i = 0; i < _array.Length; ++i)

            if (_array[i] != other[i])

                return false;

        return true;

    }

    int hashCode()

    {

        int result = 17;

        unchecked

        {

            foreach (var i in _array)

            {

                result = result * 23 + i;

            }

        }

        return result;

    }

    readonly int   _hashCode;

    readonly int[] _array;

}

如果您想使用上面的类而不需要创建数组的防御性副本，则可以将构造函数更改为：

public IntArrayKey(int[] array)

{

    _array    = array;

    _hashCode = hashCode();

    Array = new ReadOnlyCollection<int>(_array);

}

Answer 3

另一种选择是利用鲜为人知的方法IEqualityComparer来实现您自己的哈希和相等比较。关于构建良好的哈希值，您需要注意一些注意事项，并且在密钥中包含可编辑数据通常不是一个好的做法，因为如果密钥发生变化，它会带来不稳定，但它肯定比使用字符串连接。

public class ArrayKeyComparer : IEqualityComparer<int[]>

{

    public bool Equals(int[] x, int[] y)

    {

        return x == null || y == null 

            ? x == null && y == null 

            : x.SequenceEqual(y);

    }

    public int GetHashCode(int[] obj)

    {

        var seed = 0;

        if(obj != null)

            foreach (int i in obj)

                seed %= i.GetHashCode();

        return seed;

    }

}

请注意，这仍然可能不如元组那么高效，因为它仍在迭代数组而不是能够采用更恒定的表达式。

Answer 4

如果您知道正在使用的数组的长度，则可以使用Tuple.

Console.WriteLine("Tuple");

Console.WriteLine(Tuple.Create(1, 2, 3, 0).GetHashCode());

Console.WriteLine(Tuple.Create(1, 2, 3, 0).GetHashCode());

输出

Tuple

1248

1248

Answer 5

建议如下：

• int[] 作为键（最初的尝试——根本不起作用，作为基准包含在内）

• 字符串作为键（原始解决方案——有效，但速度慢）

• 元组作为键（由David建议）

• ValueTuple 作为键（受 Tuple 启发）

• 直接 int[] hash 作为 key

• IntArrayKey（由Matthew Watson建议）

• int[] 作为Skeet 的 IEqualityComparer 的键

• int[] 作为David 的 IEqualityComparer 的键

我生成了一个列表，其中包含一百万个长度为 7 的 int[] 数组，其中包含 100 000 到 999 999 之间的随机数（这是我当前用例的近似值）。然后我复制了这些数组的前 100 000 个，以便有 900 000 个唯一数组，以及 100 000 个列两次（以强制冲突）。

对于每个解决方案，我枚举了列表，并将键添加到字典中，或者如果键已经存在则增加值。然后我打印了有多少个键的 Value 大于 1**，以及花费了多少时间。

结果如下（从最好到最差排序）：

Algorithm                Works?   Time usage

NonGenericSkeetEquality  YES            392 ms

SkeetEquality            YES            422 ms

ValueTuple               YES            521 ms

QuickIntArrayKey         YES            747 ms

IntArrayKey              YES            972 ms

Tuple                    YES          1 609 ms

string                   YES          2 291 ms

DavidEquality            YES      1 139 200 ms ***

int[]                    NO             336 ms

IntHash                  NO             386 ms

Skeet IEqualityComparer 仅比直接使用 int[] 作为键稍慢，其巨大优势在于它确实有效，所以我将使用它。

** 我知道这不是一个完全万无一失的解决方案，因为理论上我可以得到预期的碰撞次数，而实际上并不是我预期的碰撞，但是经过多次运行测试，我相当确定我不。

*** 没有完成，可能是由于糟糕的散列算法和大量的相等性检查。必须将数组数量减少到 10 000 个，然后将时间使用量乘以 100 来与其他数组进行比较。