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

5回答

一只甜甜圈

第一个不同实际上是件好事。数组是一种引用类型，幸运的是它们在哈希生成期间（以某种方式）使用引用。我猜想这类似于机器代码级别使用的指针，或者某些垃圾收集器级别的值。其中一件事您没有影响，但如果您将相同的实例分配给新的引用变量，则会被复制。","在第二种情况下，您将获得由和(new[] { 1, 2, 3, 0 }).ToString();应返回的内容组成的字符串的哈希值。默认值类似于类名，因此当然在两种情况下它们都是相同的。当然，字符串具有所有这些有趣的特殊规则，例如“像值类型一样比较”和“字符串驻留”，因此散列应该是相同的。

0 0

慕妹3242003

您的字符串正确地返回相同字符串的相同哈希码，因为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);}

0 0

12345678_0001

另一种选择是利用鲜为人知的方法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; }}请注意，这仍然可能不如元组那么高效，因为它仍在迭代数组而不是能够采用更恒定的表达式。

0 0

慕村225694

如果您知道正在使用的数组的长度，则可以使用Tuple.Console.WriteLine("Tuple");Console.WriteLine(Tuple.Create(1, 2, 3, 0).GetHashCode());Console.WriteLine(Tuple.Create(1, 2, 3, 0).GetHashCode());输出Tuple12481248

0 0

慕码人2483693

建议如下：int[] 作为键（最初的尝试——根本不起作用，作为基准包含在内）字符串作为键（原始解决方案——有效，但速度慢）元组作为键（由David建议）ValueTuple 作为键（受 Tuple 启发）直接 int[] hash 作为 keyIntArrayKey（由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 usageNonGenericSkeetEquality YES 392 msSkeetEquality YES 422 msValueTuple YES 521 msQuickIntArrayKey YES 747 msIntArrayKey YES 972 msTuple YES 1 609 msstring YES 2 291 msDavidEquality YES 1 139 200 ms ***int[] NO 336 msIntHash NO 386 msSkeet IEqualityComparer 仅比直接使用 int[] 作为键稍慢，其巨大优势在于它确实有效，所以我将使用它。** 我知道这不是一个完全万无一失的解决方案，因为理论上我可以得到预期的碰撞次数，而实际上并不是我预期的碰撞，但是经过多次运行测试，我相当确定我不。*** 没有完成，可能是由于糟糕的散列算法和大量的相等性检查。必须将数组数量减少到 10 000 个，然后将时间使用量乘以 100 来与其他数组进行比较。

0 0