5

Background:

I've written a large scale WPF application using MVVM and it's been suffering from some intermittent problems. I initially asked the 'An item with the same key has already been added' Exception on selecting a ListBoxItem from code question here which explains the problem, but got no answers.

After some time, I managed to work out the cause of the Exceptions that I was getting and documented it in the What to return when overriding Object.GetHashCode() in classes with no immutable fields? question. Basically, it was because I had used mutable fields in the formula to return a value for GetHashCode.

From the very useful answers that I received for that question, I managed to deepen my understanding in that area. Here are three relevant rules:

  1. If x equals y then the hash code of x must equal the hash code of y. Equivalently, if the hash code of x does not equal the hash code of y, then x and y must be unequal.
  2. The hash code of x must remain stable while x is in a hash table.
  3. The hash function should generate a random distribution among all integers for all inputs.

These rules affected the possible solutions that I had to my problem of not knowing what to return from the GetHashCode method:

  • I couldn't return a constant because that would break the first and third rules above.
  • I couldn't create an additional readonly field for each class, solely to be used in the GetHashCode method for the same reasons.

The solution that I eventually went with was to remove each item from its ObservableCollection before editing any of the properties used in the GetHashCode method and then to re-add it again afterwards. While this has worked Ok in a number of views so far, I've run into a further problem as my UI items are animated using custom Panels. When I re-add an item (even by inserting it back to its original index in the collection), it sets off the entry animation(s) again.

I had already added a number of base class methods such as AddWithoutAnimation, RemoveWithoutAnimation, which has helped fix some of these issues, but it doesn't affect any Storyboard animations, which still get triggered after re-adding. So finally, we come to the question:

Question:

First, I'd like to clearly state that I am not using any Dictionary objects in my code... the Dictionary that throws the Exception must be internal to an ObservableCollection<T>. This point seems to have been missed by most people in my last question. Therefore, I cannot chose to simply not use a Dictionary... if only I could.

So, my question is 'is there any other way that I can implement GetHashCode in mutable classes while not breaking the three rules above, or avoid implementing it in the first place?'

I received a comment on the previous question from @HansPassant that suggested that

A good starting point is to completely remove the Equals and GetHashCode overrides, the default implementations inherited from Object are excellent and guarantee object uniqueness.

Can anyone tell me how can I remove the Equals and GetHashCode overrides? On the IEquatable<T> Interface page on MSDN it says It should be implemented for any object that might be stored in a generic collection and then on the IEquatable<T>.Equals Method page it says If you implement Equals, you should also override the base class implementations of Object.Equals(Object) and GetHashCode so that their behaviour is consistent with that of the IEquatable<T>.

If this is possible, it would be my preferred solution.

UPDATE >>>

After downloading and installing dotPeek, I have been able to look inside the PresentationFramework namespace where the Exception is actually occurring. I have found the exact part that uses the Dictionary that is causing this problem. It is in the internal InternalSelectedItemsStorage class constructor:

  internal InternalSelectedItemsStorage(Selector.InternalSelectedItemsStorage collection, IEqualityComparer<ItemsControl.ItemInfo> equalityComparer = null)
  {
    this._equalityComparer = equalityComparer ?? collection._equalityComparer;
    this._list = new List<ItemsControl.ItemInfo>((IEnumerable<ItemsControl.ItemInfo>) collection._list);
    if (collection.UsesItemHashCodes)
      this._set = new Dictionary<ItemsControl.ItemInfo, ItemsControl.ItemInfo>((IDictionary<ItemsControl.ItemInfo, ItemsControl.ItemInfo>) collection._set, this._equalityComparer);
    this._resolvedCount = collection._resolvedCount;
    this._unresolvedCount = collection._unresolvedCount;
  }

This is used internally by the Selector class after the ListBoxItem.OnSelected method has been called, so I can only assume that this has something to do with when a selection is made on the Listbox.

Community
  • 1
  • 1
