3

I'm trying to exclude entities to be added to database if they already exist there. So I decided newBillInstances.Except(dbContext.BillInstances) would be best approach for that. However it doesn't work at all (no entities are excluded) though for List<string> it works perfectly.

I read this discussion and actual decription of .Except() in MSDN. It states the class to be used in .Except() should implement IEqualityComparer<T> to use default comparer.

Actually the MSDN article doesn't fully describe process of comparison of two instances. I still don't get why both Equals() and GetHashObject() have to be overridden.

I have implemented IEqualityComparer<BillInstance> interface and put break points in boths methods, but while calling .Except(IEnumerable) it's not used. Only when I changed to .Except(IEnumerable, new BillInstanceComparer()) I've cough break in GetHashCode() but no breaks where in Equals().

Then I have implemented IEqualityComparer<BillInstance> right in BillInstance class and expected it would be used while using .Except(IEnumerable) but breaks weren't hit in both methods.

So I've got two questions:

  1. What should be done to use .Except(IEnumerable)?
  2. Why Equals() isn't used at all? Is it used only in case hash codes of two instances are same?
Community
  • 1
  • 1
Ralfeus
  • 845
  • 9
  • 31
  • 1
    http://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,e289e6c98881b2b8,references – m0sa Mar 24 '16 at 08:07
  • Please read [this](https://blog.mariusschulz.com/2011/08/08/why-enumerableexcept-might-not-work-the-way-you-might-expect) famous blog to understand the internals of `Enumerable.Except()` method. – RBT May 03 '18 at 04:57

3 Answers3

7

Because the Equals() is used only if two objects have the same GetHashCode(). If there are no objects that have the same GetHashCode() then there is no chance of using the Equals().

Internally the Except() uses a Set<> (you can see it here), that is an internal class that you should consider to be equivalent to HashSet<>. This class uses the hash of the object to "index" them, then uses the Equals() to check if two objects that have the same hash are the same or different-but-with-the-same-hash.

Link to other relevant answer: https://stackoverflow.com/a/371348/613130

Community
  • 1
  • 1
xanatos
  • 109,618
  • 12
  • 197
  • 280
  • Yeah, that definitely explains about `Equals()` and `GetHashCode()`. Just not clear yet about `IEqualityComparer` implementation. Where should it be implemented and what's the better way to call `Except()`? – Ralfeus Mar 24 '16 at 10:03
  • @Ralfeus With `Except` you can do three "things": override `GetHashCode` and `Equals` *directly* in the class you need to compare, OR you can create a separate class that implements `IEqualityComparer<>` and that does the `GetHashCode` and the `Equals` – xanatos Mar 24 '16 at 10:10
  • I did both things. None of which seems to work. And what would be the third thing? – Ralfeus Mar 24 '16 at 10:22
  • @Ralfeus It is implementing the `IEquatable<>` interface inside the class. – xanatos Mar 24 '16 at 10:23
  • And which would be the "right" approach? As for me it's overriding of `Object.GetHashCode()` and `Object.Equals()` to keep things as simple as possible – Ralfeus Mar 24 '16 at 10:46
  • 1
    @Ralfeus "right" is in the eye of the observer... Normally you should calculate `object.GetHashCode()` only on immutable fields, because otherwise "bad things" could happen (see http://stackoverflow.com/a/384411/613130). So if all the fields of your class can change during its lifetime, then you shouldn't override `GetHashCode`. `IEqualityComparer<>` doesn't have this "stigma" attached, so you can always create a "correct" `IEqualityComparer<>`. Then if you must have multiple comparers (thing case sensitive/case insensitive) then multiple `IEqualityComparer<>` is the only way. – xanatos Mar 24 '16 at 10:52
  • The [current implementation of `Except` in .NET](https://github.com/dotnet/runtime/blob/676f8eb24b0565868cbf353282957127b9cd9c4c/src/libraries/System.Linq/src/System/Linq/Except.cs#L81) directly uses a `HashSet` initialized with the second sequence, and then tests whether the elements of the first sequence are already present or not (return value of [`HashSet.Add`](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.hashset-1.add?view=net-6.0#system-collections-generic-hashset-1-add(-0))). – janw Jul 13 '22 at 20:48
  • 1
    @janw yes, they changed it an year ago: https://github.com/dotnet/runtime/pull/49543 the HashSet performance had been improved so the internal Set was useless – xanatos Jul 15 '22 at 11:33
0

Somewhere in the code a set or a map/dictionary is hidden.

These guys typically contains a number of buckets which grows with the number of elements stored in the set. An element is partitioned into buckets based on the hash code and the actual identity comparison within the bucket is done using equals.

So the hash code is used to find the correct bucket (why GetHashCode is needed) whereupon equals is used to compare it to other elements in the buckets.

That's why you need to implement both.

faester
  • 14,886
  • 5
  • 45
  • 56
0

Ok, from the IEnumerable source (thanks to m0sa) I've understood internals of calling Except(IEnumerable):

  1. enumerable1.Except(enumerable2) calls ExceptIterator(enumerable1, enumerable2, null) where null is supposed to be an instance of IEquitableComparer.

  2. ExceptIterator() creates an instance of internal class Set passing null as comparer.

  3. Since comparer is null the property EqualityComparer<TElement>.Default is used.

  4. Default property creates a comparer for TElement unless it's already created by calling CreateComparer(). Specifically 2 points were interesting for me:

    • If TElement implements IEquatable interface, then as far as I understood some generic comparer for IEquatable is created. I believe it would use then IEquatable.GetHashCode() and IEquatable.Equals().

    • For general cases (not type of byte, not implementing IEquatable, not Nullable, not enum) ObjectEqualityComparer instance is returned. ObjectEqualityComparer.GetHashCode() and ObjectEqualityComparer.Equals() generally call corresponding methods of the TElement.

So this gave me understanding for my case (each instance of BillInstance is generally immutable) it should be sufficient to override Object.GetHashCode() and Object.Equals().

Community
  • 1
  • 1
Ralfeus
  • 845
  • 9
  • 31