使用LINQ加入HashSet<T>需要帮助理解意外行为

我使用C#HastSet和LINQ的Join方法遇到了一些奇怪的行为,我不明白.我已经简化了我正在做的事情,以帮助专注于我所看到的行为.

我有以下内容:

 private HashSet _mySet; // module level

 IEnumerable searchKeys; // parameter.
 // Partial key searches are allowed.

 private IEqualityComparer _coreKeyComparer; // Module level.
 // Compares instances of MyClass and ISearchKey to determine 
 // if they match.

鉴于

searchKeys和_mySet之间存在1对多的关系.

MyClass实现接口IPartialKey和ICoreKey.

ISearchKey继承自IPartialKey和ICoreKey.

MyClass和ISearchKey实例都覆盖了GetHashCode方法.

MyClass的哈希码值基于其完整键值,包括其ICoreKey和IPartialKey值以及其他字段.

MyClass使用的完整密钥不是唯一的.两个不同的MyClass实例可以具有相同的哈希码.

ISearchKey的哈希码值仅基于其ICoreKey和IPartialKey值.即,ISearchKey哈希码可能与匹配的MyClass实例的哈希码不同.(旁注:在我第一次遇到问题的情况下,ISearchKey的IPartialKey值与MyClass完整键匹配,因此GetHashCode方法将为ISearchKey和MyClass返回相同的值.我包含额外的复杂性以更好地说明基础逻辑我正在做什么.)

_coreKeyComparer.GetHashCode方法仅使用其ICoreKey值返回匹配ISearchKey和MyClass实例的相同值.

_coreKeyComparer.Equals方法将参数分别转换为MyClass和ISearchKey,如果它们的IPartialKey值匹配则返回true.(旁注:_coreKeyComparer已经过严格测试并且工作正常.)

我预计两个集合之间的连接应该会产生如下结果:

{searchKey_a, myClass_a1},
{searchKey_a, myClass_a2},
{searchKey_a, myClass_a3},
{searchKey_b, myClass_b1},
{searchKey_b, myClass_b2},
{searchKey_c, myClass_c1},
{searchKey_c, myClass_c2},
{searchKey_c, myClass_c3},
{searchKey_c, myClass_c4},
etc....

ie同一个ISearchKey实例会多次出现,一次为它所连接的每个匹配的MyClass实例.

但是当我从searchKeys到_mySet的连接时:

        var matchedPairs = searchKeys
          .Join(
            _mySet,
            searchKey => searchKey,
            myClass => myClass,
            (searchKey, myClass) => new {searchKey, myClass},
            _coreKeyComparer)
            .ToList();

我只为每个searchKeyClass实例获得一个MyClass实例.即matchedPairs集合看起来像:

    {searchKey_a, myClass_a1},
    {searchKey_b, myClass_b1},
    {searchKey_c, myClass_c1},
etc....

但是,如果我反转连接,请从_mySet转到searchKeys:

   var matchedPairs = _mySet
          .Join(
            searchKeys,
            myClass => myClass,
            searchKey => searchKey,
            (myClass, searchKey) => new {searchKey, myClass},
            _coreKeyComparer)
            .ToList();

我得到了正确的matchedPairs集合.来自_mySet的所有匹配记录与它们匹配的searchKey一起返回.

我查看了文档并检查了多个示例,但没有看到为什么searchKeys-to-_mySet Join给出了错误的答案,而_mySet-to-searchKeys给出了正确/不同的答案.

(旁注:我也尝试了从searchKeys到_myset的GroupJoin并得到了类似的结果.即每个searchKeyClass实例最多找到一个来自_mySet的结果.)

我不明白Join方法应该如何工作,或者Join与HashSet的工作方式不同于List或其他类型的集合.

如果是前者,我需要澄清,所以我不会在将来使用Join时犯错误.

如果是后者,那么这个不同的行为是一个.Net bug,或者这是HashSet的正确行为？

假设行为是正确的,我将非常感谢有人解释这个(意外的)Join/HashSet行为背后的基础逻辑.

为了清楚起见,我已经修复了我的代码,因此它返回了正确的结果,我只想了解为什么我最初得到的结果不正确.

1> Eric Lippert..：

---

您的错误几乎肯定存在于您未在问题中显示的大量代码中.我的建议是,您将程序简化为产生错误的最简单的程序.这样做,要么你会发现你的错误,要么你会产生一个如此简单的程序,你可以在你的问题中发布所有这些,然后我们可以分析它.