Sheridan
  • 68,826
  • 24
  • 143
  • 183
  • I inherit from IEquatable of T and implement the Equals method, and never overload the GetHashCode method. But this strategy works only if you're using a generic collection like a List of T. Or anything that does not use a hash for that matter. – Gayot Fow Nov 05 '13 at 15:24
  • I don't know what the internals of the `ObservableCollection` are, but I can only imagine that there *is* a `HashTable` involved somewhere, even if it is just for selections made, because I've ended up with this horrible problem. I *did* try *not* implementing `GetHashCode` but then every item in the collection was showing up as having changed, eg. it didn't work properly without it. – Sheridan Nov 05 '13 at 15:38
  • Eric said " propose a third solution, which is: never put your object in a hash table, because a hash table is the wrong data structure in the first place ... Use the right tool for the job. Use a list, and live with the pain of doing linear searches." So why do you think there's a hash table somewhere? – Gayot Fow Nov 05 '13 at 15:58
  • 2
    "if the hash code of x does not equal the hash code of y, then x and y must be unequal" That is entirely false. "The hash function should generate a random distribution among all integers for all inputs" That's a nice to have, and helps performance, but is not *required*, strictly speaking. – Servy Nov 05 '13 at 17:24
  • @GarryVass, I think that because I get 'An item with the same key has already been added' `Exception`... please refer to my first question with a very similar title to that (linked above), where you will see the `StackTrace` which goes through the `Dictionary` constructor. Also, if I don't use `ObservableCollection`, I'll lose my collection notifications in the UI (or have to implement `INotifyCollectionChanged` I suppose). – Sheridan Nov 05 '13 at 17:27
  • @Sheridan `ObservableCollection` does *not* store the objects in a hash-based collection internally. It is logically an extension of a list, and objects being put in that collection need not have a sensible `GetHashCode` implementation. – Servy Nov 05 '13 at 17:27
  • Maybe not @Servy, but something *must* use one to contain the selected items or something... please look at the stack trace in my [first post](http://stackoverflow.com/questions/17950740/an-item-with-the-same-key-has-already-been-added-exception-on-selecting-a-list)... it *definitely* not been used by my code directly. – Sheridan Nov 05 '13 at 17:29
  • 1
    @Sheridan It may be the case that this object needs to be put in a hash based collection, but `ObservableCollection` isn't what's doing it. It's happening in the binding. Perhaps you added some sort of "unique" constraint, or who knows, but you're not quite looking in the right place, that's all I'm saying. – Servy Nov 05 '13 at 17:32
  • @Sheridan, have you totally nailed down *which* collection has invoked the throw? and exactly what the duplicate key is? The other question says you are not using a dictionary. – Gayot Fow Nov 05 '13 at 17:41
  • What @Servy said. The hash code thing is a red herring. You are doing all of this inside of a mouse event handler. And somebody under the bonnet is trying to build a dictionary to answer the methods you are calling. – Gayot Fow Nov 05 '13 at 17:51
  • Guys, did you see the stack trace? Execution goes through `OnPropertyChanged` and `Selector.OnSelected` and the `Exception` occurs when an item is selected *after an edit has been made to an item in an `ObservableCollection`*. In views where I have taken the item out of the collection before editing and then re-inserted it, the problem has gone away so I'm guessing that it has something to do with the selection made... that item must be stored internally somewhere in a `Dictionary`. @garyvass, I don't know exactly what caused it... I just have that educated guess based on the stack trace. – Sheridan Nov 05 '13 at 21:19
  • @Sheridan, override get hash code to return the constant -1 and see if the result is any different. – Gayot Fow Nov 05 '13 at 23:38
  • @GarryVass, there was no improvement in the situation when returning `-1` from `GethashCode`. – Sheridan Nov 06 '13 at 12:25
  • @Sheridan, and thus irrelevant :) Suggest you review the premise of this question... – Gayot Fow Nov 06 '13 at 17:04

1 Answers1

0

Can anyone tell me how can I remove the Equals and GetHashCode overrides? On the IEquatable Interface page on MSDN it says It should be implemented for any object that might be stored in a generic collection and then on the IEquatable.Equals Method page it says If you implement Equals, you should also override the base class implementations of Object.Equals(Object) and GetHashCode so that their behaviour is consistent with that of the IEquatable.

Mutable objects are comparable by their identity while immutable or value objects by their values.

If you have a mutable object you need to figure out its identity (e.g. if it is a representation of an entity stored in the database the identity is the primary key of the identity; if it is just an 'ad hoc' mutable object created in memory, then its identity is reference of this object (i.e. the default implementation of Equals and GetHashCode)).

So if your object is not an entity you simply implement IEquatable.Equals(T x) { return this.Equals(x); }, i.e. you say that, yes you can compare objects of this class with objects of class T and you compare it by reference (Equals() method inherited from System.Object).

If your object is an entity and e.g. has a primary key PersonId, then you do comparison by PersonId and return PersonId.GetHashCode() from your GetHashCode() method.

Btw, in case of entities you usually use some OR mapper and Identity map pattern which ensures that within a given unit of work you don't have more than one instance of a given entity, i.e. whenever primary keys are equal the object references are equal too.

Lucas
  • 73
  • 5
  • So you're saying to implement `IEquatable` but just return what `object Equals` returns from `T Equals`? – Sheridan Dec 17 '13 at 18:32
  • Yes - to be strict: return what object Equals returns from the declaring type (T does not have to be the same as the class implementing `IEquatable`, e.g you may have `Person : IEquatable` if you want). `IEquatable` is just a way to explicitly express the fact that `object.Equals` supports comparison with `T`. – Lucas Dec 19 '13 at 12:10
  • 2
    Values should be compared by content, and entities by reference. Unfortunately, instances of a mutable class may behave as values or entities, depending upon whether they will actually be mutated, and whether references to them are shared or unshared. When a mutable object is used as a value, reference equality is generally meaningless [if a class uses a mutable object as a value, it must hold a reference which won't compare equal to any other], and when it's used as an entity, value equality is misleading. Unfortunately, there's no way to tell an object whether it's a value or an entity. – supercat Feb 10 '14 at 16:24
  • 1
    IMO if there is no way to tell an object whether it is a value or an entity the safest thing you can do is to follow a practice of not allowing yourself for this ambiguity. I mean, if an object is mutable and you want to compare it by value, then maybe a specialised IComparer will be better rather than trying declare it as IEquatable (the comparer name would tell you what is the comparison method). We should not drive ourselves into having to answer a question like "equatable, yep, but when/how?". – Lucas May 02 '14 at 07:39