为两个订单 ID 的排列创建唯一哈希码

Question

我有一个集合，它是两个唯一订单的排列，其中 OrderId 是唯一的。因此它包含 Order1 (Id = 1) 和 Order2 (Id = 2) 作为 12 和 21。现在在处理路由算法时，检查的条件很少，而最终结果中包含组合，则必须忽略其反向，不需要考虑处理。现在由于 Id 是一个整数，我创建了以下逻辑：

 private static int GetPairKey(int firstOrderId, int secondOrderId)
        {
            var orderCombinationType = (firstOrderId < secondOrderId)
                ? new {max = secondOrderId, min = firstOrderId}
                : new { max = firstOrderId, min = secondOrderId };

            return (orderCombinationType.min.GetHashCode() ^ orderCombinationType.max.GetHashCode());
        }

在逻辑中，我创建了一个 Dictionary<int,int>，其中使用上面显示的方法 GetPairKey 创建了键，我确保在给定组合之外它们被正确排列，这样我就得到了相同的哈希码，可以插入并检查字典中的条目，而它的值是虚拟的并被忽略。

然而上面的逻辑似乎有一个缺陷，它并没有按预期的方式进行所有的逻辑处理，在这种情况下我做错了什么，我应该尝试一些不同的东西来创建一个Hashcode。像下面的代码是不是更好的选择，请建议

Tuple.Create(minOrderId,maxOrderId).GetHashCode，相关代码用法如下：

  foreach (var pair in localSavingPairs)
            {
                    var firstOrder = pair.FirstOrder;
                    var secondOrder = pair.SecondOrder;

                   if (processedOrderDictionary.ContainsKey(GetPairKey(firstOrder.Id, secondOrder.Id))) continue;

添加到字典中，就是下面的代码：

processedOrderDictionary.Add(GetPairKey(firstOrder.Id, secondOrder.Id), 0); 这里的值 0 是虚拟的，没有被使用

Answer 1

首先，42.GetHashCode() returns 42。其次，1 ^ 2 与 2 ^ 1 相同，因此对数字进行排序真的没有意义。第三，您的 "hash" 功能非常薄弱，会产生很多碰撞，这就是您观察到这些缺陷的原因。

我现在能想到的有两个选择：

稍微用一下"stronger"hash function
用 Dictionary<string, int> 替换你的 Dictionary<int, int> 键，键是你的两个排序数字，用你喜欢的任何字符分隔 - 例如56-6472

Answer 2

鉴于 XOR 是可交换的（所以 (a ^ b) 将始终与 (b ^ a) 相同）在我看来你的顺序被误导了......我只是

(new {firstOrderId, secondOrderId}).GetHashCode()

.Net 将为您修复匿名类型的良好分布式哈希实现。

Answer 3

您需要一个可以唯一表示每个可能值的值。

这与哈希码不同。

您可以使用 long 或 class 或包含所有适当值的结构来唯一地表示每个值。由于在达到一定的总大小后，使用 long 将不再有效，让我们看看另一种更灵活、更可扩展的方法：

public class KeyPair : IEquatable<KeyPair>
{
  public int Min { get; private set; }
  public int Max { get; private set; }

  public KeyPair(int first, int second)
  {
    if (first < second)
    {
      Min = first;
      Max = second;
    }
    else
    {
      Min = second;
      Max = first;
    }
  }

  public bool Equals(KeyPair other)
  {
    return other != null && other.Min == Min && other.Max == Max;
  }

  public override bool Equals(object other)
  {
    return Equals(other as KeyPair);
  }

  public override int GetHashCode()
  {
    return unchecked(Max * 31 + Min);
  }
}

现在，这里的 GetHashCode() 将不是唯一的，但 KeyPair 本身将是唯一的。理想情况下，散列码彼此之间会有很大差异，以便更好地分布这些对象，但比上面的更好取决于关于实际值的信息，这些信息将在实践中看到。

字典将使用它来查找项目，但它也会使用 Equals 在哈希码相同的项目之间进行选择。

（您可以通过使用 GetHashCode() 始终只是 returns 0 的版本来对此进行试验。它的性能会非常差，因为冲突会损害性能，并且它总是会发生冲突，但它仍然有效）。

为两个订单 ID 的排列创建唯一哈希码

Create Unique Hashcode for the permutation of two Order Ids

.net

c#

algorithm

dictionary

gethashcode