假设行为是正确的,我将非常感谢有人解释这个(意外的)Join/HashSet行为背后的基础逻辑.

由于我不知道出乎意料的行为是什么,我不能说为什么会这样.然而,我可以准确地说出了什么Join,也许这会有所帮助.

Join 采取以下措施:

一个"外部"集合 - 接收器Join.

"内部"集合 - 扩展方法的第一个参数

两个关键提取器,从外部和内部集合中提取密钥

一个投影,它接受其键匹配的内部和外部集合的成员,并生成该匹配的结果

比较两个键是否相等的比较操作.

这是如何Join工作的.(这在逻辑上是会发生什么;实际的实现细节有所优化.)

首先,我们迭代"内部"集合,恰好一次.

对于内部集合的每个元素,我们提取它的键,然后我们形成一个多字典,它从键映射到内部集合中所有元素的集合,其中键选择器生成该键.使用提供的比较来比较密钥的相等性.

因此,我们现在有一个从查找TKey到IEnumerable.

其次,我们迭代"外部"集合,恰好一次.

对于外部集合的每个元素,我们提取其密钥,并使用提供的密钥比较再次在该字符串的多字典中查找.

然后,我们对内部集合的每个匹配元素执行嵌套循环,调用外部/内部对上的投影,并生成结果.

也就是说,Join行为类似于伪代码实现:

static IEnumerable Join
  (IEnumerable outer, 
  IEnumerable inner, 
  Func outerKeySelector, 
  Func innerKeySelector, 
  Func resultSelector, 
  IEqualityComparer comparer) 
{
  var lookup = new SomeMultiDictionary(comparer);
  foreach(TInner innerItem in inner)
  {
    TKey innerKey = innerKeySelector(innerItem);
    lookup.Add(innerItem, innerKey);
  }
  foreach (TOuter outerItem in outer) 
  {
    TKey outerKey = outerKeySelector(outerItem);
    foreach(TInner innerItem in lookup[outerKey])
    {
      TResult result = resultSelector(outerItem, innerItem);
      yield return result;
    }
  }
}

---

一些建议:

替换所有GetHashCode实现以便它们返回0,并运行所有测试.他们应该通过!从中返回零总是合法的GetHashCode.这样做几乎肯定会破坏你的表现,但绝不能破坏你的正确性.如果您处于需要特定非零值的情况GetHashCode,那么您就有一个错误.

测试您的密钥比较以确保它是有效的比较.它必须服从三个平等规则:(1)反身性:一个事物总是等于它自己,(2)对称性:等于A和B必须相等,B和A(3)传递性:如果A等于B和B等于C那么A必须相等C.如果不满足这些规则,那么Join可能表现得很奇怪.

Join用a SelectMany和a 替换你的Where.那是:

from o in outer join i in inner on getOuterKey(o) equals getInnerKey(i) select getResult(o, i)

可以改写为

from o in outer
from i in inner
where keyEquality(getOuterKey(o), getInnerKey(i))
select getResult(o, i)

该查询比连接版本慢,但它在逻辑上完全相同.再次,运行您的测试.你得到相同的结果吗？如果没有,你的逻辑中有一个错误.

同样,我不能强烈强调你的态度"加入可能在给出哈希表时被打破"是阻止你找到你的bug的原因.加入不破.这个代码在十年内没有改变,它非常简单,当我们第一次写它时它是正确的.更有可能的是,你的复杂而神秘的关键比较逻辑在某处被打破.

---

@EricLippert,我现在意识到我没有仔细阅读你的初步答案.这个bug出现在我的IEqualityComparer中,我错误地坚持认为是正确的.部分匹配的需要导致传递失败,这意味着当应该返回true时,内部hashset上的循环返回false.规则1:永远不要发誓问题不在特定的代码块中,因为它总是在代码中.我无法找到一种方法来修复比较器以处理与一组searchkeys的部分匹配,因此我重构了代码以避免加入.谢谢你的帮助.

---

@RBDavidson：进一步阅读：如果您对“人们实施比较错误的方式”这一主题感兴趣，请参阅https://ericlippert.com/2011/01/20/bad-comparisons-part-one/。如果您对主题“人们错误地实现GetHashCode的方式”感兴趣，请参阅https://blogs.msdn.microsoft.com/ericlippert/2011/02/28/guidelines-and-rules-for-gethashcode/