Calculating GetHashCode efficiently with unordered list

Question

I'm wondering what would be the best way to calculate the hashcode when the order of a sequence doesn't matter. Here's the custom IEqualityComparer<T> i've implemented for an answer on Stackoverflow.

public class AccDocumentItemComparer : IEqualityComparer<AccDocumentItem>
{
 public bool Equals(AccDocumentItem x, AccDocumentItem y)
 {
 if (x == null || y == null)
 return false;
 if (object.ReferenceEquals(x, y))
 return true;
 if (x.AccountId != y.AccountId)
 return false;
 return x.DocumentItemDetails.Select(d => d.DetailAccountId).OrderBy(i => i)
 .SequenceEqual(y.DocumentItemDetails.Select(d => d.DetailAccountId).OrderBy(i => i));
 }
 public int GetHashCode(AccDocumentItem obj)
 {
 if (obj == null) return int.MinValue;
 int hash = obj.AccountId.GetHashCode();
 if (obj.DocumentItemDetails == null)
 return hash;
 int detailHash = 0;
 unchecked
 {
 var orderedDetailIds = obj.DocumentItemDetails
 .Select(d => d.DetailAccountId).OrderBy(i => i);
 foreach (int detID in orderedDetailIds)
 detailHash = 17 * detailHash + detID;
 }
 return hash + detailHash;
 } 
}

As you can see the foreach in GetHashCode needs to order the (nested) sequence before it starts calculating the hashcode. If the sequence is large this seems to be inefficient. Is there a better way to calculate the hashcode if the order of a sequence can be ignored?

Here are the simple classes involved:

public class AccDocumentItem
{
 public string AccountId { get; set; }
 public List<AccDocumentItemDetail> DocumentItemDetails { get; set; }
}
public class AccDocumentItemDetail
{
 public int LevelId { get; set; }
 public int DetailAccountId { get; set; }
}

• alzaimar: Why don't you simply assign a unique ID upon creation of an object and redefine 'equality' of two objects instead? Using the ID when the GetHashCode is called is efficient and in case you have to compare two objects for equal content, you can use your redefined 'Equals' method.
• svick: @alzaimar I think that most of the time, when you want some kind of value equality, you can't just use reference equality instead. For example, this could be used to detect changes in the object, but your solution wouldn't work for that.
• alzaimar: Correct, but if I want to detect changes, I would maintain a 'Modified' property instead of trying to find changes. If I want to compare two instances whether they contain the same data, I would write a method doing that etc. But I would never use 'GetHashCode' to detect changes.
• Tim Schmelter: @alzaimar: I'm not sure if i've understood your suggestion. Of course using an ID is efficient. But the whole point of creating a custom IEqualityComparer<T> is to use it for the linq extension methods like GroupBy. And the requirement was to differentiate ParentClass objets with the AccountId and the nested List<DetailClass> and their DetailAccountId. So if the AccountId is equal and all of the DetailAccountIds(independent of the order), then both objects are equal.
• alzaimar: Got it. Use any hash you like (addition, xor) and don't forget to fully compare if the hashes match, as they always is a chance for collisions.

Answer 1

If the order does not matter, use an kommutative operator to combine the hashCodes of the elements.

Possible candidates are:
^ binary xor // THIS WOULD BE MY CHOICE
+ addition // problem may be the overflow
* multiplication // problem may be the overflow
| binary or // not recommended, because after some of this operations it is likely that all bits are set, so the same hashCode would appear for quite different instances)

• Tim Schmelter: Thanks. However, Mr Skeet himself advise againt using xor: stackoverflow.com/a/263416/284240 The sum approach is problematic since 1 + 1 would be the same as 2.
• MrSmith42: @Tim Schmelter: You will never be able to avoid the possibility of collisions. And it is also not necessary to try to. Only try to avoid too many collisions because it would decrease performance of e.g. HashHmap. But feel free to multiply the hashCode of each element by the same constant before applying the kommutative operator It will change nothing 17*1 + 17*1 == 17*2.
• MrSmith42: @Tim Schmelter: If you want the order of a sequence doesn't matter feature, I cannot imagen an implementation not using an kommutative operator.
• svick: @TimSchmelter And half of the reason Skeet advises against XOR is because it's commutative. Normally, you don't want hash(x,y)==hash(y,x), but that's exactly what you're asking for. (The other half of his point still stands, though.)
• svick: @MrSmith42 * has a different (and possibly even worse) flaw: 0 * anything == 0. That's not hard to work around, but I think it's worth mentioning.